# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
When the new travel time bounds from an arc relaxation overlap with the current bounds, more than one label has to be stored. As an optimization [28], nodes can be skipped if the lower bound on the travel time to it is already greater than the tentative upper bound on the total travel time between \(s\) and \(t\). After both directions are finished, we have several nodes in the intersection of the search spaces. Where the sum of the forward and backward distance bounds of such a node overlaps with the total travel time bounds, the parent pointers are traversed to the search origin and all arcs on the paths are marked as part of the shortest path corridor. **Lazy Shortcut Unpacking** In the second query phase, we perform [PERSON]'s algorithm on the corridor obtained in the first phase. In the basic query, shortcuts are unpacked completely to evaluate their travel time. However, this may cause unnecessary and duplicate unpacking work. We now describe an optimized version of the algorithm which performs unpacking lazily. The algorithm starts with the same initialization as a regular TD-Dijkstra. All earliest arrivals are set to infinity, except for the start node which is set to the departure time. The start node is inserted into the queue. Then, nodes are popped from the queue until it is empty or the target node is reached. For each node, all outgoing arcs within the shortest path corridor are relaxed. When an arc is from the input graph, its travel time function can be evaluated directly. Shortcut arcs, however, need to be unpacked. The lazy unpacking algorithm defers as much work as possible: Only the first arc of the triangle of each shortcut will be recursively unpacked until an input arc is reached, the second arc will be added to the corridor. Figure 6 shows an example. This way, we unpack only the necessary parts and avoid relaxing arcs multiple times when shortcuts share the same paths. **Corridor A*** The query can be accelerated further, by using the lower bounds obtained during the elimination tree interval query as potentials for an A*-search. For nodes in the

Figure 6: Lazy relaxation of arc \(uv\). Since \(uv\) is a shortcut, it needs to be unpacked. This causes \(uv\) to be added to the corridor and \(uu\) to be relaxed. Relaxing \(uw\) causes \(xw\) to be added to the corridor and \(ux\) to be relaxed. In this example, \(ux\) is an original arc and the recursion stops. \(xw\) will be relaxed (or unpacked) only once \(x\) is popped from the queue. CH search space of \(t\), the lower bounds from the backward search can be used. For nodes in the CH search space of \(s\), we start at the meeting nodes from the corridor search and propagate the bounds backwards down along the parent pointers. This yields potentials for all nodes in the initial corridor. However, we also need potentials for nodes added to the corridor through unpacking. These potentials are computed during the shortcut unpacking. When unpacking a shortcut \(uv\) into the arcs \(uw\) and \(wv\), then \(\rho(w)\) will be set to \(\min(\rho(w),\rho(v)+\underline{w}_{wv})\). Justifying that A* with these potentials will always find the correct earliest arrival is surprisingly non-trivial. In fact, these potentials are not _feasible_ in the sense that \(\forall\tau\in T,uv\in A:f_{uv}(\tau)-\rho(u)+\rho(v)\geq 0\)[10]. Figure 7 shows an example where the term becomes negative and the same node has to be popped several times from the queue. Assume that all arcs have a constant travel time for the departure time of this query and lower bounds are equal to the travel time. The exception is \(v_{3}t\) which has constant travel time 100 during this query but the lower bound is zero. We use zero weights to simplify the example. They are not strictly necessary for such an example. The shortest path from \(s\) to \(t\) is \([s,w_{2},w_{1},v_{2},t]\) and has length 22. After \(s\) is settled, the queue will contain \(v_{3}\) with key \(1+0\) (distance plus lower bound to \(t\)), \(v_{1}\) with key \(1+2\) and \(w_{2}\) with key \(1+21\).