Shortest Paths with Shortest Detours | Journal of Optimization Theory and Applications
Skip to main content
Springer Nature Link
Log in

Shortest Paths with Shortest Detours

A Biobjective Routing Problem

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Fig. 1

Similar content being viewed by others

References

  1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993)

    MATH  Google Scholar 

  2. Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem. Series in Discrete Mathematics and Computer Science, vol. 74. American Mathematical Society, Providence (2009)

    Google Scholar 

  3. Martins, E.Q.V.: On a multicriteria shortest path problem. Eur. J. Oper. Res. 16, 236–245 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ehrgott, M.: Multicriteria Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 491, 2nd edn. Springer, Berlin (2005)

    MATH  Google Scholar 

  5. Ulungu, E., Teghem, J.: Multi-objective shortest path problem: a survey. In: Proceedings of the International Workshop on Multicriteria Decision Making: Methods–Algorithms–Applications at Liblice, Czechoslovakia, pp. 176–188 (1991)

  6. Serafini, P.: Some considerations about computational complexity for multi objective combinatorial problems. In: Jahn, J., Krabs, W. (eds.) Recent Advances and Historical Development of Vector Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 294, pp. 222–232. Springer, Berlin (1986)

    Chapter  Google Scholar 

  7. Hansen, P.: Bicriterion path problems. In: Fandel, G., Gal, T. (eds.) Lecture Notes in Economics and Mathematical Systems, vol. 177, pp. 109–127. Springer, Berlin (1980)

    Google Scholar 

  8. Goerigk, M., Schöbel, A.: Algorithm engineering in robust optimization. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering, pp. 245–279. Springer, Cham, Switzerland (2016)

  9. Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Nonconvex Optimization and Its Applications. Springer, Dordrecht (1997)

    Book  MATH  Google Scholar 

  10. Yu, G., Yang, J.: On the robust shortest path problem. Comput. Oper. Res. 25(6), 457–468 (1998)

    Article  MATH  Google Scholar 

  11. Zielinski, P.: The computational complexity of the relative robust shortest path problem with interval data. Eur. J. Oper. Res. 158, 570–576 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Averbakh, I., Lebedev, V.: Interval data minmax regret network optimization problems. Discrete Appl. Math. 138, 289–301 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  13. Nardelli, E., Proietti, G., Widmayer, P.: Finding the detour-critical edge of a shortest path between two nodes. Inf. Process. Lett. 67(1), 51–54 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  14. Xu, Y., Yan, H.: Real time critical edge of the shortest path in transportation networks. In: Cai, J.Y., Cooper, S., Li, A. (eds.) Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 3959, pp. 198–205. Springer, Berlin (2006)

    Chapter  Google Scholar 

  15. Hershberger, J., Suri, S.: Vickrey prices and shortest paths: What is an edge worth? In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, 2001, pp. 252–259. IEEE (2001)

  16. Corley, H., David, Y.S.: Most vital links and nodes in weighted networks. Oper. Res. Lett. 1(4), 157–160 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  17. Nardelli, E., Proietti, G., Widmayer, P.: Finding the most vital node of a shortest path. Theor. Comput. Sci. 296, 167–177 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  18. Malik, K., Mittal, A., Gupta, S.: The \(k\) most vital arcs in the shortest path problem. Oper. Res. Lett. 8(4), 223–227 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  19. Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks 40(2), 97–111 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  20. Rocco, C.M., Ramirez-Marquez, J.E.: A bi-objective approach for shortest-path network interdiction. Comput. Indus. Eng. 59(2), 232–240 (2010)

    Article  Google Scholar 

  21. Liebchen, C., Lübbecke, M., Möhring, R., Stiller, S.: The concept of recoverable robustness, linear programming recovery, and railway applications. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization, vol. 5868. Springer, Berlin (2009)

  22. Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds.) Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 372. Springer, Berlin (1989)

  23. Bar-Noy, A., Schieber, B.: The Canadian traveller problem. In: Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (1991)

  24. Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)

    Article  MathSciNet  Google Scholar 

  25. Pelegrin, B., Fernandez, P.: On the sum-max bicriterion path problem. Comput. Oper. Res. 25(12), 1043–1054 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  26. Gorski, J., Klamroth, K., Ruzika, S.: Generalized multiple objective bottleneck problems. Oper. Res. Lett. 40(4), 276–281 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are partly supported by the German Federal Ministry of Education and Research (BMBF), Reference Number 13N12825.

Author information

Authors and Affiliations

  1. Mathematisches Institut, Universität Koblenz-Landau, Universitätsstraße 1, 56070, Koblenz, Germany

    Carolin Torchiani, Jan Ohst, David Willems & Stefan Ruzika

Authors
  1. Carolin Torchiani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Ohst
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Willems
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Stefan Ruzika
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carolin Torchiani.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Torchiani, C., Ohst, J., Willems, D. et al. Shortest Paths with Shortest Detours. J Optim Theory Appl 174, 858–874 (2017). https://doi.org/10.1007/s10957-017-1145-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-017-1145-9

Keywords

Mathematics Subject Classification

Search

Navigation