A Double Decomposition Algorithm for Network Planning and Operations in Deviated Fixed-route Microtransit
Martin-Iradi Bernardo et al. — 2024
Résumé (FR)
Cet article présente une méthodologie d’optimisation pour la conception et l’exploitation de systèmes de microtransit à itinéraire dévié, qui s’appuient sur des lignes de référence avec possibilité de déviations en réponse à la demande des passagers. Une optimisation stochastique en deux étapes est formulée, avec une structure de planification réseau et d’ordonnancement en première étape et une structure de routage véhicule en seconde étape. Un algorithme de double décomposition combinant décomposition de Benders et génération de colonnes est développé. Les tests sur données de Manhattan démontrent la scalabilité de l’approche à de grandes instances avec de nombreuses lignes et arrêts candidats. Les résultats révèlent que le microtransit peut atteindre une mobilité efficace (couverture élevée, faibles coûts), équitable (portée géographique large) et durable. L’étude positionne les arrêts virtuels consolidés comme levier central pour l’efficacité des systèmes hybrides fixe/à la demande.
Summary (EN)
This paper presents an optimization methodology for designing and operating deviated fixed-route microtransit systems that rely on reference lines with possible deviations in response to passenger demand. A two-stage stochastic optimization is formulated, with a network planning and scheduling structure in the first stage and a vehicle routing structure in the second stage. A double decomposition algorithm combining Benders decomposition with column generation is developed. Tests on Manhattan data demonstrate the scalability of the approach to large instances with numerous candidate lines and stops. Results reveal that microtransit can achieve efficient mobility (high demand coverage, low costs), equitable mobility (broad geographic reach), and sustainable mobility. The study positions consolidated virtual stops as a central lever for the efficiency of hybrid fixed/on-demand systems.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Optimisation stochastique en deux étapes + algorithme de double décomposition (Benders + génération de colonnes) |
| Données | Instances synthétiques basées sur Manhattan, avec de nombreuses lignes et arrêts candidats |
| Résultat principal | Scalabilité démontrée ; les arrêts virtuels consolidés améliorent significativement l’efficacité et réduisent les coûts |
| Lien demand/offer-driven | La déviation d’itinéraire constitue une réponse à la demande individuelle (demand-driven) tout en maintenant une structure de ligne fixe (offer-driven) |
| Lien réseau/flux | Les arrêts virtuels consolidés concentrent les flux de passagers, réduisant les détours et maximisant le remplissage des véhicules |
Lien avec la problématique
Cet article illustre directement la complémentarité entre logique demand-driven (déviations adaptées à la demande) et logique offer-driven (lignes de référence préétablies), positionnant les systèmes hybrides comme un espace de tension productif entre ces deux paradigmes. La planification du réseau en première étape reflète une logique d’offre structurante, tandis que le routage en seconde étape intègre la variabilité de la demande, ce qui correspond à la problématique de thèse sur l’articulation entre ces deux logiques. Les arrêts virtuels consolidés constituent un mécanisme de concentration des flux analogue aux hubs et points PUDO, démontrant que la structuration spatiale du réseau est un levier d’efficacité pour la mobilité partagée.