# Multicriteria Route Planning for In-Operation Mass Transit under Urban Data
## 4 Multicriteria Route Planning for Mass Transit
### The Algorithm
### Summary of the Properties of BiasSpan

1. BiasSpan employs GMM to deal with nonmonotonic gain function;
2. The size of problem space for the algorithm is reduced based on the grid-like graph;
3. BiasSpan prunes the searching space with a bidirectional goal-prioritized technique;4. The herding effect (crowding-out effect) in station recommendation is neutralized by the adopted GMM with negative feedback. Apparently, there is no optimal solution to this multicriteria problem due to the trade-off between PF and length. Nonetheless, solutions are still expected to be provided by our proposed BiasSpan in a Pareto-optimal sense. Additionally, it is worth noting that although the implementation and the evaluation of the proposed BiasSpan are based on the constrained route planning for buses, where a new bus route is constrained by an existing road network and its revenue comes from fixed fares, this algorithm is still applicable for other types of mass transit. For instance, when applied to railroads, which are usually located underground but need to avoid existing pipes, a grid-like graph that avoids existing pipes and considers multiple layers could be constructed. Therefore, an unwanted collision could be prevented. Meanwhile, features needed to be considered, e.g., transference between existing routes, can still be stored in a grid-like graph for further inference. ### Time Complexity

The targeted multicriteria nonmonotonic constrained route planning problem can be first simplified as a multiple-choice branching problem to explore its time complexity. The multiple-choice branching problem is defined to search for a subset \(A^{\prime}\)\(\in\)\(A\) in a directed graph \(G=(V,A)\) with a partition of \(A\) into disjoint sets \(A_{1}\), \(A_{2}\),..., \(A_{m}\). Meanwhile, the sum of weights in subset \(A^{\prime}\) is larger than a given positive integer \(K\), so that \(A^{\prime}\) contains no cycles and at most one arc from each partition. Next, the \"multiple choice branching\" problem can be reduced into a 3-SAT problem, ends up being NP-Complete [91,92]. Furthermore, given that G is a strongly connected graph, it still remains NP-Complete since such a maximum weight branching problem can be viewed as a two-matroid intersection problem [93]. For the trajectory-routing part in BiasSpan, the time complexity turns out to be \(O(EV)\) given that the worst-case scenario is to traverse each grid in all directions. Where \(E\) is the number of maximum directions from one spanning tree (this variable is set to 2 in Algorithm 3, which equals to branching factor in the worst-case scenario), and \(V\) corresponds to the number of grids labelled in the searching area. For other routing algorithms introduced in previous sections, despite most of them turning out to be inapplicable towards solving this research problem or retrieving optimal solutions, the time complexity for brute-force searching is \(O(E^{V})\), [PERSON]'s algorithm and [PERSON]'s algorithm for \(O(EVlogV)\) or \(O(EV+VlogV)\), A* algorithm for \(O(E^{V})\), and bidirectional search for \(O(SEV/S)\). Where \(S\) is the total number of stations, and \(E\) indicates the branching factor. It is worth noting that since \(V\) is far larger than \(S\) as well as \(E\) in most cases, BiasSpan is expected to find approximate solutions in a reasonable time among all the listed algorithms. The schematic search space of different algorithms including the [PERSON]'s algorithm [94], bidirectional search, and BiasSpan is illustrated and compared in Figure 2. Based on the target-prioritized technique based on GMM, BiasSpan is expected to visit fewer candidates compared to bidirectional search. Figure 2: The schematic search space for connecting vertices based on [PERSON]’s algorithm (**left**), bidirectional search (**middle**), and BiasSpan (**right**).