Dynamic Public Transit Labeling

摘要

We study the journey planning problem in transit networks which, given the timetable of a schedule-based transit system, asks to answer to queries such as, e.g., 'seek a journey that arrives at a given destination as early as possible'. The state-of-the-art solution to such problem, in terms of query time, is Public Transit Labeling (ptl), proposed in [Delling et al., SEA 2015], that consists of three main ingredients: (i) a graph data structure for storing transit networks; (ii) a compact labeling-based representation of the transitive closure of such graph, computed via a time-consuming preprocessing routine; (iii) an efficient query algorithm exploiting both graph and precomputed data to answer quickly to queries of interest at runtime. The major drawback of ptl is not being practical in dynamic scenarios, when the network's timetable can undergo updates (e.g. delays). In fact, even after a single change, precomputed data become outdated and queries can return incorrect results. Recomputing the labeling-based representation from scratch, after a modification, is not a viable option as it yields unsustainable time overheads. Since transit networks are inherently dynamic, the above represents a major limitation of ptl. In this paper, we overcome such limit by introducing a dynamic algorithm, called D-PTL, able to update the preprocessed data whenever a delay affects the network, without recomputing it from scratch. We demonstrate the effectiveness of D-PTL through a rigorous experimental evaluation showing that its update times are orders of magnitude smaller than the time for recomputing the preprocessed data from scratch.