Document Open Access Logo

Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Authors Stefan Funke, Sören Laue, Sabine Storandt

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.18.pdf
  • Filesize: 471 kB
  • 13 pages

Document Identifiers

Author Details

Stefan Funke
Sören Laue
Sabine Storandt

Cite As Get BibTex

Stefan Funke, Sören Laue, and Sabine Storandt. Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SEA.2017.18

Abstract

In a personalized route planning query, a user can specify how relevant different criteria as travel time, gas consumption, scenicness, etc. are for his individual definition of an optimal route. Recently developed acceleration schemes for personalized route planning, which rely on preprocessing, achieve a significant speed-up over the Dijkstra baseline for a small number of criteria. But for more than five criteria, either the preprocessing becomes too complicated or the query answering is slow. In this paper, we first present a new LP-based preprocessing technique which allows to deal with many criteria efficiently. In addition, we show how to further reduce query times for all known personalized route planning acceleration schemes by considering approximate queries. We design a data structure which allows not only to have personalized costs but also individual approximation guarantees per query, allowing to trade solution quality against query time at the user's discretion. This data structure is the first to enable a speed-up of more than 100 for ten criteria while accepting only 0.01% increased costs.

Subject Classification

Keywords
  • personalized route planning
  • contraction hierarchies
  • linear program
  • separation oracle
  • approximate queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result diversity for multi-modal route planning. In ATMOS-13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, volume 33, pages 123-136, 2013. Google Scholar
  2. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck. Computing multimodal journeys in practice. In Proc. 12th International Symposium on Experimental Algorithms (SEA), pages 260-271. Springer, 2013. Google Scholar
  3. Daniel Delling, Andrew V. Goldberg, Moises Goldszmidt, John Krumm, Kunal Talwar, and Renato F. Werneck. Navigation made personal: Inferring driving preferences from GPS traces. In Proc. 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 31. ACM, 2015. Google Scholar
  4. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning. In Proc. 10th International Symposium on Experimental Algorithms (SEA), pages 376-387. Springer, 2011. Google Scholar
  5. Daniel Delling, Moritz Kobitzsch, and Renato F. Werneck. Customizing driving directions with GPUs. In Proc. 20th European Conference on Parallel Processing (EuroPar), pages 728-739. Springer, 2014. Google Scholar
  6. Daniel Delling and Renato F. Werneck. Faster customization of road networks. In Proc. 12th Int. Symposium on Experimental Algorithms (SEA), volume 13, pages 30-42. Springer, 2013. Google Scholar
  7. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. In Proc. 13th Int. Symposium on Experimental Algorithms (SEA), pages 271-282, 2014. Google Scholar
  8. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Fast exact shortest path and distance queries on road networks with parametrized costs. In Proc. 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 66. ACM, 2015. Google Scholar
  9. Stefan Funke, Sören Laue, and Sabine Storandt. Deducing individual driving preferences for user-aware navigation. In Proc. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 14. ACM, 2016. Google Scholar
  10. Stefan Funke, André Nusser, and Sabine Storandt. On k-path covers and their applications. Proceedings of the VLDB Endowment, 7(10), 2014. Google Scholar
  11. Stefan Funke and Sabine Storandt. Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In Proc. 15th Meeting on Algorithm Engineering and Experiments, ALENEX 2013, pages 41-54, 2013. Google Scholar
  12. Stefan Funke and Sabine Storandt. Personalized route planning in road networks. In Proc. 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 45. ACM, 2015. Google Scholar
  13. Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. Route planning with flexible objective functions. In Proc. 12th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 124-137, 2010. Google Scholar
  14. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388-404, 2012. Google Scholar
  15. Andrew V. Goldberg and Chris Harrelson. Computing the shortest path: A search meets graph theory. In Proc. 16th Annual ACM-SIAM Symposium on Discrete algorithms, SODA'05, pages 156-165, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. Google Scholar
  16. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. Google Scholar
  17. Raimund Seidel. Linear programming and convex hulls made easy. In Proc. 6th Ann. Symp. on Computational Geometry (SCG), pages 211-215, New York, NY, USA, 1990. ACM. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact