## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.3 Other Specific Path Problems Involving Two Functions  
Next, we overview some specific path problems involving two functions. In Table 3, a summary of some essential features of the exact algorithms of the type referred to in this subsection are shown. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Reference** & **\# Objectives** & **Problem Type** \\ \hline ([PERSON] 1984) [95] & 1 & minsum/maxmin \\ ([PERSON] 1988) [96] & 1 & minsum/max reliability \\ ([PERSON] and [PERSON] 1990) [97] & 1 & quickest \\ ([PERSON] et al., 1991) [93] & 1 & quickest \\ ([PERSON] et al., 1997) [98] & 2 & min(max-min) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Summary of some essential features of exact algorithms for other specific path problems. \begin{table} \begin{tabular}{l c c} \hline \hline
**Reference** & **\# Objectives** & **Problem Type** \\ \hline [PERSON] and [PERSON] (1997) ([PERSON] et al., 2002) ([PERSON] et al., 2003) & 1 & quickest \\ [PERSON] et al. (2003) ([PERSON] et al., 2003) ([PERSON] et al., 2004) & 2 & knapsack \\ [PERSON] et al. (2004) ([PERSON] et al., 2004) & 1 & quickest \\ [PERSON] (2008) ([PERSON] et al., 2009) ([PERSON] et al., 2009) & 1 & minsum/minsum \\ [PERSON] and [PERSON] (2009) ([PERSON] et al., 2009) & 2 & disjoint path pairs \\ [PERSON] et al. (2010) ([PERSON] et al., 2010) & 2 & knapsack \\ [PERSON] and [PERSON] (2011) ([PERSON] et al., 2011) ([PERSON] et al., 2011) & 1 & minsum with relays \\ [PERSON] et al. (2012) ([PERSON] et al., 2011) & 1 & quickest \\ [PERSON] and [PERSON] (2012) ([PERSON] et al., 2011) ([PERSON] et al., 2011) & 1 & quickest \\ [PERSON] and [PERSON] (2014) ([PERSON] et al., 2011) ([PERSON] et al., 2011) & 1 & quickest \\ [PERSON] and [PERSON] (2014) ([PERSON] et al., 2011) ([PERSON] et al., 2011) & 1 & quickest \\ [PERSON] et al. (2017) ([PERSON] et al., 2011) & 1 & quickest \\ [PERSON] and [PERSON] (2020) ([PERSON] et al., 2011) & 2 & shortest disjoint path pairs \\ [PERSON] et al. (2022) ([PERSON] et al., 2022) & 2 & \(k\)-shortest dissimilar paths \\ \hline \hline \end{tabular}  (a) Minimal cost-capacity ratio path problem  
Paper (1955) addresses the minimal cost-capacity ratio path problem by developing a polynomial time algorithm enabling a path from \(s\) to \(t\), which minimizes the cost-capacity ratio to be calculated. The objective function of this problem is as follows:  
\[f(p)=\frac{\sum_{(i,j)\in p}c_{ij}^{1}}{\min_{(i,j)\in p}\left\{c_{ij}^{2} \right\}}. \tag{7}\]  
The proposed algorithm is based on the resolution of the corresponding minsum-maxmin biobjective path problem. \begin{tabular}{l c} (b) & Minimal cost-reliability ratio path problem \\ Paper (1955) addresses the minimum cost-reliability ratio path problem that seeks the determination of a path \(p\) from \(s\) to \(t\) which minimizes the following objective function:  
\[f(p)=\frac{\sum_{(i,j)\in p}c_{ij}^{1}}{\prod_{(i,j)\in p}c_{ij}^{2}}. \tag{8}\]  
Parametric programming is used (taking into account that the optimal solution to this problem is an efficient path for a biobjective path problem), thence enabling the enumeration of the solutions. A specific sufficiency condition is applied to cut down the enumeration process. \begin{tabular}{l c} (c) & Linear fractional path problem \\ Paper (1955) addresses the linear fractional path problem, the aim of which is the calculation of a simple path \(p\) between \(s\) and \(t\) that minimizes \\ \end{tabular}  (9)  
An exact method for finding an optimal simple path when arc costs associated with the functions in the numerator and denominator are non-negative is proposed. The algorithm uses specific multiobjective optimization related techniques like path preference structures and elimination techniques enabling partial paths that cannot be part of an optimal path to be discarded. \begin{table}