## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1.2. Intr
The work in [88] addresses the multi-objective shortest path problem with sum and bottleneck objective functions and introduces a weighted sum aggregate ordering of the labels to be incorporated into label-setting algorithms. (b) Minimal complete set computation  
The authors in [84] address the minsum-maxmin path problem. This work shows that the quickest path problem (QPP) (see Section 2.2.3) is equivalent to a weighted shortest path problem associated with the defined problem. An algorithm enabling the calculation of some specific efficient paths of the minsum-maxmin path problem, based on [93], and a resolution procedure for the QPP (that coincides with the one introduced in [94]) are presented. In [85], an extension of the label setting algorithm in [12] for the MOPP is presented. This extended version handles one more maxmin OF, \(f^{r}\), besides the minsum objective functions, \(f^{1},\ldots,f^{r-1}\), and obtains the efficient paths from \(s\) to the other nodes. Note that given paths \(p,\ q\) between a given pair of nodes, \(q\) weakly dominates \(p\) if \(f^{i}(q)=f^{i}(p)\), for \(i=1,\ldots,r-1\), and \(f^{r}(q)>f^{r}(p)\). The classical version of the optimality principle \begin{table}
\begin{tabular}{l c} \hline \hline \multicolumn{1}{c}{**Reference**} & **\# Objectives** \\ \hline ([PERSON] 1984) [80] & 2 \\ ([PERSON] et al., 1985, 1988) [81; 82] & 2 \\ ([PERSON] et al., 1987) [83] & \(k\) \\ ([PERSON] and [PERSON] 1998) [84] & 2 \\ ([PERSON] et al., 2006) [85] & \(k\) \\ ([PERSON] et al., 2009, [PERSON] and [PERSON] 2010) [86; 87] & 3 \\ ([PERSON] et al., 2010) [88] & \(k\) \\ ([PERSON] et al., 2012) [89] & \(k\) \\ ([PERSON] et al., 2013) [90] & 2 \\ ([PERSON] et al., 2017) [91] & 2 \\ ([PERSON] 2018) [92] & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of some essential features of exact algorithms for the MOPP with non-additive metrics. is not valid in this case because efficient paths may contain weakly efficient subpaths, and consequently, a new dominance test is necessary. The works [86; 87; 89] address path problems with two OFs of maxmin type, and a third OF of any kind, assuming that the optimal solution with respect to that function can be found. In the first paper, a polynomial algorithm is presented enabling the generation of the minimal complete set by computing the optimal path in any subgraph where the set of arcs is constrained according to the maxmin values. The second paper seeks to improve the former method by considering the OF values of previous paths to skip some maxmin values, thence reducing the number of subproblems. The same strategy can be applied to other network optimization problems. A labeling procedure for the addressed problem is also developed as a variant of the first procedure which aims at choosing the solutions with the best maxmin value when the cost remains the same. It is shown that the time bound for the first type of algorithms is \(\mathcal{O}(m_{1}m_{2}g(n))\), \(m_{1},\ m_{2}\) being the number of distinct values for each maxmin OF and \(g(n)\) being the number of operations necessary to obtain the single source-single destination shortest path. As for the labeling procedure, it has time complexity of \(\mathcal{O}(m_{1}m_{2}\log(nm_{1}m_{2})(nm_{1}m_{2}+n))\). Finally, the third work generalizes the algorithm for more than two OFs of maxmin type. Paper [90] considers a BOPP where two parameters, namely an additive cost value and a label, are assigned to each arc. The first OF of the problem seeks the minimization of the path cost, whereas the aim of the second OF is to obtain the path with a minimal number of different labels. Two algorithms are presented that generate a set of efficient paths. One of the algorithms finds the shortest paths in a sequence of subnetworks of the original one, setting different lower bounds for the number of labels, together with a dominance test for the solutions.