Journey planning in delay prone Public Transit Networks

In this thesis, we study the journey planning problem in the context of transit networks. Given the timetable of a schedule-based transportation system (consisting, e.g., of trains, buses, etc), the problem seeks journeys optimizing some criteria, that is it asks to answer to natural queries such as, e.g., “find a journey that starts from a given source stop and arrives at a given target stop as early as possible”. The solution to this problem exhibiting the smallest query times is the algorithmic framework named Public Transit Labeling (ptl), proposed for the first time in [Delling et al., SEA 2015]. Said method consists of three main ingredients: i) a graph-based representation of the schedule of the transit network; ii) a labeling of such graph encoding its transitive closure (computed via a time-consuming preprocessing); iii) an efficient query algorithm exploiting both i) and ii) to answer quickly to queries of interest at runtime. Unfortunately, while transit networks’ timetables are inherently dynamic (they are often subject to delays or disruptions), ptl is not natively designed to handle updates in the schedule: even after a single change, precomputed data may become outdated and queries can return incorrect results. This is a major limitation, especially when dealing with massively sized inputs (e.g. metropolitan or continental sized networks), as recomputing the labeling from scratch, after each change, yields unsustainable time overheads that are not compatible with interactive applications. Contrary to this, there are solutions to handle dynamic timetables, however, their query times are very high as compared to that of ptl. In this work, we introduce a new framework that extends ptl to function in delay-prone transit networks. In particular, we provide a new set of algorithms able to update both the graph and the precomputed labeling whenever a delay affects the network, without performing any recomputation from scratch. We demonstrate the effectiveness of our solution through an extensive experimental evaluation conducted on real-world networks. Our experiments show that: i) the update time required by the new algorithms is, on average, orders of magnitude smaller than that required by the recomputation from scratch via ptl; ii) the updated graph and labeling induce both query time performance and space overhead that are equivalent to those that are obtained by the recomputation from scratch via ptl. This suggests that our new solution is an effective approach to handle the journey planning problem in delay-prone transit networks.