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

Nathalie HELAL

(Position when this person departed from the LGI2A)
Member of the research themes:

Revue Internationale avec Comité de Lecture

The capacitated vehicle routing problem with evidential demands
International Journal of Approximate Reasoning, pp 124-151, Vol. 95, 04/2018

Conférence Internationale avec Comité de Lecture

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, 07/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, 09/2016

Conférence Nationale avec Comité de Lecture

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, 10/2017
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, 02/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.