# Time-Dependent Alternative Route Planning: Theory and Practice +
## 4 Experimental Evaluation
### Experimental Results  
Our bit-level data compression technique (cf. Section 3.1) was found to be beneficial. The byte-based approach of CFLAT [21] for the succinct representation of the travel-time summaries of 2000 landmarks chosen with SR (SR2K) consumed space of 5.2 GB in Berlin, 53.6 GB in Germany, and 107.2 GB in Europe. Using the new profiling, the bit-level based approach of TDAG, the preprocessed data for SR2K landmarks consumed space of 0.28 GB in Berlin, 3.2 GB in Germany, and 31.05 GB in Europe. That is, the exploitation of the bit-level representation of a sparse matrix, without sacrificing the landmark and node indexing, leads to a significant reduction of about 70% in space requirements, which, in turn, allows for the selection of larger landmark sets--especially for continental-size instances. In Tables 1 and 2, we report the results of our experimental evaluations of TDAG on the approximation accuracy _RelativeError_ (relative error in %) and the various quality indicators (To simplify the notation, we omit, in the rest of the paper, the departure time \(t\) notation.) (cf. Section 2): \(targetFunction\)\((TargetFunction)\), \(totalDistance\)\((TotDist)\), \(averageDistance\)\((AvgDist)\), and \(decisionEdges\)\((DecEdges)\). Similar to [11], in order to evaluate the quality of the constructed alternative graph, the aggregate quality indicator \(TargetFunction\) is used, which is defined as follows:  
\[TargetFunction=totalDistance+1-averageDistance\]  
In all our experiments, the resulting alternative graphs were evaluated using the following constraints: \(maxStretch\leq 1.2\), \(averageDistance\leq 1.1\), and \(decisionEdges\leq 10\). In the path pruning step, multiple choices on penalty constants were tested. The best results were achieved by selecting up to \(p_{c}=0.3\) and \(r_{c}=0.1\). Table 1 demonstrates the effect of the parameter \(N\) on the execution time of TDAG, as well as on the quality of the constructed AG. As \(N\) grows, PHASE 1 becomes computationally more expensive; however, the relative error rapidly drops towards 0 for BE and GE. This is due to the fact that, as \(N\) increases, the expanded (forward) TDD tree becomes larger, the resulting \(od\)-paths increase in number, and we also obtain more candidate \(od\)-paths providing an AG of better quality. Figure 4 shows the quality (targetFunction) and run time performance of TDAG with respect to the number \(|L|\) of landmarks and the selection of \(N\) for GE. Each increase of the targetFunction depends on collecting and processing a larger number of candidate alternative paths between origin \(o\) and destination \(d\), which, in turn, requires a higher computation time. However, by increasing either \(|L|\) or \(N\), the error is reduced. The targetFunction obtains higher values either by a long TDD tree step or by a long predecessor tree step. The first case happens when \(|L|\) is smaller--where landmarks are more distant from each other. The second case happens when \(|L|\) is larger--where landmarks are less distant from each other. As for EU, the relative error seems to stop at 0.55 due to the steepest slopes of the earliest-arrival-time functions (which necessitate an increased number of sampled departure times during the preprocessing phase), the propagation of floating point rounding errors along the arcs of long paths, and the smaller density \(|L|/|V|\) of the preprocessed landmarks, compared to the instances of BE and GE. All these issues can be tackled by affording more memory for the computations. In Table 2, we present the results of the baseline approaches and their comparison to TDAG. DPP is a combination of the Plateau and the Penalty methods [7], which collects and evaluates the candidate \(od\)-paths using a greedy selection approach. In our time-dependent context, [PERSON]'s algorithm was replaced by its time-dependent variant, TDD. APP is, again, a combination of the Plateau and Penalty methods of [7, 11], which uses the ALT pruner and filtering approach [11].