Méthodes de résolution exactes pour le problème de routage de véhicules avec fenêtres de temps et routes multiples

Thèse soutenue

Doctorant : Florent Hernandez

Thèse soutenue le 26 Novembre 2010 , Université Montpellier 2

  • Ecole doctorale : I2S (Information, Structures, Systèmes), Université Montpellier 2 – Sciences et Techniques du Languedoc
  • Directeur de thèse : Jean-Claude König
  • Co-encadrement :  UMR ITAP ( Olivier Naud) / LIRMM (Rodolphe Giroudeau)

Mémoire de thèse :

Mots-clés : Problème de routage de véhicules, Génération de Colonnes, Routes multiples, Fenêtre de temps, Programmation dynamique, Branch and Price

Résumé :
Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW).  Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d’optimiser les transports lorsque le nombre de véhicules est limité et peu élevé.  Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème.  Notre modélisation prend la forme d’un problème de couverture des clients dont les variables sont des routes.  Des contraintes d’exclusion mutuelle expriment la disponibilité des véhicules.  Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources.  Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu’une approche classique.  La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l’un basé sur les arcs, l’autre sur la résolution d’un VRPTW.  Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW.  Nous donnons les résultats de l’algorithme sur les instances de Solomon.  Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes.  Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes,  pour cette variante du problème.

Share