# Multicriteria Route Planning for In-Operation Mass Transit under Urban Data
## 4 Multicriteria Route Planning for Mass Transit
### The Algorithm
Although BiasSpan and other comparative methods gain similar performance for route length and especially the PF of route in small-scale region, the chasm takes place in a larger region, where the length for _Distance-A\({}^{*}\)_ and _[PERSON]'s_ is two to three times longer than the one for BiasSpan, and, at the same time, the value turns out to be around four to six for _BFS_, _Best-First_, and _PF-A\({}^{*}\)_. Finally, the length of the route generated by _IDDFS_ is eight times longer than the one generated by BiasSpan. When a larger region is given, more than half of the queries of _IDDFS_ cannot successfully generate a route in time. As both _Distance-A\({}^{*}\)_ and _[PERSON]'s_ focus on retrieving a solution simply seeking the best performance in shortening the length of route, they turn out to ignore another objective in this multicriteria routing problem. Precisely, they indeed somewhat successfully suggest a trajectory that connects each pair of the stations with a lower cost compared to the other algorithms. Unfortunately, due to the nature of the iterative routing process where an adopted algorithm is conducted from station to station without proper serialization in the order of stations, these two methods, in the end, return a route with lower quality in the criterion of cost (length). For instance, given three or more stations during route construction, _Distance-A\({}^{*}\)_ and _[PERSON]'s_ algorithms may create a crooked or even zigzagging trajectory (e.g., hairpin shape or switchback) while trying to connect all these stations successively. In contrast, by adopting the multisource bidirectional spanning technique, BiasSpan is able to plan smooth, efficient routes with minimal turns and disruptions. Meanwhile, since _Best-First_ and _PF-A\({}^{*}\)_ focus on the efficacy of PF, it seems that they both fail to address the length of the route and thereafter generate trajectories that connect and make several successive detours in small regions, especially in the areas with high potential PF. An intriguing result is that, despite their emphasis on the efficacy of PF, the evaluation shows that _Best-First_ and _PF-A\({}^{*}\)_ both end up with low overall PF performance compared to _Distance-A\({}^{*}\)_ and _[PERSON]'s_. This may be attributed to the nonmonotonicity in heuristic as well as the heterogeneity in urban space. In short, the evaluation confirms that forming trajectories by simply integrating grids is definitely not a feasible approach. #### 5.3.2 Runtime

First of all, BiasSpan is able to responds to queries in the scale of \(10^{-1}\) to \(10^{-2}\) s in small- to middle-scale problem space. Meanwhile, the runtime of comparative methods are at least one logarithmic scale longer than the one of BiasSpan; among them, _IDDFS_ holds the longest runtime apart from Brute-Force and is around two to three logarithmic scales longer than BiasSpan's. This can be attributed to the nature of _IDDFS_, which is a DFS-based routing algorithm. In other words, compared BiasSpan or the other comparative methods, _IDDFS_ could easily end up with exploring regions where no station exists. For other comparative methods, _BFS_, _Best-First_, and _Distance-A\({}^{*}\)_ tend to consume less time compared to _[PERSON]'s_ and _PF-A\({}^{*}\)_ given the same problem space.