An Evolutionary Algorithm Coupled to an Outranking Method for the Multicriteria Shortest Paths Problem

HTML  XML Download Download as PDF (Size: 1724KB)  PP. 114-128  
DOI: 10.4236/ajor.2019.93007    518 Downloads   1,212 Views  Citations

ABSTRACT

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.

Share and Cite:

Gazawa, F. , Kolyang,  . and Damakoa, I. (2019) An Evolutionary Algorithm Coupled to an Outranking Method for the Multicriteria Shortest Paths Problem. American Journal of Operations Research, 9, 114-128. doi: 10.4236/ajor.2019.93007.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.