User-Constrained Multimodal Route Planning
Julian Dibbelt, Thomas Pajor, Dorothea Wagner · ACM Journal of Experimental Algorithmics · 2015
In the multimodal route planning problem, we are given multiple transportation networks (e.g., pedestrian, road, public transit) and ask for a best integrated journey between two points. The main challenge is that a seemingly optimal journey may have changes between networks that do not reflect the user’s modal preferences. In fact, quickly computing reasonable multimodal routes remains a challenging problem: previous approaches either suffer from poor query performance or their available choices of modal preferences during query time is limited. In this work, we focus on computing exact multimodal journeys that can be restricted by specifying arbitrary modal sequences at query time. For example, a user can say whether he or she wants to only use public transit, prefers to also use a taxi or walking at the beginning or end of the journey, or has no restrictions at all. By carefully adapting node contraction, a common ingredient to many speedup techniques on road networks, we are able to compute point-to-point queries on a continental network combined of cars, railroads, and flights several orders of magnitude faster than Dijkstra’s algorithm. Thereby, we require little space overhead and obtain fast preprocessing times.