Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms

Zbigniew Tarapata

doi:10.2478/v10006-007-0023-2

Abstract

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.

References

Bernstein D. and Kelly S. (1997): Solving a best path problem when the value of time function is nonlinear. — Research paper, Princeton University.
Search in Google Scholar
Brumbaugh-Smith J. and Shier D. (1989): An empirical investigation of some bicriterion shortest path algorithms. — Europ. J. Oper. Res., Vol. 43, No. 2, pp. 216-224.10.1016/0377-2217(89)90215-4
Search in Google Scholar
Carraway R.L., Morin T.L. and Moskovitz H. (1990): Generalized dynamic programming for multicriteria optimization. — Europ. J. Oper. Res., Vol. 44, No. 1, pp. 95-104.10.1016/0377-2217(90)90318-6
Search in Google Scholar
Cidon I., Rom R. and Shavitt Y. (1997): Multi-path routing combined with resource reservation. — Proc. 16th Annual Joint Conf. IEEE Computer and Communications Societies, INFOCOM'97, Kobe, Japan, pp. 92-100.10.1109/INFCOM.1997.635118
Search in Google Scholar
Cidon I., Rom R. and Shavitt Y. (1999): Analysis of multipath routing. — IEEE/ACM Trans. Netw., Vol. 7, No. 6, pp. 885-896.10.1109/90.811453
Search in Google Scholar
Climaco J.C.M. and Martins E.Q.V. (1982): A bicriterion shortest path algorithm. — Europ. J. Oper. Res., Vol. 11, No. 1, pp. 399-404.10.1016/0377-2217(82)90205-3
Search in Google Scholar
Climaco J., Craveirinha J. and Pascoal M. (2002): A bicriterion approach for routing problems in multimedia networks. — Networks, Vol. 41, No. 4, pp. 206-220.
Search in Google Scholar
Corley H.W. and Moon I.D. (1985): Shortest paths in networks with vector weights. — J. Optim. Th. Applic., Vol. 46, No. 1, pp. 79-86.10.1007/BF00938761
Search in Google Scholar
Coutinho-Rodrigues J.M., Climaco J.C.N. and Current J.R. (1999): An intercative biobjective shortest path approach: Searching for unsupported nondominated solutions. — Comput. Oper. Res., Vol. 26, No. 8, pp. 789-798.10.1016/S0305-0548(98)00094-X
Search in Google Scholar
Cox R.G. (1984): Routing of hazardous material. — Ph.D. thesis, School of Civil and Environmental Engineering, Cornell University, Ithaca, NY.
Search in Google Scholar
Current J.R., ReVelle C.S. and Cohon J.L. (1990): An interactive approach to identify the best compromise solution for two objective shortest path problems. — Comput. Oper. Res., Vol. 17, No. 2, pp. 187-198.10.1016/0305-0548(90)90042-6
Search in Google Scholar
Dial R. (1979): A model and algorithm for multicriteria route-mode choice.—Transport. Res., Vol. 13B, No. 4, pp. 311-316.10.1016/0191-2615(79)90024-9
Search in Google Scholar
Djidjev H., Pantziou G. and Zaroliagis C.D. (1995): On-line and dynamic algorithms for shortest path problems. — Lect. Notes Comput. Sci., Vol. 900, pp. 193-204.10.1007/3-540-59042-0_73
Search in Google Scholar
Ehrgott M. (1997): Multiple Criteria Optimization—Classification and Methodology. — Aachen: Shaker Verlag.
Search in Google Scholar
Ehrgott M. and Gandibleux V. (2000): A survey and annotated bibliography of multiobjective combinatorial optimization. — OR Spektrum, Vol. 22, pp. 425-460.10.1007/s002910000046
Search in Google Scholar
Ehrgott M. and Gandibleux X. (Eds.) (2002): Multiple Criteria Optimization—State of the Art Annotated Bibliographic Surveys. — Boston, MA: Kluwer.10.1007/b101915
Search in Google Scholar
Engberg D., Cohon J. and ReVelle C. (1983): Multiobjective siting of a natural gas pipeline. — Proc. 11th Ann. Pittsburgh Conf. Modeling and Simulation, Pittsburgh, USA, pp. 137-145.
Search in Google Scholar
Eppstein D. (1999): Finding the K shortest paths. — SIAM J. Comput., Vol. 28, No. 2, pp. 652-673.
Search in Google Scholar
Ergun F., Sinha R. and Zhang L. (2002): An improved FPTAS for restricted shortest path. — Inf. Process. Lett., Vol. 83, No. 5, pp. 287-291.10.1016/S0020-0190(02)00205-3
Search in Google Scholar
Fujimura K. (1996): Path planning with multiple objectives. — IEEE Robot. Automat. Mag., Vol. 3, No. 1, pp. 33-38.10.1109/100.486659
Search in Google Scholar
Gabrel V. and Vanderpooten D. (1996): 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. — Tech. Rep. 136, LAMSADE, Universitè Paris Dauphine, France.
Search in Google Scholar
Garey M. and Johnson D. (1979): Computers and Intractability: A Guide to the Theory of NP Completeness. — San Francisco, CA: W.H. Freeman.
Search in Google Scholar
Golden B.L. and Skiscim C.C. (1989): Solving k-shortest and constrained shortest path problems efficiently. — Netw. Optim. Appl. 20, Texas A&M University, College Station.10.1007/BF02216932
Search in Google Scholar
Halder D.K. and Majumber A. (1981): A method for selecting optimum number of stations for a rapid transit line: An application in Calcutta tube rail, In: Scientific Management of Transport Systems (N.K. Jaiswal, Ed.). — New York: North-Holland, pp. 97-108.
Search in Google Scholar
Hansen P. (1979a): Bicriterion path problems, In: Multiple Criteria Decision Making Theory and Application (G. Fandel and T. Gal, Ed.).— Berlin: Springer, pp. 109-127.10.1007/978-3-642-48782-8_9
Search in Google Scholar
Hansen P. (1979b): Bicriterion Path Problems. — Proc. 3rd Conf. Multiple Criteria Decision Making—Theory and Applications, Lect. Notes Econ. Math. Syst., Vol. 117, pp. 109-127.10.1007/978-3-642-48782-8_9
Search in Google Scholar
Hartley R. (1985): Vector optimal routing by dynamic programming, In: Mathematics of Multiobjective Optimization (P. Serahni, Ed.). — Vienna: Springer, pp. 215-224.
Search in Google Scholar
Hassin R. (1992): Approximation schemes for the restricted shortest path problem. — Math. Oper. Res., Vol. 17, No. 1, pp. 36-42.10.1287/moor.17.1.36
Search in Google Scholar
Henig M.I. (1985): The shortest path problem with two objective functions. — Europ. J. Oper. Res., Vol. 25, No. 22, pp. 281-291.
Search in Google Scholar
Henig M.I. (1994): Efficient interactive methods for a class of multiattribute shortest path problems. — Manag. Sci., Vol. 40, No. 7, pp. 891-897.10.1287/mnsc.40.7.891
Search in Google Scholar
Huarng F., Pulat P.S. and Shih L. (1996): A computational comparison of some bicriterion shortest path algorithms. — J. Chinese Inst. Ind. Eng., Vol. 13, No. 2, pp. 121-125.
Search in Google Scholar
Kerbache L. and Smith J. (2000): Multi-objective routing within large scale facilities using open finite queueing networks. — Europ. J. Oper. Res., Vol. 121, No. 1, pp. 105-123.10.1016/S0377-2217(99)00018-1
Search in Google Scholar
Korzan B. (1982): Method of determining compromise paths in unreliable directed graphs. — Bulletin of the Military University of Technology, Warsaw, Vol. XXXI, No. 7, pp. 21-36, (in Polish).
Search in Google Scholar
Korzan B. (1983a): Method of determining nondominated paths in unreliable directed graphs. — Bulletin of the Military University of Technology, Warsaw, Vol. XXXII, No. 11, pp. 21-33, (in Polish).
Search in Google Scholar
Korzan B. (1983b): Paths optimization in unreliable directed graphs. — Bulletin of the Military University of Technology, Warsaw, Vol. XXXII, No. 6, pp. 69-85, (in Polish).
Search in Google Scholar
Kostreva M.M. and Wiecek M.M. (1993): Time dependency in multiple objective dynamic programming. — J. Math. Anal. Appl., Vol. 173, No. 1, pp. 289-307.10.1006/jmaa.1993.1067
Search in Google Scholar
Li C.L., McCormick S.T. and Simchi-Levi D. (1992): Finding disjoint paths with different path-costs: Complexity and algorithms. — Networks, Vol. 22, No. 7, pp. 653-667.
Search in Google Scholar
Lorenz D.H. and Raz D. (2001): A simple efficient approximation scheme for the restricted shortest path problem. — Oper. Res. Letters, Vol. 28, No. 1, pp. 213-219.10.1016/S0167-6377(01)00069-4
Search in Google Scholar
Loui R.P. (1983): Optimal paths in graphs with stochastic or multidimensional weights. — Comm. ACM, Vol. 26, No. 9, pp. 670-676.10.1145/358172.358406
Search in Google Scholar
Martins E.Q.V. (1984): On a multicriteria shortest path problem. — Europ. J. Oper. Res., Vol. 16, No. 1, pp. 236-245.10.1016/0377-2217(84)90077-8
Search in Google Scholar
Martins E.Q.V. and Climaco J.C.N. (1981): On the determination of the nondominated paths in a multiobjective network problem. — Meth. Oper. Res., Vol. 40, pp. 255-258.
Search in Google Scholar
Martins E.Q.V. and Santos J.L.E. (1999): The labelling algorithm for the multiobjective shortest path problem. — Tech. Rep., Universidade de Coimbra, Portugal.
Search in Google Scholar
Modesti P. and Sciomachen A. (1998): A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks. — Europ. J. Oper. Res., Vol. 111, No. 3, pp. 495-508.10.1016/S0377-2217(97)00376-7
Search in Google Scholar
Mote J., Murthy I. and Olson D. (1991): A parametric approach to solving bicriterion shortest path problems. — Europ. J. Oper. Res., Vol. 53, No. 1, pp. 81-92.10.1016/0377-2217(91)90094-C
Search in Google Scholar
Murthy I. and Her S.S. (1992): Solving min-max shortest-path problems on a network. — Naval Res. Log., Vol. 39, No. 1, pp. 669-683.10.1002/1520-6750(199208)39:5<;669::AID-NAV3220390506>3.0.CO;2-W
Search in Google Scholar
Murthy I. and Olson D. (1994): An interactive procedure using domination cones for bicriterion shortest path problems. — Europ. J. Oper. Res., Vol. 72, No. 2, pp. 418-432.10.1016/0377-2217(94)90320-4
Search in Google Scholar
Papadimitriou C. and Yannakakis M. (2000): On the Approximability of Trade-offs and Optimal Access of Web Sources. — Proc. 41st Symp. Foundations of Computer Science, FOCS, Redondo Beach, CA, pp. 86-92.10.1109/SFCS.2000.892068
Search in Google Scholar
Pelegrin B. and Fernandez P. (1998): On the sum-max bicriterion path problem. — Comput. Oper. Res., Vol. 25, No. 12, pp. 1043-1054.10.1016/S0305-0548(98)00036-7
Search in Google Scholar
Rana K. and Vickson R.G. (1988): A model and solution algorithm for optimal routing of a time-chartered containership. — Transport. Sci., Vol. 22, No. 2, pp. 83-96.10.1287/trsc.22.2.83
Search in Google Scholar
Sancho N.G.F. (1988): A new type of multiobjective routing problem. — Eng. Optim., Vol. 14, No. 1, pp. 115-119.10.1080/03052158808941204
Search in Google Scholar
Schrijver A. (2004): Combinatorial Optimization. — Berlin: Springer.
Search in Google Scholar
Schrijver A. and Seymour P. (1992): Disjoint paths in a planar graph—A general theorem. — SIAM J. Discr. Math., Vol. 5, No. 1, pp. 112-116.
Search in Google Scholar
Sherali H., Ozbay K. and Subramanian S. (1998): The time-dependent shortest pair of disjoint paths problem: Complexity, models and algorithms. — Networks, Vol. 31, No. 4, pp. 259-272.10.1002/(SICI)1097-0037(199807)31:4<;259::AID-NET6>3.0.CO;2-C
Search in Google Scholar
Sigal E., Pritsker A. and Solberg J. (1980): The stochastic shortest route problem. — Oper. Res., Vol. 28, No. 5, pp. 1122-1129.10.1287/opre.28.5.1122
Search in Google Scholar
Silva R. and Craveirinha J. (2004): An Overview of Routing Models for MPLS Networks. — Proc. 1st Workshop Multicriteria Modelling in Telecommunication Network Planning and Design, Faculty of Economics of the University of Coimbra, Coimbra, Portugal, pp. 17-24.
Search in Google Scholar
Skriver A.J.V. and Andersen K.A. (2000): A label correcting approach for solving bicriterion shortest path problems. — Comput. Oper. Res., Vol. 27, No. 6, pp. 507-524.10.1016/S0305-0548(99)00037-4
Search in Google Scholar
Suurballe J.W. and Tarjan R.E. (1984): A quick method for finding shortest pairs of disjoint paths. — Networks, Vol. 14, No. 2, pp. 325-336.10.1002/net.3230140209
Search in Google Scholar
Tarapata Z. (1999): Optimization of many tasks sending in an unreliable parallel computing system. — Proc. NATO Reg. Conf. Military Communication and Information Systems, Zegrze, Poland, Vol. III, pp. 245-254.
Search in Google Scholar
Tarapata Z. (2000): Multi-paths optimization in unreliable time-dependent networks. — Proc. NATO Reg. Conf. Military Communication and Information Systems, Zegrze, Poland, Vol. I, pp. 181-189.
Search in Google Scholar
Tarapata Z. (2003): Military route planning in battlefield simulation: effectiveness problems and potential solutions. — J. Telecomm. Inf. Technol., No. 4, pp. 47-56.
Search in Google Scholar
Tsaggouris G. and Zaroliagis Ch. (2005): Improved FPTAS for multiobjective shortest paths with applications. — Tech. Rep. No. TR 2005/07/03, Research Academic Computer Technology Institute, Petras, Greece.
Search in Google Scholar
Tung C.T. and Chew K.L. (1988): A bicriterion Pareto-optimal path algorithm. — Asia-Pacific J. Oper. Res., Vol. 5, No. 2, pp. 166-172.
Search in Google Scholar
Tung C.T. and Chew K.L. (1992): A multicriteria Pareto-optimal path algorithm. — Europ. J. Oper. Res., Vol. 62, No. 2, pp. 203-209.10.1016/0377-2217(92)90248-8
Search in Google Scholar
Vassilvitskii S. and Yannakakis M. (2004): Efficiently computing sufficient trade-off curves. — Lect. Notes Comput. Sci., Vol. 3142, pp. 1201-1213.
Search in Google Scholar
Warburton A. (1987): Approximation of Pareto optima in multiple-objective, shortest-path problems. — Oper. Res., Vol. 35, No. 1, pp. 70-79.10.1287/opre.35.1.70
Search in Google Scholar
White D.J. (1987): The set of efficient solutions for multiple objective shortest path problems. — Comput. Oper. Res., Vol. 9, No. 2, pp. 101-107.
Search in Google Scholar
Wijeratne A.B., Turnquist M.A. and Mirchandani P.B. (1993): Multiobjective routing of hazardous materials in stochastic networks. — Europ. J. Oper. Res., Vol. 65, No. 1, pp. 33-43.10.1016/0377-2217(93)90142-A
Search in Google Scholar

Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms

Abstract

Paradigm

My account