Evolutionary Algorithms for the Multiobjective Shortest Path Problem

Authors: José Maria A. Pangilinan, Gerrit K. Janssens

Abstract:

This paper presents an overview of the multiobjective shortest path problem (MSPP) and a review of essential and recent issues regarding the methods to its solution. The paper further explores a multiobjective evolutionary algorithm as applied to the MSPP and describes its behavior in terms of diversity of solutions, computational complexity, and optimality of solutions. Results show that the evolutionary algorithm can find diverse solutions to the MSPP in polynomial time (based on several network instances) and can be an alternative when other methods are trapped by the tractability problem.

Keywords: Multiobjective evolutionary optimization, geneticalgorithms, shortest paths.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079536

References:

[1] J. Granat and F. Guerriero, ''The interactive analysis of the multicriteria shortest path problem by the reference point method'', European Journal of Operational Research, vol. 151, pp. 103-111, 2003.
[2] M. Gen and L. Lin, ''Multiobjective genetic algorithm for solving network design problem'', presented at the 20th Fuzzy Systems Symposium, Kitakyushu, Japan, June 2004.
[3] R. Kumar and N. Banerjee, ''Multicriteria network design using evolutionary algorithm'', in Lecture Notes in Computer Science vol. 2724, Berlin: Springer Verlag, 2003, pp. 2179-2190.
[4] M. Ehrgott and X. Gandibleux, ''A survey and annotated bibliography of multi-objective combinatorial optimization'', OR Spektrum vol. 22, pp. 425-460, 2000.
[5] J. Garey, Computers and Intractability: A Guide to the Theory of NP-completeness, San Francisco, CA: Freeman, 1979.
[6] X. Gandibleux, F. Beugnies, and S. Randriamasy, ''Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function'', 4OR A Quarterly Journal of Operations Research, vol. 4, pp. 47-59, 2006.
[7] M. M├╝ller-Hannemann, and K. Weihe, ''Pareto Shortest Paths is Often Feasible in Practice'', in Lecture Notes in Computer Science, vol 2141, G. Brodal, , D. Frigioni, A. Marchetti-Spaccamela Eds. Berlin: Springer Verlag, 2001, pp. 185-198.
[8] P. Hansen, ''Bicriteria path problems'', in Lecture Notes in Economics and Mathematical Systems, vol 177, G. Fandel & T. Gal Eds. Berlin: Springer Verlag, 1979, pp.109-127.
[9] A. Warburton, ''Approximation of Pareto-optima in multiple-objective shortest path problems'', Operations Research, vol. 35, pp. 70-79. 1987.
[10] J. Coutinho-Rodrigues, J. Climaco, and J. Current, ''An interactive bi-objective shortest path approach: searching for unsupported nondominated solutions'', Computers & Operations Research vol. 26, pp. 789-798, 1999.
[11] J. Granat and F. Guerriero, ''The interactive analysis of the multicriteria shortest path problem by the reference point method'', European Journal of Operational Research,, vol. 151, pp. 103-111, 2003.
[12] E. Martins and J. Santos, ''The labeling algorithm for the multiobjective shortest path problem'', Departamento de Matematica, Universidade de Coimbra, Portugal, Tech. Rep. TR-99/005, 1999.
[13] P. Mooney and A. Winstanley, ''An evolutionary algorithm for multicriteria path optimization problems'', International Journal of Geographical Information Science, vol. 20, pp. 401-423, 2006.
[14] F. Guerriero and R. Musmanno, ''Label correcting methods to solve multicriteria shortest path problems'', Journal of Optimization Theory and Applications, vol. 111, pp. 589-613, 2001.
[15] G. Tsaggouris and C. Zaroliagis, ''Multi-objective optimization: improved FPTAS for shortest paths and non-linear objectives with applications'', Computer Technology Institute, University of Patras, Greece, Tech. Rep. TR 2006/03/01, 2006.
[16] J. Crichigno and B. Baran, ''A multicast routing algorithm using multi-objective optimization'', in Lecture Notes in Computer Science, vol 3124, J. Neuman de Souza, D. Dini and P. Lorenz Eds. Berlin: Springer Verlag, 2004, pp. 1107-1113.
[17] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Chichester, UK: J. Wiley & Sons, 2004.
[18] C. Coello, ''An updated survey of GA-based multiobjective optimization techniques'', ACM Computing Surveys, vol. 32, pp. 109-143, 2000.
[19] E. Zitzler and L. Thiele, ''Multiobjective evolutionary algorithms: a comparative study and the strength Pareto approach'', IEEE Transactions on Evolutionary Computation, vol. 3, pp. 257-271, 1999.
[20] Zitzler, Eckart, Bleuler, S., Laumanns, M. and L. Thiele, ''PISA- a platform and programming language independent interface for search algorithms'', Swiss Federal Institute of Technology, Tech. Rep. TIK-Report No. 154, 2003.