## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.1 MOPP with Additive Objective Functions  
The MOSPP and its more common particular case, the biobjective shortest path problem (BOSPP), have been studied since the early works [7; 8]. They proved that, theoretically, the problem is intractable and also that instances of this problem can have an exponential number of Pareto optimal solutions depending on the number of nodes. Despite this characteristic, several exact methods have been proposed for calculating the efficient path solution set. Refs. [9; 10] obtained finiteness and boundedness conditions for the MOSPP, assuming that there are no negative cycles for one of the objective functions (cycles for which the value/cost of at least one of the OFs is negative). Furthermore, these studies also proved that, with these assumptions, if the value of any cycle is strictly positive for at least one of the OFs, then every efficient path is an efficient loopless path, and the reverse is also true. In practice, exact algorithms are fast enough to deal with many real applications.  
In Table 1, we present a summary of some essential features of exact algorithms for the MOSPPs that are referred to in this subsection by indicating the number of OFs, the essential features of the resolution technique and the class of the resolution method (APO--A posteriori aggregation of preferences; INT--Interactive; or APR--A priori aggregation of preferences) as defined above.  
We consider five types of MOSPP algorithms, namely, generalizations of labeling techniques for the single-objective shortest path problem (ls, label setting, and lc, label correcting); _parametric_ methods which compute nondominated supported solutions based on the scalarization of the objective functions depending on a varying parameter (par); _ranking_ methods which list paths in order of cost and eliminate solutions dominated by others (ran); _two-phase_ algorithms which generate the nondominated supported solutions of the problem and afterwards swap duality gap regions to find those that are unsupported nondominated (2p); and _recursive_ algorithms (rec) which extend node labels recursively, therefore following a depth-search policy and generating labels implicitly until a certain point.  
Figure 2: Classification of multiobjective path problems.  
The works [47; 48] present multiobjective combinatorial optimization surveys including sections dedicated to the MOPP; classifications including this type of problem are in [49; 50]. Later on, the biobjective shortest path problem (BOSPP) was surveyed in [6; 51] and the MOPP in [52]. Computational studies on the multiobjective shortest path problem were presented in [53], considering two OFs, and in [54], the latter including the use of utility functions for defining the next label to be scanned and considering two or more OFs. This study concluded that the features of the network structure have a decisive role in the algorithm performance.  
After reviewing the literature concerning the BOSPP, a thorough computational comparison of some of the resolution strategies for this type of problem is presented in [6].  
Let us now review the most relevant types of algorithms in each group of methods.