{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T12:21:14Z","timestamp":1776946874992,"version":"3.51.4"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally define the problem of finding alternative routes with a single via vertex, develop efficient algorithms for it, and evaluate them experimentally. Our algorithms are efficient enough for practical use and compare favorably with previous methods in both speed and solution quality.<\/jats:p>","DOI":"10.1145\/2444016.2444019","type":"journal-article","created":{"date-parts":[[2013,5,7]],"date-time":"2013-05-07T20:51:42Z","timestamp":1367959902000},"source":"Crossref","is-referenced-by-count":58,"title":["Alternative routes in road networks"],"prefix":"10.1145","volume":"18","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"Microsoft Research, Silicon Valley, Mountain View"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Delling","sequence":"additional","affiliation":[{"name":"Microsoft Research, Silicon Valley, Mountain View"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"Microsoft Research, Silicon Valley, Mountain View"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[{"name":"Microsoft Research, Silicon Valley, Mountain View"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_3"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'10)","author":"Abraham I.","unstructured":"Abraham , I. , Fiat , A. , Goldberg , A. V. , and Werneck , R. F . 2010b. Highway dimension, shortest paths, and provably efficient algorithms . In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'10) . 782--793. Abraham, I., Fiat, A., Goldberg, A. V., and Werneck, R. F. 2010b. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'10). 782--793."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS'11)","author":"Bader R.","unstructured":"Bader , R. , Dees , J. , Geisberger , R. , and Sanders , P . 2011. Alternative route graphs in road networks . In Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS'11) . Springer, 21--32. Bader, R., Dees, J., Geisberger, R., and Sanders, P. 2011. Alternative route graphs in road networks. In Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS'11). Springer, 21--32."},{"key":"e_1_2_1_4_1","unstructured":"Cambridge Vehicle Information Technology Ltd. 2005. Choice routing. http:\/\/www.camvit.com.  Cambridge Vehicle Information Technology Ltd. 2005. Choice routing. http:\/\/www.camvit.com."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2006.889437"},{"key":"e_1_2_1_6_1","volume-title":"Linear Programming and Extensions","author":"Dantzig G. B.","unstructured":"Dantzig , G. B. 1962. Linear Programming and Extensions . Princeton University Press , Princeton, NJ . Dantzig, G. B. 1962. Linear Programming and Extensions. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_13"},{"key":"e_1_2_1_9_1","volume-title":"Eds","author":"Demetrescu C.","year":"2006","unstructured":"Demetrescu , C. , Goldberg , A. V. , and Johnson , D. S. , Eds . 2006 . Proceedings of the DIMACS Implementation Challenge: Shortest Paths . Demetrescu, C., Goldberg, A. V., and Johnson, D. S., Eds. 2006. Proceedings of the DIMACS Implementation Challenge: Shortest Paths."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365697"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10)","author":"Geisberger R.","unstructured":"Geisberger , R. , Kobitzsch , M. , and Sanders , P . 2010. Route planning with flexible objective functions . In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10) . SIAM, 124--137. Geisberger, R., Kobitzsch, M., and Sanders, P. 2010. Route planning with flexible objective functions. In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10). SIAM, 124--137."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 7th International Conference on Experimental Algorithms (WEA'08)","author":"Geisberger R.","unstructured":"Geisberger , R. , Sanders , P. , Schultes , D. , and Delling , D . 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks . In Proceedings of the 7th International Conference on Experimental Algorithms (WEA'08) . Springer, 319--333. Geisberger, R., Sanders, P., Schultes, D., and Delling, D. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th International Conference on Experimental Algorithms (WEA'08). Springer, 319--333."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Goldberg A. V. Kaplan H. and Werneck R. F. 2009. Reach for A&ast;: Shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge C. Demetrescu A. V. Goldberg and D. S. Johnson Eds. American Mathematical Society 93--139.  Goldberg A. V. Kaplan H. and Werneck R. F. 2009. Reach for A&ast;: Shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge C. Demetrescu A. V. Goldberg and D. S. Johnson Eds. American Mathematical Society 93--139.","DOI":"10.1090\/dimacs\/074\/05"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04)","author":"Gutman R. J.","year":"2004","unstructured":"Gutman , R. J. 2004 . 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'04) . SIAM, 100--111. Gutman, R. J. 2004. 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'04). SIAM, 100--111."},{"key":"e_1_2_1_16_1","volume-title":"Multiple Criteria Decision Making: Theory and Application","author":"Hansen P.","unstructured":"Hansen , P. 1979. Bricriteria path problems . In Multiple Criteria Decision Making: Theory and Application , G. Fandel and T. Gal, Eds., Springer , 109--127. Hansen, P. 1979. Bricriteria path problems. In Multiple Criteria Decision Making: Theory and Application, G. Fandel and T. Gal, Eds., Springer, 109--127."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90077-8"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Schultes D.","unstructured":"Schultes , D. and Sanders , P . 2007. Dynamic highway-node routing . In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07) . Springer, 66--79. Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, 66--79."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444019","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2444016.2444019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:57Z","timestamp":1750236537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":18,"alternative-id":["10.1145\/2444016.2444019"],"URL":"https:\/\/doi.org\/10.1145\/2444016.2444019","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,19]]}}}