# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
To identify these parts, we merge the first function's lower bound with the second function's upper bound and vice versa. Where the bounds overlap, an intersection might occur. We then obtain the exact functions in the overlapping parts using Algorithm 4 and perform the exact merging. To obtain approximated upper and lower bounds of the merged function, we merge both lower bounds and both upper bounds (see Figure 5 for a visualization). We approximate whenever a function has more than \(\beta\) breakpoints after merging. This includes already approximated functions. Both \(\beta\) and the maximum difference \(\epsilon\) are tuning parameters which influence the performance (but not the correctness). We evaluate different choices in Section 3.3.1. ### Queries

#### 2.4.1 Earliest Arrival Queries

Recall that, for an earliest arrival query, we are given a source node \(s\), a target \(t\) and a departure time \(\tau\) from \(s\). The goal is to obtain the earliest arrival at \(t\). Compared to a standard (C)CH query, our query algorithm has to deal with two challenges. First, we cannot simply perform a backwards search, as we do not know the arrival time at the target node. Second, to evaluate the travel time of a shortcut, we need to obtain the path in the original graph which is an expensive operation. To address the first challenge, the query is split in two phases. In the first phase we obtain a subgraph on which we can run a forward-only Dijkstra-like search in the second phase. We now present the basic query algorithm and later introduce optimizations to address the second challenge. In the first phase, the union of the subgraphs reachable through arcs to higher ranked neighbors from \(s\) and \(t\) is obtained. We construct these subgraphs by traversing the elimination tree starting from both \(s\) and \(t\) to the root and marking all encountered arcs as part of the search space. The backward search from \(t\) maintains parent pointers to represent the subgraph: For each encountered arc \(uv\) (where \(v\) has the higher rank), we store the arc id and the tail \(u\) at \(v\). This allows efficiently traversing these downward arcs in the

Figure 5: Merging approximated travel time functions by reconstructing the exact functions where bounds overlap. forward-only Dijkstra in the second phase. In the second phase, we run [PERSON]'s algorithm on the combined search spaces. Shortcut travel times are evaluated with Algorithm 2. By the construction of CH, the search space contains the shortest path, thus [PERSON]'s algorithm will find it and this algorithm will determine the correct earliest arrival at \(t\). However, the search space is bigger than strictly necessary. This slows down the query. In the next paragraph, we discuss how to construct smaller subgraphs using an elimination tree interval query. **Elimination Tree Interval Query** The elimination tree interval query is a bidirectional search starting from both the source node \(s\) and the target node \(t\). It constructs a smaller subgraph for the second phase. We denote this subgraph as a _shortest path corridor_. Node labels contain an upper \(\overline{t}_{v}\) and a lower bound \(\underline{t}_{v}\) on the travel time to/from the search origin and a parent pointer to the previous node and the respective arc id. The bounds \(\overline{t}_{s}\), \(\overline{t}_{t}\), \(\underline{t}_{s}\), \(\underline{t}_{t}\) are all initialized to zero in their respective direction, all other bounds to infinity. We also track tentative travel time bounds for the total travel time from \(s\) to \(t\). For both directions, the path from the start node to the root of the elimination tree is traversed. For each node \(u\), all arcs \(uv\) to higher ranked neighbors are relaxed, that is checking if \(\overline{t}_{u}+\overline{b}_{uv}<\overline{t}_{v}\) or \(\underline{t}_{u}+\underline{b}_{uv}<\underline{t}_{v}\) and improving the bounds of \(v\) if possible.