MUSE: Multimodal Separators for Efficient Route Planning in Transportation Networks
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. The authors 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. The authors also augment the authors' algorithm with heuristics during the query phase to achieve further speedups with minimal effect on correctness. The authors provide experimental results on France's multimodal network containing the pedestrian, road, bicycle, and public transit networks.
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
-
Supplemental Notes:
- Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
-
Authors:
- Falek, Amine Mohamed
- Pelsser, Cristel
- Julien, Sebastien
- Theoleyre, Fabrice
- Publication Date: 2022-3
Language
- English
Media Info
- Media Type: Web
- Features: References;
- Pagination: pp 436-459
-
Serial:
- Transportation Science
- Volume: 56
- Issue Number: 2
- Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
- ISSN: 0041-1655
- Serial URL: http://transci.journal.informs.org/
Subject/Index Terms
- TRT Terms: Highways; Multimodal transportation; Networks; Public transit; Route choice; Shortest path algorithms
- Geographic Terms: France
- Subject Areas: Highways; Planning and Forecasting; Public Transportation;
Filing Info
- Accession Number: 01842707
- Record Type: Publication
- Files: TRIS
- Created Date: Apr 18 2022 5:05PM