{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T11:07:01Z","timestamp":1768820821378,"version":"3.49.0"},"reference-count":67,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,6,1]]},"abstract":"<jats:title>Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms<\/jats:title><jats:p>The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness of solving selected MOSP problems defined as mathematical programming problems (using the CPLEX 7.0 solver) and multi-weighted graph problems (using modified Dijkstra's algorithm) is given. Experimental results of using the presented methods for multicriteria path selection in a terrain-based grid network are given.<\/jats:p>","DOI":"10.2478\/v10006-007-0023-2","type":"journal-article","created":{"date-parts":[[2007,7,25]],"date-time":"2007-07-25T20:06:46Z","timestamp":1185394006000},"page":"269-287","source":"Crossref","is-referenced-by-count":73,"title":["Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms"],"prefix":"10.61822","volume":"17","author":[{"given":"Zbigniew","family":"Tarapata","sequence":"first","affiliation":[]}],"member":"37438","reference":[{"key":"1","volume-title":"Solving a best path problem when the value of time function is nonlinear","author":"D. Bernstein","year":"1997"},{"issue":"2","key":"2","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0377-2217(89)90215-4","article-title":"An empirical investigation of some bicriterion shortest path algorithms","volume":"43","author":"J. Brumbaugh-Smith","year":"1989","journal-title":"Europ. J. Oper. Res."},{"issue":"1","key":"3","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0377-2217(90)90318-6","article-title":"Generalized dynamic programming for multicriteria optimization","volume":"44","author":"R. Carraway","year":"1990","journal-title":"Europ. J. Oper. Res."},{"key":"4","first-page":"92","article-title":"Multi-path routing combined with resource reservation","author":"I. Cidon","year":"1997"},{"issue":"6","key":"5","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1109\/90.811453","article-title":"Analysis of multipath routing","volume":"7","author":"I. Cidon","year":"1999","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"1","key":"6","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/0377-2217(82)90205-3","article-title":"A bicriterion shortest path algorithm","volume":"11","author":"J. Climaco","year":"1982","journal-title":"Europ. J. Oper. Res."},{"issue":"4","key":"7","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1002\/net.10073","article-title":"A bicriterion approach for routing problems in multimedia networks","volume":"41","author":"J. Climaco","year":"2002","journal-title":"Networks"},{"issue":"1","key":"8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF00938761","article-title":"Shortest paths in networks with vector weights","volume":"46","author":"H. Corley","year":"1985","journal-title":"J. Optim. Th. Applic."},{"issue":"8","key":"9","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0305-0548(98)00094-X","article-title":"An intercative biobjective shortest path approach: Searching for unsupported nondominated solutions","volume":"26","author":"J. Coutinho-Rodrigues","year":"1999","journal-title":"Comput. Oper. Res."},{"key":"10","unstructured":"Cox R.G. (1984): <i>Routing of hazardous material<\/i>. \u2014 Ph.D. thesis, School of Civil and Environmental Engineering, Cornell University, Ithaca, NY."},{"issue":"2","key":"11","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0305-0548(90)90042-6","article-title":"An interactive approach to identify the best compromise solution for two objective shortest path problems","volume":"17","author":"J. Current","year":"1990","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"12","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0191-2615(79)90024-9","article-title":"A model and algorithm for multicriteria route-mode choice","volume":"13B","author":"R Dial","year":"1979","journal-title":"Transport. Res."},{"key":"13","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/3-540-59042-0_73","article-title":"On-line and dynamic algorithms for shortest path problems","volume":"900","author":"H. Djidjev","year":"1995","journal-title":"Lect. Notes Comput. Sci."},{"key":"14","volume-title":"Multiple Criteria Optimization\u2014Classification and Methodology","author":"M Ehrgott","year":"1997"},{"key":"15","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s002910000046","article-title":"A survey and annotated bibliography of multiobjective combinatorial optimization","volume":"22","author":"M. Ehrgott","year":"2000","journal-title":"OR Spektrum"},{"key":"16","doi-asserted-by":"crossref","DOI":"10.1007\/b101915","volume-title":"Multiple Criteria Optimization\u2014State of the Art Annotated Bibliographic Surveys","author":"M. Ehrgott","year":"2002"},{"key":"17","first-page":"137","article-title":"Multiobjective siting of a natural gas pipeline","author":"D. Engberg","year":"1983"},{"issue":"2","key":"18","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1137\/S0097539795290477","article-title":"Finding the K shortest paths","volume":"28","author":"D Eppstein","year":"1999","journal-title":"SIAM J. Comput."},{"issue":"5","key":"19","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0020-0190(02)00205-3","article-title":"An improved FPTAS for restricted shortest path","volume":"83","author":"F. Ergun","year":"2002","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"20","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1109\/100.486659","article-title":"Path planning with multiple objectives","volume":"3","author":"K Fujimura","year":"1996","journal-title":"IEEE Robot. Automat. Mag."},{"key":"21","volume-title":"Generation and selection of efficient paths in a multiple criteria graph: The case of daily planning the shots taken by a satellite with an interactive procedure","author":"V. Gabrel","year":"1996"},{"key":"22","volume-title":"Computers and Intractability: A Guide to the Theory of NP Completeness","author":"M. Garey","year":"1979"},{"key":"23","volume-title":"Solving k-shortest and constrained shortest path problems efficiently","author":"B. Golden","year":"1989"},{"key":"24","first-page":"97","volume-title":"A method for selecting optimum number of stations for a rapid transit line: An application in Calcutta tube rail","author":"D. Halder","year":"1981"},{"key":"25","first-page":"109","volume-title":"Bicriterion path problems","author":"P Hansen","year":"1979a"},{"key":"26","first-page":"109","article-title":"Bicriterion Path Problems","volume":"117","author":"P Hansen","year":"1979b"},{"key":"27","first-page":"215","volume-title":"Vector optimal routing by dynamic programming","author":"R Hartley","year":"1985"},{"issue":"1","key":"28","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","article-title":"Approximation schemes for the restricted shortest path problem","volume":"17","author":"R Hassin","year":"1992","journal-title":"Math. Oper. Res."},{"issue":"22","key":"29","first-page":"281","article-title":"The shortest path problem with two objective functions","volume":"25","author":"M Henig","year":"1985","journal-title":"Europ. J. Oper. Res."},{"issue":"7","key":"30","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1287\/mnsc.40.7.891","article-title":"Efficient interactive methods for a class of multiattribute shortest path problems","volume":"40","author":"M Henig","year":"1994","journal-title":"Manag. Sci."},{"issue":"2","key":"31","first-page":"121","article-title":"A computational comparison of some bicriterion shortest path algorithms","volume":"13","author":"F. Huarng","year":"1996","journal-title":"J. Chinese Inst. Ind. Eng."},{"issue":"1","key":"32","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0377-2217(99)00018-1","article-title":"Multi-objective routing within large scale facilities using open finite queueing networks","volume":"121","author":"L. Kerbache","year":"2000","journal-title":"Europ. J. Oper. Res."},{"issue":"7","key":"33","first-page":"21","volume-title":"Method of determining compromise paths in unreliable directed graphs","volume":"XXXI","author":"B Korzan","year":"1982"},{"issue":"11","key":"34","first-page":"21","volume-title":"Method of determining nondominated paths in unreliable directed graphs","volume":"XXXII","author":"B Korzan","year":"1983a"},{"issue":"6","key":"35","first-page":"69","volume-title":"Paths optimization in unreliable directed graphs","volume":"XXXII","author":"B Korzan","year":"1983b"},{"issue":"1","key":"36","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/jmaa.1993.1067","article-title":"Time dependency in multiple objective dynamic programming","volume":"173","author":"M. Kostreva","year":"1993","journal-title":"J. Math. Anal. Appl."},{"issue":"7","key":"37","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1002\/net.3230220705","article-title":"Finding disjoint paths with different path-costs: Complexity and algorithms","volume":"22","author":"C. Li","year":"1992","journal-title":"Networks"},{"issue":"1","key":"38","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0167-6377(01)00069-4","article-title":"A simple efficient approximation scheme for the restricted shortest path problem","volume":"28","author":"D. Lorenz","year":"2001","journal-title":"Oper. Res. Letters"},{"issue":"9","key":"39","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1145\/358172.358406","article-title":"Optimal paths in graphs with stochastic or multidimensional weights","volume":"26","author":"R Loui","year":"1983","journal-title":"Comm. ACM"},{"issue":"1","key":"40","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","article-title":"On a multicriteria shortest path problem","volume":"16","author":"E. Martins","year":"1984","journal-title":"Europ. J. Oper. Res."},{"key":"41","first-page":"255","article-title":"On the determination of the nondominated paths in a multiobjective network problem","volume":"40","author":"E. Martins","year":"1981","journal-title":"Meth. Oper. Res."},{"key":"42","volume-title":"The labelling algorithm for the multiobjective shortest path problem","author":"E. Martins","year":"1999"},{"issue":"3","key":"43","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/S0377-2217(97)00376-7","article-title":"A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks","volume":"111","author":"P. Modesti","year":"1998","journal-title":"Europ. J. Oper. Res."},{"issue":"1","key":"44","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0377-2217(91)90094-C","article-title":"A parametric approach to solving bicriterion shortest path problems","volume":"53","author":"J. Mote","year":"1991","journal-title":"Europ. J. Oper. Res."},{"issue":"1","key":"45","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1002\/1520-6750(199208)39:5<669::AID-NAV3220390506>3.0.CO;2-W","article-title":"Solving min-max shortest-path problems on a network","volume":"39","author":"I. Murthy","year":"1992","journal-title":"Naval Res. Log."},{"issue":"2","key":"46","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0377-2217(94)90320-4","article-title":"An interactive procedure using domination cones for bicriterion shortest path problems","volume":"72","author":"I. Murthy","year":"1994","journal-title":"Europ. J. Oper. Res."},{"key":"47","first-page":"86","article-title":"On the Approximability of Trade-offs and Optimal Access of Web Sources","author":"C. Papadimitriou","year":"2000"},{"issue":"12","key":"48","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1016\/S0305-0548(98)00036-7","article-title":"On the sum-max bicriterion path problem","volume":"25","author":"B. Pelegrin","year":"1998","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"49","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1287\/trsc.22.2.83","article-title":"A model and solution algorithm for optimal routing of a time-chartered containership","volume":"22","author":"K. Rana","year":"1988","journal-title":"Transport. Sci."},{"issue":"1","key":"50","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1080\/03052158808941204","article-title":"A new type of multiobjective routing problem","volume":"14","author":"N. Sancho","year":"1988","journal-title":"Eng. Optim."},{"key":"51","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2004"},{"issue":"1","key":"52","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1137\/0405009","article-title":"Disjoint paths in a planar graph\u2014A general theorem","volume":"5","author":"A. Schrijver","year":"1992","journal-title":"SIAM J. Discr. Math."},{"issue":"4","key":"53","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1002\/(SICI)1097-0037(199807)31:4<259::AID-NET6>3.0.CO;2-C","article-title":"The time-dependent shortest pair of disjoint paths problem: Complexity, models and algorithms","volume":"31","author":"H. Sherali","year":"1998","journal-title":"Networks"},{"issue":"5","key":"54","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1287\/opre.28.5.1122","article-title":"The stochastic shortest route problem","volume":"28","author":"E. Sigal","year":"1980","journal-title":"Oper. Res."},{"key":"55","first-page":"17","article-title":"An Overview of Routing Models for MPLS Networks","author":"R. Silva","year":"2004"},{"issue":"6","key":"56","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1016\/S0305-0548(99)00037-4","article-title":"A label correcting approach for solving bicriterion shortest path problems","volume":"27","author":"A. Skriver","year":"2000","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"57","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1002\/net.3230140209","article-title":"A quick method for finding shortest pairs of disjoint paths","volume":"14","author":"J. Suurballe","year":"1984","journal-title":"Networks"},{"key":"58","first-page":"245","article-title":"Optimization of many tasks sending in an unreliable parallel computing system","volume":"III","author":"Z Tarapata","year":"1999"},{"key":"59","first-page":"181","article-title":"Multi-paths optimization in unreliable time-dependent networks","volume":"I","author":"Z Tarapata","year":"2000"},{"issue":"4","key":"60","first-page":"47","article-title":"Military route planning in battlefield simulation: effectiveness problems and potential solutions","author":"Z Tarapata","year":"2003","journal-title":"J. Telecomm. Inf. Technol."},{"key":"61","volume-title":"Improved FPTAS for multiobjective shortest paths with applications","author":"G. Tsaggouris","year":"2005"},{"issue":"2","key":"62","first-page":"166","article-title":"A bicriterion Pareto-optimal path algorithm","volume":"5","author":"C. Tung","year":"1988","journal-title":"Asia-Pacific J. Oper. Res."},{"issue":"2","key":"63","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0377-2217(92)90248-8","article-title":"A multicriteria Pareto-optimal path algorithm","volume":"62","author":"C. Tung","year":"1992","journal-title":"Europ. J. Oper. Res."},{"key":"64","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1007\/978-3-540-27836-8_99","article-title":"Efficiently computing sufficient trade-off curves","volume":"3142","author":"S. Vassilvitskii","year":"2004","journal-title":"Lect. Notes Comput. Sci."},{"issue":"1","key":"65","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1287\/opre.35.1.70","article-title":"Approximation of Pareto optima in multiple-objective, shortest-path problems","volume":"35","author":"A Warburton","year":"1987","journal-title":"Oper. Res."},{"issue":"2","key":"66","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0305-0548(82)90008-9","article-title":"The set of efficient solutions for multiple objective shortest path problems","volume":"9","author":"D White","year":"1987","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"67","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0377-2217(93)90142-A","article-title":"Multiobjective routing of hazardous materials in stochastic networks","volume":"65","author":"A. Wijeratne","year":"1993","journal-title":"Europ. J. Oper. Res."}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/17\/2\/article-p269.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/view\/j\/amcs.2007.17.issue-2\/v10006-007-0023-2\/v10006-007-0023-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:27:35Z","timestamp":1709202455000},"score":1,"resource":{"primary":{"URL":"https:\/\/content.sciendo.com\/doi\/10.2478\/v10006-007-0023-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,1]]},"references-count":67,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.2478\/v10006-007-0023-2","relation":{},"ISSN":["1641-876X"],"issn-type":[{"value":"1641-876X","type":"print"}],"subject":[],"published":{"date-parts":[[2007,6,1]]}}}