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

RÉSUMÉ: 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. ABSTRACT: This dissertation focuses on the Dial-a-Ride Problem (DARP), a fundamental class of vehicle routing problems that arises in demand-responsive transportation systems such as paratransit services, medical transport, and ride-sharing platforms. The DARP involves planning vehicle routes to fulfill transportation requests defined by pickup and delivery locations, subject to a variety of operational constraints including time windows, maximum ride times, and vehicle capacity limits. In real-world applications, the complexity of DARP increases significantly due to practical constraints, large-scale challenges, and emerging requirements related to electric vehicle operations. The overarching objective of this research is to develop highperformance optimization algorithms capable of addressing these complex and large-scale DARP variants with practical realism and computational scalability. The first contribution of the dissertation addresses a practical DARP variant characterized by heterogeneous passengers (ambulant and wheelchair users), a diverse vehicle fleet, and contract-based operating rules. This version includes advanced constraints such as route duration limits, mandatory break patterns, budget restrictions per contract, and vehicleresource compatibility. The problem is modeled as a set-partitioning integer linear program with an exponential number of variables. To solve it, we develop an exact branch-priceand- cut algorithm that integrates a column generation framework with branch-and-bound and cutting plane strategies. A dedicated labeling algorithm is designed to solve the pricing subproblem efficiently, ensuring route feasibility with respect to all constraints. Extensive computational experiments on real-world instances provided by GIRO Inc., a transportation software company based in Montreal, demonstrate the effectiveness of the proposed method. The algorithm successfully solves to optimality instances involving up to 849 transportation requests and more than 70 heterogeneous vehicles operating under five distinct contracts. This represents the largest DARP instance reported in the literature to be solved exactly using an exact approach. These results also enabled a critical assessment of the heuristic used by the industrial partner, thereby offering valuable feedback for operational improvement. The second contribution targets the challenge of solving very large-scale instances of DARP, which are beyond the practical reach of exact methods due to computational limitations. We propose a variable neighborhood search (VNS) algorithm tailored for high scalability and operational realism. The algorithm incorporates a hybrid initial solution generation mechanism, combining constructive heuristics with a linear programming-based procedure. Furthermore, the VNS framework is enhanced with mixed-integer programming-based components that are applied selective

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.