Laboratoire de Génie Informatique et d’Automatique de l’Artois

Nathalie HELAL

ATER
Member of the research themes:
The capacitated vehicle routing problem with evidential demands
International Journal of Approximate Reasoning, pp 124-151, Vol. 95, avril 2018
Le problème de tournées de véhicules avec des demandes évidentielles
Actes des 26e rencontres Francophones sur la Logique Floue et ses Applications , pp 15-21, (Prix ex aequo du meilleur papier doctorant), Amiens, France, Cepaduès, octobre 2017
A Recourse Approach for the Capacitated Vehicle Routing Problem with Evidential Demands
Proceedings of the 14th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2017, pp 190-200, LNCS 10369, Lugano, Switzerland, A. Antonucci, L. Cholvy and O. Papini (Eds.), Springer, juillet 2017
The Capacitated Vehicle Routing Problem with Evidential Demands: A Belief-Constrained Programming Approach
4th International Conference on Belief Functions, BELIEF 2016, pp 212-221, LNAI 9861, Prague, Czech Republic, J. Vejnarová and V. Kratochvil (Eds.), Springer, septembre 2016
2016
French conference with review committee
Optimisation discrète sous incertitudes modélisées par des fonctions de croyance
17ème congrès ROADEF de la société Française de Recherche Opérationnelle et Aide à la Décision, Compiègne, France, février 2016

Author of the Ph.D. thesis "An evidential answer for the capacitated vehicle routing problem with uncertain demands"

2014 - 2017

The capacitated vehicle routing problem is an important combinatorial optimisation problem. Its objective is to find a set of routes of minimum cost, such that a fleet of vehicles initially located at a depot service the deterministic demands of a set of customers, while respecting capacity limits of the vehicles. Still, in many real-life applications, we are faced with uncertainty on customer demands. Most of the research papers that handled this situation, assumed that customer demands are random variables. In this thesis, we propose to represent uncertainty on customer demands using evidence theory - an alternative uncertainty theory. To tackle the resulting optimisation problem, we extend classical stochastic programming modelling approaches. Specifically, we propose two models for this problem. The first model is an extension of the chance-constrained programming approach, which imposes certain minimum bounds on the belief and plausibility that the sum of the demands on each route respects the vehicle capacity. The second model extends the stochastic programming with recourse approach: it represents by a belief function for each route the uncertainty on its recourses (corrective actions) and defines the cost of a route as its classical cost (without recourse) plus the worst expected cost of its recourses. Some properties of these two models are studied. A simulated annealing algorithm is adapted to solve both models and is experimentally tested.