# Time-Dependent Alternative Route Planning: Theory and Practice +
## 4 Experimental Evaluation
### Experimental Setup and Goal  
TDAG was implemented in C++ (GNU GCC version 9.3.0). All the experiments were conducted on an AMD Ryzen Threadripper 3960X 24-Core 3.8 GHz Processor, with 256 GB of RAM, running Ubuntu Linux (20.04 LTS). We used 24 threads for the preprocessing phase of CFLAT [21], using \(\epsilon=0.1\) as the preprocessing precision.  
Three typical benchmark instances for testing speedup techniques and oracles in time-dependent road networks were used in our experiments, kindly provided to us by TomTom and PTV for scientific purposes.  
(BE) The real-world instance of Berlin, provided by TomTom, has 473,253 nodes and 1,126,468 arcs. It is accompanied with arc-traversal-time functions taken from historical data of a working day (Tuesday) in a typical urban environment.  
(GE) The real-world instance of Germany, provided by PTV, has 4,692,091 nodes and 10,805,429 arcs. The arc-traversal-time functions represent a typical working day.  
(EU) The instance of Western Europe, provided by PTV, has 18,010,173 nodes and 42,188,664 arcs. It is a synthetic time-dependent benchmark instance that is typically considered in the related literature.  
The TDAG query algorithm was executed on a single thread. For the sake of comparison, in all the query algorithms that were evaluated in this work, we used the same set of 10,000 queries chosen i.u.a.r. from \(V\times V\times[0,T)\) in each instance, for randomly selected departure times from \([0,T)\). The static (forward-star) variant of the PGL library [30] was used for the graph representation. For Dijkstra-based algorithms, we used as priority queue [PERSON]'s implementation ([[http://algo.ii.kit.edu/sanders/programs/spq/](http://algo.ii.kit.edu/sanders/programs/spq/)]([http://algo.ii.kit.edu/sanders/programs/spq/](http://algo.ii.kit.edu/sanders/programs/spq/)), accessed on September 2020) of the sequence heap [31].  
In [21], various methods were considered for the selection of the landmark set, significantly influencing the performance of CFCA (subroutine of TDAG). In our experimental evaluation of TDAG, we consider the sparse-random (SR) landmark-selection method that provides the best performance [21]: the landmark nodes are chosen sequentially, each new landmark is chosen i.u.a.r. from the remaining nodes, and excludes a free-flow neighborhood of nodes around it from future landmark selections. That selection is simple and yet effective on providing a high performance in TDAG.  
The goal of our experimental evaluation was twofold:  
1. To investigate the _scalability_ of TDAG, i.e., how smoothly it trades higher query times with better quality guarantees for the resulting alternative graph \(H\), using the value of \(N\) as our tuning parameter;
2. To compare TDAG's performance with the performances of straightforward time-dependent variants of existing techniques for constructing alternative graphs in static graphs [7; 11], which serve as our baseline approaches.  
In general, we assume that \(D_{H}[o,d](t)\) is equal or close enough to \(D_{G}[o,d](t)\), because of the TDD-based steps. Moreover, the relative error _RelativeError_, defined as  
\[RelativeError=\frac{D_{H}[o,d](t)-D_{G}[o,d](t)}{D_{G}[o,d](t)}\,,\]  
provides the observed approximation accuracy of \(H\), that is, how close \(D_{H}[o,d](t)\) is to \(D_{G}[o,d](t)\), given that \(D_{H}[o,d](t)\geq D_{G}[o,d](t)\).