Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms

Tarapata, Zbigniew

International Journal of Applied Mathematics and Computer Science, Tome 17 (2007), p. 269-287 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2007-01-01

Zbl 1120.93051

EUDML-ID : urn:eudml:doc:207836

Bibliographie

[000] Bernstein D. and Kelly S. (1997): Solving a best path problem when the value of time function is nonlinear. - Research paper, Princeton University.

[001] 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. | Zbl 0681.90081

[002] Carraway R.L., Morin T.L. and Moskovz H. (1990): Generalized dynamic programming for multicriteria optimization. - Europ. J. Oper. Res., Vol.44,No.1, pp.95-104. | Zbl 0693.90090

[003] 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.

[004] Cidon I., Rom R. and Shavitt Y. (1999): Analysis of multi-path routing. - IEEE/ACM Trans. Netw., Vol.7, No.6, pp.885-896.

[005] 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. | Zbl 0488.90068

[006] 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. | Zbl 1090.90026

[007] 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. | Zbl 0542.90099

[008] 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. | Zbl 0932.90005

[009] Cox R.G. (1984): Routing of hazardous material. - Ph.D. thesis, School of Civil and Environmental Engineering, Cornell University, Ithaca, NY.

[010] 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. | Zbl 0698.90084

[011] Dial R. (1979): A model and algorithm for multicriteria route-mode choice. - Transport. Res., Vol.13B, No.4, pp.311-316.

[012] 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.

[013] Ehrgott M. (1997): Multiple Criteria Optimization-Classification and Methodology. - Aachen: Shaker Verlag.

[014] Ehrgott M. and Gandibleux V. (2000): A survey and annotated bibliography of multiobjective combinatorial optimization. - OR Spektrum, Vol.22,pp.425-460. | Zbl 1017.90096

[015] Ehrgott M. and Gandibleux X. (Eds.) (2002): Multiple Criteria Optimization-State of the Art Annotated Bibliographic Surveys. - Boston, MA: Kluwer. | Zbl 1024.00020

[016] Engberg D., Cohon J. and ReVelle C. (1983): Multiobjective sing of a natural gas pipeline. - Proc. 11th Ann. Pittsburgh Conf. Modeling and Simulation, Pittsburgh, USA, pp.137-145.

[017] Eppstein D. (1999): Finding the K shortest paths. - SIAM J. Comput., Vol.28, No.2, pp.652-673. | Zbl 0912.05057

[018] 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. | Zbl 1051.68152

[019] Fujimura K. (1996): Path planning with multiple objectives. - IEEE Robot.Automat. Mag., Vol.3, No.1, pp.33-38.

[020] 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 satelle with an interactive procedure. - Tech. Rep. 136, LAMSADE, Universitè Paris Dauphine, France.

[021] Garey M. and Johnson D. (1979): Computers and Intractability: A Guide to the Theory of NP Completeness. - San Francisco, CA: W.H. Freeman. | Zbl 0411.68039

[022] Golden B.L. and Skiscim C.C. (1989): Solving k-shortest and constrained shortest path problems efficiently. - Netw. Optim. Appl. 20, Texas AM University, College Station. | Zbl 0705.90088

[023] Halder D.K. and Majumber A. (1981): A method for selecting optimum number of stations for a rapid trans line: An application in Calcutta tube rail, In: Scientific Management of Transport Systems (N.K.Jaiswal, Ed.). - New York: North-Holland, pp.97-108.

[024] 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.

[025] 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.

[026] Hartley R. (1985): Vector optimal routing by dynamic programming, In: Mathematics of Multiobjective Optimization (P.Serahni, Ed.). - Vienna: Springer, pp.215-224.

[027] Hassin R. (1992): Approximation schemes for the restricted shortest path problem. - Math. Oper. Res., Vol.17, No.1, pp.36-42. | Zbl 0763.90083

[028] Henig M.I. (1985): The shortest path problem with two objective functions. - Europ. J. Oper. Res., Vol.25, No.22, pp.281-291. | Zbl 0594.90087

[029] Henig M.I. (1994): Efficient interactive methods for a class of multiattribute shortest path problems. - Manag. Sci., Vol.40, No.7, pp.891-897. | Zbl 0814.90121

[030] 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.

[031] 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. | Zbl 0971.90014

[032] 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).

[033] 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).

[034] 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).

[035] 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. | Zbl 0805.90113

[036] 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. | Zbl 0761.90094

[037] 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. | Zbl 0992.90057

[038] Loui R.P. (1983): Optimal paths in graphs with stochastic or multidimensional weights. - Comm. ACM, Vol.26, No.9, pp.670-676. | Zbl 0526.90085

[039] Martins E.Q.V. (1984): On a multicriteria shortest path problem. - Europ. J. Oper. Res., Vol.16, No.1, pp.236-245. | Zbl 0533.90090

[040] 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. | Zbl 0463.90084

[041] 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.

[042] Modesti P. and Sciomachen A. (1998): A utilty measure for finding multiobjective shortest paths in urban multimodal transportation networks. - Europ. J. Oper. Res., Vol.111, No.3, pp.495-508. | Zbl 0948.90021

[043] 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. | Zbl 0733.90073

[044] 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. | Zbl 0761.90095

[045] 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. | Zbl 0790.90074

[046] 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.

[047] Pelegrin B. and Fernandez P. (1998): On the sum-max bicriterion path problem. - Comput. Oper. Res., Vol.25, No.12, pp.1043-1054. | Zbl 1040.90557

[048] 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. | Zbl 0642.90053

[049] Sancho N.G.F. (1988): A new type of multiobjective routing problem. - Eng. Optim., Vol.14, No.1, pp.115-119.

[050] Schrijver A. (2004): Combinatorial Optimization. - Berlin: Springer. | Zbl 1138.90300

[051] 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. | Zbl 0767.05062

[052] 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. | Zbl 1002.90077

[053] Sigal E., Pritsker A. and Solberg J. (1980): The stochastic shortest route problem. - Oper. Res., Vol.28, No.5, pp.1122-1129. | Zbl 0451.90091

[054] 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.

[055] 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. | Zbl 0955.90144

[056] 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. | Zbl 0542.90100

[057] 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.

[058] 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.

[059] Tarapata Z. (2003): Military route planning in battlefield simulation: effectiveness problems and potential solutions. - J. Telecomm.Inf. Technol., No.4, pp.47-56.

[060] 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. | Zbl 1175.90366

[061] 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. | Zbl 0715.90093

[062] 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. | Zbl 0769.90079

[063] Vassilvitskii S. and Yannakakis M. (2004): Efficiently computing sufficient trade-off curves. - Lect. Notes Comput. Sci., Vol.3142,pp.1201-1213. | Zbl 1099.90577

[064] Warburton A. (1987): Approximation of Pareto optima in multiple-objective, shortest-path problems. - Oper. Res., Vol.35, No.1, pp.70-79. | Zbl 0623.90084

[065] 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.

[066] 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 | Zbl 0775.90159