# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
Then, \(v_{3}\) will be settled which will insert \(t\) with key \(101+0\) into the queue. Then, \(v_{1}\) will be settled and \(w_{1}\) will be inserted into the queue with key \(3+0\). Then, \(w_{1}\) will be settled even though the current distance of \(3\) is greater than the actual shortest distance of \(2\). This will insert \(v_{2}\) with key \(13+10\) into the queue. Now, \(w_{2}\) will be popped and the distance to \(w_{1}\) will be improved and it will be reinserted into the queue with key \(2+20\). \(w_{1}\) will be popped immediately afterwards which improves the distance and key of \(v_{2}\) which is the next node to be popped from the queue. After it has been processed, the final distance to \(t\) (22) is known, and \(t\) is the final node to be settled. Nevertheless, we claim that once \(t\) is popped from the queue the algorithm always has found the correct earliest arrival. The reason is that for all nodes \(v\) on the shortest path \(\mathrm{ea}_{v}+\rho(v)\leq\mathrm{ea}_{t}\) holds. Since this is the queue key, all nodes on the shortest path will have been popped (possibly several times) before \(t\). Let \(P=[s,\ldots,t]\) be the desired shortest path from \(s\) to \(t\) when departing from \(s\) at \(\tau\) and \(P[v_{\cdot\cdot}]\subset P\) the subpath from a node \(v\in P\) to \(t\). We denote the global lower bound on the travel time between a node \(v\) and \(t\) by \(\underline{f}_{\_{ret}}\) and the lower bound travel time on \(P[v_{\cdot\cdot}]\) by \(\underline{f}_{\_{P}}[v_{\cdot\cdot}]\). For nodes in the initial corridor obtained by the interval query, \(\mathrm{ea}_{v}+\rho(v)\leq\mathrm{ea}_{t}\) always holds because the potential \(\rho(v)\) is set to the global lower bound \(\underline{f}_{\_{ret}}\). However, nodes \(u\) added later to the corridor through unpacking may have a greater potential than \(\underline{f}_{\_{ret}}\), as depicted in the example. However, their final potential cannot be greater than the lower bound of the travel time on the shortest path

Figure 7: Example of a query where our A* potentials lead to a non-label-setting query. Dashed arcs are shortcuts. The shortcut weights are not known to the query algorithm. \(\underline{f}_{p}[u..]\). This is enough to satisfy \(\mathrm{ea}_{u}+\rho(u)\leq\mathrm{ea}_{t}\). In addition, the potential value will be set to this final value before \(t\) is settled. Assume for contraction that \(p_{i}\) is the first node on \(P\) for which this statement does not hold. \(p_{i}\) cannot be a node from the initial corridor. However, \(\rho(p_{i})\) will be set at most to \(\underline{f}_{p}[p_{i}..]\) once \(p_{i-1}\) is settled which by assumption happens before \(t\) is settled. This is a contraction. Thus, \(\mathrm{ea}_{v}+\rho(v)\leq\mathrm{ea}_{t}\) holds for all nodes \(v\in P\) and the query algorithm always finds the correct earliest arrival when terminating once \(t\) is popped from the queue. #### Profile Queries

A profile query asks for the function of the fastest travel time between two nodes over a given time period \(T\). Without loss of generality, we assume that the \(T\) equals the entire time period covered by the input network. As discussed in Section 2.1, such a query can be answered with TD-Profile-Dijkstra. However, TD-Profile-Dijkstra exhibits both prohibitive running time and memory consumption. Consider a path \([v_{0},\ldots,v_{k}]\) where the travel time function of each arc has \(b\) breakpoints. In general, linking two functions \(f\) and \(g\) creates a new function with \(\Theta(|f|+|g|)\) breakpoints. Thus, the travel time function from \(v_{0}\) to node \(v_{i}\) contains \(\Theta(i\cdot b)\) breakpoints. Thus, when applying TD-Profile-Dijkstra to compute the function between \(v_{0}\) and \(v_{k}\), the total memory consumption and the running time grows quadratically with the length of the path. We conclude that Dijkstra-based approaches to profile queries are not a promising direction. The experiments with Dijkstra-based TCH profile queries in [8] support this conclusion.