# Multicriteria Route Planning for In-Operation Mass Transit under Urban Data
## 4 Multicriteria Route Planning for Mass Transit
### The Algorithm
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Instance\textbackslash\textbackslash\textbackslash\textbackslashbackslash\textbackslashbackslashbackslash\textbackslashbackslashbackslash\textbackslashbackslash\textbackslashbackslash\textbackslashbackslash\textbackslashbackslash\textbackslash\textbackslashbackslash\textbackslashbackslash\textbackslash\textbackslashbackslash\textbackslashbackslash\textbackslash\textbackslashbackslash\textbackslash\textbackslashbackslash\textbackslash\textbackslashbackslash\textbackslash\textbackslash\textbackslashbackslash\textbackslash\text



To be more explicit, experimental results on the runtime shown in Figures 9-12 meet our estimate that, for BiasSpan, its time complexity is mainly related to the size of problem space. Meanwhile, BiasSpan holds a runtime that outperforms most of the comparative methods for at least one logarithmic scale and is close to _Best-First Search_ and _Distance-A\({}^{*}\)_. #### 5.3.3 Trade-Off between Profit and Cost

Accordingly, BiasSpan sacrifices some PF to secure the length of route; to be more precise, this trade-off is valued considering the pessimism about the error as well as the uncertainty in PF. Since the PF itself is an inferred value with RMSE as described in previous evaluations, even if the route-planning algorithm retains a solution with an outstanding PF, the exact efficacy for the route (solution) been deployed in real-world scenario rather than in this ideal evaluation scenario is referable yet uncertain. In contrast, the criterion of length of route turns out to be much more reliable since there is less error in the cost for construction, maintenance, and fuel consumption between real-world scenario and our evaluation. Nonetheless, the evaluation still demonstrates the adaptability of our proposed BiasSpan in overall performance and the ability to deal with the trade-off between PF and length of route. Despite the discussion of reliability and error in objectives, the concept of the hypervolume (HV) is adopted to evaluate the performance of methods under the multicriteria scenario. As the calculation of HV asks for a reference point with its performance worse than the nadir point in the original Pareto set for all objectives [96], and to better exemplify the analysis, the nondominated solutions from all solutions retained by different methods are illustrated in Figure 13, where both objectives, PF and inversed length, are normalized and to be maximized. The (0, 0) is then selected as the reference point for calculating HV, which thereafter makes HV to be maximized. The HV obtained by each method is listed in Table 5, where BiasSpan secures the best HV for overall solutions in both datasets. To be more precise, the HV obtained by BiasSpan compared to other methods shows an intriguing trend where BiasSpan has a better performance in middle-scale to large-scale problem spaces in the Chicago dataset, but only retains a better result in a small-scale problem space in the Tainan dataset. Furthermore, _IDDFS_ seems to achieve the best performance in HV in small-scale problem space in Chicago; however, the advantages fall to the _Distance-A\({}^{*}\)_ and _PF-A\({}^{*}\)_ for the best solutions in middle-scale and large-scale Tainan dataset, respectively. This phenomenon may be attributed to the nature of road network in the two cities, where a square structure may enhance a balance exploration in both benefit and cost for the BiasSpan. Explicitly, the distribution of spatial influence in features can be more effectively delivered from the stations to other vertices in the graph through this certain formation of connectivity. Nonetheless, the evaluation results in HV proves

Figure 3:3 Examples of the nondominated solutions (Pareto frontier) among all generated solutions in PF and inversed length for Chicago (**left**) and Tainan (**right**) dataset. Where both objectives are normalized to the maximum value of 1, and are to be maximized. For the hypervolume calculation, the (0, 0) is selected as the reference point.