## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1.1 Apo--A Posteriori Aggregation of Preferences Methods
This technique is outlined in Algorithm 1 and illustrated in Figure 3.  
```
Variables: Let \(X\) be the set that stores the nodes which correspond to the labels yet to be examined; \(L(i)\) the set that stores all the labels which are associated with node \(i\); \(\pi_{x}\) the objective function vector associated with the path from node \(s\) to node \(x\) Summary: When the algorithm starts, the only label that is considered corresponds to the path \(\langle s\rangle\). Afterwards, this label is extended using the arcs in \(A\). A dominance test is applied to any new label, with an objective function vector \(\pi_{x}+c_{ij}\), considering the current labels in \(L(j)\), ensuring that only nondominated labels are stored. When the algorithm is over, \(L(t)\) stores the nondominated labels for node \(t\), which correspond to the efficient paths from node \(s\) to node \(t\). for any node \(i\in N\)do\(L(i)\leftarrow\varnothing\)\(L(s)\leftarrow\{(0,0,\ldots,0)\}\)\(X\leftarrow\{s\}\)while set \(X\) is not emptydo\(i\leftarrow\) node in \(X\)Delete node \(i\) from set \(X\)For any arc \((i,j)\in A\)doforany label \(\pi_{x}\) in set \(L(i)\)doifvector \(\pi_{x}+c_{ij}\) is not dominated by any label in set \(L(j)\)thenAdd a new label, corresponding to the vector \(\pi_{x}+c_{ij}\), to set \(L(j)\)Delete any label in set \(L(j)\) that is dominated by the new label endifififendforifset \(L(j)\) was modifiedthenInsert node \(j\) in set \(X\) endfor
```  
**Algorithm 1**Generic multiobjective labeling method (node selection)  
Figure 3: Labeling techniques: (**a**) search tree of paths starting at node \(s\); magenta bullets represent the end of efficient paths; (**b**) nondominated points corresponding to \(\pi_{1},\ \pi_{2},\ \pi_{3}\); magenta circles represent the nondominated points corresponding to efficient paths. In order to ensure that an efficient path is calculated, the label to be scanned is normally picked in \(X\) in lexicographic order. The applied dominance test consists of comparing one label cost with the cost of the latest efficient path that was obtained for the biobjective case. In fact, if labels \((a_{1},b_{1}),\ldots,(a_{k},b_{k})\) are selected in lexicographic order, then \(a_{i}<a_{i+1}\), or \(a_{i}=a_{i+1}\) and \(b_{i}\leq b_{i+1}\) for \(i=1,\ldots,k-1\). The subsequence of a given one formed only by the nondominated labels also satisfies \(b_{i}\geq b_{i+1}\). Let us assume, without loss of generality, that some \((a_{k},b_{k})\) are not dominated and denote by \((x,y)\) a label lexicographically greater than \((a_{k},b_{k})\). Hence, \(a_{k}<x\) and \(b_{k}\geq y\) implies that \(a_{i}<x\) and \(b_{i}\geq y\) for any \(i\) associated with the nondominated labels subsequence. Otherwise, if \(a_{k}<x\) and \(b_{k}<y\), then \((x,y)\) is dominated. Similarly, if \((a_{k},b_{k})=(x,y)\), then \((x,y)\) is nondominated, like the former label, but \(a_{k}=x\) and \(b_{k}<y\) means that \((x,y)\) is dominated. Alternatively, for the case where we have more than two OFs, we have to check the cost of all the efficient paths previously obtained. Finally, it should be noted that, similarly to the single objective case, the arc costs should be non-negative so that label setting algorithms may be applied, whereas label correcting methods are valid for finite instances of the MOSPP. It is important to note that when labels are analyzed in lexicographic order, an efficient path from \(s\) to \(t\) is obtained whenever a nondominated label associated with node \(t\) is selected, meaning that label setting methods calculate these efficient paths along their labeling phase. Otherwise, if label correcting is being used, the efficient paths can only be identified after all the labels are analyzed. The experimental analysis reported in [51; 53] indicates that ranking methods for the biobjective shortest path problem (BOSPP) are close to an exhaustive search and consequently less competitive than others.