## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.3 Other Specific Path Problems Involving Two Functions
For this purpose, the original network is transformed by creating subnetworks of the original one, with different fixed-capacity lower bounds. The paths in the extended network correspond to the paths from the origin \(s\) to \(t\) in \((N,A)\) with a given capacity; therefore, one of the shortest paths from node \(s\) to any of the new terminal nodes must be the quickest one. The consideration of different levels for each defined capacity value implicitly solves the problem as a biobjective problem; this is achieved by fixing one of the OF values and obtaining the best path with respect to the other OF. This algorithm runs in a time of \(\mathcal{O}(r(m+n\text{log}\,n))\) and uses memory space of \(\mathcal{O}(r(m+n))\), where \(r\) denotes the number of values of arc capacities. In the methods proposed in [93; 94], different variants of the resolution strategy are used. In the first paper, the algorithm computes the shortest paths in a sequence of specific subnetworks of the original one, considering fixed lower bounds of the arcs capacity. These subnetworks are obtained by eliminating the arcs with a certain capacity, as new paths are being determined. Like in the previous method, this procedure implicitly solves a biobjective problem. In the second work, the QPP is approached from a biobjective perspective and applies the algorithm for minsum-maxmin problems in [80]. The outcome is very similar to the latter resolution method. These algorithms enable the reduction of the memory space complexity to \(\mathcal{O}(m+n)\). In [99], it is noted that the set of arcs of each subnetwork in the sequence used by [93] is always a subset of the previous one, thus a proposal to replace some resolution procedures of the shortest path problem by a simplified version of [PERSON]'s algorithm is put forward. Empirical tests do not demonstrate a significant enhancement in the efficiency of the algorithm. A label-setting algorithm for obtaining the quickest path is described in [101]. The original network is transformed into another one satisfying an optimality property such that each subpath of a quickest path is also a quickest path. The proposed algorithm avoids enumerating non-efficient paths which have a total transmission time greater than the minimum. The work in [106] presents algorithms for the quickest path problem and for a related problem seeking the identification of the quickest path, the reliability of which is above a given threshold. The algorithms use an enlarged network like the one proposed in [97] but that considers the number of items to be transmitted. Two approaches are presented for the second problem. The first proposes paths to be ranked in nondecreasing order of transmission time so that the first one which satisfies the reliability constraint is selected. The second approach recurs to an enlarged network and the problem is modified in terms of a constrained shortest path problem. Minmax versions of robust quickest path problems are proposed and investigated in [107]. The authors propose exact algorithms or fully polynomial-time approximation procedures depending on the complexity of the addressed problems. In [109], a label-setting algorithm for the quickest path problem is proposed. The algorithm is based on the property that the optimal solution to the problem corresponds to a supported nondominated point in the objective function space of the minsum-maxmin BOPP; note that the procedure does not require enlarging the network representation. As for [108], it describes a resolution procedure based on obtaining a lower bound of the time-to-target for the QPP, a bound which is embedded into an A* algorithm. Paper [110] addresses a variant of the quickest path problem in which each arc is associated with the energy consumed during the transmission along the arc, while each node is assigned with a limited power to transmit messages. The aim of the energy-constrained quickest path problem is to obtain the quickest path, the nodes of which can support the transmission of a message of a known size.