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.

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 selectively to refine local search and neighborhood transitions. A variety of shaking strategies, including Swap, Chain, and IP-based neighborhoods, are integrated to balance intensification and diversification. The algorithm is validated on a diverse set of large- and very large-scale real-world-inspired instances, ranging from 2,932 to 10,527 transportation requests, with vehicle fleets of up to 563 units. Results indicate that the proposed method consistently generates high-quality solutions within practical time limits—often under one hour—while outperforming traditional heuristics and providing near-optimal solutions for medium-sized instances. The study also includes a sensitivity analysis of different heuristic components, offering guidance on algorithm configuration for operational planners. The third contribution addresses the transition to electric vehicle fleets, introducing the electric dial-a-ride problem (E-DARP). In this setting, electric vehicles must service transportation requests while adhering to energy-related constraints, including limited battery capacity and recharging requirements. The problem is modeled to reflect several realistic and overlooked features, including: (1) a concave piecewise linear charging function representing the decreasing rate of charge over time, (2) station capacity constraints limiting the number of vehicles that can charge simultaneously, (3) time-dependent electricity pricing that influences charging decisions, (4) multiple charger types (e.g., fast and slow), and (5) the ability to partially charge based on route planning and energy needs. These elements make the E-DARP significantly more complex than its fuel-based counterpart, as it requires careful synchronization of routing and energy management decisions. To solve the E-DARP, we extend the VNS framework introduced in the second contribution by embedding a charging station insertion mechanism, adaptive energy-aware neighborhood structures, and an optimization model for optimizing charging plans. The algorithm is tested on large-scale instances derived from real-world and benchmark datasets, including instances with up to 10,000 transportation requests. Results show that the proposed approach not only yields competitive routing solutions but also ensures energy feasibility across diverse vehicle types and station configurations. The method handles operational challenges such as avoiding congestion at charging stations, minimizing energy costs, and satisfying service quality constraints, demonstrating strong potential for supporting the practical deployment of electric mobility systems. Overall, this dissertation makes three principal contributions to the state of the art in vehicle routing and transportation planning. First, it advances the modeling of DARP by integrating heterogeneous, contract-based, and energy-related constraints. Second, it introduces scalable and effective algorithmic frameworks that bridge the gap between exact methods and heuristics for solving very large and realistic instances. Third, it provides empirical evidence, through rigorous computational experiments, of the applicability of these methods to real-world systems. The findings of this research have practical implications for software vendors, transit agencies, and urban planners seeking to improve the efficiency, sustainability, and responsiveness of on-demand transportation services.