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

Ph.D. thesis of Jian XU

Evolutionary stochastic models for the vehicle routing problem with soft time windows and fuzzy demands

Starting date: 1 September 2004
Keywords: Vehicle routing, Time windows, Fuzzy demands, Stochastic, Dynamic, Possibility theory, Genetic Algorithm, Simulation
Advising:

The work of this thesis considers the vehicle routing problem with time windows and fuzzy demands (VRPTWFD). The goal of the problem is to find the routes of the vehicles with a minimal cost so that the vehicles can service each client exactly only once respecting some constraints. The customers specify their demands by a fuzzy number. The VRPTWFD is studied as the static case as well as the dynamic case.

We use the possibility theory to handle the constraint of capacity by setting certain thresholds for the degrees of the possibility and necessity. Using this capacity constraint, a chance constrained programming model (CCP) and a two-stages stochastic programming with recourse model (SPR) in stochastic programming were proposed to treat the VRPTWFD. The genetic algorithms integrating these models have been proposed as the optimization approach in order to find the optimal solutions.

In the dynamic VRPTWFD, some customers can call in their orders during the daily operation. A simulation platform, which has the capability of simulating the daily operation, has been developed to solve online the dynamic VRPTWFD.

In order to assess the performance of the proposed models, we have constructed a benchmark for the static VRPTWFD and a benchmark for the dynamic VRPTWFD adapting from Solomon’s benchmark for the VRPTW, then we have evaluated the quality of the solutions, which were obtained by using these models, by simulating the real world situations with the help of the “test” scenarios.

Involved research axes:

No partner is associated with this element.

Defense

Defense took place the 18/12/2007 pm31 14:00 Prestige room - FSA - Béthune

Jury:

  • Président Rémy DUPAS Université Bordeaux 1
  • Rapporteur Aziz MOUKRIM Université de Technologie de Compiègne
  • Rapporteur Abdelhakim ARTIBA Institut Supérieur de Mécanique de Paris
  • Examinateur Daniel JOLLY Université d'Artois
  • Advisor Gilles GONCALVES Université d'Artois
  • Co-advisor Tienté HSU Université d'Artois