Fast Multimodal Journey Planning for Three Criteria
Moritz Potthoff, Jonas Sauer · Society for Industrial and Applied Mathematics eBooks · 2022
We study the journey planning problem for multimodal networks consisting of public transit and a non-schedule-based transfer mode (e.g., walking, bicycle, e-scooter). So far, all efficient algorithms for this problem either restrict usage of the transfer mode or Pareto-optimize only two criteria: arrival time and the number of used public transit trips. However, we show that both limitations must be lifted in order to obtain high-quality solutions. In particular, the time spent using the (unrestricted) transfer mode must be optimized as a third criterion. We present McTB, the first algorithm that optimizes three criteria efficiently by avoiding costly data structures for maintaining Pareto sets. To enable unlimited transfers, we combine it with a three-criteria extension of the ULTRA [3, 16] preprocessing technique. Furthermore, since full Pareto sets become impractically large for more than two criteria, we adapt an approach by Delling et al. [5] to restrict the Pareto set in a methodical manner. Extensive experiments on real-world data show that our algorithms are fast enough for interactive queries even on large country-sized networks. Compared to the state of the art for multicriteria multimodal journey planning, MCR [6], we achieve a speedup of up to 80.