Publication Date:
2019-12-18
Description:
This paper studies the journey planning problem in the context of transit networks. Giventhe timetable of a schedule-based transportation system (consisting, e.g., of trains, buses, etc.),the problem seeks journeys optimizing some criteria. Specifically, it seeks to answer natural queriessuch as, for example, “find a journey starting from a source stop and arriving at a target stop as earlyas possible”. The fastest approach for answering to these queries, yielding the smallest average querytime even on very large networks, is the Public Transit Labeling framework, proposed for the firsttime in Delling et al., SEA 2015. This method combines three main ingredients: (i) a graph-basedrepresentation of the schedule of the transit network; (ii) a labeling of such graph encoding itstransitive closure (computed via a time-consuming pre-processing); (iii) an efficient query algorithmexploiting both (i) and (ii) to answer quickly to queries of interest at runtime. Unfortunately, whiletransit 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 majorlimitation, especially when dealing with massively sized inputs (e.g., metropolitan or continentalsized networks), as recomputing the labeling from scratch, after each change, yields unsustainabletime overheads that are not compatible with interactive applications. In this work, we introduce a newframework that extends PTL to function in delay-prone transit networks. In particular, we providea new set of algorithms able to update both the graph and the precomputed labeling whenevera delay affects the network, without performing any recomputation from scratch. We demonstratethe effectiveness of our solution through an extensive experimental evaluation conducted onreal-world networks. Our experiments show that: (i) the update time required by the new algorithmsis, on average, orders of magnitude smaller than that required by the recomputation from scratch viaPTL; (ii) the updated graph and labeling induce both query time performance and space overhead thatare equivalent to those that are obtained by the recomputation from scratch via PTL. This suggests thatour new solution is an effective approach to handling the journey planning problem in delay-pronetransit networks.
Electronic ISSN:
1999-4893
Topics:
Computer Science
Permalink