## 2 Overview of Multiobjective Path Problems and Algorithms
### Types of Multiobjective Path Problems
#### 2.2.3 Other Specific Path Problems Involving Two Functions
\begin{tabular}{l c c} \hline \hline
**Reference** & **\# Objectives** & **Problem Type** \\ \hline [PERSON] and [PERSON] (1997) ([PERSON] and [PERSON], 1997) ([PERSON] et al., 2002) ([PERSON] et al., 2009) & 1 & quickest \\ [PERSON] et al. (2003) ([PERSON] et al., 2003) ([PERSON] et al., 2004) & 2 & knapsack \\ [PERSON] et al. (2004) ([PERSON] et al., 2004) ([PERSON] et al., 2004) & 1 & quickest \\ [PERSON] (2008) ([PERSON] et al., 2004) ([PERSON] et al., 2009) ([PERSON] et al., 2009) & 1 & minsum/minsum \\ [PERSON] and [PERSON] (2009) ([PERSON] et al., 2009) ([PERSON] et al., 2009) & 2 & disjoint path pairs \\ [PERSON] et al. (2010) ([PERSON] et al., 2011) ([PERSON] et al., 2011) & 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) ([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) ([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  
[PERSON] (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{9}\]  
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 \\ [PERSON] (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{10}\]  
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}  (10)  
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. * Quickest path problem The goal of this optimization problem is to find a path \(p\) that minimizes \[f(p)=\sum_{(i,j)\in p}c_{ij}^{1}+\frac{\sigma}{\min_{(i,j)\in p}\left\{c_{ij}^{2 }\right\}},\] (10) for a given \(\sigma\in\mathbb{R}^{+}\). In a telecommunication network routing context, the function \(f(p)\) gives the total transmission time of \(\sigma\) data units between nodes \(s\) and \(t\) along path \(p\), and \(c_{ij}^{1}\) and \(c_{ij}^{2}\) denote the expected delay and the bandwidth (transmission capacity) of arc \((i,j)\), respectively. This problem (QPP) was introduced in [113], and a survey on this topic is in [114]. The authors in [97] noted that for constant arc capacities, the QPP is reducible to the shortest path problem.