Multi-level Partitioning Algorithms & Reliability Analysis for Transit Networks

Abstract

Public transit systems are an indispensable part of any metropolitan city. Its success depends on many factors, chief among which is the ease with which users can query for optimal journeys using mobile apps. Conventional approaches model the transit network as a time-expanded or time-dependent graph and run a variant of the Dijkstra's algorithm. However, this method turns out to be too slow for large networks. Furthermore, while planning a journey using public transit, besides travel time, the number of transfers is equally important. To address these problems, several multi-criteria journey planning algorithms such as Round-based Public Transit Routing (RAPTOR), Transfer Patterns, and Trip-based Public Transit Routing (TBTR) have been designed in the past decade.

The thesis proposes several modifications to the TBTR algorithm in order to achieve faster queries. Specifically, building on the premise of the range TBTR (rTBTR) problem which finds the optimal journeys departing within a certain time window, we introduce a new One-To-Many rTBTR. Empirical results show that, for one-to-many range queries, our implementation reduces the query times by approximately 70--80\% compared with repeated application of rTBTR. It helps in scenarios where users query for the shortest paths between two geographical locations (instead of two stops) since a location can have multiple nearby stops.

Although algorithms such as TBTR and RAPTOR are efficient, they can be speeded up using partitioning-based techniques. To this end, we propose HypTBTR to efficiently solve the bicriteria shortest paths by combining TBTR with a partitioning-based speed-up. We also explore how multi-level partitioning of hypergraphs derived from the transit networks can be used to reduce preprocessing times. The proposed upgrades make the TBTR algorithm practical for large-scale applications. The benefits of our approach are demonstrated using several country-level open datasets. For one-to-one shortest path queries, HypTBTR is 30--40% faster than the TBTR algorithm. Multi-level partitioning in NHypTBTR was found to reduce the preprocessing time by approximately 20--50% on our test networks. The thesis also analyzes the effect of different hypergraph partitioning algorithms such as hMETIS and KaHyPar along with the effect of different weighting schemes on the algorithm's performance.

Lastly, the thesis presents an empirical case study demonstrating another real-world application of journey planning algorithms. We study the problem of unreliability in the transit systems, which is one of the main contributing factors behind the decline in transit ridership. We empirically quantify unreliability by evaluating the difference between the scheduled timetables and the actual operations using the Intelligent Transportation System (ITS) data from Bangalore Metropolitan Transport Corporation (BMTC). Our findings can help transit operators create realistic schedules that are easy to adhere to. We also explore how differences in scheduled and actual trips translate to changes in travel time at a source-destination level. Since transit itineraries often involve transfers, departures from schedules can lead to missed connections and longer out-of-vehicle travel times. Using RAPTOR, we queried over a million bi-criteria shortest paths on one day of ITS data. The results show that an average travel time difference of about 17% at the trip level can result in approximately 50% longer journeys for popular source destinations.