Document Open Access Logo

Time-Dependent Alternative Route Planning

Authors Spyros Kontogiannis, Andreas Paraskevopoulos, Christos D. Zaroliagis

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.8.pdf
  • Filesize: 1.14 MB
  • 14 pages

Document Identifiers

Author Details

Spyros Kontogiannis
  • Department of Computer Science & Engineering, University of Ioannina, Greece
  • Computer Technology Institute & Press "Diophantus", Patras, Greece
Andreas Paraskevopoulos
  • Department of Computer Engineering & Informatics, University of Patras, Greece
Christos D. Zaroliagis
  • Department of Computer Engineering & Informatics, University of Patras, Greece
  • Computer Technology Institute & Press "Diophantus", Patras, Greece

Funding

This research was supported by the Operational Program Competitiveness, Entrepreneurship and Innovation (call Research-Create-Innovate, co-financed by EU and Greek national funds), under contract no. T1EDK-03616 (project SocialPARK).

Cite AsGet BibTex

Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis. Time-Dependent Alternative Route Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.8

Abstract

We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches. In particular, the entire alternative graph can be computed in less than 0.384sec for the road network of Germany, and in less than 1.24sec for that of Europe. Our approach provides also "quick-and-dirty" results of decent quality, in about 1/300 of the above mentioned query times for continental-size instances.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Combinatorial algorithms
Keywords
  • time-dependent shortest path
  • alternative routes
  • travel-time oracle
  • plateau and penalty methods

Metrics

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

References

  1. Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck. Alternative routes in road networks. In Experimental Algorithms, volume 6049 of LNCS, pages 23-34. Springer, 2010. Google Scholar
  2. Roland Bader, Jonathan Dees, Robert Geisberger, and Peter Sanders. Alternative route graphs in road networks. In Theory and Practice of Algorithms in (Computer) Systems, volume 6595 of LNCS, pages 21-32. Springer, 2011. Google Scholar
  3. G Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. Minimum time-dependent travel times with contraction hierarchies. ACM Journal of Experimental Algorithmics, 18(1.4):1-43, 2013. Google Scholar
  4. Camvit: Choice routing, 2009. URL: http://www.camvit.com.
  5. Yanyan Chen, Michael GH Bell, and Klaus Bogenberger. Reliable pretrip multipath planning and dynamic adaptation for a centralized road navigation system. IEEE Transactions on Intelligent Transportation Systems, 8(1):14-20, 2007. Google Scholar
  6. Daniel Delling and Dorothea Wagner. Pareto paths with sharc. In Experimental Algorithms, volume 5526 of LNCS, pages 125-136. Springer, 2009. Google Scholar
  7. James Doran. An approach to automatic problem-solving. Machine Intelligence, 1:105-127, 1967. Google Scholar
  8. Stuart E Dreyfus. An appraisal of some shortest-path algorithms. Operations Research, 17(3):395-412, 1969. Google Scholar
  9. eCOMPASS project, 2011-2014. URL: http://www.ecompass-project.eu.
  10. David Eppstein. Finding the k-shortest paths. SIAM Journal on Computing, 28(2):652-673, 1998. Google Scholar
  11. Pierre Hansen. Bicriterion path problems. In Multiple criteria decision making theory and application, pages 109-127. Springer, 1980. Google Scholar
  12. Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968. Google Scholar
  13. Moritz Kobitzsch. An alternative approach to alternative routes: Hidar. In Algorithms, volume 8125 of LNCS, pages 613-624. Springer, 2013. Google Scholar
  14. Felix Koenig. Future challenges in real-life routing. In Workshop on New Prospects in Car Navigation, February 2012. Google Scholar
  15. Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved oracles for time-dependent road networks. In Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, volume 59 of OASIcs, pages 4:1-4:17. Dagstuhl Publishing, 2017. Google Scholar
  16. Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis. Hierarchical time-dependent oracles. In Algorithms and Computation, volume 64 of LIPIcs, pages 47:1-47:13. Dagstuhl Publishing, 2016. Google Scholar
  17. Spyros Kontogiannis and Christos Zaroliagis. Distance oracles for time-dependent networks. Algorithmica, 74(4):1404-1434, 2016. Google Scholar
  18. Dennis Luxen and Dennis Schieferdecker. Candidate sets for alternative routes in road networks. In Experimental Algorithms, volume 7276 of LNCS, pages 260-270. Springer, 2012. Google Scholar
  19. Georgia Mali, Panagiotis Michail, Andreas Paraskevopoulos, and Christos Zaroliagis. A new dynamic graph structure for large-scale transportation networks. In Algorithms and Complexity, volume 7878 of LNCS, pages 312-323. Springer, 2013. Google Scholar
  20. Ernesto Queiros Vieira Martins. On a multicriteria shortest path problem. European Journal of Operational Research, 16(2):236-245, 1984. Google Scholar
  21. Andreas Paraskevopoulos and Christos Zaroliagis. Improved Alternative Route Planning. In Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, volume 33 of OASIcs, pages 108-122. Dagstuhl Publishing, 2013. Google Scholar
  22. Peter Sanders. Fast priority queues for cached memory. ACM Journal of Experimental Algorithmics, 5:1-25, 2000. Google Scholar
  23. Jin Y Yen. Finding the k shortest loopless paths in a network. Management Science, 17(11):712-716, 1971. 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 Imprint Privacy Contact