# Multimodal Dynamic Journey-Planning +
## 1 Introduction
An actual journey planner is usually in heavy demand--for instance, the journey planner of German railways may receive more than 420 queries per second during peak hours--and the real-time response requirements should be met both for answering queries, as well as for digesting the frequently occurred delays of schedule-based vehicles. Our focus in this work is the multimodal journey-planning problem, for which there exist three main approaches for solving it in the literature [1]. A first approach considers a combined cost function of travel time with penalties for modal transfers (see e.g., [3; 4; 5]). A second approach obtains journeys that explicitly include (or exclude) certain sequences of transportation modes by building upon the label-constrained shortest path problem (see e.g., [6; 7; 8]. A third approach computes Pareto sets of multimodal journeys using a carefully chosen set of optimization criteria that aim at providing diverse (with respect to the transportation modes) alternative journeys (see e.g., [7; 9]). Some of these approaches include flights and car driving in their modeling, both of which are beyond the scope of this paper. In this work we investigate the multimodal schedule-based public transport problem in an _urban_ environment that involves various transport modes (train, bus, tram) along with unrestricted ones with respect to departing time traveling. The latter includes walking and electric vehicles (EVs). The most closely related work to ours is that in [7; 8], which computes multicriteria multimodal journeys. Our prime aim is to investigate whether the recently introduced unimodal dynamic timetable model (DTM) [10], which efficiently handles EA journey-planning queries and updates the underlying timetable information structure in case of delays extremely quickly, can be extended in the multimodal setting and can provide competitive query and update times with respect to state-of-the-art approaches. Our main contribution is _Multimodal DTM_ (MDTM), an extension of the dynamic timetable model (DTM) [10]. MDTM can indeed model multimodal journeys, especially in urban environments, while it simultaneously offers competitive state-of-the-art query times for computing best journeys, as well as extremely fast update times for updating the timetable information in the case of delays. We carried out a comparative experimental study on two metropolitan public transport networks (Berlin and London). Our experimental study showed that our algorithms answer multimodal EA and multicriteria queries very efficiently when public transport (train, bus, tram), along with unrestricted ones with respect to departing time traveling (walking and EVs) is considered, and remain competitive to state-of-the-art approaches even in the case of unlimited walking. In the case of delays, our timetable information structure can be updated in less than 164 microseconds on the largest input instance. The rest of this paper is organized as follows. Section 2 presents preliminary notions and concepts regarding the modeling of timetable information and planning of (multimodal) journeys, as well as a succinct review of DTM. Section 3 presents our new mode, the multimodal DTM, along with its query and update algorithms. Section 4 presents our comparative experimental study on the two metropolitan public transport networks. Conclusions are offered in Section 5. A preliminary version of this work appeared as [11].