# 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
Index\(f_{i,j}(r)\) is estimated by the next mathematical formula:  
\[f_{i,j}(r)=\ \left\{ \begin{array}{cc}-\Big{(}\frac{b_{1}}{x_{m}}\Big{)}x^{2}+b_{1 }x+\ K_{1},&0\leq x\leq x_{m}\\ 0,&x>x_{m}\end{array} \right. \tag{6}\]  
where \(x=IVT_{i,j}(r)-minT_{i,j}\), \(x_{m}\) is the upper limit value of \(x\), \(K_{1}\) is a positive user-defined parameter which defines the maximum value of \(f_{i,j}(r)\) and \(K_{1}/x_{m}\leq b_{1}\leq 0\). Index \(f_{i,j}(r)\) is then used in order to calculate the value of \(F_{1}(r)\) as follows:  
\[F_{1}(r)=\ \frac{\sum_{\forall(i,j)\in S_{r}}d_{i,j}f_{i,j}}{\sum_{\forall(i,j) \in S_{r}}d_{i,j}} \tag{7}\]  
where \(S_{r}\) is the set of node pairs (\(i\),\(j\)) for which transfer demands, \(d_{i,j}\), are satisfied by route set \(r\). One must notice that calculating the minimum time using Equation (7) is not so obvious, since different results may appear if someone considers transfer times or not. The selection of a route by a passenger may be done either without considering possible transfer delays (method A) or by considering all delays introduced by possible transfers (method B). We decided to examine both route evaluation methods and concluded that method B is much more computational demanding. Consequently, we used method A to evaluate routes during the execution of the algorithm and, then, the resulting route sets were also evaluated with method B, as it is obvious that this method is used in the published literature ([13; 25; 37]). \(F_{2}(r)\) represents the percentage of passengers traveling to their destination from their origin directly by making a single transfer or by making two transfers. Estimating \(F_{2}(r)\) is realized by the next mathematical formula:  
\[F_{2}(r)=\ \frac{K_{2}-b_{2}a}{a^{2}}d_{T}^{2}(r)+b_{2}d_{T}(r) \tag{8}\]  
where \(K_{2}\) is a positive user-defined parameter which defines the upper limit of \(F_{2}(r)\), \(K_{2}/\alpha\leq b_{2}\leq 2\cdot K_{2}/\alpha\) and \(\alpha\) is the upper limit of \(d_{T}(r)\); \(d_{T}(r)\) is estimated by the following formula:  
\[d_{T}(r)=a\cdot d_{0}(r)+b\cdot d_{1}(r)+c\cdot d_{2}(r) \tag{9}\]  
where \(d_{0}(r)\), \(d_{1}(r)\), \(d_{2}(r)\) are the percentages of passengers who travel from their origin to their destination directly, with one transfer or with two transfers, respectively. Parameters \(a\), \(b\) and \(c\) are determined by the user (\(a\geq b\geq c\)). They represent the respective importance of the ways in which the demand should be satisfied in a qualitative route set, for example, trying to have a low percentage of intermediate transfers may lead to a larger average travel time. \(F_{3}(r)\) represents the percentage of passengers who are not able to go from their origin to their destination by route set \(r\), and it is estimated as follows:  
\[F_{3}(r)=\ -(b_{3}+\ K_{3})\cdot d_{unsat}^{2}(r)+b_{3}\cdot d_{unsat}(r)+\ K_{3} \tag{10}\]  
where \(K_{3}\) is a positive parameter determined by the user, defining the upper limit of \(F_{3}(r)\); \(-K_{3}\leq b_{3}\leq 0\); and \(d_{unsat}(r)\) is the percentage of total transit demand which cannot be satisfied by route set \(r\).