Public Transit Labeling
- Daniel Delling ,
- Julian Dibbelt ,
- Thomas Pajor ,
- Renato F. Werneck
Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15) |
Published by Springer
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.