# Solving the Urban Transit Routing Problem Using a Cat Swarm Optimization-Based Algorithm
## 3 The Proposed CSO-Based Algorithm
### The Proposed CSO-Based Approach
#### 3.1.3 Route Set Evaluation  
Since the path of each route is strongly dependent on the paths of the other routes belonging to the same route set, separate evaluation of each route has no meaning. Consequently, all routes belonging to the same route set are evaluated together. The evaluation of route sets is based on several criteria measuring the \"quality\" level of each route set (see Section 2.2). \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline
1 st Route: & 1 & 3 & 5 & 14 & 6 & 9 & 10 & 12 & 13 \\ \hline
2 nd Route: & 4 & 1 & 2 & 5 & 7 & 9 & 10 & \(-\)1 & \(-\)1 \\ \hline
3 rd Route: & 2 & 5 & 3 & 11 & 10 & 12 & \(-\)1 & \(-\)1 & \(-\)1 \\ \hline
4 th Route: & 1 & 3 & 5 & 7 & \(-\)1 & \(-\)1 & \(-\)1 & \(-\)1 & \(-\)1 \\ \hline
5 th Route: & 8 & 14 & 6 & 9 & 13 & \(-\)1 & \(-\)1 & \(-\)1 & \(-\)1 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The route set representation (example). All criteria used for route set evaluation by the proposed CSO method are the ones already adopted by other researchers in the literature ([25; 26; 31; 37; 43; 46]). To be more precise, we have adopted the evaluation procedure proposed in [31; 37; 43], where all evaluation criteria presented in Section 2.2 are put in a mathematical formula in order to calculate one single number, i.e., \(FIT(r)\). The arithmetic formula of \(FIT(r)\), which is used to calculate the fitness of each route set \(r\), is the following equation:  
\[FIT(r)=\ \omega_{1}\cdot F_{1}(r)+\ \omega_{2}\cdot F_{2}(r)+\ \omega_{3}\cdot F_{3}(r) \tag{4}\]  
where \(F_{1}(r)\) is the score obtained by evaluating the route set \(r\) using the second criterion only (that is, the average travel time in minutes per transit user; see Section 2.2), \(F_{2}(r)\) is the score obtained by evaluating the route set \(r\) using the third criterion (that is, the percentage of demand satisfied without any transfers, see Section 2.2) and \(F_{3}(r)\) is the score obtained by evaluating the route set \(r\) using the first criterion only (that is, the percentage of demands unsatisfied; see Section 2.2). Parameters \(\omega_{1}\), \(\omega_{2}\), and \(\omega_{3}\) are user specified weights for scores \(F_{1}(r)\), \(F_{2}(r)\) and \(F_{3}(r)\), respectively. Based on the methodology introduced by [PERSON] and [PERSON] [31], we estimate \(F_{1}(r)\), \(F_{2}(r)\) and \(F_{3}(r)\). \(F_{1}(r)\) represents the average time spent by each passenger when using a specific route set. If the respective average traveling time is big, \(F_{1}(r)\) has a small value; otherwise, its value is big. To estimate \(F_{1}(r)\), one has both to calculate the average traveling time and determine whether the calculated value can be considered as \"big\" or \"small\". Estimating \(F_{1}(r)\) is performed according to the following steps:  
1 st Step: For every node pair (\(i\),\(j\)) and a given route set \(r\) the in-vehicle travel time \(IVT_{i,j}(r)\) is computed by determining the smallest time in which a passenger can travel from node \(i\) to node \(j\) using the routes of the \(r\)th transit route set. Traveling time \(T_{p}(r)\), on a path \(p\), is calculated using the next mathematical formula:  
\[T_{p}(r)=\ \sum_{\forall a\in p}t_{a}+nU \tag{5}\]  
where \(t_{a}\) is the traveling time to node \(\alpha\) starting from the previous node of the path, \(n\) is the number of transfers involved in path \(p\) and \(U\) is a time penalty paid for each transfer. In the current approach, parameter \(U\) is set to 5 min, as proposed in [25; 26; 31; 37] and [43]. \(IVT_{i,j}(r)\) is the smallest \(T_{p}(r)\) of all possible paths connecting nodes \(i\) and \(j\). 2 nd Step: The absolute minimum traveling time \(minT_{i,j}\) between nodes \(i\) and \(j\) is calculated. This parameter is determined totally by the road network and neither by the route set nor the respective transfer delays. 3 rd Step: Index \(f_{i,j}(r)\) is determined by comparing traveling time \(minT_{i,j}\) with the respective \(IVT_{i,j}(r)\). Its value indicates whether \(IVT_{i,j}(r)\) is \"big\" or \"small\".