Thumbnail
Access Restriction
Subscribed

Author Dibbelt, Julian ♦ Pajor, Thomas ♦ Wagner, Dorothea
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Shortest paths ♦ Contraction ♦ Multimodal ♦ Route planning
Abstract In the multimodal route planning problem, we are given multiple transportation networks (e.g., pedestrian, road, public transit) and ask for a best $\textit{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 $\textit{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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-04-03
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 19
Page Count 19
Starting Page 1
Ending Page 19


Open content in new tab

   Open content in new tab
Source: ACM Digital Library