# Multimodal Dynamic Journey-Planning +
## 1 Introduction  
Mobile and web-based journey planners for scheduled public transport are plentiful, as journey-planning is a prime activity in our everyday lives. A schedule-based public transport system implies the existence of a timetable, dictating the departure and arrival times of the scheduled vehicles. This timetable is provided as input to the _journey-planning_ problem, which asks for computing in real-time answers to the best journey queries: \"Which is the best journey from a station \(X\) to another station \(Y\), provided that a specific passenger wishes to depart at time \(t\)?\". In its simplest setting, the journey-planning problem considers only one mode of transport (i.e., type of vehicle), and thus it is commonly referred to as the _unimodal_ journey-planning problem. Another, more realistic setting is to consider the problem when several different transport modes (metro, bus, tram, train, car, bicycles, EVs, walking, etc.) are combined, in which case the overall problem is referred to as the _multimodal journey-planning_ problem. In that problem, computing the best route implies employing a holistic algorithmic approach, which on the one hand takes into account each individual transport mode, and on the other hand it optimizes their choice and sequence. The uni- or multimodal journey-planning problem specializes in a host of optimization problems, depending on the metric used and the modeling assumptions. There are two core optimization problems when one seeks to find best routes from an origin-station \(X\) to a destination-station \(Y\): (i) The _earliest arrival-time problem_ (EAP), where one seeks to find the best journey from \(X\) to \(Y\) that minimizes the overall travel time to reach \(Y\); (ii) The _minimum number of transfers problem_ (MNTP), where one seeks to find a best journey from \(X\) to \(Y\) that minimizes the total number of vehicle changes required for a passenger in order to reach \(Y\). These two optimization criteria are often considered in combination,giving rise to _multi-criteria problems_. A comprehensive overview on unimodal and multimodal journey planning can be found in [1]. To meet the requirement for answering the best journey queries in real-time, the most commonly used approach for solving unimodal and multimodal journey-planning optimization problems is to carry out a preprocessing stage during which a suitable data structure is created representing the timetable information. Best journey requests are then answered by querying this data structure, and the challenge is that the structure is suitably built so that it subsequently allows for fast answering of queries. Vast literature on this approach can be found at [1] and the references therein. Despite its simple formulation, the journey-planning problem is quite challenging, actually much more than its route-planning counterpart in road networks. The reason is that schedule-based transport possesses an inherent time-dependent component. This requires a complex modeling approach to obtain realistic results, particularly when transfer times among different vehicles should be taken into account [2]. An additional challenge in the unimodal and multimodal journey-planning setting is dealing with the delays of public transport vehicles that unfortunately occur quite often. The prime task is how to efficiently update the underlying data structure representing the timetable information so that the best journey (mostly earliest arrival (EA)) queries are still answered optimally and in real-time with respect to the new (updated after the delays) timetable. Solving the aforementioned challenges as efficiently as possible is crucial, since otherwise the real-time response requirements posed to an actual journey planner cannot be met.