## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1.1 Apo--A Posteriori Aggregation of Preferences Methods
For this purpose, a modification of a multiobjective label-setting algorithm, operating on the cover graph and employing a dimensionality reduction procedure enabling switter domination checks, is developed. The original procedure preserves the Pareto optimality of the solutions; in addition, it enables the incorporation of existing heuristics for achieving further efficiency improvements. The authors in [33] introduce efficient, constant-time, dominance tests between labels in labeling algorithms for the BOSPP. The new dominance tests are combined with an algorithm based on the procedure A*. Also [35] addresses a biobjective shortest path algorithm equipped with efficient pruning checks. In this work, different types of pruning techniques are highlighted, some of them known from the previous literature. The pruning operations are classified depending on the type (op-pruning, cl-pruning, old-filter, new-filter), the moment of their application (eager, early, lazy), and the use of dimensionality reduction. The early pruning technique is introduced, which reduces the computational overhead of lazy op-pruning and filtering. Parametric techniques  
Algorithms of this type compute efficient paths corresponding to supported nondominated solutions based on the scalarization of the objective functions. This scalarization depends on a parameter which varies in order to output the different solutions. It is often used as the first phase of the two-phase method described below. In [21], a biobjective parametric solution framework is introduced based on an approximate label-setting algorithm for the parameterized and constrained single-objective subproblem. This method finds the supported efficient paths and a large percentage of non-supported efficient paths. In addition, a general projection scheme is proposed to decompose a multiobjective problem into a number of biobjective problems. The introduced parametric algorithm is polynomial in time. Ranking techniques  
Algorithms of this type rank paths in non-decreasing order of one of the objective functions and partition the set of efficient solutions into subsets, \(S_{i}\), by means of a dominance test, comparing each obtained path with the previous, and selecting the efficient ones. For the biobjective case, the search starts with the lexicographic shortest path with respect to \(f^{1}\) and halts when the minimal value of \(f^{2}\) is achieved. If paths are listed in non-decreasing order of \(f^{1}\), then the \(f^{2}\) values of efficient paths appear in non-increasing order. The algorithm recurs to a set \(P_{X}\) for storing temporarily any computed path while it is not dominated by any other, and there is no guarantee that it is efficient. Therefore, the algorithm stores in \(P_{X}\) the paths that are candidates to be efficient, and the dominance test for \(p\in S_{i}\) compares \(f^{1}(p)\) with \(M_{1}\) and \(f^{2}(p)\) with \(m_{2}\), where \(M_{1}\) is the greatest value of \(f^{1}\) for the paths previously determined, whereas \(m_{2}\) is the lowest value of \(f^{2}\) for the same paths. As paths are found in non-decreasing order of \(f^{1}\), either \(f^{1}(p)=M_{1}\) or \(f^{1}(p)>M_{1}\). In the first case, \(p\) is dominated by some other path if \(m_{2}<f^{2}(p)\); otherwise, \(p\) is a candidate to be an efficient path, therefore it is inserted in \(P_{X}\). In the second case, the paths in \(P_{X}\) are efficient, and \(p\) is temporarily the only new efficient path candidate in \(P_{X}\) and also the only element calculated so far from the elements in a new set \(S_{i}\). This technique is summarized in Algorithm 2, and it is illustrated in Figure 4.  
```
Variables: Let \(P_{X}\) be the set that stores potential efficient paths; \(X_{E}\) the set that stores the efficient paths from node \(s\) to node \(t\) Summary: Firstly, the algorithm computes the optimal path with respect to each objective function, also providing \(\hat{f}^{1}\), an upper bound on \(f^{1}(p)\), for any efficient path \(p\).