Problème d'horaire d'autobus avec dépôts multiples et modification contrôlée des heures de début des voyages

Dans le domaine des transports en commun, et en particulier des réseaux d'autobus, organiser efficacement et à moindres coûts le réseau est crucial. A partir d'une grille horaire donnant les heures de départ des trajets de chaque ligne, la compagnie d'autobus doit organiser sa flotte de véhicules et son personnel afin d'assurer le service de transport. Dans ce problème de planification opérationnelle, nous nous intéressons à la gestion des véhicules. Il s'agit de construire le parcours de chacun des véhicules afin de couvrir tous les trajets désirés, et cela au coût le plus faible possible. Dès lors que la compagnie entrepose ses véhicules dans des dépôts différents, ce problème est très difficile à résoudre (classe des problèmes NP-difficiles). On l'appelle problème d'horaire d'autobus avec dépôts multiples ou MDVSP pour l'anglais Multiple Depot Vehicle Scheduling Problem. Dans ce mémoire, on ajoute au MDVSP la possibilité de modifier les heures de départ initialement prévues. Cela laisse espérer une réduction du nombre d'autobus nécessaires et des trajets à vide moins coûteux pour la compagnie d'autobus. Pour modéliser ce problème, nous introduisons un graphe hybride entre les deux réseaux classiques de modélisation du MDVSP, à savoir le réseau de connexions et le réseau espacetemps. Le premier modélise explicitement par un arc chacune des connexions possibles entre deux trajets, le second représente chaque mouvement envisageable d'un autobus par un arc de déplacement dans le temps et éventuellement l'espace. Le réseau hybride introduit permet de conserver l'adaptabilité du premier type de réseau et le faible nombre d'arcs du second. En terme de temps de calcul, ce nouveau réseau donne de très bonnes performances pour résoudre le MDVSP classique et le MDVSP avec modification des horaires de départ. Pour résoudre les modèles ainsi construits, on décompose le modèle en deux entités, l'une construit des itinéraires d'autobus admissibles, l'autre choisit une combinaison de ces itinéraires de coût minimal. On peut ainsi résoudre la relaxation linéaire de notre problème par génération de colonnes et donc le problème en nombres entiers par un algorithme de Branch and Price. On décrit et implémente dans ce travail plusieurs méthodes pour accélérer cet algorithme, ralenti entre autres par la dégénérescence des problèmes. Les résultats obtenus montrent qu'on peut ainsi trouver des solutions quasi-optimales en des temps de calcul fortement réduits. Sur des exemples de 300 ou 500 voyages où l'on permet de modifier les horaires de plus ou moins 2 minutes, on voit qu'il est possible de réduire le nombre de véhicules nécessaires de 1 à 3 unités. On étudie également une instance réelle de plus de 1000 voyages que l'on résout en un peu plus d'une heure. Les réductions de coût pour la compagnie d'autobus peuvent donc être importantes. Cependant, modifier les heures de départ ne doit pas détériorer la qualité des horaires pour les utilisateurs du réseau. On voudrait, en particulier, garder des espacements égaux entre les trajets consécutifs d'une même ligne. Un équilibre doit donc être trouvé entre réduction des coûts pour la compagnie et qualité des horaires pour les passagers. Pour cela, on propose d'adopter une approche en deux phases : la première résout le MDVSP avec modification d'horaires, la seconde optimise les horaires de départ compatibles avec les itinéraires trouvés dans la première phase. Pour coordonner ces deux étapes, on tire profit du réseau hybride introduit précédemment. Les résultats montrent qu'on peut ainsi trouver de bons compromis entre le coût des itinéraires d'autobus et la qualité des horaires pour les passagers.

Abstract

In the field of public transit, and especially of bus systems, it is crucial to organize the network efficiently and at a low cost. Given a timetable for each line, a bus company should determine the schedule of all its vehicles and drivers to provide the required service. In this operational planning problem, we will focus on vehicle scheduling. The aim is to build vehicle itineraries in order to cover all desired trips, and this at the lowest possible cost. If the company stores its buses in several depots, this problem is hard to solve (NP-hard problem). It is called Multiple Depot Vehicle Scheduling Problem, abbreviated by MDVSP hereafter. In this work, we add to the classical MDVSP the possibility of modifying the initial timetable, in other words, we allow trip shifting. This way, one can expect to reduce the required number of vehicles and to limit the cost of deadhead trips, i.e. trips without any passengers. To model this problem, we introduce a hybrid graph mixing the two classical graphs used to model MDVSP, namely the connection network and the time-space network. The first one represents explicitly every possible connection between two compatible trips, the second one models every possible bus movement through an arc representing a move in time and possibly in space. Our hybrid network keeps the modeling flexibility of the first type of network and the small number of arcs of the second one. In terms of computation time, this new network performs very well when solving both the classical MDVSP and the MDVSP with trip shifting. In order to solve this problem, we split the model into two entities, one builds feasible bus itineraries, the other chooses a combination of these itineraries at the lowest cost. The linear relaxation of our problem could then be solved using a column generation method and the integer problem thus using a Branch and Price algorithm. In this work, we describe and implement several ways to speed up this algorithm, which is otherwise slowed down by degeneracy (among other things). For our test instances, we manage to find solutions very close to optimality with a substantial reduction of computation time. On instances with 300 or 500 trips, where schedule shifts of up to two minutes were allowed, the bus company can save up to 3 vehicles. We studied also a real-life problem involving more than 1000 trips that we solved in a bit more than one hour. Costs reduction can therefore be very significant. However, shifting trips should not be detrimental to the timetable quality for passengers. In particular, we wish to keep constant headways, i.e. the time lapses between two consecutive departures on the same line. Hence, a tradeoff should be found between cost reduction for the bus company and timetable quality for passengers. To this end, we propose to adopt a two-step algorithm: the first step solves the MDVSP with trip shifting, the second one optimizes the departure schedules while taking into consideration the itineraries found in the first step. To coordinate these two phases, we take advantage of the previously introduced hybrid network. Computational results with this algorithm show that one can quickly find interesting tradeoffs between itineraries costs and timetable quality.