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.