2015/05/06 by Daniel Delling, Julian Dibbelt, Delling, Daniel +5 · 1 citation
Computer Science · Social Sciences · #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2 #G.2.3 #Geographic Information Systems Studies #H.2.8 #H.3.5 #Transportation Planning and Optimization
paper · pdf · doi:10.48550/arxiv.1505.01446
openalex publication_date 2015/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the journey planning problem in public transit networks. Developing efficient preprocessing-based speedup techniques for this problem has been challenging: current approaches either require massive preprocessing effort or provide limited speedups. Leveraging recent advances in Hub Labeling, the fastest algorithm for road networks, we revisit the well-known time-expanded model for public transit. Exploiting domain-specific properties, we provide simple and efficient algorithms for the earliest arrival, profile, and multicriteria problems, with queries that are orders of magnitude faster than the state of the art.