## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1.2. Intr
Concerning the works [46; 79], the first paper addresses the'resource-constrained shortest path problem', the aim of which is to obtain the shortest path under constraints corresponding to upper bounds on resource consumption along the path. A new resolution method, based on the reference point methodology, is described. Furthermore, the concept of the Chebyshev distance is used for obtaining models and methods enabling upper and lower bounds on the consumption of resources along the paths to be found. The second work addresses the MOSPP and applies a reference point method using a non-additive scalarizing function for finding the 'best Pareto optimal path' according to the considered preference-based approach. For this purpose, a reference point-based constrained shortest path problem is formulated. A two-phase method is described for its resolution where, in the first phase, a bound on the optimal solution is computed and used to define the constraints, whereas in the second phase, a labeling algorithm is applied to search for an optimal solution. The proposed method is applied to grid networks. In [41], a method of analysis of efficient solutions enabling the automated ordering and selection of solutions of a MOPP is proposed and applied to a telecom network routing model based on a BOSPP formulation as it will be referred to in Section 3. The described algorithm is based on a reference point approach such that the paths in a specific priority region in the OF space are ranked by non-decreasing order of a weighted Chebyshev metric. The priority regions are specified from preference thresholds that represent requested and acceptable values previously defined for each OF. Paper [45] introduces a hybrid method for a MOSPP seeking to generate an efficient path which fulfils the decision maker's preferences. The method takes advantage of common weights methodology to define the relative importance of some of the objectives, which results in a single-objective shortest path problem. 2.2.2. MOPP with Other Objective Functions  
The methods presented here are a posteriori aggregation of preferences methods. Maximal complete set computation and minimal complete set computation approaches are included in the following paragraphs. In Table 2, we present a summary of some essential features of exact algorithms for the MOPP with non-additive metrics referred to in this subsection by indicating the number of OFs of the addressed problems. (a) Maximal complete set computation  
In [80], BOPPs having at least one maxmin objective function are addressed. The other OF can either be of that type or be a minsum or minratio type function. Two algorithms are proposed: the first one enabling the minimal complete set of efficient paths to be found; the second one enabling the maximal complete set to be obtained. Both algorithms can be utilized as long as there is an OF of maxmin type and an algorithm is available for determining the best solution for the other OF. The minimal complete set can be computed in a time of \(\mathcal{O}(m_{1}g(n))\), \(m_{1}\) being the number of maxmin objectives and \(g(n)\) being the number of operations needed to calculate an optimal path. The papers [81; 82] define the maximum covering/shortest path, the minimum covering/shortest path and the maximum population/shortest path problems, the latter being a special case of the former. The problems are formulated as biobjective integer programs. The paper also presents a summary of the results obtained for a sample problem concerning the latter formulation. Also, variants and applications of both problem formulations are shown. Note that these formulations extend the concept of 'coverage' used in facility location analysis to network design and routing analysis. The work in [83] puts forward the median shortest path problem (MeSPP), a BOSPP, the objective functions of which are the path length and the travel time required for the demand to reach a node on the path. An algorithm is proposed incorporating a ranking path procedure for identifying efficient solutions.