{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:17:00Z","timestamp":1761621420181},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T00:00:00Z","timestamp":1544486400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00291-018-0543-1","type":"journal-article","created":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T18:34:00Z","timestamp":1544553240000},"page":"469-489","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Bi-criteria path problem with minimum length and maximum survival probability"],"prefix":"10.1007","volume":"41","author":[{"given":"Nir","family":"Halman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail Y.","family":"Kovalyov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Quilliot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dvir","family":"Shabtay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Zofi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,11]]},"reference":[{"key":"543_CR1","first-page":"295","volume":"13","author":"YP Aneja","year":"1983","unstructured":"Aneja YP, Aggarwal V, Nair KPK (1983) Shortest chain subject to side constraints. Nav Res Logist Quart 13:295\u2013302","journal-title":"Nav Res Logist Quart"},{"key":"543_CR2","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1002\/nav.3800250314","volume":"25","author":"YP Aneja","year":"1978","unstructured":"Aneja YP, Nair KPK (1978) The constrained shortest path problem. Nav Res Logist Quart 25:549\u2013555","journal-title":"Nav Res Logist Quart"},{"key":"543_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman R (1958) On a routing problem. Quart Appl Math 16:87\u201390","journal-title":"Quart Appl Math"},{"key":"543_CR4","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.orl.2004.11.011","volume":"34","author":"N Boland","year":"2006","unstructured":"Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper Res Lett 34:58\u201368","journal-title":"Oper Res Lett"},{"key":"543_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6kler F (2017) The multiobjective shortest path problem is NP-hard, or is it, EMO 2017. Lect Notes Comput Sci 10173:77\u201387","DOI":"10.1007\/978-3-319-54157-0_6"},{"key":"543_CR6","unstructured":"Brent RP (2010) Multiple-precision zero-finding methods and the complexity of elementary function evaluation. \n                    arXiv:1004.3412v2\n                    \n                   [cs.NA] 30 May"},{"key":"543_CR7","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.cor.2016.06.022","volume":"78","author":"T Breugem","year":"2017","unstructured":"Breugem T, Dollevoet T, van den Heuvel W (2017) Analysis of FPTASes for the multi-objective shortest path problem. Comput Oper Res 78:44\u201358","journal-title":"Comput Oper Res"},{"issue":"4","key":"543_CR8","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1080\/01441647.2014.921797","volume":"34","author":"B Casey","year":"2014","unstructured":"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\u2013539","journal-title":"Transp Rev"},{"issue":"2","key":"543_CR9","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1137\/S1052623495288192","volume":"8","author":"TCE Cheng","year":"1998","unstructured":"Cheng TCE, Janiak A, Kovalyov MY (1998) Bicriterion single machine scheduling with resource dependent processing times. SIAM J Optim 8(2):617\u2013630","journal-title":"SIAM J Optim"},{"key":"543_CR10","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press and McGraw-Hill, London","edition":"3"},{"key":"543_CR11","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/0377-2217(93)90140-I","volume":"65","author":"J Current","year":"1993","unstructured":"Current J, Marsh M (1993) Multiobjective transportation network design and routing problems: taxonomy and annotation. Eur J Oper Res 65:4\u201319","journal-title":"Eur J Oper Res"},{"key":"543_CR12","unstructured":"Desrochers M (1986) La Fabrication D\u2019horaires De Travail Pour Les Conducteurs D\u2019autobus Par Une Methode De Generation De Colonnes, Ph.D. Thesis, Centre De Recherche Sur Les Transports, Publication 470, Universite de Montreal, Canada"},{"key":"543_CR13","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0191-2615(79)90024-9","volume":"13","author":"RB Dial","year":"1979","unstructured":"Dial RB (1979) A model and algorithm for multicriteria route-mode choice. Transp Res B 13:311\u2013316","journal-title":"Transp Res B"},{"key":"543_CR14","unstructured":"Dumitrescu I (2002) Constrained path and cycle problems. Ph.D. thesis, University of Melbourne"},{"key":"543_CR15","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connection with graphs. Numerische Mathematik 1:269\u2013271","journal-title":"Numerische Mathematik"},{"key":"543_CR16","volume-title":"Multicriteria optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott M (2005) Multicriteria optimization, 2nd edn. Springer, Berlin, Heidelberg","edition":"2"},{"key":"543_CR17","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.1007\/b101915"},{"issue":"4","key":"543_CR18","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1016\/j.tra.2011.11.015","volume":"46","author":"M Ehrgott","year":"2012","unstructured":"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\u2013663","journal-title":"Transp Res A Policy Pract"},{"key":"543_CR19","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0020-0190(02)00205-3","volume":"83","author":"F Ergun","year":"2002","unstructured":"Ergun F, Sinha R, Zhang L (2002) An improved FPTAS for the restricted shortest path problem. Inf Process Lett 83:287\u2013291","journal-title":"Inf Process Lett"},{"issue":"6","key":"543_CR20","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd RW (1962) Algorithm 97: shortest path. Commun ACM 5(6):345","journal-title":"Commun ACM"},{"key":"543_CR21","unstructured":"Ford Jr. LR (1956) Network flow theory. Paper P-923, RAND Corporation. Santa Monica, California"},{"key":"543_CR22","doi-asserted-by":"crossref","unstructured":"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\u2013346","DOI":"10.1109\/SFCS.1984.715934"},{"key":"543_CR23","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/j.is.2015.10.005","volume":"57","author":"E Galbrun","year":"2016","unstructured":"Galbrun E, Pelechrinis K, Terzi E (2016) Urban navigation beyond shortest route: the case of safe paths. Inf Syst 57:160\u2013171","journal-title":"Inf Syst"},{"key":"543_CR24","unstructured":"Garcia R (2009) Resource constrained shortest paths and extensions. Ph.D. thesis, Georgia Institute of Technology"},{"key":"543_CR25","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco"},{"key":"543_CR26","doi-asserted-by":"crossref","first-page":"3081","DOI":"10.1016\/j.comnet.2010.05.017","volume":"54","author":"RG Garroppo","year":"2010","unstructured":"Garroppo RG, Giordano S, Tavanti L (2010) A survey on multi-constrained optimal path computation: exact and approximate algorithms. Comput Netw 54:3081\u20133107","journal-title":"Comput Netw"},{"key":"543_CR27","unstructured":"Goel A, Ramakrishnan KG, Kataria D, Logothetis D (2001) Efficient computation of delay-sensitive routes from one source to all destinations. In: Proceedings INFOCOM"},{"key":"543_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2017.07.003","volume":"695","author":"P Halffmann","year":"2017","unstructured":"Halffmann P, Ruzika S, Thielen C, Willems D (2017) A general approximation method for bicriteria minimization problems. Theor Comput Sci 695:1\u201315","journal-title":"Theor Comput Sci"},{"key":"543_CR29","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1287\/moor.1090.0391","volume":"34","author":"N Halman","year":"2009","unstructured":"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\u2013685","journal-title":"Math Oper Res"},{"key":"543_CR30","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.1137\/130925153","volume":"28","author":"N Halman","year":"2014","unstructured":"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\u20131796","journal-title":"SIAM J Discrete Math"},{"key":"543_CR31","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.ejor.2018.04.013","volume":"270","author":"N Halman","year":"2018","unstructured":"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\u2013447","journal-title":"Eur J Oper Res"},{"key":"543_CR32","volume-title":"Multiple criteria decision making and applications","author":"P Hansen","year":"1980","unstructured":"Hansen P (1980) Bictiterion path problems. In: Fandel G, Gal T (eds) Multiple criteria decision making and applications. Sptinger, Berlin"},{"key":"543_CR33","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math Oper Res 17:36\u201342","journal-title":"Math Oper Res"},{"key":"543_CR34","doi-asserted-by":"crossref","unstructured":"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\u2013107","DOI":"10.1109\/TSSC.1968.300136"},{"key":"543_CR35","doi-asserted-by":"crossref","unstructured":"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\u201365","DOI":"10.1007\/0-387-25486-2_2"},{"issue":"2","key":"543_CR36","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0022-247X(66)90020-5","volume":"14","author":"HC Joksch","year":"1966","unstructured":"Joksch HC (1966) The shortest route problem with constraints. J Math Anal Appl 14(2):191\u2013197","journal-title":"J Math Anal Appl"},{"key":"543_CR37","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/B978-0-12-468662-5.50020-3","volume":"4","author":"B Korte","year":"1981","unstructured":"Korte B, Schrader R (1981) On the existence of fast approximation schemes. Nonlinear Program 4:415\u2013437. \n                    https:\/\/doi.org\/10.1016\/B978-0-12-468662-5.50020-3","journal-title":"Nonlinear Program"},{"key":"543_CR38","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0167-6377(01)00069-4","volume":"28","author":"D Lorenz","year":"2001","unstructured":"Lorenz D, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Oper Res Lett 28:213\u2013219","journal-title":"Oper Res Lett"},{"key":"543_CR39","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0020-0190(85)90061-4","volume":"21","author":"A Marchetti-Spaccamela","year":"1985","unstructured":"Marchetti-Spaccamela A, Romano G (1985) On different approximation criteria for subset product problems. Inf Process Lett 21:213\u2013218","journal-title":"Inf Process Lett"},{"key":"543_CR40","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"MV Marathe","year":"1998","unstructured":"Marathe MV, Ravi R, Sundaran R, Ravi SS, Rosenkrantz DJ, Harry B (1998) Bicriteria network design problems. J Algorithms 28:142\u2013171","journal-title":"J Algorithms"},{"issue":"5","key":"543_CR41","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1287\/opre.5.5.724","volume":"5","author":"GJ Minty","year":"1957","unstructured":"Minty GJ (1957) A comment on the shortest-route problem. Oper Res 5(5):724\u2013724","journal-title":"Oper Res"},{"key":"543_CR42","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1016\/j.ejor.2010.05.034","volume":"207","author":"CT Ng","year":"2010","unstructured":"Ng CT, Barketau MS, Cheng TCE, Kovalyov MY (2010) \u201cProduct Partition\u201d and related problems of scheduling and systems reliability: computational complexity and approximation. Eur J Oper Res 207:601\u2013604","journal-title":"Eur J Oper Res"},{"key":"543_CR43","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.1109\/SFCS.2000.892068"},{"key":"543_CR44","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1016\/j.cor.2008.02.002","volume":"36","author":"A Raith","year":"2009","unstructured":"Raith A, Ehrgott M (2009) A comparison of solution strategies for biobjective shortest path problems. Comput Oper Res 36:1299\u20131331","journal-title":"Comput Oper Res"},{"key":"543_CR45","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.disopt.2006.05.007","volume":"3","author":"G Righini","year":"2006","unstructured":"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\u2013273","journal-title":"Discrete Optim"},{"key":"543_CR46","doi-asserted-by":"crossref","DOI":"10.1201\/9781420072747","volume-title":"Introduction to scheduling","author":"Y Robert","year":"2009","unstructured":"Robert Y, Vivien F (2009) Introduction to scheduling. Chapman and Hall\/CRC Computational Science, Boca Raton"},{"key":"543_CR47","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/j.cie.2010.04.004","volume":"59","author":"SCM Rocco","year":"2010","unstructured":"Rocco SCM, Ramirez-Marquez JE (2010) A bi-objective approach for shortest-path network interdiction. Comput Ind Eng 59:232\u2013240","journal-title":"Comput Ind Eng"},{"key":"543_CR48","unstructured":"Roy B (1959) Transitivite et Connexite. C R Acad Sci Paris 249:216\u2013218"},{"key":"543_CR49","unstructured":"Safer HM (1992) Fast approximation schemes for multi-criteria combinatorial optimization. Ph.D. thesis, Massachusetts Institute of Technology"},{"key":"543_CR50","unstructured":"Safer HM, Orlin JB (1995) Fast approximation schemes for multi-criteria combinatorial optimization. Technical report, Operations Research Center, Massachusetts Institute of Technology"},{"issue":"2","key":"543_CR51","first-page":"199","volume":"17","author":"AJV Skriver","year":"2000","unstructured":"Skriver AJV (2000) A classiffication of bicriterion shortest path (BSP) algorithms. Asia Pac J Oper Res 17(2):199\u2013212","journal-title":"Asia Pac J Oper Res"},{"issue":"4","key":"543_CR52","doi-asserted-by":"crossref","first-page":"45:1","DOI":"10.1145\/2530531","volume":"46","author":"C Sommer","year":"2014","unstructured":"Sommer C (2014) Shortest-path queries in static networks. ACM Comput Surv 46(4):45:1\u201345:31","journal-title":"ACM Comput Surv"},{"issue":"1","key":"543_CR53","doi-asserted-by":"crossref","first-page":"1550005","DOI":"10.1142\/S0218539315500059","volume":"22","author":"N Takahashi","year":"2015","unstructured":"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","journal-title":"Int J Reliab Qual Saf Eng"},{"issue":"2","key":"543_CR54","doi-asserted-by":"crossref","first-page":"269","DOI":"10.2478\/v10006-007-0023-2","volume":"17","author":"Z Tarapata","year":"2007","unstructured":"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\u2013287","journal-title":"Int J Appl Math Comput Sci"},{"issue":"1","key":"543_CR55","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/s00224-007-9096-4","volume":"45","author":"G Tsaggouris","year":"2009","unstructured":"Tsaggouris G, Zaroliagis C (2009) Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications. Theory Comput Syst 45(1):162\u2013186","journal-title":"Theory Comput Syst"},{"key":"543_CR56","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1007\/978-3-540-27836-8_99","volume":"3142","author":"S Vassilvitskii","year":"2004","unstructured":"Vassilvitskii S, Yannakakis M (2004) Efficiently computing sufficient trade-off curves. Lect Notes Comput Sci 3142:1201\u20131213","journal-title":"Lect Notes Comput Sci"},{"key":"543_CR57","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1287\/opre.35.1.70","volume":"35","author":"A Warburton","year":"1987","unstructured":"Warburton A (1987) Approximation of Pareto optima in multiple-objective, shortest-path problems. Oper Res 35:70\u201379","journal-title":"Oper Res"},{"issue":"1","key":"543_CR58","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall S (1962) A theorem on boolean matrices. J ACM 9(1):11\u201312","journal-title":"J ACM"},{"key":"543_CR59","unstructured":"Ziegelmann M (2001) Constrained shortest paths and related problems. Doctoral dissertation, Universitat des Saarlandes, Saarbruecken (2001)"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-018-0543-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00291-018-0543-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-018-0543-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,11]],"date-time":"2019-12-11T00:12:11Z","timestamp":1576023131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00291-018-0543-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,11]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["543"],"URL":"https:\/\/doi.org\/10.1007\/s00291-018-0543-1","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"value":"0171-6468","type":"print"},{"value":"1436-6304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,11]]},"assertion":[{"value":"29 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}