Critical Review of Time-Dependent Shortest Path Algorithms: A Multimodal Trip Planner Perspective

References

• Batz, G. V., Delling, D., & Sanders, P. (2009). Time-dependent contraction hierarchies. Proceedings of the 11th workshop on Algorithm Engineering and Experiments (ALENEX'09), New York. Retrieved from http://www.siam.org/meetings/alenex09/
   Google Scholar
• Batz, G. V., Geisberger, R., Sanders, P., & Vetter, C. (2013). Minimum time-dependent travel times with contraction hierarchies. Journal of Experimental Algorithmics, 18, 1.1–1.43. doi: 10.1145/2444016.2444020
   Google Scholar
• Bauer, R., & Delling, D. (2009). SHARC: Fast and Robust unidirectional routing. ACM Journal of Experimental Algorithmics, 14, 2.4–2.29. Retrieved from http://dl.acm.org/citation.cfm?id=1537599
   Google Scholar
• Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16, 87–90.
   Google Scholar
• Bousquet, A., Sophie, C., & Nour-Eddin, E. F. (2009). On the adaptation of a label-setting shortest path algorithm for one-way and two-way routing in multimodal urban transport networks. International Network Optimization Conference, Pisa, Italy. Retrieved from http://ifors.org/web/international-network-optimization-conference-inoc-2013/
   Google Scholar
• Brunel, E., Delling, D., Gemsa, A., & Wagner, D. (2010, May 20–22). Space-Efficient SHARC-routing. Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy. Proceedings, Springer. Retrieved from http://link.springer.com/chapter/10.1007%2F978-3-642-13193-6_5
   Google Scholar
• Casey, B., Bhaskar, A., & Chung, E. (2012). Data requirements and graph data structures for a multi-modal, multi-objective trip planner. 25th Australian Road Research Board Conference, Perth, Australia.
   Google Scholar
• Casey, B., Guo, H., & Bhaskar, A. (2013). A computational analysis of shortest path algorithms for integrated transit and automobile trip planning. 36th Australasian Transport Research Forum, Brisbane, Australia.
   Google Scholar
• Chabini, I. (1997). A new algorithm for shortest paths in discrete dynamic networks. Presented at the 8th IFAC Symposium on Transportation Systems, Chania, Greece. Retrieved from http://trid.trb.org/view.aspx?id=505732
   Google Scholar
• Chabini, I. (1998). Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record: Journal of the Transportation Research Board, 1645(1), 170–175. doi: 10.3141/1645-21
   Google Scholar
• Chabini, I., & Lan, S. (2002). Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. Intelligent Transportation Systems, IEEE Transactions On, 3(1), 60–74. doi: 10.1109/6979.994796
   Web of Science ®Google Scholar
• Chen, B. Y., Lam, W. H., Sumalee, A., Li, Q., & Tam, M. L. (2013). Reliable shortest path problems in stochastic time-dependent networks. Journal of Intelligent Transportation Systems 18(2), 177–189. doi: 10.1080/15472450.2013.806851
   Web of Science ®Google Scholar
• Cooke, K. L., & Halsey, E. (1966). The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical analysis and applications, 14(3), 493–498. doi: 10.1016/0022-247X(66)90009-6
   Web of Science ®Google Scholar
• Dean, B. C. (2004). Shortest paths in FIFO time-dependent networks: Theory and algorithms. Technical Report, Massachusetts Institute of Technology, Cambridge, MA.
   Google Scholar
• Delling, D. (2011). Time-dependent SHARC-Routing. Algorithmica, 60(1), 60–94. doi: 10.1007/s00453-009-9341-0
   Web of Science ®Google Scholar
• Delling, D., & Nannicini, G. (2012). Core routing on dynamic time-dependent road networks. INFORMS Journal on Computing, 24(2), 187–201. doi: 10.1287/ijoc.1110.0448
   Web of Science ®Google Scholar
• Delling, D., & Wagner, D. (2007). Landmark-based routing in dynamic graphs. Experimental Algorithms, Springer, 4525, 52–65.
   Google Scholar
• Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. doi: 10.1007/BF01386390
   Google Scholar
• Dreyfus, S. E. (1969). An appraisal of some shortest-path algorithms. Operations Research, 17(3), 395–412. doi: 10.1287/opre.17.3.395
   Web of Science ®Google Scholar
• Goldberg, A. V., & Harrelson, C. (2003). Computing the shortest path: A* search meets graph theory. Technical report. Retrieved from http://www.avglab.com/andrew/pub/soda05.pdf
   Google Scholar
• Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. doi: 10.1109/TSSC.1968.300136
   Web of Science ®Google Scholar
• Kaufman, D. E., & Smith, R. L. (1993). Fastest paths in time-dependent networks for intelligent vehicle-highway systems application∗. Journal of Intelligent Transportation Systems, 1(1), 1–11.
   Google Scholar
• Khani, A., Lee, S., Hickman, M., Noh, H., & Nassir, N. (2012). Intermodal path algorithm for time-dependent auto network and scheduled transit service. Transportation Research Record: Journal of the Transportation Research Board, Washington, DC, Transportation Research Board of the National Academies.
   Google Scholar
• Nannicini, G., Delling, D., Schultes, D., & Liberti, L. (2012). Bidirectional A* search on time-dependent road networks. Networks, 59(2), 240–251. doi: 10.1002/net.20438
   Web of Science ®Google Scholar
• Schulz, F. (2005). Timetable information and shortest paths (PhD Dissertation). Karlsruhe University, Karlsruhe.
   Google Scholar