# Multicriteria Route Planning for In-Operation Mass Transit under Urban Data
## 4 Multicriteria Route Planning for Mass Transit
### The Algorithm
* Iterative Deepening Depth-First Search (IDDFS) [95]--IDDFS acts as a depth-limited version of deep-first search (DFS). Towards the route planning problem, IDDFS is adopted to search for stations iteratively and employed with an increasing value in the setting of depth limit. Precisely, the searching process terminates once IDDFS can reach the stopping criteria where a route with all stations connected is formed under any setting of depth limit. * Best-First Search (Best-First)--similar to the concept of BFS towards the routing process, Best-First explores the adjacent candidate with the highest PF iteratively. As a somewhat greedy algorithm focusing on the local optimal, the searching process terminates until a legal route is suggested. * Distance-Based A* (Distance-A*)--the A* algorithm [25] is adopted with a heuristic emphasizing the distance between the candidate grid and the destination. * Passenger-Flow-Based A* (PF-A*)--similar to Distance-A*, the A* algorithm here is adopted with a heuristic that predicts the PF between the candidate grid and the destination based on the pre-trained PF inference module introduced in Section 3.1. * Brute-Force (BF)--acting as a baseline method, BF systematically enumerates all possible combinations in the problem space, and then the solution that retains the Pareto optimal among all enumerated candidate solutions is retrieved. In accordance with our optimization objectives, which refer to reaching the Pareto-optimal between the PF and the cost of route, the PF and the cost will be reported along with an index of \"PF per unit length\" (or \"unit PF\"). It is worth mentioning that this \"unit PF\" index is one of the evaluating criteria in mass-transit planning according to our interview with civil servants in the Tainan City Bureau of Transportation; however, this is not one of the formulated optimization objectives concerning the multicriteria characteristic of the targeted research problem. The evaluation is based on 1000 randomly generated testing cases under various user-constrained settings. All methods are implemented in Java with a single core of an Intel i7-7700 [EMAIL_ADDRESS] GHz with 16 GB of RAM. To accommodate real-world scenarios, queries executed for over 20 min are identified as failures. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**City** & \multicolumn{2}{c}{**Tainan**} & \multicolumn{2}{c}{**Chicago**} \\ \hline
**Projection** & **EPSG:3857** & **EPSG:4326** & **EPSG:3857** & **EPSG:4326** \\ \hline Upper bound & 2,685,908.464 & 23.4448777 & 5,173,573.713 & 42.08402107 \\ Lower bound & 2,616,308.464 & 22.8700296 & 5,106,973.713 & 41.63844856 \\ Right bound & 13,433,041.310 & 120.6710632 & 9,7



### Evaluation of BiasSpan against Comparative Methods

The BiasSpan and comparative route-planning algorithms are performed under different user-constrained settings, including various area ranges and the number of must-visit stations. In this section, PF and length for each method is divided by the corresponding value of BiasSpan into a \"PF ratio\" or \"length ratio;\" and the unit PF for each method is divided by the value of BiasSpan into a unit PF ratio. The optimization criteria, the unit PF ratio, and runtime among all the methods are then compared. The Pareto-efficient frontier and solutions under different area ranges are illustrated in Figure 4. The evaluation results for the optimization criteria including PF and length of route are illustrated in Figures 5-8 for Chicago and Tainan datasets respectively. The PF ratio, length ratio, unit PF ratio, and runtime by varying area range (Figures 5, 6, 9 and 10) and the number of must-visit stations (Figures 7, 8, 11 and 12) are then compared. Detailed performance for Brute-Force are not depicted in Figures 5-8 since it can only obtain solutions for very small ranges (<1 km\({}^{2}\)).