MSPP description

The multi-objective formulation was proposed by Vincke [17] in which several parameters are associated with each arc, allowing the possibility of incorporating various criteria. The objectives can be defined as cost, distance, time, reliability [10], accessibility [7], capacity [12] and others. For a review of the multi-objective shortest path problem (MSPP), the interested reader is referred to [6].

Therefore, one intends to determine a path that minimizes simultaneously all the criteria under consideration. Usually, there is not a path exhibiting the best value for all the criteria. Hence, for the MSPP, we are looking for non-dominated (ND) paths in the network (also called Pareto optimal or efficient solutions), that is, paths for which it is not possible to find a better value for one criterion without getting worse for some of the other criteria.

The MSPP is known as being hard to solve. Hansen [10] proved that it may exist an exponential number of non-dominated solutions in the worst case.

The large number of applications of the MSPP led to the development of various strategies to obtain the optimal solutions. Martins and Santos [13] classified the existing approaches in two classes. The first one includes algorithms which determine a single non-dominated path. This is the case of a global optimization problem where an utility function is defined [2]. Interactive procedures [3], where the user is guiding the search into the criteria space, are also considered in this group. In the second class, the entire calculation of the set of non-dominated paths is required. The well-known labelling algorithm [1, 8, 9, 10, 11, 15, 16, 17] and the procedures based on ranking paths proposed by Clímaco and Martins [4, 5, 11, 15] are elements of this group. It also contains Mote's algorithm [14], which computes the complete non-dominated set after solving the linear programming relaxation of the MSPP.

References

[1] J. Brumbaugh-Smith and D. Shier, ''An empirical investigation of some bicriterion shortest path algorithms'', European Journal of Operational Research, 43, 216—224, 1989.

[2] R.L. Carraway, T.L. Morin, and H. Moskowitz. “Generalized dynamic programming for multicriteria optimization”, European Journal of Operational Research, 44:95--104, 1990.

[3] J.N. Clímaco, C.H. Antunes, and M.J. Alves. “Interactive decision support for multiobjective transportation problems”, European Journal of Operational Research, 65/1:58--67, 1993.

[4] J.N. Clímaco and E.Q. Martins. “On the determination of the nondominated paths in a multiobjective network problem”. Proceedings of V Symposium uber Operations Research, Koln, (1980), in Methods in Operations Research , Anton Hain, Konigstein, 40:255--258, 1981.

[5] J.N. Clímaco and E.Q. Martins. “A bicriterion shortest path algorithm”. European Journal of Operational Research, 11:399--404, 1982.

[6] J. Current and M. Marsh, ''Multiple transportation network design and routing problems: taxonomy and annotation'', European Journal of Operational Research, 65, 4—19, 1993.

[7] J. Current, C.S. Marsh and J.L. Cohon, ''The Median Shortest Path Problem: A Multiobjective Approach to Analyze Cost vs. Accessibility in the Design of Transportation Networks'', Transportation Science, 21(3), 188—197, 1987.

[8] F. Guerriero and R. Musmanno. “Label correcting methods to solve multicriteria shortest path problems”, Journal of Optimization Theory and Applications, 111:589--613, 2001.

[9] W. Habenicht, ''Efficient routes in vector-valued graphs'', In Proceedings of the 7th conference on graphtheoretic concepts in computer science (WG 81), 349--355. Muhlbacher, 1982.

[10] P. Hansen, ''Bicriterion path problems'', in Multiple Criteria Decision Making: Theory and Application, editors: G. Fandel and T. Gal, Lectures Notes in Economics and Mathematical Systems, 177, 109-127, Springer Heidelberg, 1980.

[11] E.Q. Martins. “On a multicriteria shortest path problem”. European Journal of Operational Research, 16:236--245, 1984.

[12] E.Q. Martins and J.L. Santos. “An algorithm for the quickest path problem”. Operations Research Letters, 20:195-198, 1997.

[13] E.Q. Martins and J.L. Santos. “The labelling algorithm for the multiobjective shortest path problem”. Internal Technical Report, TR 1999/005, CISUC.

[14] J. Mote, I. Murthy, and D.L. Olson. “A parametric approach to solving bicriterion shortest path problems”, European Journal of Operational Research, 53:81--92, 1991.

[15] J.L. Santos. “Optimização vectorial em redes”, PhD thesis, Departamento de Matemática, Universidade de Coimbra, 2003.

[16] A.J. Skriver and K.A. Andersen. “A label correcting approach for solving bicriterion shortest-path problems”, Computers & Operations Research, 27:507--524, 2000.

[17] P. Vincke, ''Problèmes multicritères'', Cahiers du Centre d'Etudes de Recherche Opérationelle, 16, 425—439, 1974.

=================

Last update:22 December 2007