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

Frédéric Guidana Gazawa^1*,   Kolyang², Irépran Damakoa³

¹Department of Mathematics and Computer Science, Faculty of Science, The University of Ngaoundere, Ngaoundere, Cameroon.
²Department of Computer Science, Higher Teacher’s Training College, The University of Maroua, Maroua, Cameroon.
³Department of Applied Mathematics and Computer Science, School of Geology and Mining Engineering, The University of Ngaoundere, Ngaoundere, Cameroon.

DOI: 10.4236/ajor.2019.93007                

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.

Keywords

Multi-Criteria Decision Making, Evolutionary Algorithm, Shortest Path, Outranking Method, Induced Subgraphs

1. Introduction

The concept of relations was born out of difficulties encountered with diverse concrete outranking problems [1] . They can handle simultaneously qualitative and quantitative criteria. Criteria scores can be left in their own units, which is important when they are related to diverse domains (e.g. economics, ecology and sociology). This method makes it possible to take into account the incomparability of actions. Outranking methods are the only methods that can take into account this situation [2] [3] . Unfortunately, outranking methods are not able to compare a lot of alternatives ( [3] [4] [5] ). For that, [6] [7] [8] argue that the outranking methods seem inappropriate for land suitability assessment.

Although this method is simple and allows a very thorough analysis of the robustness, this limitation makes several researchers prefer to use the MAUT (multiple attribute utility theory) method. This other approach tries to define a complete pre-order on the set of alternatives. Most often, the formal rules consist in mathematical formulas that lead to an explicit definition of a unique criterion synthesizing the m criteria. The weaknesses that result from this method are the reduction of the multicriteria problem into a unique criterion problem. The consequence of this reduction is that all the actions are comparable, a property that is not always desirable to have because one observes that for a human decision-maker, there are situations involving incomparable alternatives [9] . Moreover, it is often difficult to gather all the criteria of the decision-maker in a single criterion, and sometimes impossible to model such a function in a relevant way.

In view of the above, we thought it would be useful to find a way to overcome the weakness of limiting alternatives using the outranking method. In our work, we want to show that it is possible to remove this limitation. Instead of searching for the “best” solutions directly in the outranking graph, which is impossible if there are a very large number of alternatives, we show how to iteratively explore its induced subgraphs. To test our approach, we applied it to the shortest paths problem in a multi-attribute graph.

In the first part, we present the basic concepts related to Multi-criteria Decision Making, multi-attribute graphs, difficulties in finding the shortest multicriteria path and the SPARTE (Solution au PARadoxe de voTE—Solution to the voting paradox) outranking method which is very close to the ELECTRE (ELimination Et Choix Traduisant la REalité—elimination and choice expressing reality) outranking method. In the second part, we introduce our method by describing some properties that we will use as algorithmic basis. Finally, we present in the third part our numerical experiments and the results obtained.

2. Background Concepts

2.1. Notations

$G=\left(V\left(G\right),E\left(G\right)\right)$ : graph G defined by the set of vertex V(G) and the set of edge E(G);

G_c: condensed graph of the graph G;

P(s, t): set of all elementary (s, t)-paths;

Kr[G] or Kr: Reduced Kernel of a graph G;

K[G] or K: Kernel set of a graph G;

$\lambda \left(p\right)$ : Performance of path p in a strongly connected component;

${\delta }_k$ : weight of criterion k;

w_k (u, v): Evaluation of edge (u, v) according to criterion k;

W_k(p): Evaluation of the path p on the criterion k;

$W\left(p\right)=\left(W_{\text{1}}\left(p\right),W_{\text{2}}\left(p\right),\cdots ,W_m\left(p\right)\right)$ : Evaluation of the path p on m criteria.

2.2. Multi-Attribute Decision Making

Multi-criteria Decision Making (MCDM) is classified into two general categories: multi-objective decision making (MODM) and multi-attribute decision making (MADM) [10] [11] , based on the different purposes and different data types. In the MADM problems, the decision-maker must choose from among a finite number of explicitly identified alternatives, characterized by multiple attributes, where these attributes define the decision criteria. The methods for dealing with MADM problems can be mainly divided into multiple attribute utility theory (MAUT) and outranking methods (especially refer to ELECTRE [12] [13] and PROMETHEE (Preference Ranking Organisation METHod for Enrichment Evaluations) methods [14] ).

2.3. Graph

1) Definitions and notation

A graph G is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, formed by pairs of vertices. In order to avoid any possible confusion, the vertex set of a graph G is denoted by V(G) and its edge set by E(G). A directed graph (or just digraph) G consists of the directed edges. A digraph H is a subdigraph of a digraph G if $V\left(H\right)\subseteq V\left(G\right)$, $E\left(H\right)\subseteq E\left(G\right)$ and every edge in E(H) has both end-vertices in V(H). If every edge of E(G) with both end-vertices in V(H) is in E(H), we say that H is induced by V(H) and H is called an induced subdigraph of G. A strongly connected component H of the digraph G is a directed subgraph of G (not a null graph) such that H is strongly connected, but if we add any vertex or edge to it, then it is not strongly connected anymore. The condensed graph G_c of the digraph G is obtained by contracting all the edges in every strongly connected component. A subset $K\left[G\right]\subseteq V\left(G\right)$ is a kernel if it is independent and absorbing/dominating. K[G] is dominating if $\forall u\in K\left[G\right],\exists v/\left(v,u\right)\in E\left(G\right)$. It is independent if $\forall u,v\in K\left[G\right],\left(v,u\right)\notin E\left(G\right)$. A kernel represents a set of winning positions in a graph [15] .

2) Multi-Attribute graph

Let G = (V, E) be a directed and connected graph. Without loss of generality, we only considered the graph in which there exists at most one edge between a pair of ordered nodes. For a given graph, each edge connecting two nodes u and v is specified by a weight vector $\omega \left(u,v\right)=\left({\omega }_1\left(u,v\right),{\omega }_2\left(u,v\right),\cdots ,{\omega }_m\left(u,v\right)\right)$ where ${\omega }_k\left(u,v\right),k=1,2,\cdots ,m$ is the evaluation of the edge $e=\left(u,v\right)\in E$ according to the criterion (or point of view) k. m represent the number of criteria. Each criterion is associated with a value ${\delta }_k$ representing its weight.

A criterion k can be quantitative or qualitative. If it is a qualitative criterion, ${\omega }_k\left(u,v\right)$ can be expressed in words (for example, “very bad”, ..., “average”, ..., “very good”) or letters with which numbers are associated to insist on the order that exists between these words/letters. In this case, they are ordinal numbers. They do not have an algebraic structure, which prohibits the use of arithmetic operations (for example addition “+”, multiplication “×”) on such numbers.

2.4. Shortest Paths Problem in Multi-Attribute Graph

Given a directed graph G = (V, E), an origin $s\in V$ and a destination $t\in V$, the shortest-path problem (SPP) aims to find the minimum distance path in G from s to t. The Multi-Attribute Shortest Paths Problem is an extension of the traditional shortest path problem and is concerned with finding a set of efficient paths with respect to two or more criteria that are usually in conflict and incommensurable. In MODM, the problem is known to be NP-hard [16] [17] . The objectives are usually conflicting and there exists no best solution to the problem, but a set of Pareto optimal solutions representing the best compromise among the objectives [18] [19] .

Let $P\left(s,t\right)$ denote the set of all s-t paths in G. If a path $p=\left(e_1,e_2,\cdots ,e_L\right)$ $\in P\left(s,t\right)$. Its evaluation is the vector $W\left(p\right)=\left(W_1\left(p\right),W_2\left(p\right),\cdots ,W_m\left(p\right)\right)$ where $W_k\left(p\right)$ is the path evaluation according to the criterion k. If k is a quantitative criterion, $W_k\left(p\right)={\displaystyle \underset{e\in p}{\sum }{\omega }_k\left(e\right)}$, $k=1,2,\cdots ,m$ (additive criterion). When k is a qualitative criterion, $W_k\left(p\right)=opt\left({\omega }_k\left(e_1\right),{\omega }_k\left(e_2\right),\cdots ,{\omega }_k\left(e_L\right)\right)$ (Non-additive criterion) where “opt” may be one of the following operator min, max, median, mean, etc.

In general a multi-criteria shortest path is a kind of vector optimization problem, which can be described as follows: $\underset{p\in P\left(s,t\right)}{“\text{Minimize}”}W\left(p\right)=\left(W_1\left(p\right),W_2\left(p\right),\cdots ,W_m\left(p\right)\right)$. To solve this problem, we have two large groups of approach.

The first one is called traditional approach. It can be characterized by assigning a well-defined degree to the m performances $\left(W_1\left(p\right),W_2\left(p\right),\cdots ,W_m\left(p\right)\right)$ values. Most often a numerical value $v\left(p\right)=\Psi \left(W_1\left(p\right),W_2\left(p\right),\cdots ,W_m\left(p\right)\right)$ is assigned to each $p\in P\left(s,t\right)$ on an appropriate scale. The way the aggregation problem is addressed in this approach leads to define a complete pre-order on the set $P\left(s,t\right)$. Most often, the formal rules consist in mathematical formulas that lead to an explicit definition of a unique criterion synthesizing the m criteria. This is the case with MAVT, MAUT, SMART, TOPSIS, MACBETH, AHP, etc. The complete preorder on the set $P\left(s,t\right)$ can be established. We usually find a better solution than all the others. In anyway, this approach does not allow any incomparability [20] . However, in a real traffic situation, the decision maker is not content with one solution but with a set of more effective solutions to make his own choice.

The second approach is based on pairwise comparison of actions (paths). The approach can be reduced to a single binary relation. This second operational approach has led to various methods, most of which are covered by the label of outranking methods (mainly PROMETHEE and ELECTRE methods). For the choice problematic ( $P.\alpha$ ) solving the problem consists of two parts: construction of an outranking graph, and exploitation of the graph corresponding to this relation. The subset searched is the kernel of the graph [20] .

2.5. Outranking Method SPARTE

The SPARTE outranking method [21] is based on the general approach of the ELECTRE outranking methods. Let p and q be two paths belonging to the set $P\left(s,t\right)$. It is possible to build the following sets of indices:

· $J^{+}\left(p,q\right)=\left\{j/W^j\left(p\right)>W^j\left(q\right)\right\}$, the set of criteria for which the path p is preferred to the path q.

· $J^{-}\left(p,q\right)=\left\{j/W^j\left(p\right)<W^j\left(q\right)\right\}$, the set of criteria for which the path q is preferred to the path p.

· $J^{=}\left(p,q\right)=\left\{j/W^j\left(p\right)=W^j\left(q\right)\right\}$, the set of criteria for which the path q is equal to the path p.

The preference index is similar to the global concordance index of the ELECTRE methods. It is calculated as follows: $C\left(p,q\right)=\frac{{\displaystyle \underset{k\in \left(J^{+}\cup J^{=}\right)}{\sum }{\delta }_k}}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\delta }_i}}$.

There is a difference only in the formulation of the discordance matrix. The idea is based on the assumption that outranking can be accepted even if the minority shows strong opposition [21] . It is enough for the majority to impose the option with a determination at least as important as that expressed by the minority to reject it. To formulate this idea, we define an adhesion indicator, denoted $m\left(p,q\right)$, at any point symmetrical to the opposition indicator given by [21] :

· $m\left(p,q\right)=median\left\{\left(W^j\left(q\right)-W^j\left(p\right),\delta j\right)\text{where}j\in J^{+}\left(p,q\right)\right\};$

· $m^{\prime }\left(p,q\right)=median\left\{\left(W^j\left(q\right)-W^j\left(p\right),\delta j\right)\text{where}j\in J^{-}\left(p,q\right)\right\};$

· $D\left(p,q\right)=\{\begin{array}{l}1\text{if}m\left(p,q\right)\ge m^{\prime }\left(p,q\right)\\ 0\text{otherwise}\end{array}.$

The outranking relations S of which meaning is at least as good as is defined as follow:

$S\left(p,q\right)=\{\begin{array}{l}\text{1}\text{if}C\left(p,q\right)\ge c^{*}\text{and}D\left(p,q\right)=1\\ \text{0}\text{otherwise}\end{array}$ where $c^{*}\in \left[0.5,1\right]$ is the concordance threshold.

3. Our Contribution: Kernel Search in Combinatorial Set

The search for the kernel of a graph is an NP-complete problem [22] . If the graph is cyclic, the kernel set is not unique and may not exit [23] . However, when a graph is directed and acyclic, there is always a single kernel [24] and can be computed in polynomial time [25] .

3.1. Definitions and Properties

A subset Kr[G], denoted simply Kr when there is no possibility of confusion, of the kernel in a digraph $G=\left(V,E\right)$ is a reduced kernel of G if it is independent, absorbing/dominating and not dominated. Kr is not dominated if $\forall u\in Kr,\neg \exists v\in \left(V\backslash Kr\right)/\left(v,u\right)\in E$. This means that there is not a dominated solution that outranked u.

Let $\phi$ be a function which at a digraph G matches its condensed graph $Gc=\left(V\left(Gc\right),E\left(Gc\right)\right)$. Where $V\left(Gc\right)$ is the set of strongly connected components of G and $E\left(Gc\right)=\left\{\left(X,Y\right)\in V\left(Gc\right)\times V\left(Gc\right)/\exists \left(x,y\right)\in X\times Y\wedge \left(x,y\right)\in E\right\}$. This transformation can be carried out in polynomial time by the Kosaraju algorithm [26] and the Tarjan algorithm [27] . The condensed graph $Gc=\left(V\left(Gc\right),E\left(Gc\right)\right)$ is an acyclic digraph [28] .

Property 1: If the digraph G is acyclic then $Gc=G$. The condensed graph Gc and G are the same.

Proof: Let $V\left(Gc\right)$ the set of strongly connected components of an acyclic graph $G=\left(V,E\right)$. Let $U\in V\left(Gc\right)$. Suppose that $\left|U\right|>1\Rightarrow \exists \left(u,u^{\prime }\right)\in U$ there is a way from u to $u^{\prime }$ and another way from $u^{\prime }$ to u. Thus, the way from u to $u^{\prime }$ connected to the way from $u^{\prime }$ to u gives a cycle. Absurd because Gc is an acyclic digraph. So $\forall U\in V\left(Gc\right),\left|U\right|=1\Rightarrow \left|V\left(Gc\right)\right|=\left|V\right|$. Then $V\left(Gc\right)=V$. Similarly $E\left(Gc\right)=E$. By definition

$\begin{array}{c}E\left(Gc\right)=\left\{\left(X,Y\right)\in V\left(Gc\right)\times V\left(Gc\right)/\exists \left(x,y\right)\in X\times Y\wedge \left(x,y\right)\in E\right\}\\ =\left\{\left(x,y\right)\in V/\left(x,y\right)\in E\right\}\end{array}$

Theorem 1: In an acyclic digraph, there exist at least one source (a vertex of which in-degree is zero) and at least one sink (a vertex of which out-degree is zero) [28] .

In this method, we reduce the search for “best solutions” in search of the subset $Kr\subseteq K$ which is actually the set of source vertices in the outranking graph. Let $Gc=\left(V\left(Gc\right),E\left(Gc\right)\right)$ be the condensed graph of an outranking graph. Let Kr[Gc] denote its reduced kernel. We have:

Property 2: Let $G_i=\left(V_i,E_i\right)$ be an induced subgraph of $Gc=\left(V\left(Gc\right),E\left(Gc\right)\right)$ then:

a) $Kr\left[G_i\right]\ne \varphi$.

b) If a vertex $p\in Kr\left[Gc\right]\cap V_i$ then $p\in Kr\left[G_i\right]$.

Proof:

a) The subgraph of an acyclic graph is acyclic and therefore admits at least one source. So $Kr\left[G_i\right]\ne \phi$.

b) If $p\in Kr\left[Gc\right]$ then $\neg \exists q\in V_i$ that $\left(q,p\right)\in E_i$ then $p\in Kr\left[G_i\right]$.if $p\in V_i$.

Property 3: Let $G_i=\left(V_i,E_i\right)$ and $G_j=\left(V_j,E_j\right)$ be two graphs induced of Gc, respectively having Kr[G_i] and Kr[G_j] as a reduced kernel. If we construct a third induced subgraph $G_k=\left(\left(Kr\left[G_i\right]\cup V_j\right),E_k\right)$ then:

a) $Kr\left[G_k\right]\subseteq Kr\left[G_i\right]\cup Kr\left[G_j\right]$.

b) If $V_i\cup V_j=V\left(Gc\right)$ then $Kr\left[G{}_k\right]\supseteq Kr\left[Gc\right]$.

Proof:

a) Let $p\in Kr\left[G_k\right]$ $\Rightarrow$ $p\in Kr\left[G_i\right]$ by definition. Let’s show that $p\in Kr\left[G_j\right]$. Let’s assume that $p\notin Kr\left[G_i\right]$ $\Rightarrow$ $\forall q\in \left(Kr\left[G_i\right]\cup V_j\right)$, $\left(q,p\right)\notin E_j$ because $p\in Kr\left[G_k\right]$. So $p\in Kr\left[G_j\right]$. Conlusion $Kr\left[G_k\right]\subseteq Kr\left[G_i\right]\cup Kr\left[G_j\right]$.

b) Let $p\in Kr\left[Gc\right]$ $\Rightarrow$ $\forall q\in V\left(Gc\right),\left(q,p\right)\notin E\left(Gc\right)$. We have $V_i\cup V_j=V\left(Gc\right)$ $\Rightarrow$ $E_i\subseteq E\left(Gc\right)$ and $E_j\subseteq E\left(Gc\right)$ then $\left(q,p\right)\notin E_i$ and $\left(q,p\right)\notin E_j$ for all $q\in V_i\cup V_j$. Then $\forall q\in Kr\left[V_i\right]\cup V_j$, $\left(q,p\right)\notin E_k$. Hence $p\in$ $Kr\left[G_k\right]$.

Theorem 2: Let $G=\left(V,E\right)$ be an acyclic graph, and be the subsets $V_i,i=1,2,\cdots ,n$ of vertices V such that $V={\displaystyle \underset{i=1}{\overset{n}{\cup }}{V}_i}$ then the reduced kernel Kr of G(V, E) can be obtained recursively from its n subsets by the following recursion relation:

Step 1: Let $G1=\left(V_1,E_1\right)$ the induced subgraph with its reduced kernel Kr₁.

Step 2: Construct the induced subgraph $G2=\left(\left(V_2\cup K{r}_1\right),E_2\right)$ and extract its reduced kernel Kr₂.

...

Step n: Construct the induced subgraph $Gn=\left(\left(V_n\cup K{r}_{\left(n-1\right)}\right),E_n\right)$ and extract its reduced kernel Kr_n.

So $Kr\subseteq K{r}_n\subseteq {\displaystyle \underset{i=1}{\overset{n}{\cup }}kr\left[{G^{\prime }}_i\right]}$. Where ${G^{\prime }}_i=\left(V_i,E\left({G^{\prime }}_i\right)\right)$ are induced subgraphs formed only of V_i vertices.

Proof: Follows from property 3:

- We have $Kr\subseteq K{r}_n$ from proprety 3b.

- We have $K{r}_n\subseteq {\displaystyle \underset{i=1}{\overset{n}{\cup }}kr\left[{G^{\prime }}_i\right]}$ from proprety 3a.

3.2. Performance of Actions in a Strongly Connected Component

When a fictional alternative is a strongly connected component and belongs to a reduced kernel, we evaluate the performance of each real alternative that composes it in order to keep only the alternatives that are really significant in the component. We proceed as follows for evaluation.

In a first time we determine for each alternative p all of its successors $N^{+}\left(p\right)=\left\{p^{\prime }/pS{p}^{\prime }\text{andnot}\left(p^{\prime }Sp\right)\right\}$, all of its predecessors $N^{-}\left(p\right)=\left\{p^{\prime }/p^{\prime }Sp\text{andnot}\left(pS{p}^{\prime }\right)\right\}$, the set of alternatives that are indifferent to it $I^{+}\left(p\right)=\left\{p^{\prime }/p^{\prime }Sp\text{and}pS{p}^{\prime }\right\}$ and the set of actions that are incomparable to it $I^{-}\left(p\right)=\left\{p^{\prime }/\text{not}\left(p^{\prime }Sp\right)\text{andnot}\left(pS{p}^{\prime }\right)\right\}$.

In a second time we calculate the performance $\lambda \left(p\right)$ of each alternative in the strongly connected component as follow:

$\lambda \left(p\right)=\left|N^{+}\left(p\right)\right|-\left|N^{-}\left(p\right)\right|+\frac{{\displaystyle \underset{q\in I^{+}\left(p\right)}{\sum }\left(\left|N^{+}\left(q\right)\right|-\left|N^{-}\left(q\right)\right|\right)}}{\left|I^{+}\left(p\right)\right|}-\frac{\left|I^{-}\left(p\right)\right|}{n}$ where n is the size of the strongly connected component.

In Figure 1 we have an example of strong components of a graph with two subsets of vertices forming the reduced kernel $K_r=\left\{x_9,\left\{x_4,x_5,x_6,x_7\right\}\right\}$. The

Figure 1. Example of a reduced kernel of a strongly connected component.

Table 1. Evaluating the performance of each real alternative of a strongly connected component {x_4, x_5, x_6, x₇}.

subset $\left\{x_4,x_5,x_6,x_7\right\}$ is not a singleton whose performance (see Table 1) of each alternative in the strongly connected component must be calculated. Depending on the problem, one can either retain the best performer or retain only those who have a positive performance.

3.3. Using the Evolutionary Algorithm for the Problem

An evolutionary algorithm operates on a set of candidate solutions that is subsequently modified by two basic operators: selection and variation. Selection is used to model the reproduction mechanism among living beings, while variation mimics the natural capability of creating new living things by means of recombination and mutation [29] . In our proposed evolution algorithm, the selection consists in looking for the paths forming the reduced kernel of the outranking graph. This operation subdivides the current population into two subsets: the set of paths forming the reduced kernel of the outranking graph and the set of paths that do not belongs to the first subset. The crossing operator consists of selecting a path among those forming the kernel of the outranking graph and crossing it with another path. With a probability p_r, this other path is chosen from the same subset and chosen in another subset with the probability 1 − p_r. The mutation operation will consist in deleting or inserting an edge from a randomly selected kernel path. The algorithm is as follows:

1) Generate random initial population Pop with size N;

2) Perform crossover and mutation to members of the mating pool;

3) Form a new population PopNew made up of Pop and the offspring resulting from crossing and mutation;

4) Calculate the matrix performance of PopNew be MatPop;

5) Find the outranking graph;

6) Find the condensed outranking graph from the main outranking graph and look for its reduced kernel;

7) Form two subsets: KernelPop population from the kernel of condensed outranking graph and NotKernelPop population not belonging to KernelPop;

8) Assign Pop the population members of KernelPop or remove in Pop all population members of NotKernelPop;

9) Return Pop and stop if maximum number of generations is reached. Else consider go to Step 3.

3.4. Convergence of the Algorithm

We used two performance indices [30] to measure the convergence of our multi-attribute optimization method. The Error Ratio (ER) checks the proportion of non true Pareto points in the approximation front over the population size and the Generational Distance (GD) measures how far the evolved solution set is from the true Pareto front. We can observe the evolution of these two metrics in Figure 2. The algorithm is applied on a graph of 50 vertices having 734,455 paths.

4. Experiments and Results

4.1. Test Environment and Implementation

The programming environment used for implementation of the approach is

Figure 2. Evolution of the error ratio and generational distance curves during generation.

MATLAB (Matrix Laboratry). All experiments were performed on a computer with a 2.3 GHz Intel(R) Core(TM) i3-2348M CPU and 4.00 GB of RAM. Three different outranking methods are implemented. Five parameters: CPU time (second), Size of “best” paths, Error Ratio (ER), Generational Distance (GD), Percentage of paths found (%) and Generation) were chosen to study the convergence of our method.

4.2. Tables of Results and Discussion

Example 1: Multi-attribute graph with nine vertices.

In Figure 3, we present a graph with two criteria to be minimized simultaneously. The first is an additive criterion and the second is a non-additive, but a bottleneck criterion. In Figure 4, we can see the points representing the 24 paths of the graph, with the two criteria to be minimized. Among these paths, five form the reduced kernel of the outranking graph. These five paths are located on the Pareto front. The paths forming the reduced kernel are:

Path 1 (10; 30): S®C®G®T; Path 2 (15; 25): S ® B ® C ® T; Path 3 (13; 27): S ® B ® C ® G ® T.

Path 4 (40; 10): S ® A ® E ® T; Path 5 (20; 15): S ® A ® D ® C ® T.

Example 2: Multi-attribute graph with 50 vertices.

An acyclic graph with 50 vertices of 10% density and two attributes was randomly generated for simulation. The first criterion is additive, the second is a bottleneck criterion. At first, we generated all the paths in the graph. The exhaustive search time was 9 h 20 m 10 s. The number of paths found is 734,455. The second step was the generation of Pareto-efficient paths. Table 2 shows the CPU time and size of Pareto-efficient paths. The symbol “−” (resp. “+”) means that the criterion must be minimized (resp. maximized). Thus for example (+, −) means that the first criterion is maximized while the second is minimized. Third, we ran our method and compared the “best solutions” obtained with the Pareto front. For each sense of optimizing criteria, we ran our method ten times. Tables 3-5 present the results obtained by applying our method respectively to PROMETHEE,

Figure 3. Example of multi-attribute graph.

Figure 4. Different paths: the paths forming the reduced kernel located on pareto front.

Table 2. The set of Pareto solutions for exhaustive search.

ELECTRE SPARTE methods.

In Table 3 to Table 5, we have on the first row the execution time of our algorithm; on the second row the number of the best solutions found; on the third and fourth rows the Error Ratio and Generational Distance performance metrics. On the fifth row the percentage of distinct solutions found during the search for best solutions. And finally, the number of generations reached iteratively by the genetic algorithm. On the columns, for the ten executions, we display the minimum (min), the average (avg) and the maximum (max) value of each parameter.

In Figure 5, we observe all the solutions forming the reduced kernel and the set of combinatorial alternatives. This is the case where the first criterion is maximized while the second criterion is minimized.

By observing these results, the PROMETHEE method has better Error Ratio (ER) and GD. However the number of solutions provided is not significant compared to the other two methods. The SPARTE and ELECTRE methods yielded similar results. In these two methods, the five observation parameters are very satisfactory. On the four senses of optimizing criteria, the SPARTE method is better in execution time. The time does not exceed 4 minutes and the error ratio is always very close to 0. The distance of the set of “best” solutions found in relation to the Pareto front is equal to 0 for the best execution cases. The percentage of paths found never exceeded 2%. This shows that our method does not need to explore a very large number of alternatives to converge to the Pareto front.

Table 3. PROMETHEE method coupled with an evolutionary algorithm.

Table 4. Statistic ELECTRE1 method coupled with an evolutionary algorithm.

Table 5. Statistic SPARTE method coupled with an evolutionary algorithm.

Figure 5. Different paths: the paths forming the reduced kernel located on Pareto front.

5. Conclusions and Perspectives

In this paper, we have shown that it is possible to use the outranking methods for solving a multi-attribute combinatorial problem. This approach is based on searching for the reduced kernel of the outranking graph. Theorem 2, which we have established on the reduced kernel of induced subgraphs, has served us as an algorithmic basis. Thus, by iteratively searching for the reduced kernel of the induced subgraphs, it is possible to extract the solutions from a combinatorial optimization problem. Three outranking methods: PROMETHEE, SPARTE and ELECTRE were each coupled to an evolutionary algorithm. The resulting solutions were compared to the Pareto front. The results were very satisfactory for the SPARTE and ELECTRE methods compared to the PROMETHEE method.

As perspectives we intend to use this method with other metaheuristic such as simulated annealing and Taboo search, and apply it to other combinatorial optimization problems like Minimum Spanning Tree Problem multi-attributes that have real applications in the network coverage domain.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	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
[2]	Valerie, B. (1990) Multiple Criteria Decision Analysis: Practically the Only Way to Choose. University of Strathclyde, Glasgow.
[3]	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
[4]	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
[5]	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
[6]	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.
[7]	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
[8]	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
[9]	Grabisch, M. (2005) Une approche constructive de la décision multicritère. Traitement du signal, 22, 321-337.
[10]	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.
[11]	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
[12]	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.
[13]	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
[14]	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.
[15]	Neumann, J.V., Morgenstern, O., Kuhn, H.W. and Rubinstein, A. (2007) Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ.
[16]	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
[17]	Garey, M.R. (1979) Computers and Intractability: A Guide to the Theory of Np-Completeness. Revista Da Escola De Enfermagem Da USP, 44, 340.
[18]	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
[19]	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.
[20]	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
[21]	Fustier, B. (1981) Une méthode d’analyse multicritère SPARTE. Diss. Institut de mathématiques économiques (IME).
[22]	Jørgen, B.-J. and Gutin, G.Z. (2008) Digraphs: Theory, Algorithms and Applications. Springer Science & Business Media，Berlin/Heidelberg.
[23]	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
[24]	Richardson, M. (1953) Solutions of Irreflexive Relations. Annals of Mathematics, 58, 573-590. https://doi.org/10.2307/1969755
[25]	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
[26]	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
[27]	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.
[28]	Ruohonen, K. (2013) Graph Theory.
[29]	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
[30]	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