Document Open Access Logo

Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks

Authors Matúš Mihalák, Sandro Montanari

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2015.82.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Matúš Mihalák
Sandro Montanari

Cite As Get BibTex

Matúš Mihalák and Sandro Montanari. Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 82-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/OASIcs.ATMOS.2015.82

Abstract

Based on time-dependent travel times for N past days, we consider the computation of robust routes according to the min-max relative regret criterion. For this method we seek a path minimizing its maximum weight in any one of the N days, normalized by the weight of an optimum for the respective day. In order to speed-up this computationally demanding approach, we observe that its output belongs to the Pareto front of the network with time-dependent
multi-criteria edge weights. We adapt a well-known algorithm for computing Pareto fronts in time-dependent graphs and apply the bi-directional search technique to it. We also show how to parametrize this algorithm by a value K to compute a K-approximate Pareto front. An experimental evaluation for the cases N = 2 and N = 3 indicates a considerable speed-up of the bi-directional search over the uni-directional.

Subject Classification

Keywords
  • shortest path
  • time-dependent
  • bi-criteria
  • bi-directional search
  • min-max relative regret

Metrics

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

References

  1. H. Aissi, C. Bazgan, and D. Vanderpooten. Min-max and min-max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research, 197(2):427-438, 2009. Google Scholar
  2. G. V. Batz, R. Geisberger, P. Sanders, and C. Vetter. Minimum time-dependent travel times with contraction hierarchies. ACM Journal of Experimental Algorithmics, 18, 2013. Google Scholar
  3. G. V. Batz and P. Sanders. Time-dependent route planning with generalized objective functions. In ESA, pages 169-180, 2012. Google Scholar
  4. J. M. Buhmann, M. Mihalák, R. Šrámek, and P. Widmayer. Robust optimization in the presence of uncertainty. In ITCS, pages 505-514, 2013. Google Scholar
  5. European Commission. eCOMPASS Project. http://www.ecompass-project.eu/, 2011-2014.
  6. C. Daskalakis, I. Diakonikolas, and M. Yannakakis. How good is the chord algorithm? CoRR, abs/1309.7084, 2013. Google Scholar
  7. D. Delling. Time-dependent SHARC-routing. Algorithmica, 60(1):60-94, 2011. Google Scholar
  8. D. Delling and D. Wagner. Pareto paths with SHARC. In SEA, pages 125-136, 2009. Google Scholar
  9. S. Demeyer, J. Goedgebeur, P. Audenaert, M. Pickavet, and P. Demeester. Speeding up Martins' algorithm for multiple objective shortest path problems. 4OR, 11(4):323-348, 2013. Google Scholar
  10. S. Erb, M. Kobitzsch, and P. Sanders. Parallel bi-objective shortest paths using weight-balanced B-trees with bulk updates. In SEA, pages 111-122, 2014. Google Scholar
  11. L. Foschini, J. Hershberger, and S. Suri. On the complexity of time-dependent shortest paths. Algorithmica, 68(4):1075-1097, 2014. Google Scholar
  12. S. Funke and S. Storandt. Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In ALENEX, pages 41-54, 2013. Google Scholar
  13. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  14. R. Geisberger, M. Kobitzsch, and P. Sanders. Route planning with flexible objective functions. In ALENEX, pages 124-137, 2010. Google Scholar
  15. A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In SODA, pages 156-165, 2005. Google Scholar
  16. A. V. Goldberg and R. F. Werneck. Computing point-to-point shortest paths from external memory. In ALENEX, pages 26-40, 2005. Google Scholar
  17. T. Gräbener, A. Berro, and Y. Duthen. Time dependent multiobjective best path for multimodal urban routing. Electronic Notes in Discrete Mathematics, 36, 2010. Google Scholar
  18. H. W. Hamacher, S. Ruzika, and S. A. Tjandra. Algorithms for time-dependent bicriteria shortest path problems. Discrete Optimization, 3(3):238-254, 2006. Google Scholar
  19. P. Hansen. Bicriterion path problems. In Multiple Criteria Decision Making Theory and Application, pages 109-127. Springer Berlin Heidelberg, 1980. Google Scholar
  20. J. Hershberger, M. Maxel, and S. Suri. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 2007. Google Scholar
  21. S. C. Kontogiannis and C. D. Zaroliagis. Distance oracles for time-dependent networks. In ICALP 2014, pages 713-725, 2014. Google Scholar
  22. P. Kouvelis and G. Yu. Robust discrete optimization and its applications, volume 14. Springer Science &Business Media, 2013. Google Scholar
  23. E. Q. V. Martins. On a multicriteria shortest path problem. European Journal of Operational Research, 16(2):236-245, 1984. Google Scholar
  24. G. Nannicini, D. Delling, D. Schultes, and L. Liberti. Bidirectional A* search on time-dependent road networks. Networks, 59(2):240-251, 2012. Google Scholar
  25. G. Yu and J. Yang. On the robust shortest path problem. Computers & OR, 25(6):457-468, 1998. 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