Exact and Heuristic Algorithms for Large-Scale Dial-a-Ride Problems: A Study of Practical and Electric Variants

Cette thèse porte sur le problème de transport à la demande avec réservation préalable, plus connu sous le nom de Dial-a-Ride Problem (DARP), qui constitue une classe fondamentale de problèmes de tournées de véhicules. Le DARP trouve son application dans les systèmes de transport à la demande, tels que les services de transport adapté, le transport médical et les plateformes de covoiturage. Il s’agit d’organiser des itinéraires de véhicules afin de satisfaire un ensemble de demandes de transport, tout en respectant diverses contraintes opérationnelles telles que les fenêtres temporelles, les temps de trajet maximaux des passagers et les limites de capacité des véhicules. Dans les applications réelles, la complexité du DARP est exacerbée par des contraintes pratiques, la taille des instances à traiter, et l’émergence de nouvelles exigences liées à l’introduction des véhicules électriques. L’objectif principal de cette recherche est de concevoir des algorithmes d’optimisation performants capables de résoudre ces variantes réalistes et de très grande taille du DARP, en alliant rigueur dans la modélisation et efficacité en termes de temps de calcul. La première contribution de la thèse s’intéresse à une version pratique du DARP, incluant des passagers hétérogènes (utilisateurs ambulants ou en fauteuil roulant), une flotte de véhicules diversifiée, et des règles contractuelles spécifiques. Cette version tient compte de contraintes avancées telles que la durée maximale des tournées, les pauses obligatoires selon les contrats, les budgets limités par contrat, ainsi que la compatibilité entre les passagers et les véhicules. Le problème est modélisé sous forme d’un programme linéaire en nombres entiers de type partitionnement d’ensemble, comportant un nombre exponentiel de variables. Pour le résoudre, nous avons développé un algorithme exact de type branch-price-and-cut, combinant génération de colonnes, séparation de coupes et exploration d’un arbre de recherche. Un algorithme d’étiquetage sur mesure a été conçu pour résoudre efficacement les sous-problèmes de génération de colonnes, tout en assurant la faisabilité des tournées générées. Les expérimentations réalisées sur des données réelles fournies par GIRO Inc., entreprise montréalaise spécialisée dans les logiciels de planification de transport public, montrent l’efficacité de notre approche. L’algorithme a permis de résoudre de manière optimale des instances comportant jusqu’à 849 demandes et plus de 70 véhicules hétérogènes répartis sur cinq contrats distincts, ce qui constitue, à notre connaissance, la plus grande instance de DARP jamais résolue de façon optimale dans la littérature. Ces résultats ont également permis d’évaluer les performances de l’algorithme heuristique utilisé par notre partenaire industriel. La deuxième contribution traite du défi posé par les instances de très grande taille, pour lesquelles les méthodes exactes ne sont plus applicables en pratique. Pour cela, nous proposons un algorithme de type Variable Neighborhood Search (VNS) conçu pour traiter les contraintes opérationnelles du DARP tout en limitant l’augmentation des temps de calcul en fonction de la taille des instances. L’algorithme repose sur une phase de génération de solution initiale hybride combinant des heuristiques de construction et une procédure basée sur la programmation linéaire. Il intègre également des composantes exactes en programmation en nombres entiers mixtes pour améliorer la recherche locale et la transition entre les voisinages. Différentes structures de voisinage (échange, chaîne, voisinages guidés par la programmation entière) sont utilisées afin d’équilibrer diversification et intensification. L’algorithme est testé sur un grand ensemble d’instances inspirées de cas réels, comportant entre 2 932 et 10 527 demandes, et des flottes allant jusqu’à 563 véhicules. Les résultats expérimentaux montrent que l’approche proposée génère systématiquement des solutions de haute qualité en moins d’une heure de calcul, surpassant les heuristiques classiques tout en produisant des solutions proches de l’optimal pour les cas de taille moyenne. Une analyse de sensibilité sur les composantes heuristiques est également présentée, apportant des recommandations concrètes pour la configuration de l’algorithme en contexte opérationnel. La troisième contribution s’inscrit dans le contexte de la transition énergétique, en adaptant le DARP aux flottes de véhicules électriques, donnant lieu au Electric Dial-a-Ride Problem (E-DARP). Cette variante tient compte des contraintes énergétiques propres aux véhicules électriques, notamment leur autonomie limitée et la nécessité de recharge. Le problème est enrichi par plusieurs éléments réalistes qui ont souvent été omis dans la littérature : (1) une fonction de recharge concave et linéaire par morceaux reflétant le ralentissement du taux de recharge, (2) des contraintes de capacité aux stations de recharge, (3) une tarification dynamique de l’électricité selon l’heure, (4) la coexistence de différents types de bornes (rapides/ lentes), et (5) la possibilité de recharges partielles selon les besoins énergétiques. Ces considérations rendent le E-DARP plus complexe que son équivalent thermique, car elles nécessitent une synchronisation fine entre la planification des tournées et la gestion énergétique. Pour résoudre ce problème, nous étendons le cadre du VNS développé précédemment en y intégrant une stratégie d’insertion de stations de recharge, des structures de voisinage sensibles aux contraintes énergétiques, et un modèle d’optimisation pour planifier les recharges. L’algorithme est évalué sur des instances de grande taille issues de données réelles et de travaux précédents, allant jusqu’à 10 000 demandes. Les résultats montrent que notre méthode permet non seulement de produire des solutions de qualité, mais aussi d’assurer la faisabilité énergétique en tenant compte de la diversité des véhicules et des infrastructures. L’approche gère efficacement les défis opérationnels liés à la congestion aux stations, à la minimisation des coûts énergétiques, et au respect des exigences de qualité de service, démontrant ainsi son potentiel pour une mise en oeuvre concrète dans les systèmes de transport durable. En résumé, cette thèse apporte trois contributions majeures à l’état de l’art en planification de tournées de véhicules dans des contextes complexes. Elle propose (1) des modèles réalistes intégrant l’hétérogénéité des usagers et des véhicules, les contraintes contractuelles et énergétiques ; (2) des algorithmes performants et évolutifs combinant exactitude et efficacité heuristique ; (3) des validations expérimentales rigoureuses démontrant l’applicabilité des méthodes développées à des cas industriels de très grande échelle. Ces travaux ouvrent des perspectives concrètes pour les agences de transport, les fournisseurs de solutions logicielles et les collectivités souhaitant améliorer l’efficacité, la durabilité et la réactivité de leurs services de transport à la demande.