# Multicriteria Route Planning for In-Operation Mass Transit under Urban Data
## 1 Introduction  
Constrained planning is ubiquitous in urban design [1]. Many automatic planning or artificial intelligence tasks involving assigning values to variables that are subject to a set of constraints could be formulated as a constraint-satisfaction problem (CSP) [2]. Among CSPs, multicriteria constrained route planning turns out to be one of the most significant research topics with broad applications, especially in the field of transportation [3; 4; 5; 6; 7; 8], in which the algorithms often have specific or defined heuristic functions. This research focuses on nonmonotonic multicriteria route planning in urban space, by deploying additional transportation routes for in-operation public transit systems. Employing new services for an in-operation mobility system such as bus or light rail is difficult and time-consuming for governments or public transportation authorities. To be more explicit, factors including, but not limited to, the potential passenger flow (PF), social welfare, road network structure, and fuel consumption need to be considered for this newly deployed service. Furthermore, how to address the transfer as well as competitive relationship between this new service and other existing routes is complex and difficult to quantify. Indeed, even though there are various well-developed traffic planning software (e.g., VISUM, EMME), it is still difficult for authorities to either provide quantitative analysis or present near-optimal plans in a timely manner due to specific requests. Designing an intelligent route planning algorithm that effectively combines multicriteria factors is also quite challenging. During the route construction process, when an algorithm selects the areas for forming a new route, it will encounter a severe problem: the potential PF of a new route is not monotonic. That is, by viewing the process and the structure of this newly growing route as a spanning tree, instead of increasing the potential profit, adding a new area for this route to cruise might decrease its overall PF as a result of the relationship with in-operation routes and the complex urban functionalities. For instance, a new route with adequate intersections towards the in-operation service canbring passengers to transfer across routes. This not only results in a higher PF, but also enhances the social welfare. On the contrary, when a new route has indistinct boundary against other in-operation services' areas, its PF could conversely decrease. That is, those who need this service in certain areas with less accessibility cannot benefit from this new deployment, and passengers simply take the original route instead of this new service; both of which thereafter makes this deployment a waste of resources. In this work, considering the complex correlations between locations and stations (e.g., transferring between routes) and heterogeneous urban functions (e.g., the security/scenery of surroundings), an effective route-planning method is proposed to deal with the nonmonotonic multicriteria scenario. Towards the targeted nonmonotonic multicriteria constrained route planning problem, this paper first harvests heterogeneous input features from Open Street Map (OSM) as well as open data platforms from governments, and then adopts a PF inference [9] for the proposed Multisource Bidirectional Gaussian-Prioritized Spanning Tree (BiasSpan). Precisely, the input constraints from authorities/users include a range on the map, a set of must-visit stations to deploy, maximum length of route, and a number of additional stations to be deployed, and BiasSpan accordingly suggests a route with maximized PF along with a near-optimally minimized cost.