# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 7 Experimental Study
### Experimental Setup  
Our experimental evaluation is divided in two parts. The first part deals with the basic version of PTL and single criterion queries and thus aims at evaluating the performance of d-ptl in its basic version, that updates the red-te graph, the 2 hc-r labeling and the stop labeling. The second part, on the other hand, focuses on the multi-criteria version of PTL and hence on the performance of d-ptl in this latter case, that has to update the wred-te graph, the 2 hc-sp labeling and the extended stop labeling. We remark that in this paper we provide a compacted version of the data structure used by multi-criteria PTL, namely the _extended stop labeling_, and a new dynamic (decremental) algorithm for updating 2 hc-sp labelings in DAGS. Both are experimentally evaluated to assess their performance in terms of query time and update time, respectively. Our experimental study is structured as follows: depending on the considered setting (either basic or multi-criteria) for each input, we build either the red-te graph \(G\) or the wred-te one, and execute PTL to compute corresponding labelings, namely:  
* in the basic case: a 2 hc-r labeling l, and a stop labeling sl of \(G\);
* in the multi-criteria case: a 2 hc-sp labeling l, and an extended stop labeling e-sl of \(G\). Then, we select a connection \(c_{j}\) of the timetable uniformly at random and delay it by \(\delta\) minutes, where \(\delta\) is randomly chosen within \([5,time(m)-time(v_{d}^{c_{j}})+10]\) and \(m=argmax_{v_{\text{\tiny{$\in$DV[s]}}}}\,time(v)\). Choosing \(\delta\) in such a way ensures the occurrence of all meaningful cases, that is the corresponding departure and arrival vertices can be shifted through the whole set of departure and arrival vertices of the corresponding stop. Finally, we run d-ptl to update both the graph and the labelings. In particular, the specific version to handle either the basic or the multi-criteria setting are executed. In parallel, we run PTL to recompute graph and labelings from scratch (again, we recompute the specific basic or multi-criteria version). After each execution, we measure both the _update time_ of d-ptl and the computational time taken by PTL for the recomputation from scratch. Moreover, we also measure the _average size of the labelings_ and the _average query time_. The former is the average space occupancy, in megabytes, of the different labelings employed by the approaches. The latter, instead, is obtained by computing the average time to answer to \(100,000\) queries, of both earliest arrival, profile and multi-criteria type via the corresponding query algorithms described in Sections 5 and 6. This is done to evaluate the quality of the data structures when updated via d-ptl against that of the data structures recomputed from scratch and to show that using d-ptl to update the graph and the labelings does not affect the performance of the framework. The two most important quality metrics in this context are space occupancy and query time (which are also somehow related). Note that, for the above queries, stops and departure times (ranges for profile queries, respectively) are chosen uniformly at random. For each query, for the sake of validity, we compare the result by comparing the two outputs with the result of an exhaustive Dijkstra's-like visit on the graph [9]. We repeat the above process for 50 connections, in order to compute average values and collect statistically significant results. As inputs to our experiments, we considered, as other studies of this kind [2; 4; 10; 13], real-world transit networks whose data is publicly available (Public Transit Feeds Archive--https://transitfeeds. com/.) and is formatted according to the _General Transit Feeds Specification_ (shortly, GTFS). In particular, GTFS is a data specification standard for transit datasets, which enforces uniformity in the structure of data coming from different sources in order to be consumed by a wide variety of software applications, such as journey planners.