MUSE: Multimodal Separators for Efficient Route Planning in Transportation Networks

Note: actually, [Ulloa, Lehoux-159 Lebacque, and Roulland (2018)] handles two criteria (with an exact approach), and not a single one..Many algorithms compute shortest-path queries in mere microseconds on continental-scale networks. Mostsolutions are, however, tailored to either road or public transit networks in isolation. To fully exploit thetransportation infrastructure, multimodal algorithms are sought to compute shortest-paths combining var-ious modes of transportation. Nonetheless, current solutions still lack performance to efficiently handleinteractive queries under realistic network conditions where traffic jams, public transit cancelations, or delaysoften occur. We present MUSE, a new multimodal algorithm based on graph separators to compute shortesttravel time paths. It partitions the network into independent, smaller regions, enabling fast and scalablepreprocessing. The partition is common to all modes and independent of traffic conditions so that the pre-processing is only executed once. MUSE relies on a state automaton that describes the sequence of modes toconstrain the shortest path during the preprocessing and the online phase. The support of new sequences ofmobility modes only requires the preprocessing of the cliques, independently for each partition. We also aug-ment our algorithm with heuristics during the query phase to achieve further speedups with minimal effecton correctness. We provide experimental results on France’s multimodal network containing the pedestrian,road, bicycle, and public transit networks