Problèmes de tournées de véhicules sur deux niveaux pour la logistique urbaine : approches basées sur les méthodes exactes de l'optimisation mathématique

Abstract

Cette thèse s’intéresse principalement au développement de méthodes d’optimisation mathématique exactes pour résoudre des problèmes de tournées de véhicules dans un réseau de distribution à deux niveaux. Dans un tel réseau, des camions circulent au premier niveau et transportent des marchandises d’un centre de distribution vers des dépôts intermédiaires appelés « satellites ». Au second niveau, des véhicules légers récupèrent les marchandises aux satellites puis livrent les clients. Chaque client doit être visité une seule fois. L’objectif du problème de tournées de véhicules sur deux niveaux est de minimiser le coût total de transport dans un tel réseau de distribution.Dans un premier temps, nous nous intéressons au « Two-Echelon Capacitated Vehicle Routing Problem ». Nous présentons une nouvelle formulation du problème basée sur des routes, une nouvelle stratégie de branchement et une nouvelle famille d’inégalités valides. Les expérimentations montrent que notre algorithme résout toutes les instances de la littérature.Ensuite, nous nous intéressons au « Two-Echelon Vehicle Routing Problem with Time Windows ». Ici, nous considérons une variante avec des contraintes de précédence aux satellites : un camion doit livrer les marchandises à un satellite avant qu’elles soient chargées dans un véhicule léger. Nous proposons une formulation basée sur les routes dont le nombre de contraintes de précédence croît exponentiellement en fonction du nombre de satellites. Nous montrons comment prendre en compte ces contraintes dans le problème de pricing de l’algorithme de génération de colonnes. Les expérimentations montrent que notre algorithme peut résoudre à l’optimalité des instances qui contiennent jusqu’à 100 clients.Enfin, nous nous intéressons à des problèmes de tournées de véhicules contenant des contraintes de type sac-à-dos. Nous présentons quelques familles d’inégalités valides. Ces familles sont utilisées pour résoudre les trois problèmes suivants: « Capacitated Vehicle Routing Problem with Capacitated Multiple Depots », « Location- Routing Problem » et « Vehicle Routing Problem with Time Windows and Shifts ». Ces problèmes apparaissent lorsque les routes au premier niveau du réseau de distribution à deux niveaux sont fixées. Nos expérimentations permettent de trouver de nouvelles solutions optimales.