Bi-criteria path problem with minimum length and maximum survival probability | OR Spectrum Skip to main content
Springer Nature Link
Log in

Bi-criteria path problem with minimum length and maximum survival probability

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

We study a bi-criteria path problem on a directed multigraph with cycles, where each arc is associated with two parameters. The first is the survival probability of moving along the arc, and the second is the length of the arc. We evaluate the quality of a path by two independent criteria. The first is to maximize the survival probability along the entire path, which is the product of the arc probabilities, and the second is to minimize the total path length, which is the sum of the arc lengths. We prove that the problem of finding a path which satisfies two bounds, one for each criterion, is NP-complete, even in the acyclic case. We further develop approximation algorithms for the optimization versions of the studied problem. One algorithm is based on approximate computing of logarithms of arc probabilities, and the other two are fully polynomial time approximation schemes (FPTASes). One FPTAS is based on scaling and rounding of the input, while the other FPTAS is derived via the method of K-approximation sets and functions, introduced by Halman et al. (Math Oper Res 34:674–685, 2009).

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aneja YP, Aggarwal V, Nair KPK (1983) Shortest chain subject to side constraints. Nav Res Logist Quart 13:295–302

    Google Scholar 

  • Aneja YP, Nair KPK (1978) The constrained shortest path problem. Nav Res Logist Quart 25:549–555

    Google Scholar 

  • Bellman R (1958) On a routing problem. Quart Appl Math 16:87–90

    Google Scholar 

  • Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper Res Lett 34:58–68

    Google Scholar 

  • Bökler F (2017) The multiobjective shortest path problem is NP-hard, or is it, EMO 2017. Lect Notes Comput Sci 10173:77–87

  • Brent RP (2010) Multiple-precision zero-finding methods and the complexity of elementary function evaluation. arXiv:1004.3412v2 [cs.NA] 30 May

  • Breugem T, Dollevoet T, van den Heuvel W (2017) Analysis of FPTASes for the multi-objective shortest path problem. Comput Oper Res 78:44–58

    Google Scholar 

  • Casey B, Bhaskar A, Guo H, Chung E (2014) Critical review of time-dependent shortest path algorithms: a multimodal trip planner perspective. Transp Rev 34(4):522–539

    Google Scholar 

  • Cheng TCE, Janiak A, Kovalyov MY (1998) Bicriterion single machine scheduling with resource dependent processing times. SIAM J Optim 8(2):617–630

    Google Scholar 

  • Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press and McGraw-Hill, London

    Google Scholar 

  • Current J, Marsh M (1993) Multiobjective transportation network design and routing problems: taxonomy and annotation. Eur J Oper Res 65:4–19

    Google Scholar 

  • Desrochers M (1986) La Fabrication D’horaires De Travail Pour Les Conducteurs D’autobus Par Une Methode De Generation De Colonnes, Ph.D. Thesis, Centre De Recherche Sur Les Transports, Publication 470, Universite de Montreal, Canada

  • Dial RB (1979) A model and algorithm for multicriteria route-mode choice. Transp Res B 13:311–316

    Google Scholar 

  • Dumitrescu I (2002) Constrained path and cycle problems. Ph.D. thesis, University of Melbourne

  • Dijkstra EW (1959) A note on two problems in connection with graphs. Numerische Mathematik 1:269–271

    Google Scholar 

  • Ehrgott M (2005) Multicriteria optimization, 2nd edn. Springer, Berlin, Heidelberg

    Google Scholar 

  • Ehrgott M, Gandibleux X (eds) (2002) Multiple criteria optimization: state of the art annotated bibliographic surveys. In: International series in operations research and management science, vol 52. Kluwer

  • Ehrgott M, Wang JYT, Raith A, van Houtte C (2012) A bi-objective cyclist route choice model. Transp Res A Policy Pract 46(4):652–663

    Google Scholar 

  • Ergun F, Sinha R, Zhang L (2002) An improved FPTAS for the restricted shortest path problem. Inf Process Lett 83:287–291

    Google Scholar 

  • Floyd RW (1962) Algorithm 97: shortest path. Commun ACM 5(6):345

    Google Scholar 

  • Ford Jr. LR (1956) Network flow theory. Paper P-923, RAND Corporation. Santa Monica, California

  • Fredman ML, Tarjan RE, (1984) Fibonacci Heaps and their uses in improved network optimization algorithms. In: 25th Annual symposium on foundations of computer science, IEEE, pp 338–346

  • Galbrun E, Pelechrinis K, Terzi E (2016) Urban navigation beyond shortest route: the case of safe paths. Inf Syst 57:160–171

    Google Scholar 

  • Garcia R (2009) Resource constrained shortest paths and extensions. Ph.D. thesis, Georgia Institute of Technology

  • Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco

  • Garroppo RG, Giordano S, Tavanti L (2010) A survey on multi-constrained optimal path computation: exact and approximate algorithms. Comput Netw 54:3081–3107

    Google Scholar 

  • Goel A, Ramakrishnan KG, Kataria D, Logothetis D (2001) Efficient computation of delay-sensitive routes from one source to all destinations. In: Proceedings INFOCOM

  • Halffmann P, Ruzika S, Thielen C, Willems D (2017) A general approximation method for bicriteria minimization problems. Theor Comput Sci 695:1–15

    Google Scholar 

  • Halman N, Klabjan D, Mostagir M, Orlin J, Simchi-Levi D (2009) A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Math Oper Res 34:674–685

    Google Scholar 

  • Halman N, Klabjan D, Li CL, Orlin J, Simchi-Levi D (2014) Fully polynomial time approximation schemes for stochastic dynamic programs. SIAM J Discrete Math 28:1725–1796

    Google Scholar 

  • Halman N, Kellerer H, Strusevich V (2018) Approximation schemes for non-separable non-linear boolean programming problems under nested knapsack constraints. Eur J Oper Res 270:435–447

    Google Scholar 

  • Hansen P (1980) Bictiterion path problems. In: Fandel G, Gal T (eds) Multiple criteria decision making and applications. Sptinger, Berlin

    Google Scholar 

  • Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math Oper Res 17:36–42

    Google Scholar 

  • Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern SSC4 4(2):100–107

  • Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, New York, pp 33–65

  • Joksch HC (1966) The shortest route problem with constraints. J Math Anal Appl 14(2):191–197

    Google Scholar 

  • Korte B, Schrader R (1981) On the existence of fast approximation schemes. Nonlinear Program 4:415–437. https://doi.org/10.1016/B978-0-12-468662-5.50020-3

    Article  Google Scholar 

  • Lorenz D, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Oper Res Lett 28:213–219

    Google Scholar 

  • Marchetti-Spaccamela A, Romano G (1985) On different approximation criteria for subset product problems. Inf Process Lett 21:213–218

    Google Scholar 

  • Marathe MV, Ravi R, Sundaran R, Ravi SS, Rosenkrantz DJ, Harry B (1998) Bicriteria network design problems. J Algorithms 28:142–171

    Google Scholar 

  • Minty GJ (1957) A comment on the shortest-route problem. Oper Res 5(5):724–724

    Google Scholar 

  • Ng CT, Barketau MS, Cheng TCE, Kovalyov MY (2010) “Product Partition” and related problems of scheduling and systems reliability: computational complexity and approximation. Eur J Oper Res 207:601–604

    Google Scholar 

  • Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of Web Sources. In: Proceedings of 41st symposium foundations of computer science, FOCS, Redondo Beach, CA, pp 86-92

  • Raith A, Ehrgott M (2009) A comparison of solution strategies for biobjective shortest path problems. Comput Oper Res 36:1299–1331

    Google Scholar 

  • Righini G, Salani M (2006) Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim 3:255–273

    Google Scholar 

  • Robert Y, Vivien F (2009) Introduction to scheduling. Chapman and Hall/CRC Computational Science, Boca Raton

    Google Scholar 

  • Rocco SCM, Ramirez-Marquez JE (2010) A bi-objective approach for shortest-path network interdiction. Comput Ind Eng 59:232–240

    Google Scholar 

  • Roy B (1959) Transitivite et Connexite. C R Acad Sci Paris 249:216–218

  • Safer HM (1992) Fast approximation schemes for multi-criteria combinatorial optimization. Ph.D. thesis, Massachusetts Institute of Technology

  • Safer HM, Orlin JB (1995) Fast approximation schemes for multi-criteria combinatorial optimization. Technical report, Operations Research Center, Massachusetts Institute of Technology

  • Skriver AJV (2000) A classiffication of bicriterion shortest path (BSP) algorithms. Asia Pac J Oper Res 17(2):199–212

    Google Scholar 

  • Sommer C (2014) Shortest-path queries in static networks. ACM Comput Surv 46(4):45:1–45:31

    Google Scholar 

  • Takahashi N, Akiba T, Nomura S, Yamamoto H (2015) An approach for the fast calculation method of Pareto solutions of a two-objective network. Int J Reliab Qual Saf Eng 22(1):1550005

    Google Scholar 

  • Tarapata Z (2007) Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms. Int J Appl Math Comput Sci 17(2):269–287

    Google Scholar 

  • Tsaggouris G, Zaroliagis C (2009) Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications. Theory Comput Syst 45(1):162–186

    Google Scholar 

  • Vassilvitskii S, Yannakakis M (2004) Efficiently computing sufficient trade-off curves. Lect Notes Comput Sci 3142:1201–1213

    Google Scholar 

  • Warburton A (1987) Approximation of Pareto optima in multiple-objective, shortest-path problems. Oper Res 35:70–79

    Google Scholar 

  • Warshall S (1962) A theorem on boolean matrices. J ACM 9(1):11–12

    Google Scholar 

  • Ziegelmann M (2001) Constrained shortest paths and related problems. Doctoral dissertation, Universitat des Saarlandes, Saarbruecken (2001)

Download references

Author information

Authors and Affiliations

  1. Hebrew University of Jerusalem, Jerusalem, Israel

    Nir Halman

  2. United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk, Belarus

    Mikhail Y. Kovalyov

  3. Université Blaise Pascal, (Clermont-Ferrand II, LIMOS), Aubiére Cedex, France

    Alain Quilliot

  4. Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer Sheva, Israel

    Dvir Shabtay

  5. Department of Industrial Management, Sapir College, Sderot, Israel

    Moshe Zofi

Authors
  1. Nir Halman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mikhail Y. Kovalyov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alain Quilliot
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dvir Shabtay
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Moshe Zofi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dvir Shabtay.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Halman, N., Kovalyov, M.Y., Quilliot, A. et al. Bi-criteria path problem with minimum length and maximum survival probability. OR Spectrum 41, 469–489 (2019). https://doi.org/10.1007/s00291-018-0543-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-018-0543-1

Keywords

Search

Navigation