{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:10:14Z","timestamp":1758273014595,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T00:00:00Z","timestamp":1420588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Research Foundation (DFG) within the Research Training Group GRK 1194 \u201cSelf-organizing Sensor-Actuator-Networks\u201d"},{"name":"DFG","award":["SA 933\/5-1"],"award-info":[{"award-number":["SA 933\/5-1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We present a fast preprocessing method for computing multiple good alternatives and apply this result in an online setting. This setting makes our result applicable in legacy systems with negligible memory overhead. An extensive experimental analysis on a continental-sized real- world road network proves the performance of our algorithm and supports the general systematic algorithm engineering approach. We also show how to combine our results with the competing concept of alternative graphs that encode many alternative paths at once.<\/jats:p>","DOI":"10.1145\/2674395","type":"journal-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:02:10Z","timestamp":1421092930000},"page":"1-28","source":"Crossref","is-referenced-by-count":3,"title":["Candidate Sets for Alternative Routes in Road Networks"],"prefix":"10.1145","volume":"19","author":[{"given":"Dennis","family":"Luxen","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]},{"given":"Dennis","family":"Schieferdecker","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Ittai Abraham Daniel Delling Amos Fiat Andrew V. Goldberg and Renato F. Werneck. 2011a. VC-Dimension and Shortest Path Algorithms. In International Colloquium on Automata Languages and Programming (ICALP\u201911).   Ittai Abraham Daniel Delling Amos Fiat Andrew V. Goldberg and Renato F. Werneck. 2011a. VC-Dimension and Shortest Path Algorithms. In International Colloquium on Automata Languages and Programming (ICALP\u201911).","DOI":"10.1007\/978-3-642-22006-7_58"},{"volume-title":"International Symposium on Experimental Algorithms (SEA\u201911)","author":"Abraham Ittai","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2444016.2444019"},{"volume-title":"ACM--SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Abraham Ittai","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Roland Bader Jonathan Dees Robert Geisberger and Peter Sanders. 2011. Alternative Route Graphs in Road Networks. In Theory and Practice of Algorithms in (Computer) Systems (TAPAS\u201911).   Roland Bader Jonathan Dees Robert Geisberger and Peter Sanders. 2011. Alternative Route Graphs in Road Networks. In Theory and Practice of Algorithms in (Computer) Systems (TAPAS\u201911).","DOI":"10.1007\/978-3-642-19754-3_5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1137521"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34862-4_7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2444016.2444020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_11_1","unstructured":"Cambridge Vehicle Information Tech. Ltd. 2005. Choice Routing. Retrieved from http:\/\/camvit.com.  Cambridge Vehicle Information Tech. Ltd. 2005. Choice Routing. Retrieved from http:\/\/camvit.com."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2006.889437"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_13"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.02.007"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.108"},{"volume-title":"Robust Mobile Route Planning with Limited Connectivity. In Meeting on Algorithm Engineering and Experiments (ALENEX\u201912)","author":"Delling Daniel","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_13"},{"key":"e_1_2_1_19_1","unstructured":"Camil Demetrescu Andrew V. Goldberg and David S. Johnson (Eds.). 2006. The 9th DIMACS Implementation Challenge\u2014Shortest Paths. American Mathematical Society.  Camil Demetrescu Andrew V. Goldberg and David S. Johnson (Eds.). 2006. The 9th DIMACS Implementation Challenge\u2014Shortest Paths. American Mathematical Society."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"volume-title":"Route Planning with Flexible Objective Functions. In Workshop on Algorithm Engineering and Experiments (ALENEX\u201910)","year":"2010","author":"Geisberger Robert","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"volume-title":"ACM--SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Andrew","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Andrew V. Goldberg Haim Kaplan and Renato F. Werneck. 2009. Reach for A&ast;: Shortest Path Algorithms with Preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge Camil Demetrescu Andrew V. Goldberg and David S. Johnson (Eds.). DIMACS Book Vol. 74. American Mathematical Society 93--139.  Andrew V. Goldberg Haim Kaplan and Renato F. Werneck. 2009. Reach for A&ast;: Shortest Path Algorithms with Preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge Camil Demetrescu Andrew V. Goldberg and David S. Johnson (Eds.). DIMACS Book Vol. 74. American Mathematical Society 93--139.","DOI":"10.1090\/dimacs\/074\/05"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"P. Hansen. 1980. Bicriterion Path Problems. In Multiple Criteria Decision Making: Theory and Applications.  P. Hansen. 1980. Bicriterion Path Problems. In Multiple Criteria Decision Making: Theory and Applications.","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_28_1","volume-title":"DIMACS Book","volume":"74","author":"Hilger Moritz","year":"2009"},{"volume-title":"Computing Many-to-Many Shortest Paths Using Highway Hierarchies. In Workshop on Algorithm Engineering and Experiments (Alenex\u201907)","year":"2007","author":"Knopp Sebastian","key":"e_1_2_1_29_1"},{"volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V","author":"Lauther Ulrich","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_23"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90077-8"},{"volume-title":"SCOTCH: A Software Package for Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs. In High-Performance Computing and Networking (LNCS)","year":"1996","author":"Pellegrini Francois","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(70)90007-X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2133803.2330080"},{"key":"e_1_2_1_36_1","volume-title":"Engineering Multilevel Graph Partitioning Algorithms. In European Symposium on Algorithms (ESA\u201911)","volume":"6942","author":"Sanders Peter","year":"2011"},{"key":"e_1_2_1_37_1","unstructured":"Dominik Schultes. 2008. Route Planning in Road Networks. Ph.D. Dissertation. Universit\u00e4t Karlsruhe. Retrieved from http:\/\/algo2.iti.uka.de\/schultes\/hwy\/schultes_diss.pdf.  Dominik Schultes. 2008. Route Planning in Road Networks. Ph.D. Dissertation. Universit\u00e4t Karlsruhe. Retrieved from http:\/\/algo2.iti.uka.de\/schultes\/hwy\/schultes_diss.pdf."},{"key":"e_1_2_1_38_1","volume-title":"Dynamic Highway-Node Routing. In Workshop on Experimental Algorithms (WEA\u201907)","volume":"4525","author":"Schultes Dominik","year":"2007"},{"key":"e_1_2_1_39_1","unstructured":"Christian Vetter. 2009. Parallel Time-Dependent Contraction Hierarchies. Student Research Project. Retrieved from http:\/\/algo2.iti.kit.edu\/download\/vetter_sa.pdf.  Christian Vetter. 2009. Parallel Time-Dependent Contraction Hierarchies. Student Research Project. Retrieved from http:\/\/algo2.iti.kit.edu\/download\/vetter_sa.pdf."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2674395","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2674395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:55:48Z","timestamp":1750229748000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2674395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":40,"alternative-id":["10.1145\/2674395"],"URL":"https:\/\/doi.org\/10.1145\/2674395","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}