TITRE : Résolution du problème de localisation-routage avec un GRASP combinant mémorisation et path relinking

CONFÉRENCIÈRE : Caroline Prodhon, Université de Technologie de Troyes

DATE et ENDROIT : 9 février 2005, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE : Gilbert Laporte (343-6143)

RÉSUMÉ : La logistique du transport est une discipline qui regroupe un grand nombre de problèmes, très souvent difficiles à résoudre de manière optimale. L'approche qui paraît la plus logique pour la résolution de tels problèmes est la décomposition en deux ou trois parties selon les niveaux de décision, en commençant par le niveau stratégique. C'est d'ailleurs celle qui est majoritairement utilisée. L'avantage est la simplification apportée. Cependant, cette manière de procéder ne prend pas en compte l'intégralité du problème et résulte souvent en une perte d'optimalité globale. Le but ici est donc d'étudier les problèmes combinant la localisation de dépôts et l'élaboration de tournées de véhicules simultanément. Ce type de problème est communément appelé problème de localisation-routage, ou LRP (Location-Routing Problem). Il est NP-difficile au sens fort. L'approche de résolution proposée est une métaheuristique : un Greedy Randomized Adaptive Search Procedure (GRASP), utilisant une généralisation de l'algorithme de Clarke et Wright. La base d'un GRASP a été choisie pour les bons résultats qu'elle fournit pour divers problèmes de logistique. Afin de la rendre plus pertinente, la méthode de base a été ici agrémentée d'une technique de mémorisation et d'une post-optimisation par Path Relinking (PR). Cette métaheuristique est efficace. Sur deux tiers instances utilisées, elle améliore les résultats obtenus par une heuristique de recherche locale ainsi que par une recherche taboue dédiée à un problème de localisation-routage avec des capacités uniquement sur les tournées. Seul le temps CPU est un peu long comparé à la recherche taboue mais reste raisonnable pour un problème stratégique de taille réelle puisqu'il ne dépasse pas quelques minutes.