MUSE: itinerary planning inspired by Multimodal Separators

This paper presents a multimodal shortest path algorithm based on graph separators. By dividing the network into partitions, preprocessing can be parallelized, allowing for efficient shortest path computations across different transportation modes. During the query phase, the algorithm retrieves the shortest route quickly for any given sequence of modes. Ongoing work focuses on scaling the approach to larger graphs (France and Europe) and exploring multi-level partitions with bidirectional search to further improve performance, as well as adapting the method for dynamic graphs with time-dependent travel times.

‍

With the development of the cloud, the field of algorithms for calculating shorter paths is booming. Some solutions, known as multimodal, are designed to combine various modes of transport, but at the cost of a significant increase in complexity. Here, we propose MUSE, an algorithm based on graph separators, but adapted to the multimodal case. In a pre-processing phase, we first divide the graph into independent partitions (or cells), each partitioned into transport modes, so that we can later answer any query. We then pre-calculate all the shortest routes on this small number of cells, taking into account the labels (modes) of each edge. In this way, we can respond to a query very quickly in the online phase: the user specifies the mode sequences he allows, and uses the pre-calculated shortest routes.