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

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-4Search 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-6Search 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.635118Search 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.811453Search 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-3Search 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/BF00938761Search 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-XSearch 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-6Search 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-9Search 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_73Search 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/s002910000046Search 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/b101915Search 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-3Search 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.486659Search 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/BF02216932Search 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_9Search 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_9Search 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.36Search 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.891Search 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-1Search 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.1067Search 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-4Search 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.358406Search 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-8Search 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-7Search 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-CSearch 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-WSearch 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-4Search 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.892068Search 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-7Search 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.83Search 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/03052158808941204Search 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-CSearch 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.1122Search 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-4Search 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.3230140209Search 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-8Search 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.70Search 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-ASearch in Google Scholar