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

Ph.D. thesis of Xin ZHAO

Une méthode génétique pour la résolution du problème dynamique de routage de véhicules avec temps de parcours variables

Starting date: 1 October 2004
Keywords: Vehicle routing problem, VRP ; VRPTW, PDTRP, Genetic algorithm, Simulation, Real time, Time-dependent travel time, Speed profile

We treat the dynamic vehicle routing problem with time windows (DVRPTW) and the partially dynamic travelling repairman problem (PDTRP) where the inclusion of new customers during the routing execution is possible. In a first approach, we consider speed profiles based on average travel time depending on the time period (morning, noon, afternoon) to reflect the evolution of road traffic. Depending on the connection type between two customers, several profiles can be considered (feeder road, arterial road and freeway). In a second approach, we integrate traffic information obtained in real time to change the speed profile according to the accidents of the road network (congestion, etc.). The analysis of the results of these experiments shows that our method with real-time traffic information provides a good performance, a better robustness against a simple model with time dependent travel time.

Involved research axes:

Involved application areas:

No partner is associated with this element.


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