Exact Routing in Large Road Networks Using Contraction Hierarchies

References

• Abraham I., Delling D., Goldberg A. V., Werneck R. F., Festa P. Alternative routes in road networks. Proc. 9th Sympos. Experiment. Algorithms (SEA) (2010a) 6049(Springer, Berlin/Heidelberg) 23–34Lecture Notes Comput. Sci.Google Scholar
• Abraham I., Delling D., Goldberg A. V., Werneck R. F., Pardalos P. M., Rebennack S. A hub-based labeling algorithm for shortest paths in road networks. Proc. 10th Sympos. Experiment. Algorithms (SEA) (2011) 6630(Springer, Berlin/Heidelberg) 230–241Lecture Notes Comput. Sci.Google Scholar
• Abraham I., Fiat A., Goldberg A. V., Werneck R. F., Charikar M. Highway dimension, shortest paths, and provably efficient algorithms. Proc. 21st ACM–SIAM Sympos. Discrete Algorithms (SODA) (2010b) (SIAM, Philadelphia) 782–793Google Scholar
• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Upper Saddle River, NJ) Google Scholar
• Batz G. V., Delling D., Sanders P., Vetter C. Time-dependent contraction hierarchies. Proc. 11th Workshop on Algorithm Engrg. Experiments (ALENEX) (2009) (SIAM, Philadelphia) 97–105Google Scholar
• Bauer R., Delling D. SHARC: Fast and robust unidirectional routing. ACM J. Experiment. Algorithmics (2009) 14(December). Article 4Google Scholar
• Bauer R., Columbus T., Katz B., Krug M., Wagner D. Preprocessing speed-up techniques is hard. Proc. 7th Conf. Algorithms and Complexity (CIAC) (2010a) 6078(Springer, Berlin/Heidelberg) 359–370Lecture Notes Comput. Sci.Google Scholar
• Bauer R., Delling D., Sanders P., Schieferdecker D., Schultes D., Wagner D. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. ACM J. Experiment. Algorithmics (2010b) 15(March). Article 2.3Google Scholar
• Delling D., Wagner D., Demetrescu C. Landmark-based routing in dynamic graphs. Proc. 6th Workshop Experiment. Algorithms (WEA) (2007) 4525(Springer, Berlin/Heidelberg) 52–65Lecture Notes Comput. Sci.Google Scholar
• Delling D., Goldberg A. V., Nowatzyk A., Werneck R. F. PHAST: Hardware-accelerated shortest path trees. (2010) . Technical report MSR-TR-2010-125, Microsoft Research, Palo Alto, CAGoogle Scholar
• Delling D., Sanders P., Schultes D., Wagner D., Lerner J., Wagner D., Zweig K. A. Engineering route planning algorithms. Algorithmics of Large and Complex Networks (2009) (Springer-Verlag, Berlin/Heidelberg) 117–139Crossref, Google Scholar
• Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik (1959) 1:269–271Crossref, Google Scholar
• Fu L., Sun D., Rilett L. R. Heuristic shortest path algorithms for transportation applications: State of the art. Comput. Oper. Res. (2006) 33(11):3324–3343Crossref, Google Scholar
• Geisberger R. Contraction hierarchies. (2008) . Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdfGoogle Scholar
• Geisberger R., Festa P. Contraction of timetable networks with realistic transfers. Proc. 9th Sympos. Experiment. Algorithms (SEA) (2010) 6049(Springer, Berlin/Heidelberg) 71–82Lecture Notes Comput. Sci.Google Scholar
• Geisberger R., Kobitzsch M., Sanders P. Route planning with flexible objective functions. Proc. 12th Workshop on Algorithm Engrg. Experiments (ALENEX) (2010) (SIAM, Philadelphia) 124–137Google Scholar
• Geisberger R., Sanders P., Schultes D. Contraction hierarchies source code. (2008) . http://algo2.iti.kit.edu/routeplanning.phpGoogle Scholar
• Geisberger R., Sanders P., Schultes D., Delling D., McGeoch C. C. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Proc. 7th Workshop Experiment. Algorithms (WEA) (2008) 5038(Springer, Berlin/Heidelberg) 319–333Lecture Notes Comput. Sci.Google Scholar
• Goldberg A. V., Harrelson C. Computing the shortest path: A* search meets graph theory. Proc. 16th ACM–SIAM Sympos. Discrete Algorithms (SODA) (2005) (SIAM, Philadelphia) 156–165Google Scholar
• Goldberg A. V., Werneck R. F. Computing point-to-point shortest paths from external memory. Proc. 7th Workshop on Algorithm Engrg. Experiments (ALENEX) (2005) (SIAM, Philadelphia) 26–40Google Scholar
• Goldberg A. V., Kaplan H., Werneck R. F., Demetrescu C. Better landmarks within reach. Proc. 6th Workshop Experiment. Algorithms (WEA) (2007) 4525(Springer-Verlag, Berlin/Heidelberg) 38–51Lecture Notes Comput. Sci.Google Scholar
• Goldberg A. V., Kaplan H., Werneck R. F., Demetrescu C, Goldberg A. V., Johnson D. S. Reach for A*: Shortest path algorithms with preprocessing. The Shortest Path Problem: Ninth DIMACS Implementation Challenge (2009) 74(American Mathematical Society, Providence, RI) 93–139DIMACS: Series in Discrete Mathematics and Theoretical Computer ScienceGoogle Scholar
• Hilger M., Köhler E., Möhring R. H., Schilling H., Demetrescu C., Goldberg A. V., Johnson D. S. Fast point-to-point shortest path computations with arc-flags. The Shortest Path Problem: Ninth DIMACS Implementation Challenge (2009) 74(American Mathematical Society, Providence, RI) 41–72DIMACS: Series in Discrete Mathematics and Theoretical Computer ScienceGoogle Scholar
• Kieritz T., Luxen D., Sanders P., Vetter C., Festa P. Distributed time-dependent contraction hierarchies. Proc. 9th sympos. Experiment. Algorithms (SEA) (2010) 6049(Springer, Berlin/Heidelberg) 83–93Lecture Notes Comput. Sci.Google Scholar
• Klunder G. A., Post H. N. The shortest path problem on large-scale real-road networks. Networks (2006) 48(4):182–194Crossref, Google Scholar
• Knopp S., Sanders P., Schultes D., Schulz F., Wagner D. Computing many-to-many shortest paths using highway hierarchies. Proc. 9th Workshop on Algorithm Engrg. Experiments (ALENEX) (2007) (SIAM, Philadelphia) 36–45Google Scholar
• Lauther U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. Geoinformation und Mobilität—von der Forschung zur Praktischen Anwendung (2004) 22(IfGI Prints, Münster) 219–230Google Scholar
• Maue J., Sanders P., Matijevic D. Goal directed shortest path queries using precomputed cluster distances. Proc. 5th Workshop on Experiment. Algorithms (WEA) (2006) 4007(Springer, Berlin/Heidelberg) 316–328Lecture Notes Comput. Sci.Google Scholar
• Pijls W., Post H. N. A new bidirectional search algorithm with shortened postprocessing. Eur. J. Oper. Res. (2009) 198(2):363–369Crossref, Google Scholar
• Rice M., Tsotras V. J. Graph indexing of road networks for shortest path queries with label restrictions. Proc. VLDB Endowment (2010) 4(2):69–80Crossref, Google Scholar
• Sanders P., Schultes D. Highway hierarchies hasten exact shortest path queries. Proc. 13th Annual Eur. Sympos. Algorithms (ESA) (2005) 3669(Springer, Berlin/Heidelberg) 568–579Lecture Notes Comput. Sci.Google Scholar
• Sanders P., Schultes D., Vetter C. Mobile route planning. Proc. 16th Annual Eur. Sympos. Algorithms (ESA) (2008) 5193(Springer, Berlin/Heidelberg) 732–743Lecture Notes Comput. Sci.Google Scholar
• Schultes D. Route planning in road networks. (2008) . Ph.D. thesis, Universität Karlsruhe (TH), Fakultät für Informatik, http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdfGoogle Scholar
• Schultes D., Sanders P., Demetrescu C. Dynamic highway-node routing. Proc. 6th Workshop Experiment. Algorithms (WEA) (2007) 4525(Springer, Berlin/Heidelberg) 66–79Lecture Notes Comput. Sci.Google Scholar
• U.S. Census Bureau U.S. Census 2000 TIGER/Line Files. (2002) (Washington DC ). Accessed March 1, 2005, http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.htmlGoogle Scholar
• Vetter C. Parallel time-dependent contraction hierarchies. (2009) . Student research project, Universität Karlsruhe, Fakultät für Informatik http://algo2.iti.kit.edu/download/vetter_sa.pdfGoogle Scholar
• Vetter C. Monav. (2010) . http://code.google.com/p/monav/Google Scholar
• Winter S. Modeling costs of turns in route planning. GeoInformatica (2002) 6(4):345–361Crossref, Google Scholar