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%.

Abstract

The SNCF (French railway company) has developed transportation system combining the advantages of rail and the flexibility of road. This system is a demand-responsive transport system designed to serve passengers at stations, by transporting each passenger to a specific location and bringing passengers from their locations to the stations. It meets each passenger’s preferences, such as maximum travel times and availability times. It also respects available resources, including the number of vehicles, their capacities, and train departure times. The efficiency of this transportation system depends on the optimization of its vehicles routes as they navigate a road network.To address this, our goal is to optimize the transportation system by providing a valid mathematical model and an optimization method. First, we start by positioning the problem in the literature, where we found that the problem can be seen as an intersection between the Dial-a-Ride Problem and the Vehicle Routing Problem with Backhauls. Then, we formulate the problem as a mixed integer program by describing the problem on the road network graph, that preserves the backhaul constraints, and where the objective is to minimize the costs of traveling and unserved passengers. Afterwards, we propose a decomposition of the problem into a master problem and subproblems, then we detail the implementation of the resolution method which is a Column Generation-based Diving Heuristic. We model the subproblem as a shortest path problem with resource constraints. This subproblem is solved using an exact dynamic programming method based on a labeling algorithm adapted to our problem. Finally, we test our method using a set of synthetically generated instances. This allows us to evaluate the effectiveness of the proposed resolution method, the integer program, and the quality of the provided solutions. The results demonstrate the effectiveness of the resolution method where it was able to solve optimally 80% of total instances and provide an integrality gap average of only 3.6%.