## 2 Overview of Multiobjective Path Problems and Algorithms  
### Basic Concepts  
Let \(G=(N,A)\) be a directed graph and \(s,t\in N\) be two given nodes in \(G\). A path from \(s\) to \(t\) in \(G\) is a sequence \(p=\langle v_{1},v_{2},\ldots,v_{\ell}\rangle\), where \(v_{1}=s\), \(v_{\ell}=t\), \(v_{i}\in N,i=1,\ldots,\ell\), and \((v_{i},v_{i+1})\in A,i=1,\ldots,\ell-1\). The set of paths from \(s\) to \(t\) in \(G\), denoted by \(P_{st}\), can be represented by means of linear constraints, as  
\[\sum\
olimits_{(i,j)\in A}x_{ij}-\sum\
olimits_{(j,j)\in A}x_{ji}=\left\{ \begin{array}{ll}1&\text{if }i=s\\ 0&\text{if }i\in N\backslash\{s,t\}\\ -1&\text{if }i=t\end{array} \right. \tag{1}\]  
where \(x_{ij}\in\{0,1\}\) are binary decision variables associated with any arc \((i,j)\in A\). Constraints (1) are known as flow balance constraints. Under these conditions, each vector \(x\) is the indicator vector of a path from \(s\) to \(t\) and the arcs \((i,j)\) with flow \(x_{ij}=1\) form a path from \(s\) to \(t\)[5]. We can also write  
\[P_{st}=\left\{x\in\{0,1\}:\sum\
olimits_{(i,j)\in A}x_{ij}-\sum\
olimits_{(j,j)\in A}x_{ji}=\left\{ \begin{array}{ll}1&\text{if }i=s\\ 0&\text{if }i\in N\backslash\{s,t\}\\ -1&\text{if }i=t\end{array} \right.\right\} \tag{2}\]  
Let us consider that each arc \((i,j)\in A\) is associated with \(r\) cost values, \(c_{ij}^{k}\in\mathbb{R},k=1,2,\ldots,r\), and that the functions \(f^{k}\) assign a real value to any path in \(P_{st}\), based on its arc costs, for \(k=1,2,\ldots,r\). The multiobjective path problem can be formulated as an optimization program with linear constraints, considering the previous decision variables \(x_{ij}\) for any \((i,j)\in A\). The problem can be formulated as  
\[\min f(x)=\left(f^{1}(x),f^{2}(x),\ldots,f^{r}(x)\right) \tag{3}\]  
\[\text{s. t. (\ref{eq:f_st})}\]  
\[x_{ij}\in\{0,1\},\text{ for all }(i,j)\in A. \tag{4}\]  
The image of the feasible set, \(P_{st}\), is \(f(P_{st})\). In general, there is no optimal solution to a MOPP since there is not a path in \(P_{st}\) which optimizes all objective functions simultaneously. Thus, in a MOPP, the concept of optimality is replaced by the concept of efficiency (or nondominance). A path \(p\in P_{st}\) is said to be efficient if and only if it does not exist any other path \(q\in P_{st}\) that dominates \(p\), that is, such that \(f(q)\leq f(p)\) and \(f(q)\
eq f(p)\). In this case, the image of \(p\), \(f(p)\), is said to be a nondominated point. Let \(X_{E}\) denote the set of efficient paths in \(P_{st}\) and \(F_{N}\) denote the corresponding set of nondominated points or Pareto front. We distinguish between supported and unsupported efficient solutions. Supported efficient solutions are efficient solutions for the images which are located on the boundary of the convex hull of the nondominated solution set defined in the objective function space, while the images of unsupported efficient solutions are located in the interior of this hull, in the duality gaps. Details on duality gaps can be seen in [6]. Supported shortest paths can be obtained as optimal solutions of the _single-objective weighted shortest path_ problem (WSPP):  
\[\min_{x\in X}\Bigl{\{}\sum_{k=1}^{r}\lambda_{k}f^{k}(x)\Bigr{\}}, \tag{5}\]  
with given weights \(\lambda_{k}>0\), for \(k=1,2,\ldots,r\). The set of supported efficient paths will be represented by \(X_{S}\), and its nondominated image, \(f(X_{S})\), denoted by \(F_{S}\). The remaining efficient solutions in \(X_{NE}=X_{E}\backslash X_{S}\) are designated non-supported efficient paths. These cannot be obtained as the solution of a WSPP. The set of non-supported nondominated points, \(f(X_{NE})\), is represented by \(F_{NN}\). Two paths \(p,q\in P_{st}\) are designated as alternative (or equivalent solutions) if \(f(p)=f(q)\). In this paper, the set of all efficient paths is designated as a _maximal complete set_, and it may contain equivalent solutions.