# Multicriteria Route Planning for In-Operation Mass Transit under Urban Data
## 4 Multicriteria Route Planning for Mass Transit
### The Algorithm
## 5 Evaluation

### Dataset and Preprocessing

Two contrasting types (radial and square structure) of in-operation mass-transit networks retrieved from Tainan City Government and Chicago Transit Authority (CTA) are selected as the datasets for evaluation. As we introduced in previous sections, the proposed method is applicable for solving a multicriteria constrained planning problem towards various types of mass-transit systems. For evaluation, the bus-ticket data for Tainan lists the ticket ID, route ID, timestamps, and the starting and ending stations; on the other hand, the transit-ticket data for Chicago records the route ID, timestamps, and the number of passengers. Meanwhile, with 14,336,226 and 231,196,847 ticket records, respectively, for the mass-transit in these two cities, they both hold at least 100 routes and thousands of stations in service. Accordingly, the in-operation mass-transit networks for these two cities under the same scale are shown in Figure 3.

Next, as introduced in Section 3.1, heterogeneous urban information is harvested for constituting the input feature set in the PF inference module. To extract the necessary information, the POI is extracted from the GoogleMap, the road network structure with transportation hierarchy is loaded from the OpenStreetMap, and the population pyramid is fetched from respective agencies. Apart from the static features, the human mobility is represented by the bicycle and taxi record that lists both pick-up and drop-off locations. The size figure for the input instances of the two cities are listed in Table 2.

Meanwhile, the urban spaces of Tainan and Chicago are divided into 505,296 and 330,335 disjoint grids (0.1 km \(\times\) 0.1 km) based on EPSG: 3857, where only 94,282 and 91,320 grids (vertices) would be considered in route recommendation. The ranges in both \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Instance\textbackslash{}Dataset** & **Tainan** & **Chicago** \\ \hline \multirow{4}{*}{Bus data} & Existing routes & 104 & 139 \\  & Existing stations & 6575 & 11,592 \\  & Ticket records & 14,336,226 & 231,196,847 \\  & Period & 1 January 2017-31 December 2017 & 1 November 2017-30 October 2018 \\ \hline Gridization & Grids (0.1 km \(\times\) 0.1 km) & 505,296 & 330,335 \\ \hline \multirow{4}{*}{Features} & POI & 8734 & 21,889 \\  & Bike trips (for human mobility) & 139,478 & N/A \\ \cline{1-1}  & Taxi trips (for human mobility) & N/A & 68,461,612 \\ \cline{1-1}  & Road nodes & 237,866 & 390,509 \\ \cline{1-1}  & Road edges & 414,409 & 560,810 \\ \cline{1-1}  & Census blocks (for population) & 14,730 & 46,293 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Size figures for our input instances. Figure 3: Public transit networks for Tainan (**left**) and Chicago (**right**) on the same scale. EPSG: 3857 and 4326 projection for grid-like graph of two cities are listed in Table 3. The number of grids in both cities are reduced from 72.36% to 81.34% compared to the road network structure in real world. ### Evaluation Setting

Six route-planning algorithms are selected as the comparative methods to search from one must-visit station for another iteratively:

* [PERSON]'s Algorithm ([PERSON]'s) [94]--[PERSON]'s algorithm is performed to search from one must-visit station towards other stations, either a must-visit one or recommended one. The destination then turns out to be the origin of a searching process in the next round for the [PERSON]'s algorithm to look for another stations. As an iterative process, it terminates until a route that connects all stations exactly once is formed. * Breadth-First Search (BFS)--BFS is applied to take turns beginning the searching process from each of the must-visit stations. During the searching process, BFS will iteratively explore the adjacent candidate until there is no candidate that can be reached. Accordingly, the route planning is terminated until BFS successfully visits all the stations at least once, where a linear route is constructed.