## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.3 Other Specific Path Problems Involving Two Functions
Algorithms are proposed for this problem as well as to find the complete set of efficient paths for the problem in which the OFs are the transmission time and the total used energy. Minimum range and ratio path problem  
In [98], a study on the following path problems is presented: _minrange problem_, the aim of which is to find a path with the smallest range of arc lengths, \(\underset{(i,j)\in p}{\max}\left\{c_{ij}^{1}\right\}-\underset{(i,j)\in p}{ \min}\left\{c_{ij}^{1}\right\}\), and the _minratio problem_, the goal of which is to calculate a path for which the ratio of the largest to the smallest arc length is minimum, that is, with the following objective function:  
\[f(p)=\frac{\underset{(i,j)\in p}{\max}\left\{c_{ij}^{1}\right\}}{\underset{ (i,j)\in p}{\min}\left\{c_{ij}^{1}\right\}}. \tag{11}\]  
The optimal solution to these problems is an efficient minsum-maxmin path. The proposed algorithms are based on the enumeration of candidate paths in decreasing order of the objective values, skipping those paths with an OF value greater than or equal to the best known so far. The described algorithms have a time complexity of \(\mathcal{O}\left(m^{2}\mathrm{log}\log n\right)\) in directed networks and \(\mathcal{O}\left(m^{2}\right)\) in undirected networks. The paper also investigates biobjective extensions of these problems. The works [100; 104] study the performance of new labeling algorithms devised for finding all of the efficient solutions of the multiobjective integer knapsack problem. The algorithm proposed in the first paper takes advantage of the conversion of the 0-1 knapsack problem into a BOPP over an acyclic network. The second paper describes a generic labeling algorithm for finding all efficient solutions of the multiobjective integer knapsack problem. This algorithm is based on the resolution of the MOPP on an underlying network. Algorithms devised for defining four network modes representing the problem are proposed. Disjoint path pair problems  
Paper [103] proposes an exact method for calculating efficient biobjective shortest pairs of disjoint simple paths. The resolution approach is based on an algorithm for ranking pairs of disjoint simple paths in non-decreasing order of cost [71], which constitutes an adaptation of a path ranking algorithm application to a network obtained from the original one after a specific duplication of the topology. Each path in this transformed network corresponds to a pair of paths in the former one. The obtained listed paths are then put through an effective dominance test. The work in [111] uses an analogous approach for finding pairs of paths that simultaneously minimize the number of arcs that they share and the total cost of the two paths. The performance of the proposed method is assessed also when applied to obtain efficient solutions close to the maximally disjoint path pair (that is, quasi-disjoint pairs, for a given admissible relaxation value). The work in [105] studies the minimum cost path problem with relays (MCPPR). This problem consists of obtaining a shortest path from \(s\) to \(t\), with a resource weight constraint. In order to fulfill this constraint, the path nodes can be utilized as relays, resetting the transported weight to 0 while generating a node-dependent cost. The MCPPRis formulated as a BOPP involving an aggregated function of the path and relay costs and a weight function, dealing with a variant which takes all three functions separately. The paper presents labeling algorithms in which \(W\), the bound on the weight of paths, determines the number of node labels. The proposed algorithm for the constrained single objective function version has a time complexity of \(\mathcal{O}(Wm+Wn\mathrm{log}\max\ \{W,n\})\). Furthermore, the algorithm is extended to consider two additive OFs: the path cost and the relay cost. 1. Dissimilar paths problem  
The problem of finding sets of paths with minimal cost and maximal dissimilarity between them is addressed in [112].