MUSE: Multimodal Separators for Efficient Route Planning in Transportation Networks

Amine Mohamed Falek (), Cristel Pelsser (), Sebastien Julien () and Fabrice Theoleyre ()
Additional contact information
Amine Mohamed Falek: Department of Engineering, Technology & Strategy Group, 67300 Schiltigheim, France
Cristel Pelsser: ICube Laboratory, CNRS/University of Strasbourg, Pole API, 67412 Illkirch, France
Sebastien Julien: Department of Engineering, Technology & Strategy Group, 67300 Schiltigheim, France
Fabrice Theoleyre: ICube Laboratory, CNRS/University of Strasbourg, Pole API, 67412 Illkirch, France

Transportation Science, 2022, vol. 56, issue 2, 436-459

Abstract: Many algorithms compute shortest-path queries in mere microseconds on continental-scale networks. Most solutions are, however, tailored to either road or public transit networks in isolation. To fully exploit the transportation infrastructure, multimodal algorithms are sought to compute shortest paths combining various modes of transportation. Nonetheless, current solutions still lack performance to efficiently handle interactive queries under realistic network conditions where traffic jams, public transit cancelations, or delays often occur. We present a multimodal separators–based algorithm (MUSE), a new multimodal algorithm based on graph separators to compute shortest travel time paths. It partitions the network into independent, smaller regions, enabling fast and scalable preprocessing. The partition is common to all modes and independent of traffic conditions so that the preprocessing is only executed once. MUSE relies on a state automaton that describes the sequence of modes to constrain the shortest path during the preprocessing and the online phase. The support of new sequences of mobility modes only requires the preprocessing of the cliques, independently for each partition. We also augment our algorithm with heuristics during the query phase to achieve further speedups with minimal effect on correctness. We provide experimental results on France’s multimodal network containing the pedestrian, road, bicycle, and public transit networks.

Keywords: multimodal shortest path; graph separators; route planning; time-dependent graph (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:56:y:2022:i:2:p:436-459

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().