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

Ph.D. thesis of Nathalie HELAL

An evidential answer for the capacitated vehicle routing problem with uncertain demands

Starting date: 1 October 2014
Keywords: Optimization under uncertainty, Belief functions theory, Vehicle routing problem

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.

Involved research themes:

Involved application areas:

No partner is associated with this element.


Defense took place the 20/12/2017 pm31 13:00 Room Prestige FSA Béthune


  • Rapporteur Didier DUBOIS Université Paul Sabatier Toulouse
  • Rapporteur Arnaud MARTIN Université Rennes 1
  • Examinateur Laetitia JOURDAN Université de Lille 1
  • Examinateur Caroline THIERRY Université Jean Jaurès Toulouse
  • Examinateur Sébastien DESTERCKE Université de Technologie de Compiègne
  • Invité David MERCIER Université d'Artois