# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data  
The key element of our approach is the information we store with each arc of the augmented graph. We store time-dependent unpacking information, which allows us to efficiently reconstruct the original path represented by a shortcut for a point in time. In (C)CH, shortcuts \(uv\) are inserted when a node \(w\) is contracted and the arcs \(uw\) and \(wv\) exist. Thus, a shortcut \(uv\) always skips over a triangle \([u,w,v]\). However, there may be several triangles and which one is the fastest may change over time. There may also be an arc \(uv\) in the input graph which might sometimes be the fastest path. This is the information our unpacking data structure has to capture. For each arc \(uv\), we store a set of time-dependent _expansions_\(X_{uv}\) for unpacking. Figure 3 presents an example. For an expansion \(x\in X_{uv}\), we denote the time during which \(x\) represents the shortest path as the _validity interval_\(\Pi_{x}\) of \(x\). When formally referring to the path represented by an expansion, we use the _expand function_\(E:X\to V\cup A\). \(E\) either maps to an original arc or to the middle node \(w_{x}\) of the lower triangle \([u,w_{x},v]\). Knowing the middle node for each expansion is also sufficient to obtain longer paths. These can be computed by unpacking shortcuts recursively. In our implementation, the expansion information is represented as an array of triples \((\pi,uw_{x},w_{x}v)\). \(\pi\) is the beginning of the validity interval and \(uw\) and \(wv\) are arc ids. This information can be stored in 16 bytes for each entry--8 bytes for the timestamp and 4 bytes for each arc id. An expansion can also represent an original arc or no arc at all during a certain time interval. Both these cases are represented as special arc id values. Two invalid arc ids indicate no arc at all. One invalid id indicates that the other arc id represents an original arc. Beside the expansions, we also maintain a scalar lower bound \(\underline{b}_{uv}\) and an upper bound \(\overline{b}_{uv}\) on the travel time for each arc. During preprocessing, we have to compute the bounds and expansion sets for each arc in the augmented graph. This is done using the same schema as in CCH. We iterate over all arcs and relax their lower triangles. Algorithm 1 depicts the routine for each triangle. The routine requires travel time functions for all involved arcs. We maintain these functions during preprocessing but discard them later. To relax the lower triangle \([u,w,v]\), the functions \(f_{uw}\) and \(f_{wv}\) are linked and the result is merged with the current function of \(f_{uv}\). Where \([u,v,w]\) is faster, new expansions are inserted into \(X_{uv}\). Where the current \(uv\) travel time is faster, the current expansions are kept. The bounds are updated with the new minimum and maximum of the merged function. Once the unpacking information for an arc is complete, we can use it to compute the arc's travel time, unpack it to the path in the original graph or compute the travel time function for the arc. All these operations follow the same basic schema: Determine the relevant expansions and apply the operation recursively until arcs from the input graph are reached. The simplest case is the travel time evaluation. Algorithm 2 depicts this operation. First, the relevant expansion is determined using binary search. If it points to an original arc, this arc's travel time can be evaluated and returned. If the expansion points to a lower triangle, we first recursively evaluate the first arc of the triangle. Then, the second arc can be evaluated at the entry time plus the travel time of the first arc. ```
1:\(\pi\) = \(\pi\) = \(\pi\) = \(\


```
Input: Preliminaries unpacking data for arc \(uv\): \(X_{uv},\underline{b}_{uv},\overline{b}_{uv}\) and travel time function \(f_{uv}\). Travel time functions of lower triangle arcs \(f_{uw}\) and \(f_{uv}\). Output: Improved data \(X_{uv},\underline{b}_{uv},\overline{b}_{uv}\) and function \(f_{uv}\).