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

 Access to full text

 Full (PDF)

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. Zbl0681.90081
3. 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. Zbl0693.90090
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 multi-path 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. Zbl0488.90068
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. Zbl1090.90026
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. Zbl0542.90099
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. Zbl0932.90005
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. Zbl0698.90084
12. Dial R. (1979): A model and algorithm for multicriteria route-mode 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. Zbl1017.90096
16. Ehrgott M. and Gandibleux X. (Eds.) (2002): Multiple Criteria Optimization-State of the Art Annotated Bibliographic Surveys. - Boston, MA: Kluwer. Zbl1024.00020
17. 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. 
18. Eppstein D. (1999): Finding the K shortest paths. - SIAM J. Comput., Vol.28, No.2, pp.652-673. Zbl0912.05057
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. Zbl1051.68152
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 satelle 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. Zbl0411.68039
23. 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. Zbl0705.90088
24. 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. 
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. Zbl0763.90083
29. Henig M.I. (1985): The shortest path problem with two objective functions. - Europ. J. Oper. Res., Vol.25, No.22, pp.281-291. Zbl0594.90087
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. Zbl0814.90121
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. Zbl0971.90014
33. 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). 
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. Zbl0805.90113
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. Zbl0761.90094
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. Zbl0992.90057
39. Loui R.P. (1983): Optimal paths in graphs with stochastic or multidimensional weights. - Comm. ACM, Vol.26, No.9, pp.670-676. Zbl0526.90085
40. Martins E.Q.V. (1984): On a multicriteria shortest path problem. - Europ. J. Oper. Res., Vol.16, No.1, pp.236-245. Zbl0533.90090
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. Zbl0463.90084
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 utilty measure for finding multiobjective shortest paths in urban multimodal transportation networks. - Europ. J. Oper. Res., Vol.111, No.3, pp.495-508. Zbl0948.90021
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. Zbl0733.90073
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. Zbl0761.90095
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. Zbl0790.90074
47. 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. 
48. Pelegrin B. and Fernandez P. (1998): On the sum-max bicriterion path problem. - Comput. Oper. Res., Vol.25, No.12, pp.1043-1054. Zbl1040.90557
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. Zbl0642.90053
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. Zbl1138.90300
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. Zbl0767.05062
53. 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. Zbl1002.90077
54. Sigal E., Pritsker A. and Solberg J. (1980): The stochastic shortest route problem. - Oper. Res., Vol.28, No.5, pp.1122-1129. Zbl0451.90091
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. Zbl0955.90144
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. Zbl0542.90100
58. 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. 
59. 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. 
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. Zbl1175.90366
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. Zbl0715.90093
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. Zbl0769.90079
64. Vassilvitskii S. and Yannakakis M. (2004): Efficiently computing sufficient trade-off curves. - Lect. Notes Comput. Sci., Vol.3142,pp.1201-1213. Zbl1099.90577
65. Warburton A. (1987): Approximation of Pareto optima in multiple-objective, shortest-path problems. - Oper. Res., Vol.35, No.1, pp.70-79. Zbl0623.90084
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 Zbl0775.90159

1. Pedro A. Góngora, David A. Rosenblueth, A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria
2. Julio B. Clempner, Alexander S. Poznyak, Convergence method, properties and computational complexity for Lyapunov games