{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T07:11:22Z","timestamp":1775027482004,"version":"3.50.1"},"publisher-location":"Cham","reference-count":262,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319494869","type":"print"},{"value":"9783319494876","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-49487-6_2","type":"book-chapter","created":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T14:11:38Z","timestamp":1478787098000},"page":"19-80","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":299,"title":["Route Planning in Transportation Networks"],"prefix":"10.1007","author":[{"given":"Hannah","family":"Bast","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Delling","sequence":"additional","affiliation":[]},{"given":"Andrew","family":"Goldberg","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"M\u00fcller-Hannemann","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Pajor","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,11]]},"reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/978-3-642-22006-7_58","volume-title":"Automata, Languages and Programming","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 690\u2013699. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22006-7_58"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: HLDB: Location-based services in databases. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 339\u2013348. ACM Press 2012. Best Paper Award","DOI":"10.1145\/2424321.2424365"},{"key":"2_CR3","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. Technical report MSR-TR-2013-91, Microsoft Research (2013)"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-642-20662-7_20","volume-title":"Experimental Algorithms","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: A hub-based labeling algorithm for shortest paths in road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 230\u2013241. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20662-7_20"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-33090-2_4","volume-title":"Algorithms \u2013 ESA 2012","author":"I Abraham","year":"2012","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 24\u201335. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-33090-2_4"},{"issue":"1","key":"2_CR6","first-page":"1","volume":"18","author":"I Abraham","year":"2013","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Alternative routes in road networks. ACM J. Exp. Algorithm. 18(1), 1\u201317 (2013)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 782\u2013793. SIAM (2010)","DOI":"10.1137\/1.9781611973075.64"},{"issue":"2","key":"2_CR8","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"RK Ahuja","year":"1990","unstructured":"Ahuja, R.K., Mehlhorn, K., Orlin, J.B., Tarjan, R.: Faster algorithms for the shortest path problem. J. ACM 37(2), 213\u2013223 (1990)","journal-title":"J. ACM"},{"issue":"4","key":"2_CR9","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1002\/net.10072","volume":"41","author":"RK Ahuja","year":"2003","unstructured":"Ahuja, R.K., Orlin, J.B., Pallottino, S., Scutell\u00e0, M.G.: Dynamic shortest paths minimizing travel times and costs. Networks 41(4), 197\u2013205 (2003)","journal-title":"Networks"},{"issue":"1","key":"2_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.3141\/2032-04","volume":"2032","author":"G Aifadopoulou","year":"2007","unstructured":"Aifadopoulou, G., Ziliaskopoulos, A., Chrisohoou, E.: Multiobjective optimum path algorithm for passenger pretrip planning in multimodal transportation networks. J. Transp. Res. Board 2032(1), 26\u201334 (2007). doi: 10.3141\/2032-04","journal-title":"J. Transp. Res. Board"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Kawarabayashi, K., Kawata, Y.: Fast shortest-path distance queries on road networks by pruned highway labeling. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX 2014), pp. 147\u2013154. SIAM (2014)","DOI":"10.1137\/1.9781611973198.14"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida,Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD 2013), pp. 349\u2013360. ACM Press (2013)","DOI":"10.1145\/2463676.2465315"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-319-07959-2_25","volume-title":"Experimental Algorithms","author":"L Allulli","year":"2014","unstructured":"Allulli, L., Italiano, G.F., Santaroni, F.: Exploiting GPS data in public transport journey planners. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 295\u2013306. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-07959-2_25"},{"key":"2_CR14","unstructured":"Antsfeld, L., Walsh, T.: Finding multi-criteria optimal paths in multi-modal public transportation networks using the transit algorithm. In: Proceedings of the 19th ITS World Congress (2012)"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-38527-8_7","volume-title":"Experimental Algorithms","author":"J Arz","year":"2013","unstructured":"Arz, J., Luxen, D., Sanders, P.: Transit node routing reconsidered. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 55\u201366. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38527-8_7"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-642-39206-1_7","volume-title":"Automata, Languages, and Programming","author":"M Babenko","year":"2013","unstructured":"Babenko, M., Goldberg, A.V., Gupta, A., Nagarajan, V.: Algorithms for hub label optimization. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 69\u201380. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-39206-1_7"},{"key":"2_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-19754-3_5","volume-title":"Theory and Practice of Algorithms in (Computer) Systems","author":"R Bader","year":"2011","unstructured":"Bader, R., Dees, J., Geisberger, R., Sanders, P.: Alternative route graphs in road networks. In: Marchetti-Spaccamela, A., Segal, M. (eds.) TAPAS 2011. LNCS, vol. 6595, pp. 21\u201332. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-19754-3_5"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-540-68880-8_5","volume-title":"Algorithmic Aspects in Information and Management","author":"C Barrett","year":"2008","unstructured":"Barrett, C., Bisset, K., Holzer, M., Konjevod, G., Marathe, M., Wagner, D.: Engineering label-constrained shortest-path algorithms. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 27\u201337. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-68880-8_5"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Barrett, C., Bisset, K., Holzer, M., Konjevod, G., Marathe, M.V., Wagner, D.: Engineering label-constrained shortest-path algorithms. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 309\u2013319. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/12"},{"key":"2_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-45749-6_15","volume-title":"Algorithms \u2014 ESA 2002","author":"C Barrett","year":"2002","unstructured":"Barrett, C., Bisset, K., Jacob, R., Konjevod, G., Marathe, M.: Classical and contemporary shortest path problems in road networks: implementation and experimental analysis of the TRANSIMS router. In: M\u00f6hring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 126\u2013138. Springer, Heidelberg (2002). doi: 10.1007\/3-540-45749-6_15"},{"issue":"3","key":"2_CR21","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C Barrett","year":"2000","unstructured":"Barrett, C., Jacob, R., Marathe, M.V.: Formal-language-constrained path problems. SIAM J. Comput. 30(3), 809\u2013837 (2000)","journal-title":"SIAM J. Comput."},{"key":"2_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-642-03456-5_24","volume-title":"Efficient Algorithms","author":"H Bast","year":"2009","unstructured":"Bast, H.: Car or public transport\u2014two worlds. In: Albers, S., Alt, H., N\u00e4her, S. (eds.) Efficient Algorithms. LNCS, vol. 5760, pp. 355\u2013367. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-03456-5_24"},{"key":"2_CR23","unstructured":"Bast, H., Brodesser, M., Storandt, S.: Result diversity for multi-modal route planning. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 123\u2013136 (2013)"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-642-15775-2_25","volume-title":"Algorithms \u2013 ESA 2010","author":"H Bast","year":"2010","unstructured":"Bast, H., Carlsson, E., Eigenwillig, A., Geisberger, R., Harrelson, C., Raychev, V., Viger, F.: Fast routing in very large public transportation networks using transfer patterns. In: Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6346, pp. 290\u2013301. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-15775-2_25"},{"key":"2_CR25","unstructured":"Bast, H., Sternisko, J., Storandt, S.: Delay-robustness of transfer patterns in public transportation route planning. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 42\u201354 (2013)"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Bast, H., Storandt, S.: Flow-based guidebook routing. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX 2014), pp. 155\u2013165. SIAM (2014)","DOI":"10.1137\/1.9781611973198.15"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Bast, H., Storandt, S.: Frequency-based search for public transit. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 13\u201322. ACM Press, November 2014","DOI":"10.1145\/2666310.2666405"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D.: Ultrafast shortest-path queries via transit nodes. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 175\u2013192. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/07"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant shortest-path queries in road networks. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), pp. 46\u201359. SIAM (2007)","DOI":"10.1137\/1.9781611972870.5"},{"issue":"5824","key":"2_CR30","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1126\/science.1137521","volume":"316","author":"H Bast","year":"2007","unstructured":"Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316(5824), 566 (2007)","journal-title":"Science"},{"key":"2_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-34862-4_7","volume-title":"Design and Analysis of Algorithms","author":"GV Batz","year":"2012","unstructured":"Batz, G.V., Geisberger, R., Luxen, D., Sanders, P., Zubkov, R.: Efficient route compression for hybrid route planning. In: Even, G., Rawitz, D. (eds.) MedAlg 2012. LNCS, vol. 7659, pp. 93\u2013107. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-34862-4_7"},{"issue":"1.4","key":"2_CR32","first-page":"1","volume":"18","author":"GV Batz","year":"2013","unstructured":"Batz, G.V., Geisberger, R., Sanders, P., Vetter, C.: Minimum time-dependent travel times with contraction hierarchies. ACM J. Exp. Algorithm. 18(1.4), 1\u201343 (2013)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-33090-2_16","volume-title":"Algorithms \u2013 ESA 2012","author":"GV Batz","year":"2012","unstructured":"Batz, G.V., Sanders, P.: Time-dependent route planning with generalized objective functions. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 169\u2013180. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-33090-2_16"},{"key":"2_CR34","unstructured":"Bauer, A.: Multimodal profile queries. Bachelor thesis, Karlsruhe Institute of Technology, May 2012"},{"issue":"3","key":"2_CR35","doi-asserted-by":"publisher","first-page":"265","DOI":"10.7155\/jgaa.00294","volume":"17","author":"R Bauer","year":"2013","unstructured":"Bauer, R., Baum, M., Rutter, I., Wagner, D.: On the complexity of partitioning graphs for arc-flags. J. Graph Algorithms Appl. 17(3), 265\u2013299 (2013)","journal-title":"J. Graph Algorithms Appl."},{"key":"2_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-642-13073-1_32","volume-title":"Algorithms and Complexity","author":"R Bauer","year":"2010","unstructured":"Bauer, R., Columbus, T., Katz, B., Krug, M., Wagner, D.: Preprocessing speed-up techniques is hard. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 359\u2013370. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13073-1_32"},{"key":"2_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-39206-1_9","volume-title":"Automata, Languages, and Programming","author":"R Bauer","year":"2013","unstructured":"Bauer, R., Columbus, T., Rutter, I., Wagner, D.: Search-space size in contraction hierarchies. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 93\u2013104. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-39206-1_9"},{"issue":"2","key":"2_CR38","doi-asserted-by":"publisher","first-page":"447","DOI":"10.7155\/jgaa.00270","volume":"16","author":"R Bauer","year":"2012","unstructured":"Bauer, R., D\u2019Angelo, G., Delling, D., Schumm, A., Wagner, D.: The shortcut problem - complexity and algorithms. J. Graph Algorithms Appl. 16(2), 447\u2013481 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2.4","key":"2_CR39","first-page":"1","volume":"14","author":"R Bauer","year":"2009","unstructured":"Bauer, R., Delling, D.: SHARC: Fast and robust unidirectional routing. ACM J. Exp. Algorithm. 14(2.4), 1\u201329 (2009). Special Section on Selected Papers from ALENEX 2008","journal-title":"ACM J. Exp. Algorithm."},{"issue":"2.3","key":"2_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1868237.1868241","volume":"15","author":"R Bauer","year":"2010","unstructured":"Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., Wagner, D.: Combining hierarchical, goal-directed speed-up techniques for Dijkstra\u2019s algorithm. ACM J. Exp. Algorithm. 15(2.3), 1\u201331 (2010). Special Section devoted to WEA 2008","journal-title":"ACM J. Exp. Algorithm."},{"issue":"1","key":"2_CR41","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1002\/net.20382","volume":"57","author":"R Bauer","year":"2011","unstructured":"Bauer, R., Delling, D., Wagner, D.: Experimental study on speed-up techniques for timetable information systems. Networks 57(1), 38\u201352 (2011)","journal-title":"Networks"},{"key":"2_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/978-3-642-14355-7_6","volume-title":"Algorithmic Aspects in Information and Management","author":"R Bauer","year":"2010","unstructured":"Bauer, R., Krug, M., Meinert, S., Wagner, D.: Synthetic road networks. In: Chen, B. (ed.) AAIM 2010. LNCS, vol. 6124, pp. 46\u201357. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14355-7_6"},{"key":"2_CR43","unstructured":"Baum, M., Dibbelt, J., H\u00fcbschle-Schneider, L., Pajor, T., Wagner, D.: Speed-consumption tradeoff for electric vehicle route planning. In: Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2014), OpenAccess Series in Informatics (OASIcs), pp. 138\u2013151 (2014)"},{"key":"2_CR44","doi-asserted-by":"crossref","unstructured":"Baum, M., Dibbelt, J., Pajor, T., Wagner, D.: Energy-optimal routes for electric vehicles. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 54\u201363. ACM Press (2013)","DOI":"10.1145\/2525314.2525361"},{"key":"2_CR45","first-page":"929","volume":"10","author":"N Baumann","year":"1988","unstructured":"Baumann, N., Schmidt, R.: Buxtehude-Garmisch in 6 Sekunden. die elektronische Fahrplanauskunft (EFA) der Deutschen Bundesbahn. Zeitschrift f\u00fcr aktuelle Verkehrsfragen 10, 929\u2013931 (1988)","journal-title":"Zeitschrift f\u00fcr aktuelle Verkehrsfragen"},{"key":"2_CR46","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Q. Appl. Math. 16, 87\u201390 (1958)","journal-title":"Q. Appl. Math."},{"key":"2_CR47","unstructured":"Berger, A., Delling, D., Gebhardt, A., M\u00fcller-Hannemann, M.: Accelerating time-dependent multi-criteria timetable information is harder than expected. In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2009), OpenAccess Series in Informatics (OASIcs) (2009)"},{"key":"2_CR48","unstructured":"Berger, A., Gebhardt, A., M\u00fcller-Hannemann, M., Ostrowski, M.: Stochastic delay prediction in large train networks. In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2011), OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 100\u2013111 (2011)"},{"key":"2_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-642-13193-6_4","volume-title":"Experimental Algorithms","author":"A Berger","year":"2010","unstructured":"Berger, A., Grimmer, M., M\u00fcller-Hannemann, M.: Fully dynamic speed-up techniques for multi-criteria shortest path searches in time-dependent networks. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 35\u201346. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13193-6_4"},{"issue":"3","key":"2_CR50","doi-asserted-by":"publisher","first-page":"1705","DOI":"10.1016\/j.ejor.2005.02.036","volume":"175","author":"M Bielli","year":"2006","unstructured":"Bielli, M., Boulmakoul, A., Mouncif, H.: Object modeling and path computation for multimodal travel systems. Eur. J. Oper. Res. 175(3), 1705\u20131730 (2006)","journal-title":"Eur. J. Oper. Res."},{"key":"2_CR51","unstructured":"B\u00f6hmov\u00e1, K., Mihal\u00e1k, M., Pr\u00f6ger, T., \u0160r\u00e1mek, R., Widmayer, P.: Robust routing in urban public transportation: how to find reliable journeys based on past observations. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 27\u201341 (2013)"},{"key":"2_CR52","doi-asserted-by":"crossref","unstructured":"Botea, A.: Ultra-fast optimal pathfinding without runtime search. In: Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2011), pp. 122\u2013127. AAAI Press (2011)","DOI":"10.1609\/aiide.v7i1.12443"},{"key":"2_CR53","doi-asserted-by":"crossref","unstructured":"Botea, A., Harabor, D.: Path planning with compressed all-pairs shortest paths data. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling, AAAI Press (2013)","DOI":"10.1609\/icaps.v23i1.13600"},{"key":"2_CR54","series-title":"Theoretical Computer Science and General Issues","doi-asserted-by":"crossref","DOI":"10.1007\/b106453","volume-title":"Network Analysis: Methodological Foundations","author":"U Brandes","year":"2005","unstructured":"Brandes, U., Erlebach, T.: Network Analysis: Methodological Foundations. Theoretical Computer Science and General Issues, vol. 3418. Springer, Heidelberg (2005)"},{"key":"2_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/3-540-44808-X_10","volume-title":"Algorithm Engineering and Experimentation","author":"U Brandes","year":"2001","unstructured":"Brandes, U., Schulz, F., Wagner, D., Willhalm, T.: Travel planning with self-made maps. In: Buchsbaum, A.L., Snoeyink, J. (eds.) ALENEX 2001. LNCS, vol. 2153, pp. 132\u2013144. Springer, Heidelberg (2001). doi: 10.1007\/3-540-44808-X_10"},{"key":"2_CR56","doi-asserted-by":"crossref","unstructured":"Brodal, G., Jacob, R.: Time-dependent networks as models to achieve fast exact time-table queries. In: Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2003), Electronic Notes in Theoretical Computer Science, vol. 92, pp. 3\u201315 (2004)","DOI":"10.1016\/j.entcs.2003.12.019"},{"issue":"4","key":"2_CR57","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s11786-007-0023-5","volume":"1","author":"F Bruera","year":"2008","unstructured":"Bruera, F., Cicerone, S., D\u2019Angelo, G., Di Stefano, G., Frigioni, D.: Dynamic multi-level overlay graphs for shortest paths. Math. Comput. Sci. 1(4), 709\u2013736 (2008)","journal-title":"Math. Comput. Sci."},{"key":"2_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-13193-6_5","volume-title":"Experimental Algorithms","author":"E Brunel","year":"2010","unstructured":"Brunel, E., Delling, D., Gemsa, A., Wagner, D.: Space-efficient SHARC-routing. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 47\u201358. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13193-6_5"},{"issue":"2","key":"2_CR59","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/366105.366184","volume":"4","author":"T Caldwell","year":"1961","unstructured":"Caldwell, T.: On finding minimum routes in a network with turn penalties. Commun. ACM 4(2), 107\u2013108 (1961)","journal-title":"Commun. ACM"},{"key":"2_CR60","unstructured":"Cambridge Vehicle Information Technology Ltd. Choice routing (2005). http:\/\/www.camvit.com"},{"key":"2_CR61","first-page":"129","volume":"73","author":"BV Cherkassky","year":"1996","unstructured":"Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms. Math. Programm. Ser. A 73, 129\u2013174 (1996)","journal-title":"Math. Programm. Ser. A"},{"key":"2_CR62","unstructured":"Cherkassky, B.V., Goldberg, A.V., Silverstein, C.: Buckets, heaps, lists, and monotone priority queues. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 83\u201392. IEEE Computer Society Press (1997)"},{"key":"2_CR63","unstructured":"Cionini, A., D\u2019Angelo, G., D\u2019Emidio, M., Frigioni, D., Giannakopoulou, K., Paraskevopoulos, A.: Engineering graph-based models for dynamic timetable information systems. In: Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2014), OpenAccess Series in Informatics (OASIcs), pp. 46\u201361 (2014)"},{"issue":"5","key":"2_CR64","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2_CR65","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/0022-247X(66)90009-6","volume":"14","author":"K Cooke","year":"1966","unstructured":"Cooke, K., Halsey, E.: The shortest route through a network with time-dependent intermodal transit times. J. Math. Anal. Appl. 14(3), 493\u2013498 (1966)","journal-title":"J. Math. Anal. Appl."},{"key":"2_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-30850-5_13","volume-title":"Experimental Algorithms","author":"G D\u2019Angelo","year":"2012","unstructured":"D\u2019Angelo, G., D\u2019Emidio, M., Frigioni, D., Vitale, C.: Fully dynamic maintenance of arc-flags in road networks. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 135\u2013147. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-30850-5_13"},{"key":"2_CR67","volume-title":"Linear Programming and Extensions","author":"BD George","year":"1962","unstructured":"George, B.D.: Linear Programming and Extensions. Princeton University Press, Princeton (1962)"},{"key":"2_CR68","unstructured":"Dean, B.C.: Continuous-time dynamic shortest path algorithms. Master\u2019s thesis, Massachusetts Institute of Technology (1999)"},{"issue":"1","key":"2_CR69","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1002\/net.20013","volume":"44","author":"BC Dean","year":"2004","unstructured":"Dean, B.C.: Algorithms for minimum-cost paths in time-dependent networks with waiting policies. Networks 44(1), 41\u201346 (2004)","journal-title":"Networks"},{"key":"2_CR70","unstructured":"Dean, B.C.: Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report, Massachusetts Institute Of Technology (2004)"},{"key":"2_CR71","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/s00453-010-9461-6","volume":"62","author":"F Dehne","year":"2012","unstructured":"Dehne, F., Omran, M.T., Sack, J.-R.: Shortest paths in time-dependent FIFO networks. Algorithmica 62, 416\u2013435 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"2_CR72","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00453-009-9341-0","volume":"60","author":"D Delling","year":"2011","unstructured":"Delling, D.: Time-dependent SHARC-routing. Algorithmica 60(1), 60\u201394 (2011)","journal-title":"Algorithmica"},{"key":"2_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-38527-8_24","volume-title":"Experimental Algorithms","author":"D Delling","year":"2013","unstructured":"Delling, D., Dibbelt, J., Pajor, T., Wagner, D., Werneck, R.F.: Computing multimodal journeys in practice. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 260\u2013271. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38527-8_24"},{"key":"2_CR74","unstructured":"Delling, D., Giannakopoulou, K., Wagner, D., Zaroliagis, C.: Timetable information updating in case of delays: modeling issues. Technical report 133, Arrival Technical report (2008)"},{"issue":"7","key":"2_CR75","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1016\/j.jpdc.2012.02.007","volume":"73","author":"D Delling","year":"2013","unstructured":"Delling, D., Goldberg, A.V., Nowatzyk, A., Werneck, R.F.: PHAST: Hardware-accelerated shortest path trees. J. Parallel Distrib. Comput. 73(7), 940\u2013952 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"key":"2_CR76","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-642-20662-7_32","volume-title":"Experimental Algorithms","author":"D Delling","year":"2011","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376\u2013387. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20662-7_32"},{"key":"2_CR77","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-662-44777-2_27","volume-title":"Algorithms - ESA 2014","author":"D Delling","year":"2014","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Robust distance queries on massive networks. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 321\u2013333. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44777-2_27"},{"key":"2_CR78","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning in road networks. Transp. Sci. (2015)"},{"key":"2_CR79","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: 25th International Parallel and Distributed Processing Symposium (IPDPS 2011), pp. 1135\u20131146. IEEE Computer Society (2011)","DOI":"10.1109\/IPDPS.2011.108"},{"key":"2_CR80","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-319-07959-2_22","volume-title":"Experimental Algorithms","author":"D Delling","year":"2014","unstructured":"Delling, D., Goldberg, A.V., Savchenko, R., Werneck, R.F.: Hub labels: theory and practice. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 259\u2013270. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-07959-2_22"},{"key":"2_CR81","unstructured":"Delling, D., Goldberg, A.V., Werneck, R.F.: Faster batched shortest paths in road networks. In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2011), OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 52\u201363 (2011)"},{"key":"2_CR82","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-38527-8_4","volume-title":"Experimental Algorithms","author":"D Delling","year":"2013","unstructured":"Delling, D., Goldberg, A.V., Werneck, R.F.: Hub label compression. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 18\u201329. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38527-8_4"},{"key":"2_CR83","doi-asserted-by":"crossref","unstructured":"Delling, D., Holzer, M., M\u00fcller, K., Schulz, F., Wagner, D., High-performance multi-level routing. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 73\u201392. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/04"},{"key":"2_CR84","doi-asserted-by":"crossref","unstructured":"Delling, D., Italiano, G.F., Pajor, T., Santaroni, F.: Better transit routing by exploiting vehicle GPS data. In: Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science. ACM Press, November 2014","DOI":"10.1145\/2674918.2674923"},{"issue":"4","key":"2_CR85","first-page":"4. 1","volume":"17","author":"D Delling","year":"2012","unstructured":"Delling, D., Katz, B., Pajor, T.: Parallel computation of best connections in public transportation networks. ACM J. Exp. Algorithm. 17(4), 4. 1\u20134. 26 (2012)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR86","doi-asserted-by":"crossref","unstructured":"Delling, D., Kobitzsch, M., Luxen, D., Werneck, R.F.: Robust mobile route planning with limited connectivity. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 150\u2013159. SIAM (2012)","DOI":"10.1137\/1.9781611972924.15"},{"key":"2_CR87","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1007\/978-3-319-09873-9_61","volume-title":"Euro-Par 2014 Parallel Processing","author":"D Delling","year":"2014","unstructured":"Delling, D., Kobitzsch, M., Werneck, R.F.: Customizing driving directions with GPUs. In: Silva, F., Dutra, I., Santos Costa, V. (eds.) Euro-Par 2014. LNCS, vol. 8632, pp. 728\u2013739. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-09873-9_61"},{"issue":"2","key":"2_CR88","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1287\/ijoc.1110.0448","volume":"24","author":"D Delling","year":"2012","unstructured":"Delling, D., Nannicini, G.: Core routing on dynamic time-dependent road networks. Informs J. Comput. 24(2), 187\u2013201 (2012)","journal-title":"Informs J. Comput."},{"key":"2_CR89","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/978-3-642-04128-0_53","volume-title":"Algorithms - ESA 2009","author":"D Delling","year":"2009","unstructured":"Delling, D., Pajor, T., Wagner, D.: Accelerating multi-modal route planning by access-nodes. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 587\u2013598. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-04128-0_53"},{"key":"2_CR90","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-05465-5_7","volume-title":"Robust and Online Large-Scale Optimization","author":"D Delling","year":"2009","unstructured":"Delling, D., Pajor, T., Wagner, D.: Engineering time-expanded graphs for faster timetable information. In: Ahuja, R.K., M\u00f6hring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 182\u2013206. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-05465-5_7"},{"key":"2_CR91","unstructured":"Delling, D., Pajor, T., Wagner, D., Zaroliagis, C.: Efficient route planning in flight networks. In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2009), OpenAccess Series in Informatics (OASIcs) (2009)"},{"key":"2_CR92","doi-asserted-by":"crossref","unstructured":"Delling, D., Pajor, T., Werneck, R.F.: Round-based public transit routing. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 130\u2013140. SIAM (2012)","DOI":"10.1137\/1.9781611972924.13"},{"key":"2_CR93","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1287\/trsc.2014.0534","volume":"49","author":"D Delling","year":"2014","unstructured":"Delling, D., Pajor, T., Werneck, R.F.: Round-based public transit routing. Transp. Sci. 49, 591\u2013604 (2014)","journal-title":"Transp. Sci."},{"key":"2_CR94","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-02094-0_7","volume-title":"Algorithmics of Large and Complex Networks","author":"D Delling","year":"2009","unstructured":"Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering route planning algorithms. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics of Large and Complex Networks. LNCS, vol. 5515, pp. 117\u2013139. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02094-0_7"},{"key":"2_CR95","doi-asserted-by":"crossref","unstructured":"Delling, D., Sanders, P., Schultes, D., Wagner, D.: Highway hierarchies star. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 141\u2013174. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/06"},{"key":"2_CR96","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-540-72845-0_5","volume-title":"Experimental Algorithms","author":"D Delling","year":"2007","unstructured":"Delling, D., Wagner, D.: Landmark-based routing in dynamic graphs. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 52\u201365. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-72845-0_5"},{"key":"2_CR97","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-642-02011-7_13","volume-title":"Experimental Algorithms","author":"D Delling","year":"2009","unstructured":"Delling, D., Wagner, D.: Pareto paths with SHARC. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 125\u2013136. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02011-7_13"},{"key":"2_CR98","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-05465-5_8","volume-title":"Robust and Online Large-Scale Optimization","author":"D Delling","year":"2009","unstructured":"Delling, D., Wagner, D.: Time-dependent route planning. In: Ahuja, R.K., M\u00f6hring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 207\u2013230. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-05465-5_8"},{"key":"2_CR99","doi-asserted-by":"crossref","unstructured":"Delling, D., Werneck, R.F.: Customizable point-of-interest queries in road networks. In: Proceedings of the 21st ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2013), pp. 490\u2013493. ACM Press (2013)","DOI":"10.1145\/2525314.2525470"},{"key":"2_CR100","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-38527-8_5","volume-title":"Experimental Algorithms","author":"D Delling","year":"2013","unstructured":"Delling, D., Werneck, R.F.: Faster customization of road networks. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 30\u201342. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38527-8_5"},{"key":"2_CR101","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book","year":"2009","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74. American Mathematical Society, Providence (2009)"},{"key":"2_CR102","doi-asserted-by":"crossref","unstructured":"Demiryurek, U., Banaei-Kashani, F., Shahabi, C.: A case for time-dependent shortest path computation in spatial networks. In: Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2010), pp. 474\u2013477 (2010)","DOI":"10.1145\/1869790.1869865"},{"issue":"1","key":"2_CR103","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1287\/opre.27.1.161","volume":"27","author":"EV Denardo","year":"1979","unstructured":"Denardo, E.V., Fox, B.L.: Shortest-route methods: 1. reaching, pruning, and buckets. Oper. Res. 27(1), 161\u2013186 (1979)","journal-title":"Oper. Res."},{"issue":"11","key":"2_CR104","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1145\/363269.363610","volume":"12","author":"RB Dial","year":"1969","unstructured":"Dial, R.B.: Algorithm 360: shortest-path forest with topological ordering [H]. Commun. ACM 12(11), 632\u2013633 (1969)","journal-title":"Commun. ACM"},{"key":"2_CR105","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-642-38527-8_6","volume-title":"Experimental Algorithms","author":"J Dibbelt","year":"2013","unstructured":"Dibbelt, J., Pajor, T., Strasser, B., Wagner, D.: Intriguingly simple and fast transit routing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 43\u201354. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38527-8_6"},{"key":"2_CR106","doi-asserted-by":"crossref","unstructured":"Dibbelt, J., Pajor, T., Wagner, D.: User-constrained multi-modal route planning. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 118\u2013129. SIAM (2012)","DOI":"10.1137\/1.9781611972924.12"},{"key":"2_CR107","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-319-07959-2_23","volume-title":"Experimental Algorithms","author":"J Dibbelt","year":"2014","unstructured":"Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 271\u2013282. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-07959-2_23"},{"key":"2_CR108","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"2_CR109","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-540-68552-4_26","volume-title":"Experimental Algorithms","author":"Y Disser","year":"2008","unstructured":"Disser, Y., M\u00fcller\u2013Hannemann, M., Schnee, M.: Multi-criteria shortest paths in time-dependent train networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 347\u2013361. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-68552-4_26"},{"key":"2_CR110","doi-asserted-by":"crossref","unstructured":"Drews, F., Luxen, D.: Multi-hop ride sharing. In: Proceedings of the 5th International Symposium on Combinatorial Search (SoCS 2012), pp. 71\u201379. AAAI Press (2013)","DOI":"10.1609\/socs.v4i1.18279"},{"issue":"3","key":"2_CR111","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"SE Dreyfus","year":"1969","unstructured":"Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395\u2013412 (1969)","journal-title":"Oper. Res."},{"key":"2_CR112","doi-asserted-by":"crossref","unstructured":"Efentakis, A., Pfoser, D.: Optimizing landmark-based routing and preprocessing. In: Proceedings of the 6th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 25:25\u201325:30. ACM Press, November 2013","DOI":"10.1145\/2533828.2533838"},{"key":"2_CR113","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/978-3-662-44777-2_30","volume-title":"Algorithms - ESA 2014","author":"A Efentakis","year":"2014","unstructured":"Efentakis, A., Pfoser, D.: GRASP. Extending graph separators for the single-source shortest-path problem. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 358\u2013370. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44777-2_30"},{"key":"2_CR114","doi-asserted-by":"crossref","unstructured":"Efentakis, A., Pfoser, D., Vassiliou., Y.: SALT: a unified framework for all shortest-path query variants on road networks. CoRR, abs\/1411.0257 (2014)","DOI":"10.1007\/978-3-319-20086-6_23"},{"key":"2_CR115","doi-asserted-by":"crossref","unstructured":"Efentakis, A., Pfoser, D., Voisard, A.: Efficient data management in support of shortest-path computation. In: Proceedings of the 4th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 28\u201333. ACM Press (2011)","DOI":"10.1145\/2068984.2068990"},{"key":"2_CR116","doi-asserted-by":"crossref","unstructured":"Efentakis, A., Theodorakis, D., Pfoser,D.: Crowdsourcing computing resources for shortest-path computation. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 434\u2013437. ACM Press (2012)","DOI":"10.1145\/2424321.2424383"},{"key":"2_CR117","doi-asserted-by":"crossref","DOI":"10.1007\/b101915","volume-title":"Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys","author":"M Ehrgott","year":"2002","unstructured":"Ehrgott, M., Gandibleux, X.: Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic Publishers Group, New York (2002)"},{"key":"2_CR118","doi-asserted-by":"crossref","unstructured":"Eisenstat, D.: Random road networks: the quadtree model. In: Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2011), pp. 76\u201384. SIAM, January 2011","DOI":"10.1137\/1.9781611973013.9"},{"key":"2_CR119","doi-asserted-by":"crossref","unstructured":"Eisner, J., Funke, S.: Sequenced route queries: getting things done on the way back home. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 502\u2013505. ACM Press (2012)","DOI":"10.1145\/2424321.2424400"},{"key":"2_CR120","doi-asserted-by":"crossref","unstructured":"Eisner, J., Funke, S.: Transit nodes - lower bounds and refined construction. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 141\u2013149. SIAM (2012)","DOI":"10.1137\/1.9781611972924.14"},{"key":"2_CR121","doi-asserted-by":"crossref","unstructured":"Eisner, J., Funke, S., Herbst, A., Spillner, A., Storandt, S.: Algorithms for matching and predicting trajectories. In: Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX 2011), pp. 84\u201395. SIAM (2011)","DOI":"10.1137\/1.9781611972917.9"},{"key":"2_CR122","doi-asserted-by":"crossref","unstructured":"Eisner, J., Funke, S., Storandt, S.: Optimal route planning for electric vehicles in large network. In: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. AAAI Press, August 2011","DOI":"10.1609\/aaai.v25i1.7991"},{"key":"2_CR123","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Goodrich, M.T.: Studying (non-planar) road networks through an algorithmic lens. In: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2008), pp. 1\u201310. ACM Press (2008)","DOI":"10.1145\/1463434.1463455"},{"key":"2_CR124","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-319-07959-2_10","volume-title":"Experimental Algorithms","author":"S Erb","year":"2014","unstructured":"Erb, S., Kobitzsch, M., Sanders, P.: Parallel bi-objective shortest paths using weight-balanced B-trees with bulk updates. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 111\u2013122. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-07959-2_10"},{"key":"2_CR125","unstructured":"Firmani, D., Italiano, G.F., Laura, L., Santaroni, F.: Is timetabling routing always reliable for public transport? In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 15\u201326 (2013)"},{"issue":"6","key":"2_CR126","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)","journal-title":"Commun. ACM"},{"key":"2_CR127","unstructured":"Ford, Jr., L.R.: Network flow theory. Technical report P-923, Rand Corporation, Santa Monica, California (1956)"},{"issue":"4","key":"2_CR128","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1007\/s00453-012-9714-7","volume":"68","author":"L Foschini","year":"2014","unstructured":"Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. Algorithmica 68(4), 1075\u20131097 (2014)","journal-title":"Algorithmica"},{"issue":"3","key":"2_CR129","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"11","key":"2_CR130","doi-asserted-by":"publisher","first-page":"3324","DOI":"10.1016\/j.cor.2005.03.027","volume":"33","author":"L Fu","year":"2006","unstructured":"Fu, L., Sun, D., Rilett, L.R.: Heuristic shortest path algorithms for transportation applications: state of the art. Comput. Oper. Res. 33(11), 3324\u20133343 (2006)","journal-title":"Comput. Oper. Res."},{"key":"2_CR131","doi-asserted-by":"crossref","unstructured":"Funke, S., Nusser, A., Storandt, S.: On k-path covers and their applications. In: Proceedings of the 40th International Conference on Very Large Databases (VLDB 2014), pp. 893\u2013902 (2014)","DOI":"10.14778\/2732951.2732963"},{"key":"2_CR132","doi-asserted-by":"crossref","unstructured":"Funke, S., Nusser, A., Storandt, S.: Placement of loading stations for electric vehicles: no detours necessary! In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press (2014)","DOI":"10.1613\/jair.4688"},{"key":"2_CR133","doi-asserted-by":"crossref","unstructured":"Funke, S., Storandt, S.: Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In: Proceedings of the 15th Meeting on Algorithm Engineering and Experiments (ALENEX 2013), pp. 31\u201354. SIAM (2013)","DOI":"10.1137\/1.9781611972931.4"},{"issue":"2\u20133","key":"2_CR134","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16(2\u20133), 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"key":"2_CR135","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53, 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"2_CR136","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-642-13193-6_7","volume-title":"Experimental Algorithms","author":"R Geisberger","year":"2010","unstructured":"Geisberger, R.: Contraction of timetable networks with realistic transfers. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 71\u201382. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13193-6_7"},{"key":"2_CR137","unstructured":"Geisberger, R.: Advanced route planning in transportation networks. Ph.D. thesis, Karlsruhe Institute of Technology, February 2011"},{"key":"2_CR138","doi-asserted-by":"crossref","unstructured":"Geisberger, R., Kobitzsch, M., Sanders, P.: Route planning with flexible objective functions. In: Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX 2010), pp. 124\u2013137. SIAM (2010)","DOI":"10.1137\/1.9781611972900.12"},{"key":"2_CR139","unstructured":"Geisberger, R., Luxen, D., Sanders, P., Neubauer, S., Volker, L.: Fast detour computation for ride sharing. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2010), OpenAccess Series in Informatics (OASIcs), vol. 14, pp. 88\u201399 (2010)"},{"issue":"1","key":"2_CR140","first-page":"1","volume":"17","author":"R Geisberger","year":"2012","unstructured":"Geisberger, R., Rice, M., Sanders, P., Tsotras, V.: Route planning with flexible edge restrictions. ACM J. Exp. Algorithm. 17(1), 1\u201320 (2012)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR141","unstructured":"Geisberger, R., Sanders, P.: Engineering time-dependent many-to-many shortest paths computation. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2010), OpenAccess Series in Informatics (OASIcs), vol. 14 (2010)"},{"issue":"3","key":"2_CR142","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/trsc.1110.0401","volume":"46","author":"R Geisberger","year":"2012","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci. 46(3), 388\u2013404 (2012)","journal-title":"Transp. Sci."},{"key":"2_CR143","doi-asserted-by":"crossref","unstructured":"Geisberger, R., Schieferdecker, D.: Heuristic contraction hierarchies with approximation guarantee. In: Proceedings of the 3rd International Symposium on Combinatorial Search (SoCS 2010). AAAI Press (2010)","DOI":"10.1609\/socs.v1i1.18161"},{"key":"2_CR144","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-642-20662-7_9","volume-title":"Experimental Algorithms","author":"R Geisberger","year":"2011","unstructured":"Geisberger, R., Vetter, C.: Efficient routing in road networks with turn costs. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 100\u2013111. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20662-7_9"},{"key":"2_CR145","unstructured":"Goerigk, M., He\u00dfe, S., M\u00fcller-Hannemann, M., Schmidt, M.: Recoverable robust timetable information. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 1\u201314 (2013)"},{"key":"2_CR146","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1287\/trsc.2013.0470","volume":"48","author":"M Goerigk","year":"2014","unstructured":"Goerigk, M., Knoth, M., M\u00fcller-Hannemann, M., Schmidt, M., Sch\u00f6bel, A.: The price of strict and light robustness in timetable information. Transp. Sci. 48, 225\u2013242 (2014)","journal-title":"Transp. Sci."},{"key":"2_CR147","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1137\/070698774","volume":"37","author":"AV Goldberg","year":"2008","unstructured":"Goldberg, A.V.: A practical shortest path algorithm with linear expected time. SIAM J. Comput. 37, 1637\u20131655 (2008)","journal-title":"SIAM J. Comput."},{"key":"2_CR148","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 156\u2013165. SIAM (2005)"},{"key":"2_CR149","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Kaplan, H., Werneck, R.F.: Reach for A*: shortest path algorithms with preprocessing. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 93\u2013139. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/05"},{"key":"2_CR150","unstructured":"Goldberg, A.V., Werneck, R.F.: Computing point-to-point shortest paths from external memory. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 26\u201340. SIAM (2005)"},{"key":"2_CR151","unstructured":"Goldman, R., Shivakumar, N.R., Venkatasubramanian, S., Garcia-Molina, H.: Proximity search in databases. In: Proceedings of the 24th International Conference on Very Large Databases (VLDB 1998), pp. 26\u201337. Morgan Kaufmann, August 1998"},{"key":"2_CR152","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Pszona, P.: Two-phase bicriterion search for finding fast and efficient electric vehicle routes. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press, November 2014","DOI":"10.1145\/2666310.2666382"},{"issue":"1","key":"2_CR153","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.20380","volume":"57","author":"T Gunkel","year":"2011","unstructured":"Gunkel, T., Schnee, M., M\u00fcller-Hannemann, M.: How to find good night train connections. Networks 57(1), 19\u201327 (2011)","journal-title":"Networks"},{"key":"2_CR154","unstructured":"Gutman, R.J., Reach-based routing: a new approach to shortest path algorithms optimized for road networks. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX 2004), pp. 100\u2013111. SIAM (2004)"},{"key":"2_CR155","series-title":"Lecture Notes in Economics and Mathematical Systems","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-48782-8_9","volume-title":"Multiple Criteria Decision Making - Theory and Application","author":"P Hansen","year":"1979","unstructured":"Hansen, P.: Bricriteria path problems. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making - Theory and Application. LNEMS, vol. 177, pp. 109\u2013127. Springer, Heidelberg (1979). doi: 10.1007\/978-3-642-48782-8_9"},{"key":"2_CR156","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"2_CR157","doi-asserted-by":"crossref","unstructured":"Hilger, M., K\u00f6hler, E., M\u00f6hring, R.H., Schilling, H., Fast point-to-point shortest path computations with arc-flags. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 41\u201372. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/03"},{"key":"2_CR158","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-642-23719-5_38","volume-title":"Algorithms \u2013 ESA 2011","author":"P Hlin\u011bn\u00fd","year":"2011","unstructured":"Hlin\u011bn\u00fd, P., Mori\u0161, O.: Scope-based route planning. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 445\u2013456. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-23719-5_38"},{"key":"2_CR159","unstructured":"Holzer, M.: Engineering planar-separator and shortest-path algorithms. Ph.D. thesis, Karlsruhe Institute of Technology (KIT) - Department of Informatics (2008)"},{"issue":"2.5","key":"2_CR160","first-page":"1","volume":"13","author":"M Holzer","year":"2008","unstructured":"Holzer, M., Schulz, F., Wagner, D.: Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exp. Algorithm. 13(2.5), 1\u201326 (2008)","journal-title":"ACM J. Exp. Algorithm."},{"issue":"2.5","key":"2_CR161","first-page":"1","volume":"10","author":"M Holzer","year":"2006","unstructured":"Holzer, M., Schulz, F., Wagner, D., Willhalm, T.: Combining speed-up techniques for shortest-path computations. ACM J. Exp. Algorithm. 10(2.5), 1\u201318 (2006)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR162","doi-asserted-by":"crossref","unstructured":"Horvitz, E., Krumm, J.: Some help on the way: opportunistic routing under uncertainty. In: Proceedings of the 2012 ACM Conference on Ubiquitous Computing (Ubicomp 2012), pp. 371\u2013380. ACM Press (2012)","DOI":"10.1145\/2370216.2370273"},{"key":"2_CR163","doi-asserted-by":"crossref","unstructured":"Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., Shimoura, H., Hashimoto, T., Tenmoku, K., Mitoh, K.: A fast algorithm for finding better routes by AI search techniques. In: Proceedings of the Vehicle Navigation and Information Systems Conference (VNSI 1994), pp. 291\u2013296. ACM Press (1994)","DOI":"10.1109\/VNIS.1994.396824"},{"issue":"3","key":"2_CR164","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1109\/69.687976","volume":"10","author":"N Jing","year":"1998","unstructured":"Jing, N., Huang, Y.-W., Rundensteiner, E.A.: Hierarchical encoded path views for path query processing: an optimal model and its performance evaluation. IEEE Trans. Knowl. Data Eng. 10(3), 409\u2013432 (1998)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"5","key":"2_CR165","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","volume":"14","author":"S Jung","year":"2002","unstructured":"Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng. 14(5), 1029\u20131046 (2002)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2_CR166","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1613\/jair.460","volume":"7","author":"H Kaindl","year":"1997","unstructured":"Kaindl, H., Kainz, G.: Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. 7, 283\u2013317 (1997)","journal-title":"J. Artif. Intell. Res."},{"key":"2_CR167","unstructured":"Kaufmann, H.: Towards mobile time-dependent route planning. Bachelor thesis, Karlsruhe Institute of Technology (2013)"},{"key":"2_CR168","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-13193-6_8","volume-title":"Experimental Algorithms","author":"T Kieritz","year":"2010","unstructured":"Kieritz, T., Luxen, D., Sanders, P., Vetter, C.: Distributed time-dependent contraction hierarchies. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 83\u201393. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13193-6_8"},{"key":"2_CR169","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-642-30850-5_21","volume-title":"Experimental Algorithms","author":"D Kirchler","year":"2012","unstructured":"Kirchler, D., Liberti, L., Wolfler Calvo, R.: A label correcting algorithm for the shortest path problem on a multi-modal route network. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 236\u2013247. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-30850-5_21"},{"key":"2_CR170","unstructured":"Kirchler, D., Liberti, L., Pajor, T., Calvo, R.W.: UniALT for regular language constraint shortest paths on a multi-modal transportation network. In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2011), OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 64\u201375 (2011)"},{"key":"2_CR171","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 444\u2013453. IEEE Computer Society Press (2004)","DOI":"10.1109\/FOCS.2004.70"},{"key":"2_CR172","doi-asserted-by":"crossref","unstructured":"Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), pp. 36\u201345. SIAM (2007)","DOI":"10.1137\/1.9781611972870.4"},{"key":"2_CR173","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/978-3-642-40450-4_52","volume-title":"Algorithms \u2013 ESA 2013","author":"M Kobitzsch","year":"2013","unstructured":"Kobitzsch, M.: HiDAR: an alternative approach to alternative routes. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 613\u2013624. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40450-4_52"},{"key":"2_CR174","unstructured":"Kobitzsch, M., Radermacher, M., Schieferdecker, D.: Evolution and evaluation of the penalty method for alternative graphs. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 94\u2013107 (2013)"},{"key":"2_CR175","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/978-3-662-43948-7_59","volume-title":"Automata, Languages, and Programming","author":"S Kontogiannis","year":"2014","unstructured":"Kontogiannis, S., Zaroliagis, C.: Distance oracles for time-dependent networks. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 713\u2013725. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-43948-7_59"},{"issue":"2","key":"2_CR176","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1080\/17489725.2013.788228","volume":"7","author":"J Krumm","year":"2013","unstructured":"Krumm, J., Gruen, R., Delling, D.: From destination prediction to route prediction. J. Locat. Based Serv. 7(2), 98\u2013120 (2013)","journal-title":"J. Locat. Based Serv."},{"issue":"4","key":"2_CR177","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1109\/MC.2007.141","volume":"40","author":"J Krumm","year":"2007","unstructured":"Krumm, J., Horvitz, E.: Predestination: where do you want to go today? IEEE Comput. 40(4), 105\u2013107 (2007)","journal-title":"IEEE Comput."},{"key":"2_CR178","doi-asserted-by":"crossref","unstructured":"Lauther, U.: An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol. 74, DIMACS Book, pp. 19\u201340. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/02"},{"issue":"3","key":"2_CR179","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1109\/TKDE.2010.243","volume":"24","author":"CK Ken","year":"2012","unstructured":"Ken, C.K., Lee, J.L., Zheng, B., Tian, Y.: ROAD: a new spatial object search framework for road networks. IEEE Trans. Knowl. Data Eng. 24(3), 547\u2013560 (2012)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"2_CR180","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"issue":"2","key":"2_CR181","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"2_CR182","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF00936165","volume":"43","author":"P Loridan","year":"1984","unstructured":"Loridan, P.: $$\\epsilon $$ -solutions in vector minimization problems. J. Optim. Theory Appl. 43(2), 265\u2013276 (1984)","journal-title":"J. Optim. Theory Appl."},{"key":"2_CR183","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-642-20662-7_21","volume-title":"Experimental Algorithms","author":"D Luxen","year":"2011","unstructured":"Luxen, D., Sanders, P.: Hierarchy decomposition for faster user equilibria on road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 242\u2013253. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20662-7_21"},{"key":"2_CR184","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-30850-5_23","volume-title":"Experimental Algorithms","author":"D Luxen","year":"2012","unstructured":"Luxen, D., Schieferdecker, D.: Candidate sets for alternative routes in road networks. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 260\u2013270. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-30850-5_23"},{"key":"2_CR185","doi-asserted-by":"crossref","unstructured":"Luxen, D., Vetter, C.: Real-time routing with OpenStreetMap data. In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press (2011)","DOI":"10.1145\/2093973.2094062"},{"key":"2_CR186","doi-asserted-by":"crossref","unstructured":"Madduri, K., Bader, D.A., Berry, J.W., Crobak, J.R., Parallel shortest path algorithms for solving large-scale instances. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 249\u2013290. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/10"},{"issue":"3","key":"2_CR187","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","volume":"26","author":"EQ Martins","year":"1984","unstructured":"Martins, E.Q.: On a multicriteria shortest path problem. Eur. J. Oper. Res. 26(3), 236\u2013245 (1984)","journal-title":"Eur. J. Oper. Res."},{"key":"2_CR188","doi-asserted-by":"crossref","first-page":"3.2:1","DOI":"10.1145\/1498698.1564502","volume":"14","author":"J Maue","year":"2009","unstructured":"Maue, J., Sanders, P., Matijevic, D.: Goal-directed shortest-path queries using precomputed cluster distances. ACM J. Exp. Algorithm. 14, 3.2:1\u20133.2:27 (2009)","journal-title":"ACM J. Exp. Algorithm."},{"issue":"3","key":"2_CR189","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K Mehlhorn","year":"1988","unstructured":"Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27(3), 125\u2013128 (1988)","journal-title":"Inf. Process. Lett."},{"key":"2_CR190","volume-title":"The Basic Toolbox","author":"K Mehlhorn","year":"2008","unstructured":"Mehlhorn, K., Sanders, P., Algorithms, D.S.: The Basic Toolbox. Springer, Heidelberg (2008)"},{"key":"2_CR191","unstructured":"Mellouli, T., Suhl, L.: Passenger online routing in dynamic networks. In: Mattfeld, D.C., Suhl, L. (eds.) Informations probleme in Transport und Verkehr, vol. 4, pp. 17\u201330. DS&OR Lab, Universit\u00e4t Paderborn (2006)"},{"key":"2_CR192","unstructured":"Meyer, U.: Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 797\u2013806 (2001)"},{"issue":"1","key":"2_CR193","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/S0196-6774(03)00076-2","volume":"49","author":"U Meyer","year":"2003","unstructured":"Meyer, U., Sanders, P.: $$\\delta $$ -stepping: a parallelizable shortest path algorithm. J. Algorithms 49(1), 114\u2013152 (2003)","journal-title":"J. Algorithms"},{"key":"2_CR194","doi-asserted-by":"crossref","unstructured":"Milosavljevi\u0107, N.: On optimal preprocessing for contraction hierarchies. In: Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 33\u201338. ACM Press (2012)","DOI":"10.1145\/2442942.2442949"},{"issue":"3","key":"2_CR195","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/S0377-2217(97)00376-7","volume":"111","author":"P Modesti","year":"1998","unstructured":"Modesti, P., Sciomachen, A.: A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks. Eur. J. Oper. Res. 111(3), 495\u2013508 (1998)","journal-title":"Eur. J. Oper. Res."},{"key":"2_CR196","doi-asserted-by":"crossref","unstructured":"M\u00f6hring, R.H.: Verteilte Verbindungssuche im \u00f6ffentlichen Personenverkehr - Graphentheoretische Modelle und Algorithmen. In: Angewandte Mathematik insbesondere Informatik, Beispiele erfolgreicher Wege zwischen Mathematik und Informatik, pp. 192\u2013220. Vieweg (1999)","DOI":"10.1007\/978-3-322-83092-0_11"},{"issue":"28","key":"2_CR197","first-page":"1","volume":"11","author":"RH M\u00f6hring","year":"2006","unstructured":"M\u00f6hring, R.H., Schilling, H., Sch\u00fctz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speedup Dijkstra\u2019s algorithm. ACM J. Exp. Algorithm. 11(28), 1\u201329 (2006)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR198","unstructured":"Moore, E.F.: The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching, pp. 285\u2013292. Harvard University Press (1959)"},{"key":"2_CR199","unstructured":"M\u00fcller-Hannemann, M., Schnee, M.: Paying less for train connections with MOTIS. In: Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2005), OpenAccess Series in Informatics (OASIcs), p. 657 (2006)"},{"key":"2_CR200","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-74247-0_13","volume-title":"Algorithmic Methods for Railway Optimization","author":"M M\u00fcller-Hannemann","year":"2007","unstructured":"M\u00fcller-Hannemann, M., Schnee, M.: Finding all attractive train connections by multi-criteria pareto search. In: Geraets, F., Kroon, L., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization. LNCS, vol. 4359, pp. 246\u2013263. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-74247-0_13"},{"key":"2_CR201","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-642-05465-5_10","volume-title":"Robust and Online Large-Scale Optimization","author":"M M\u00fcller-Hannemann","year":"2009","unstructured":"M\u00fcller-Hannemann, M., Schnee, M.: Efficient timetable information in the presence of delays. In: Ahuja, R.K., M\u00f6hring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 249\u2013272. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-05465-5_10"},{"issue":"6","key":"2_CR202","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/S1571-0661(04)80525-5","volume":"66","author":"M M\u00fcller-Hannemann","year":"2002","unstructured":"M\u00fcller-Hannemann, M., Schnee, M., Weihe, K.: Getting train timetables into the main storage. Electron. Notes Theoret. Comput. Sci. 66(6), 8\u201317 (2002)","journal-title":"Electron. Notes Theoret. Comput. Sci."},{"key":"2_CR203","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-540-74247-0_3","volume-title":"Algorithmic Methods for Railway Optimization","author":"M M\u00fcller-Hannemann","year":"2007","unstructured":"M\u00fcller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.: Timetable information: models and algorithms. In: Geraets, F., Kroon, L., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization. LNCS, vol. 4359, pp. 67\u201390. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-74247-0_3"},{"key":"2_CR204","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-44688-5_15","volume-title":"Algorithm Engineering","author":"M M\u00fcller-Hannemann","year":"2001","unstructured":"M\u00fcller-Hannemann, M., Weihe, K.: Pareto shortest paths is often feasible in practice. In: Brodal, G.S., Frigioni, D., Marchetti-Spaccamela, A. (eds.) WAE 2001. LNCS, vol. 2141, pp. 185\u2013197. Springer, Heidelberg (2001). doi: 10.1007\/3-540-44688-5_15"},{"key":"2_CR205","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1007\/978-3-540-75520-3_58","volume-title":"Algorithms \u2013 ESA 2007","author":"LF Muller","year":"2007","unstructured":"Muller, L.F., Zachariasen, M.: Fast and compact oracles for approximate distances in planar graphs. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 657\u2013668. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-75520-3_58"},{"issue":"1","key":"2_CR206","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0377-2217(94)E0349-G","volume":"83","author":"K Nachtigall","year":"1995","unstructured":"Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1), 154\u2013166 (1995)","journal-title":"Eur. J. Oper. Res."},{"key":"2_CR207","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1002\/net.20438","volume":"59","author":"G Nannicini","year":"2012","unstructured":"Nannicini, G., Delling, D., Liberti, L., Schultes, D.: Bidirectional A* search on time-dependent road networks. Networks 59, 240\u2013251 (2012). Best Paper Award","journal-title":"Networks"},{"issue":"3","key":"2_CR208","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/79147.214078","volume":"37","author":"A Orda","year":"1990","unstructured":"Orda, A., Rom, R.: Shortest-path and minimum delay algorithms in networks with time-dependent edge-length. J. ACM 37(3), 607\u2013625 (1990)","journal-title":"J. ACM"},{"key":"2_CR209","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1002\/net.3230210304","volume":"21","author":"A Orda","year":"1991","unstructured":"Orda, A., Rom, R.: Minimum weight paths in time-dependent networks. Networks 21, 295\u2013319 (1991)","journal-title":"Networks"},{"key":"2_CR210","unstructured":"Pajor, T.: Multi-modal route planning. Master\u2019s thesis, Universit\u00e4t Karlsruhe (TH), March 2009"},{"key":"2_CR211","doi-asserted-by":"crossref","unstructured":"Pallottino, S., Scutell\u00e0, M.G.: Shortest path algorithms in transportation models: Classical and innovative aspects. In: Equilibrium and Advanced Transportation Modelling, pp. 245\u2013281. Kluwer Academic Publishers Group (1998)","DOI":"10.1007\/978-1-4615-5757-9_11"},{"key":"2_CR212","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pp. 86\u201392 (2000)","DOI":"10.1109\/SFCS.2000.892068"},{"key":"2_CR213","unstructured":"Paraskevopoulos, A., Zaroliagis, C.: Improved alternative route planning. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 108\u2013122 (2013)"},{"issue":"2","key":"2_CR214","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/1003021","volume":"3","author":"SV Parter","year":"1961","unstructured":"Parter, S.V.: The use of linear graphs in Gauss elimination. SIAM Rev. 3(2), 119\u2013130 (1961)","journal-title":"SIAM Rev."},{"issue":"3","key":"2_CR215","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"key":"2_CR216","doi-asserted-by":"crossref","unstructured":"Pohl, I.: Bi-directional and heuristic search in path problems. Technical report SLAC-104, Stanford Linear Accelerator Center, Stanford, California (1969)","DOI":"10.2172\/4785039"},{"key":"2_CR217","unstructured":"Pohl, I.: Bi-directional search. In: Proceedings of the Sixth Annual Machine Intelligence Workshop, vol. 6, pp. 124\u2013140. Edinburgh University Press (1971)"},{"key":"2_CR218","unstructured":"Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Experimental comparison of shortest path approaches for timetable information. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX 2004), pp. 88\u201399. SIAM (2004)"},{"issue":"24","key":"2_CR219","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1227161.1227166","volume":"12","author":"E Pyrga","year":"2008","unstructured":"Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient models for timetable information in public transportation systems. ACM J. Exp. Algorithm. 12(24), 1\u201339 (2008)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR220","unstructured":"Rice, M., Tsotras, V.: Bidirectional A* search with additive approximation bounds. In: Proceedings of the 5th International Symposium on Combinatorial Search (SoCS 2012), AAAI Press (2012)"},{"key":"2_CR221","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-642-30850-5_30","volume-title":"Experimental Algorithms","author":"MN Rice","year":"2012","unstructured":"Rice, M.N., Tsotras, V.J.: Exact graph search algorithms for generalized traveling salesman path problems. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 344\u2013355. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-30850-5_30"},{"key":"2_CR222","doi-asserted-by":"crossref","unstructured":"Sanders, P., Mandow, L.: Parallel label-setting multi-objective shortest path search. In: 27th International Parallel and Distributed Processing Symposium (IPDPS 2013), pp. 215\u2013224. IEEE Computer Society (2013)","DOI":"10.1109\/IPDPS.2013.89"},{"key":"2_CR223","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/11561071_51","volume-title":"Algorithms \u2013 ESA 2005","author":"P Sanders","year":"2005","unstructured":"Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 568\u2013579. Springer, Heidelberg (2005). doi: 10.1007\/11561071_51"},{"key":"2_CR224","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schultes, D.: Robust, almost constant time shortest-path queries in road networks. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 193\u2013218. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/08"},{"issue":"1","key":"2_CR225","first-page":"1","volume":"17","author":"P Sanders","year":"2012","unstructured":"Sanders, P., Schultes, D.: Engineering highway hierarchies. ACM J. Exp. Algorithm. 17(1), 1\u201340 (2012)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR226","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1007\/978-3-540-87744-8_61","volume-title":"Algorithms - ESA 2008","author":"P Sanders","year":"2008","unstructured":"Sanders, P., Schultes, D., Vetter, C.: Mobile route planning. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 732\u2013743. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-87744-8_61"},{"key":"2_CR227","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 16\u201329. SIAM (2012)","DOI":"10.1137\/1.9781611972924.2"},{"key":"2_CR228","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, J., Alborzi, H., Samet, H.: Efficient query processing on spatial networks. In: Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems (GIS 2005), pp. 200\u2013209 (2005)","DOI":"10.1145\/1097064.1097093"},{"issue":"8","key":"2_CR229","doi-asserted-by":"publisher","first-page":"1158","DOI":"10.1109\/TKDE.2010.75","volume":"22","author":"J Sankaranarayanan","year":"2010","unstructured":"Sankaranarayanan, J., Samet, H.: Query processing using distance oracles for spatial networks. IEEE Trans. Knowl. Data Eng. 22(8), 1158\u20131175 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"2_CR230","first-page":"4","volume":"33","author":"J Sankaranarayanan","year":"2010","unstructured":"Sankaranarayanan, J., Samet, H.: Roads belong in databases. IEEE Data Eng. Bull. 33(2), 4\u201311 (2010)","journal-title":"IEEE Data Eng. Bull."},{"key":"2_CR231","unstructured":"Schilling, H.: TomTom navigation - How mathematics help getting through traffic faster (2012). Talk given at ISMP"},{"issue":"3","key":"2_CR232","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1145\/356004.356006","volume":"8","author":"R Schreiber","year":"1982","unstructured":"Schreiber, R.: A new implementation of sparse Gaussian elimination. ACM Trans. Math. Softw. 8(3), 256\u2013276 (1982)","journal-title":"ACM Trans. Math. Softw."},{"key":"2_CR233","unstructured":"Schultes, D.: Route planning in road networks. Ph.D. thesis, Universit\u00e4t Karlsruhe (TH), February 2008"},{"key":"2_CR234","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-540-72845-0_6","volume-title":"Experimental Algorithms","author":"D Schultes","year":"2007","unstructured":"Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 66\u201379. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-72845-0_6"},{"issue":"12","key":"2_CR235","first-page":"1","volume":"5","author":"F Schulz","year":"2000","unstructured":"Schulz, F., Wagner, D., Weihe, K.: Dijkstra\u2019s algorithm on-line: an empirical case study from public railroad transport. ACM J. Exp. Algorithm. 5(12), 1\u201323 (2000)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR236","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-45643-0_4","volume-title":"Algorithm Engineering and Experiments","author":"F Schulz","year":"2002","unstructured":"Schulz, F., Wagner, D., Zaroliagis, C.: Using multi-level graphs for timetable information in railway systems. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 43\u201359. Springer, Heidelberg (2002). doi: 10.1007\/3-540-45643-0_4"},{"issue":"1","key":"2_CR237","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01840435","volume":"1","author":"R Sedgewick","year":"1986","unstructured":"Sedgewick, R., Vitter, J.S.: Shortest paths in Euclidean graphs. Algorithmica 1(1), 31\u201348 (1986)","journal-title":"Algorithmica"},{"issue":"4","key":"2_CR238","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2530531","volume":"46","author":"C Sommer","year":"2014","unstructured":"Sommer, C.: Shortest-path queries in static networks. ACM Comput. Surv. 46(4), 1\u201331 (2014)","journal-title":"ACM Comput. Surv."},{"key":"2_CR239","doi-asserted-by":"crossref","unstructured":"Storandt, S.: Route planning for bicycles - exact constrained shortest paths made practical via contraction hierarchy. In: Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, pp. 234\u2013242 (2012)","DOI":"10.1609\/icaps.v22i1.13495"},{"key":"2_CR240","unstructured":"Storandt, S., Funke, S.: Cruising with a battery-powered vehicle and not getting stranded. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AAAI Press (2012)"},{"key":"2_CR241","doi-asserted-by":"crossref","unstructured":"Storandt, S., Funke, S.: Enabling e-mobility: facility location for battery loading stations. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press (2013)","DOI":"10.1609\/aaai.v27i1.8478"},{"key":"2_CR242","doi-asserted-by":"crossref","unstructured":"Strasser, B., Wagner, D.: Connection scan accelerated. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX 2014), pp. 125\u2013137. SIAM (2014)","DOI":"10.1137\/1.9781611973198.12"},{"key":"2_CR243","unstructured":"Theune, D.: Robuste und effiziente Methoden zur L\u00f6sung von Wegproblemen. Ph.D. thesis, Universit\u00e4t Paderborn (1995)"},{"key":"2_CR244","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. In: 35th ACM Symposium on Theory of Computing, pp. 149\u2013158. ACM, New York (2003)","DOI":"10.1145\/780542.780566"},{"issue":"6","key":"2_CR245","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"issue":"1","key":"2_CR246","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/s00224-007-9096-4","volume":"45","author":"G Tsaggouris","year":"2009","unstructured":"Tsaggouris, G., Zaroliagis, C.: Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications. Theory Comput. Syst. 45(1), 162\u2013186 (2009)","journal-title":"Theory Comput. Syst."},{"key":"2_CR247","first-page":"170","volume":"88","author":"E Tulp","year":"1988","unstructured":"Tulp, E., Sikl\u00f3ssy, L.: TRAINS, an active time-table searcher. ECAI 88, 170\u2013175 (1988)","journal-title":"ECAI"},{"issue":"3","key":"2_CR248","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1017\/S0890060400002675","volume":"5","author":"E Tulp","year":"1991","unstructured":"Tulp, E., Sikl\u00f3ssy, L.: Searching time-table networks. Artif. Intell. Eng. Des. Anal. Manuf. 5(3), 189\u2013198 (1991)","journal-title":"Artif. Intell. Eng. Des. Anal. Manuf."},{"issue":"1","key":"2_CR249","first-page":"7","volume":"12","author":"D Vliet van","year":"1978","unstructured":"van Vliet, D.: Improved shortest path algorithms for transport networks. Transp. Res. Part B: Methodol. 12(1), 7\u201320 (1978)","journal-title":"Transp. Res. Part B: Methodol."},{"key":"2_CR250","unstructured":"Wagner, D., Willhalm, T.: Drawing graphs to speed up shortest-path computations. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 15\u201324. SIAM (2005)"},{"issue":"1.3","key":"2_CR251","first-page":"1","volume":"10","author":"D Wagner","year":"2005","unstructured":"Wagner, D., Willhalm, T., Zaroliagis, C.: Geometric containers for efficient shortest-path computation. ACM J. Exp. Algorithm. 10(1.3), 1\u201330 (2005)","journal-title":"ACM J. Exp. Algorithm."},{"key":"2_CR252","unstructured":"Weller, M.: Optimal hub labeling is NP-complete. CoRR, abs\/1407.8373 (2014)"},{"issue":"2","key":"2_CR253","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF00940762","volume":"49","author":"DJ White","year":"1986","unstructured":"White, D.J.: Epsilon efficiency. J. Optim. Theory Appl. 49(2), 319\u2013337 (1986)","journal-title":"J. Optim. Theory Appl."},{"issue":"6","key":"2_CR254","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"JWJ Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: heapsort. J. ACM 7(6), 347\u2013348 (1964)","journal-title":"J. ACM"},{"issue":"4","key":"2_CR255","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1020853410145","volume":"6","author":"S Winter","year":"2002","unstructured":"Winter, S.: Modeling costs of turns in route planning. GeoInformatica 6(4), 345\u2013361 (2002)","journal-title":"GeoInformatica"},{"key":"2_CR256","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1007\/978-3-662-48350-3_85","volume-title":"Algorithms - ESA 2015","author":"S Witt","year":"2015","unstructured":"Witt, S.: Trip-based public transit routing. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 1025\u20131036. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48350-3_85"},{"issue":"5","key":"2_CR257","doi-asserted-by":"publisher","first-page":"406","DOI":"10.14778\/2140436.2140438","volume":"5","author":"W Lingkun","year":"2012","unstructured":"Lingkun, W., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. Proc. VLDB Endow. 5(5), 406\u2013417 (2012)","journal-title":"Proc. VLDB Endow."},{"key":"2_CR258","doi-asserted-by":"crossref","unstructured":"Yu, H., Lu, F.: Advanced multi-modal routing approach for pedestrians. In: 2nd International Conference on Consumer Electronics, Communications and Networks, pp. 2349\u20132352 (2012)","DOI":"10.1109\/CECNet.2012.6201641"},{"issue":"4","key":"2_CR259","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1109\/2.53","volume":"21","author":"LA Zadeh","year":"1988","unstructured":"Zadeh, L.A.: Fuzzy logic. IEEE Comput. 21(4), 83\u201393 (1988)","journal-title":"IEEE Comput."},{"key":"2_CR260","doi-asserted-by":"crossref","unstructured":"Zhong, R., Li, G., Tan, K.-L., Zhou, L.: G-tree: an efficient index for KNN search on road networks. In: Proceedings of the 22nd International Conference on Information and Knowledge Management, pp. 39\u201348. ACM Press (2013)","DOI":"10.1145\/2505515.2505749"},{"key":"2_CR261","doi-asserted-by":"crossref","unstructured":"Zhu, A.D., Ma, H., Xiao, X., Luo, S., Tang, Y., Zhou, S.: Shortest path, distance queries on road networks: towards bridging theory and practice. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD 2013), pp. 857\u2013868. ACM Press (2013)","DOI":"10.1145\/2463676.2465277"},{"key":"2_CR262","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-44676-1_3","volume-title":"Algorithms \u2014 ESA 2001","author":"U Zwick","year":"2001","unstructured":"Zwick, U.: Exact and approximate distances in graphs \u2014 a survey. In: Heide, F.M. (ed.) ESA 2001. LNCS, vol. 2161, pp. 33\u201348. Springer, Heidelberg (2001). doi: 10.1007\/3-540-44676-1_3"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-49487-6_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T10:07:45Z","timestamp":1749722865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-49487-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319494869","9783319494876"],"references-count":262,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-49487-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"11 November 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}