# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 1 Introduction  
Routing in road networks is a well-studied topic with a plethora of real world applications. Services such as Google, Baidu, Yandex, Bing, Apple or HERE Maps are ubiquitous and used by millions of users on a daily basis. The core problem is to compute the fastest route between a source and a target. The idealized problem can be formalized as the classic point-to-point shortest path problem. Streets are modeled as arcs. Street intersections are modeled as nodes. Travel times are modeled as scalar arc weights. Unfortunately, this idealized view does not model certain important real world effects. An example are recurring commuter congestions. In this article, we consider an extended problem in which travel times are time-dependent. The travel time of an arc is a function of the moment where a car enters the arc. Figure 1 depicts an example. Computing shortest-paths using [PERSON]'s [1] algorithm is possible both in the classical and in the time-dependent setting. However, for many applications, its running time is too  
Figure 1: The graph of a small road network with predicted travel times for each road segment. large. To achieve fast running times, a two-phase approach is used. In the first phase, the _preprocessing_ phase, an index is constructed. The index only depends on the road networks and the arc travel times. In the second phase, the _query_ phase, shortest paths are computed utilizing this index. An important ingredient for many two-phase techniques [2; 3; 4; 5; 6] are _shortcuts_. Shortcuts are additional arcs introduced during preprocessing, which bypass parts of the input graph such as in Figure 2a. The weight of a shortcut is set to the length of the shortest path between its endpoints. When computing shortest paths, only few shortcuts are explored instead of many arcs in the input graph. The path represented by a shortcut can be obtained lazily, for example by running local Dijkstra searches [7] or iterating over possible middle nodes when shortcuts always represent two other (shortcut) arcs [5; 6]. This approach has been extended to the time-dependent setting [8; 9]. Shortcuts are no longer associated with scalar weights. Instead, _travel time functions_ are used that map the entry time into a shortcut to the travel time through it. Typically, these functions are represented as piecewise linear functions. They are stored as a sequence of _breakpoints_. Unfortunately, these functions can become very complex. Computing and storing them is expensive. The number of breakpoints in a shortcut's function practically corresponds to the accumulated number of breakpoints of the functions of bypassed arcs. Contrary to the classic setting, shortcuts aggregate the complexity of paths they represent, rather than skipping it. This leads to slow preprocessing and prohibitive memory consumption. In this paper, we explore an alternative approach to shortcut travel time functions. Rather than explicitly storing them and obtaining paths lazily, we store paths and obtain travel times lazily. We expect that the shortest path between two nodes changes less frequently than the travel time. Intuitively, going via a highway may be slower due to congestion but is usually still the fastest option. Consider the functions \(f\) and \(g\) in Figure 2b. These functions are travel time functions of two paths between the same endpoints and have many breakpoints. If we want to store the travel time function of a shortcut between these endpoints, we need to store the function \(h=\min(f,g)\). Storing \(h\) explicitly requires roughly a number of breakpoints proportional to the number of breakpoints in \(f\) and \(g\). However, if we only store which path is the fastest, we only need to store the points in time when the faster path switches. We expect significantly fewer switches than breakpoints.