{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:29Z","timestamp":1750307189176,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2012,3,30]],"date-time":"2012-03-30T00:00:00Z","timestamp":1333065600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0705916IIS-0803410"],"award-info":[{"award-number":["IIS-0705916IIS-0803410"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>In this work, we explore a new type of flexible shortest-path query, in which the query can be dynamically parameterized to constrain the type of edges that may be included in the resulting shortest path (e.g., find the shortest path in a road network that avoids toll roads and low overpasses, respective of the specified vehicle height). We extend the hierarchical preprocessing technique known as Contraction Hierarchies to efficiently support such flexible queries. We also present several effective algorithmic optimizations for further improving the overall scalability and query times of this approach, including the addition of goal-directed search techniques, search space pruning techniques, and generalizing the constraints of the local search. Experiments are presented for both the North American and the European road networks, showcasing the general effectiveness and scalability of our proposed methodology to large-scale, real-world graphs.<\/jats:p>","DOI":"10.1145\/2133803.2133805","type":"journal-article","created":{"date-parts":[[2012,3,27]],"date-time":"2012-03-27T15:17:31Z","timestamp":1332861451000},"source":"Crossref","is-referenced-by-count":12,"title":["Route planning with flexible edge restrictions"],"prefix":"10.1145","volume":"17","author":[{"given":"Robert","family":"Geisberger","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT)"}]},{"given":"Michael N.","family":"Rice","sequence":"additional","affiliation":[{"name":"University of California, Riverside (UCR)"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT)"}]},{"given":"Vassilis J.","family":"Tsotras","sequence":"additional","affiliation":[{"name":"University of California, Riverside (UCR)"}]}],"member":"320","published-online":{"date-parts":[[2012,3,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"volume":"4525","volume-title":"Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Delling D.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768570"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"volume-title":"Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10)","author":"Geisberger R.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Geisberger R. Sanders P. Schultes D. and \n      \n      \n      Delling D\n      \n  \n  . \n  2008\n  . Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08). C. C. McGeoch Ed. Lecture Notes in Computer Science vol. \n  5038 Springer Berlin 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 Workshop on Experimental Algorithms (WEA'08). C. C. McGeoch Ed. Lecture Notes in Computer Science vol. 5038 Springer Berlin 319--333.","DOI":"10.1007\/978-3-540-68552-4_24"},{"volume-title":"Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'05)","author":"Goldberg A. V.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05)","author":"Goldberg A. V.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"volume":"74","volume-title":"DIMACS Book","author":"Hilger M.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412239"},{"volume-title":"Geoinformation und Mobilit\u00e4t\u2014von der Forschung zur praktischen Anwendung.","author":"Lauther U.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921074"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"volume":"4525","volume-title":"Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Schultes D.","key":"e_1_2_1_16_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2133805","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133803.2133805","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:05:52Z","timestamp":1750241152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2133805"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,30]]},"references-count":16,"alternative-id":["10.1145\/2133803.2133805"],"URL":"https:\/\/doi.org\/10.1145\/2133803.2133805","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2012,3,30]]}}}