## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1.1 Apo--A Posteriori Aggregation of Preferences Methods
Then, the paths from \(s\) to \(t\) are listed by nondecreasing order of function \(f^{1}\) and the dominance of each one is checked by comparing its objective function vector with \((M_{1},m_{2})\), a pair formed by the worst value of function \(f^{1}\) and the best value of function \(f^{2}\), respectively, for the paths previously analyzed. A path \(p\) is included in \(X_{E}\) in case it is not dominated; if it is dominated then it is discarded, and otherwise, it is temporarily stored in \(P_{X}\). 1 for\(i=1,2\)do\(p_{i}^{*}\leftarrow\) shortest path with respect to the objective function \(f^{i}\)
2\(\hat{f}^{1}\gets f^{1}(p_{2}^{*})\)
3\(M_{1}\gets f^{1}(p_{1}^{*})\); \(m_{2}\gets f^{2}(p_{1}^{*})\)
4\(P_{X}\leftarrow\varnothing\); \(X_{E}\leftarrow\varnothing\)
5\(p\gets p_{1}^{*}\)
6 while\(f_{1}(p)\leq f^{1}\)do
7 if\(f^{1}(p)=M_{1}\)then
8 if\(f^{2}(p)=m_{2}\)then Insert path \(p\) in set \(P_{X}\)
9 else
10 if\(f^{2}(p)<m_{2}\)then
11\(P_{X}\leftarrow\{p\}\)
12\(m_{2}\gets f^{2}(p)\)
13 endif
14 endif
15 else
16 if\(f^{2}(p)<m_{2}\)then
17 Insert all the paths in \(P_{X}\) in set \(X_{E}\)
18\(M_{1}\gets f^{1}(p)\); \(m_{2}\gets f^{2}(p)\)
19 endif
20 endif
21\(p\leftarrow\) next shortest path with respect to the objective function \(f^{1}\)
22 endifwhile
```  
**Algorithm 2**Generic biobjective ranking method  
Note that when there are more than two OFs, the test of dominance has to take into account all the cost values of the previously determined paths. The initial proposal of this type of method used the ranking algorithm in [64]. The efficiency of the subroutine used for ranking paths is critical regarding the method's performance since the dominance test and the stopping condition bound the number of generated solutions. Nevertheless, in the worst cases, the calculation of the complete set can require an exponential number of paths to be listed; although, the results in [65] showed  
Figure 4: Ranking technique according to the objective function \(f^{1}\). Magenta circles represent nondominated points; grey crosses represent dominated points; the numbers indicate the order of calculation of the different points. that this limit is never reached for practical problems; the empirical results reported in the studies below also showed reasonable running times. Path ranking methods can be classified into the following three groups:  
* _Deletion algorithms_: After the shortest path calculation, a new network is constructed with all the original paths except the shortest ones. The repetition of this procedure enables the paths to be listed by order of cost. Various versions of this algorithm were proposed in [64; 66; 67]. The algorithm in [68] is a recursive method that calculates a new path by obtaining the best alternative to the current path to each node. This can be envisaged as a recursive variant of the method in [67]. * _Labeling algorithms_: If there are no cycles with negative cost in the network, the \(k\)-shortest path problem satisfies an extension of the optimality principle, thus paths can be ranked by using labeling methods. To do so, a label is made to represent a path from \(s\) up to a certain node and at most \(k\) labels have to be stored for each network node (see [69]). * _Deviation algorithms_: In these algorithms any path from \(s\) to \(t\) is the deviation from a shorter path, split into an initial subpath common to both paths, a deviation arc and the shortest path from its head up to \(t\). Since the shortest path from any node to \(t\) can be calculated in advance by recurring to a shortest path algorithm, new candidate paths can be generated by selecting the next deviation arc, see [70; 71; 72]. Among the most efficient algorithms for ranking loopless paths, we cite the deviation algorithms in [73; 74; 75; 71]. Next, we summarize some representative papers using _ranking techniques_ for multiobjective shortest path problems. The work [9] presents computational experiments for the MOSPP, considering labeling and ranking approaches, in random instances.