Fast Robust Shortest Path Computations

Authors Christoph Hansknecht, Alexander Richter, Sebastian Stiller



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.5.pdf
  • Filesize: 0.53 MB
  • 21 pages

Document Identifiers

Author Details

Christoph Hansknecht
  • Institute for Mathematical Optimization, Technical University Braunschweig, Germany
Alexander Richter
  • Institute for Mathematical Optimization, Technical University Braunschweig, Germany
Sebastian Stiller
  • Institute for Mathematical Optimization, Technical University Braunschweig, Germany

Cite AsGet BibTex

Christoph Hansknecht, Alexander Richter, and Sebastian Stiller. Fast Robust Shortest Path Computations. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.ATMOS.2018.5

Abstract

We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an s-t-graph D(V,A) and for each arc a nominal length c(a) and a maximal increase d(a) of its length. We consider all scenarios in which for the increased lengths c(a) + bar{d}(a) we have bar{d}(a) <= d(a) and sum_{a in A} (bar{d}(a)/d(a)) <= Gamma. Each path is measured by the length in its worst-case scenario. A classic result [Bertsimas and Sim, 2003] minimizes this path length by solving (|A| + 1)-many shortest path problems. Easily, (|A| + 1) can be replaced by |Theta|, where Theta is the set of all different values d(a) and 0. Still, the approach remains impractical for large graphs. Using the monotonicity of a part of the objective we devise a Divide and Conquer method to evaluate significantly fewer values of Theta. This methods generalizes to binary linear robust problems. Specifically for shortest paths we derive a lower bound to speed-up the Divide and Conquer of Theta. The bound is based on carefully using previous shortest path computations. We combine the approach with non-preprocessing based acceleration techniques for Dijkstra adapted to the robust case. In a computational study we document the value of different accelerations tried in the algorithm engineering process. We also give an approximation scheme for the robust shortest path problem which computes a (1 + epsilon)-approximate solution requiring O(log(d^ / (1 + epsilon))) computations of the nominal problem where d^ := max d(A) / min (d(A)\{0}).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph Algorithms
  • Shortest Paths
  • Robust Optimization

Metrics

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

References

  1. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 782-793. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  2. Rachit Agarwal, Matthew Caesar, Brighten Godfrey, and Ben Y. Zhao. Shortest paths in less than a millisecond. CoRR, abs/1206.1134, 2012. URL: http://dx.doi.org/10.1145/2342549.2342559.
  3. Alper Atamtürk and Muhong Zhang. Two-stage robust network flow and design under demand uncertainty. Oper. Res., 55(4):662-673, 2007. URL: http://dx.doi.org/10.1287/opre.1070.0428.
  4. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks, pages 19-80. Springer International Publishing, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49487-6_2.
  5. Dimitris Bertsimas, David B. Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM Review, 53(3):464-501, 2011. URL: http://dx.doi.org/10.1137/080734510.
  6. Dimitris Bertsimas and Melvyn Sim. Robust discrete optimization and network flows. Mathematical Programming, 98(1):49-71, 2003. URL: http://dx.doi.org/10.1007/s10107-003-0396-4.
  7. Christina Büsing. The exact subgraph recoverable robust shortest path problem. In Ravindra K. Ahuja, Rolf H. Möhring, and Christos Zaroliagis, editors, Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems, pages 231-248. Springer Berlin Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-642-05465-5_9.
  8. Christina Büsing. Recoverable robust shortest path problems. Networks, 59(1):181-189, 2012. URL: http://dx.doi.org/10.1002/net.20487.
  9. Atish Das Sarma, Sreenivas Gollapudi, Marc Najork, and Rina Panigrahy. A sketch-based distance oracle for web-scale graphs. In Proceedings of the Third ACM International Conference on Web Search and Data Mining, WSDM '10, pages 401-410. ACM, 2010. URL: http://dx.doi.org/10.1145/1718487.1718537.
  10. Daniel Delling and Dorothea Wagner. Time-dependent route planning. Robust and online large-scale optimization, 5868(1):207-230, 2009. URL: http://dx.doi.org/10.1007/978-3-319-17885-1_101392.
  11. Maged M Dessouky, Fernando Ordonez, and Ilgaz Sungur. A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Transactions, 40(5):509-523, 2008. URL: http://dx.doi.org/10.1080/07408170701745378.
  12. Maciej Drwal. Complexity of scheduling on parallel identical machines to minimize total flow time with interval data and minmax regret criterion. CoRR, abs/1412.4273, 2014. URL: http://arxiv.org/abs/1412.4273.
  13. Virginie Gabrel, Cécile Murat, and Aurélie Thiele. Recent advances in robust optimization: An overview. European Journal of Operational Research, 235(3):471-483, 2014. URL: http://dx.doi.org/10.1016/j.ejor.2013.09.036.
  14. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Catherine C. McGeoch, editor, Experimental Algorithms: 7th International Workshop, WEA 2008 Provincetown, MA, USA, May 30-June 1, 2008 Proceedings, pages 319-333. Springer Berlin Heidelberg, 2008. URL: http://dx.doi.org/10.1007/978-3-540-68552-4_24.
  15. Andrew V. Goldberg and Chris Harrelson. Computing the shortest path: A search meets graph theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pages 156-165. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  16. Andrey Gubichev, Srikanta Bedathur, Stephan Seufert, and Gerhard Weikum. Fast and accurate estimation of shortest paths in large graphs. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM '10, pages 499-508. ACM, 2010. URL: http://dx.doi.org/10.1145/1871437.1871503.
  17. 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, SSC-4(2):100-107, 1968. URL: http://dx.doi.org/10.1109/tssc.1968.300136.
  18. Moritz Hilger, Ekkehard Köhler, Rolf H. Möhring, and Heiko Schilling. Fast point-to-point shortest path computations with arc-flags. In The Shortest Path Problem, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 13-14, 2006, pages 41-72, 2006. URL: http://dx.doi.org/10.1090/dimacs/074/03.
  19. Changhyun Kwon, Taehan Lee, and Paul Berglund. Robust shortest path problems with two uncertain multiplicative cost coefficients. Naval Research Logistics (NRL), 60(5):375-394, 2013. URL: http://dx.doi.org/10.1002/nav.21540.
  20. Supakom Mudchanatongsuk, Fernando Ordóñez, and Jie Liu. Robust solutions for network design under transportation cost and demand uncertainty. Journal of the Operational Research Society, 59(5):652-662, 2008. URL: http://dx.doi.org/10.1057/palgrave.jors.2602362.
  21. Michael Poss. Robust combinatorial optimization with variable cost uncertainty. European Journal of Operational Research, 237:836-845, 2014. URL: http://dx.doi.org/10.1016/j.ejor.2014.02.060.
  22. Muhong Zhang. Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty. Operations Research Letters, 39(5):342-345, 2011. URL: http://dx.doi.org/10.1016/j.orl.2011.06.013.
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