In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article.
Bernard, R. (1990) Decision-Aid and Decision-Making. European Journal of Operational Research, 45, 324-331. https://doi.org/10.1016/0377-2217(90)90196-I
Valerie, B. (1990) Multiple Criteria Decision Analysis: Practically the Only Way to Choose. University of Strathclyde, Glasgow.
Florent, J., Thériault, M. and Musy, A. (2001) Using GIS and Outranking Multicriteria Analysis for Land-Use Suitability Assessment. International Journal of Geographical Information Science, 15, 153-174. https://doi.org/10.1080/13658810051030487
Kepaptsoglou, K., Karlaftis, M.G. and Gkountis, J. (2013) A Fuzzy AHP Model for Assessing the Condition of Metro Stations. KSCE Journal of Civil Engineering, 17, 1109-1116. https://doi.org/10.1007/s12205-013-0411-0
Marinoni, O. (2006) A Discussion on the Computational Limitations of Outranking Methods for Land-Use Suitability Assessment. International Journal of Geographical Information Science, 20, 69-87. https://doi.org/10.1080/13658810500287040
Eastman, J.R., Kyem, P.A.K. and Toledano, J. (1993) A Procedure for Multi-Objective Decision Making in GIS under Conditions of Conflicting Objectives. Proceedings of the 4th European Conference on Geographic Information Systems, EGIS’93 (Utrecht: EGIS Foundation), 438–448.
jankowski, P., Nyerges, T.L., Smith, A., Moore, T.J. and Horvath, E. (1997) Spatial Group Choice: A SDSS Tool for Collaborative Spatial Decisionmaking. International Journal of Geographical Information Science, 11, 577-602. https://doi.org/10.1080/136588197242202
Pereira, J.M.C. and Duckstein, L. (1993) A Multiple Criteria Deci-sion-Making Approach to GIS-Based Land Suitability Evaluation. International Journal of Geographical Information Science, 7, 407-424. https://doi.org/10.1080/02693799308901971
Grabisch, M. (2005) Une approche constructive de la décision multicritère. Traitement du signal, 22, 321-337.
Dammak, F., Baccour, L. and Alimi, A.M. (2016) Crisp Multi-Criteria Decision Making Methods: State of the Art. International Journal of Computer Science and Information Security, 14, 252.
Hwang, C.-L. and Yoon, K. (1981) Methods for Multiple Attribute Decision Making. In: Multiple Attribute Decision Making. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 58-191. https://doi.org/10.1007/978-3-642-48318-9_3
Benayoun, R., Roy, B. and Sussman, B. (1966) Electre: Une méthode pour guider le choix en présence de points de vue multiples. Note de travail, 49.
Roy, Bernard. (1968) Classement et choix en présence de points de vue multiples. Revue française d’informatique et de recherche opérationnelle, 2, 57-75. https://doi.org/10.1051/ro/196802V100571
Brans, J.P., Mareschal, B. and Vincke, P. (1978) A New Family of Outranking Methods in Multi-Criteria Analysis. Cahiers du Centre d’études de Recherche Opérationnelle, 3-24.
Neumann, J.V., Morgenstern, O., Kuhn, H.W. and Rubinstein, A. (2007) Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ.
Kalyanmoy, D. (2014) Multi-Objective Optimization. In: Burke, E. and Kendall, G., Eds., Search Methodologies, Springer, Boston, MA, 403-449. https://doi.org/10.1007/978-1-4614-6940-7_15
Garey, M.R. (1979) Computers and Intractability: A Guide to the Theory of Np-Completeness. Revista Da Escola De Enfermagem Da USP, 44, 340.
He, F., Huan, Q. and Qiong, F. (2007) An Evolutionary Algorithm for the Multi-Objective Shortest Path Problem. Proceedings of the International Conference on Intelligent Systems and Knowledge Engineering (2007), ISKE 2007, Chengdu 15-16 October 2007. https://doi.org/10.2991/iske.2007.217
Pangilinan, J.M.A. and Gerrit, J. (2007) Evolutionary Algorithms for the Mul-ti-Objective Shortest Path Problem. Int J Appl Sci Eng Technol, 4, 205-210.
Greco, S., Figueira, J.R. and Ehrgott, M. (2016) Multiple Criteria Decision Analysis. Springer, New York. https://doi.org/10.1007/978-1-4939-3094-4
Fustier, B. (1981) Une méthode d’analyse multicritère SPARTE. Diss. Institut de mathématiques économiques (IME).
Jørgen, B.-J. and Gutin, G.Z. (2008) Digraphs: Theory, Algorithms and Applications. Springer Science & Business Media，Berlin/Heidelberg.
Tzeng, G.-H. and Huang, J.-J. (2011) Multiple Attribute Decision Making: Methods and Applications. Springer-Verlag, New York. https://doi.org/10.1201/b11032
Richardson, M. (1953) Solutions of Irreflexive Relations. Annals of Mathematics, 58, 573-590. https://doi.org/10.2307/1969755
Fraenkel, A.S. (1981) Planar Kernel and Grundy with d≤ 3, dout≤ 2, din≤ 2 Are NP-Complete. Discrete Applied Mathematics, 3, 257-262. https://doi.org/10.1016/0166-218X(81)90003-2
Sharir, M. (1981) A Strong-Connectivity Algorithm and Its Applications in Data Flow Analysis. Computers & Mathematics with Applications, 7, 67-72. https://doi.org/10.1016/0898-1221(81)90008-0
Chen, R. and Jean-Jacques, L. (2017) Une preuve formelle de l’algorithme de Tarjan-1972 pour trouver les composantes fortement connexes dans un graphe. JFLA 2017-Vingt-huitièmes Journées Francophones des Langages Applicatifs.
Ruohonen, K. (2013) Graph Theory.
Zhou, A., et al. (2011) Mul-tiobjective Evolutionary Algorithms: A Survey of the State of the Art. Swarm and Evolutionary Computation, 1, 32-49. https://doi.org/10.1016/j.swevo.2011.03.001
Van Veldhuizen, D.A. and Lamont, G.B. (2000) Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art. Evolutionary Computation, 8, 125-147. https://doi.org/10.1162/106365600568158