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

• Autorzy: Tarapata Z.
• Języki publikacji: EN

Abstrakty

EN

The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multiobjective 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.

Słowa kluczowe

EN

multiobjective shortest path; stochastic shortest path; algorithm complexity; routing problem; terrain-based modeling; approximation algorithm

PL

problem najkrótszej ścieżki; złożoność algorytmu; algorytm aproksymacyjny

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2007
• Tom: Vol. 17, no 2
• Strony: 269--287
• Opis fizyczny: Bibliogr. 67 poz., rys., tab., wykr.

Twórcy

autor

Tarapata Z.

• Division of Operations Research and Decision Support Cybernetics Faculty, Military University of Technology ul. Kaliskiego 2, 00–908 Warsaw, Poland,

Bibliografia

• [1] Bernstein D. and Kelly S. (1997): Solving a best path problem when the value of time function is nonlinear. - Research paper, Princeton University.
• [2] 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.
• [3] 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.
• [4] 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.
• [5] Cidon I., Rom R. and Shavitt Y. (1999): Analysis of multipath routing. - IEEE/ACM Trans. Netw., Vol. 7, No. 6, pp. 885-896.
• [6] 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.
• [7] 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.
• [8] 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.
• [9] 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] Cox R.G. (1984): Routing of hazardous material. - Ph.D. thesis, School of Civil and Environmental Engineering, Cornell University, Ithaca, NY.
• [11] 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.
• [12] Dial R. (1979): A model and algorithm for multicriteria routemode choice.-Transport. Res., Vol. 13B, No. 4, pp. 311-316.
• [13] 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.
• [14] Ehrgott M. (1997): Multiple Criteria Optimization - Classification and Methodology. - Aachen: Shaker Verlag.
• [15] Ehrgott M. and Gandibleux V. (2000): A survey and annotated bibliography of multiobjective combinatorial optimization. - OR Spektrum, Vol. 22, pp. 425-460.
• [16] Ehrgott M. and Gandibleux X. (Eds.) (2002): Multiple Criteria Optimization-State of the Art Annotated Bibliographic Surveys. -Boston, MA: Kluwer.
• [17] 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.
• [18] Eppstein D. (1999): Finding the K shortest paths. - SIAM J. Comput., Vol. 28, No. 2, pp. 652-673.
• [19] 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.
• [20] Fujimura K. (1996): Path planning with multiple objectives. - IEEE Robot. Automat. Mag., Vol. 3, No. 1, pp. 33-38.
• [21] 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.
• [22] Garey M. and Johnson D. (1979): Computers and Intractability: A Guide to the Theory of NP Completeness. - San Francisco, CA: W.H. Freeman.
• [23] 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.
• [24] 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.
• [25] 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.
• [26] 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.
• [27] Hartley R. (1985): Vector optimal routing by dynamic programming, In: Mathematics of Multiobjective Optimization (P. Serahni, Ed.).-Vienna: Springer, pp. 215-224.
• [28] Hassin R. (1992): Approximation schemes for the restricted shortest path problem.-Math. Oper. Res., Vol. 17, No. 1, pp. 36-42.
• [29] Henig M.I. (1985): The shortest path problem with two objective functions. - Europ. J. Oper. Res., Vol. 25, No. 22, pp. 281-291.
• [30] Henig M.I. (1994): Efficient interactive methods for a class of multiattribute shortest path problems. - Manag. Sci., Vol. 40, No. 7, pp. 891-897.
• [31] 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.
• [32] 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.
• [33] Korzan B. (1982): Method of determining compromise paths in unreliable directed graphs.-Bulletin of theMilitary University of Technology, Warsaw, Vol. XXXI, No. 7, pp. 21-36, (in Polish).
• [34] 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).
• [35] 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).
• [36] 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.
• [37] 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.
• [38] 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.
• [39] Loui R.P. (1983): Optimal paths in graphs with stochastic or multidimensional weights.-Comm.ACM,Vol. 26,No. 9, pp. 670-676.
• [40] Martins E.Q.V. (1984): On a multicriteria shortest path problem. - Europ. J. Oper. Res., Vol. 16, No. 1, pp. 236-245.
• [41] 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.
• [42] 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.
• [43] 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,m No. 3, pp. 495-508.
• [44] 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.
• [45] 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.
• [46] 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.
• [47] Papadimitriou C. and YannakakisM. (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.
• [48] Pelegrin B. and Fernandez P. (1998): On the sum-max bicriterion path problem.-Comput. Oper. Res., Vol. 25, No. 12, pp. 1043-1054.
• [49] 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.
• [50] Sancho N.G.F. (1988): A new type of multiobjective routing problem. - Eng. Optim., Vol. 14, No. 1, pp. 115-119.
• [51] Schrijver A. (2004): Combinatorial Optimization. - Berlin: Springer.
• [52] 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.
• [53] Sherali H., Ozbay K. and Subramanian S. (1998): The timedependent shortest pair of disjoint paths problem: Complexity, models and algorithms. - Networks, Vol. 31, No. 4, pp. 259-272.
• [54] Sigal E., Pritsker A. and Solberg J. (1980): The stochastic shortest route problem.-Oper. Res., Vol. 28, No. 5, pp. 1122-1129.
• [55] 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.
• [56] 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.
• [57] 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.
• [58] Tarapata Z. (1999): Optimization of many tasks sending in an unreliable parallel computing system.- Proc. NATOReg. Conf. Military Communication and Information Systems, Zegrze, Poland, Vol. III, pp. 245-254.
• [59] Tarapata Z. (2000): Multi-paths optimization in unreliable timedependent networks. - Proc. NATO Reg. Conf. Military Communication and Information Systems, Zegrze, Poland, Vol. I, pp. 181-189.
• [60] Tarapata Z. (2003): Military route planning in battlefield simulation: effectiveness problems and potential solutions. - J. Telecomm. Inf. Technol., No. 4, pp. 47-56.
• [61] 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.
• [62] 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.
• [63] 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.
• [64] Vassilvitskii S. and Yannakakis M. (2004): Efficiently computing sufficient trade-off curves.-Lect. Notes Comput. Sci., mVol. 3142, pp. 1201-1213.
• [65] Warburton A. (1987): Approximation of Pareto optima in multiple-objective, shortest-path problems. - Oper. Res., Vol. 35, No. 1, pp. 70-79.
• [66] 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.
• [67] 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.