Problème d'optimisation d'un système de transport à la demande sur plusieurs gares

La SNCF (Société nationale des chemins de fer français) a développé un système de transport combinant les avantages du rail et la flexibilité de la route. Ce système est un transport à la demande destiné à servir les passagers dans les gares, en les transportant chacun vers un lieu spécifique, puis de les ramener de leur emplacement vers les gares, tout en satisfaisant les préférences de chaque passager, telles que les temps de trajet maximum et les temps de disponibilité, et en respectant les ressources disponibles, comme le nombre de véhicules, leur capacité et les heures de départ des trains. L’efficacité de ce système de transport dépend de l’optimisation des itinéraires des véhicules qui circulent sur le réseau routier. Notre but ici est d’optimiser ce système de transport en fournissant un modèle mathématique valide et une méthode d’optimisation. Nous commençons par situer le problème dans la littérature, où nous avons trouvé que le problème peut être vu comme une intersection entre le problème Dial-a-Ride et le problème de tournées de véhicules avec Backhauls. Ensuite, nous formulons le problème comme un programme linéaire en nombres entiers mixtes en le décrivant sur le graphe du réseau routier, tout en respectant les contraintes de Backhauls, et où l’objectif est de minimiser les coûts de déplacement ainsi que les coûts des passagers non desservis. Nous proposons par la suite une décomposition du problème en un problème maître et des sous-problèmes, puis nous détaillons la mise en oeuvre de la méthode de résolution qui est une heuristique de plongée basée sur la génération de colonnes. Nous modélisons le sous-problème comme un problème de plus court chemin avec contraintes de ressources. Ce dernier est résolu à l’aide d’une méthode de programmation dynamique exacte basée sur un algorithme d’étiquetage adapté pour notre problème. Enfin, nous testons notre méthode en utilisant 40 instances générées synthétiquement pour évaluer l’efficacité de la méthode de résolution proposée et du programme en nombres entiers, ainsi que la qualité des solutions fournies. Les résultats démontrent l’efficacité de la méthode de résolution, qui a permis de résoudre de manière optimale 80% des instances et de fournir un écart d’intégralité moyen de seulement 3, 6%.