evaluation.tex

% !TeX root = thesis.tex
%% evaluation.tex
%%

%% ==============
\chapter{Evaluation\label{ch:Evaluation}}
In this section, we evaluate the running time and behavior of our algorithms of Chapter~\ref{ch:Algorithm}. Our machine runs openSUSE Leap 15.3, has \SI{128}{\giga\byte} (8x\SI{16}{\giga\byte}) of \SI{2133}{\mega\hertz} DDR4 RAM, and a 4-core Intel Xeon E5-1630v3 CPU which runs at \SI{3.7}{\giga\hertz}. The code is written in Rust and compiled with cargo 1.64.0-nightly using the release profile with \texttt{lto~=~true} and \texttt{codegen-units~=~1}.

\subparagraph{Data.} Our data is a road network of Europe\footnote{\url{https://download.geofabrik.de/europe-latest.osm.pbf} of March 22, 2022} and of Germany\footnote{\url{https://download.geofabrik.de/europe/germany-latest.osm.pbf} of March 22, 2022} from Open Street Map (OSM). We extract the routing graph and parking nodes from the OSM data using a custom extension\footnote{\url{https://github.com/maxoe/RoutingKit}} of RoutingKit\footnote{\url{https://github.com/RoutingKit/RoutingKit}}. The obtained routing graph of Europe has $81.5$ million nodes and $190$ million edges. Our set $P$ of parking nodes in the European routing graph consists of \num{6796} nodes which were selected according to their OSM attributes. The routing graph of Germany has $12.5$ million nodes, $29.5$ million edges, and we selected \num{3222} nodes as parking nodes.

RoutingKit constructs the routing graph by filtering the OSM data using a rich set of attributes to determine which of the OSM objects can be used for driving with a car. The OSM objects types of importance are OSM nodes and OSM ways. An OSM node is a location with associated geographic coordinates and an OSM way is a polyline consisting of multiple OSM nodes. RoutingKit removes OSM nodes which are only used for modelling of the shape of roads to obtain the set of nodes for the routing graph. It then uses additional attributes to classify the OSM ways into categories with different assumed average speeds. The categorized OSM ways and their spatial length are used to determine driving times between the routing nodes which can then be used as the length function $\len$ of the routing graph. In our custom extension, we additionally extract parking nodes from the OSM data. The extraction again is based on attributes which indicate a designated parking location for heavy goods vehicles (HGV), i.e., if \texttt{hgv = "yes"} or \texttt{hgv = "designated"} or \texttt{access = "hgv"} is true. Figure~\ref{fig:parking_qgis} gives an overview over all extracted HGV parking locations. Visualizations of spatial data in this chapter are obtained from the QGIS software\cite{qgisdevelopmentteam:2022}. It is apparent that in some areas in Europe there are a lot more parking areas marked as HGV parking than in others. In general, the location of designated HGV parking areas correlates with the location of highways. Figure \ref{fig:parking_central_europe_qgis} shows that especially in areas with many designated HGV parking locations, the structure of the highway network becomes visible.

\begin{figure}[hbtp]
	\centering
	\subfigure[Full HGV Parking Set]{
		\includegraphics[width=.48\textwidth]{figures/parking_all_europe.png}
		\label{fig:parking_europe_qgis}
	}\hfill
	\subfigure[Highways networks become visible since many designated HGV parking locations are close to a highway]{
		\includegraphics[width=.48\textwidth]{figures/parking_central_europe.png}
		\label{fig:parking_central_europe_qgis}
	}
	\caption{Parking set of designated HGV parking locations which was extracted from OSM data of Europe.}
	\label{fig:parking_qgis}
\end{figure}

We consider OSM nodes and OSM ways as potential parking areas. If an OSM node is found which is marked as HGV parking, we simply flag it as a routing node so that RoutingKit does not remove it from the graph even if it would consider it a modelling node only. Additionally, we add a parking flag for all parking nodes. Some parking areas are modelled as an area instead of a node. In this case, an OSM way which encloses the parking area is flagged as HGV parking. We need to define parking nodes ourselves which we then can add to the routing graph. Additionally, we have to connect these nodes to the rest of the routing graph in order to allow routing from and to them. As a pragmatic solution, we search for OSM nodes on the OSM way which is modelling the parking area that are part of a second OSM way which is marked as suitable for driving with a car. We flag all of these nodes as routing nodes and parking nodes. RoutingKit will include them in the routing graph. As a result, a parking area which is modelled using an OSM way can result in multiple parking nodes in the routing graph, each of which can be viewed as an entry or exit node. In the routing algorithm, this does not lead to noteworthy overhead since the label which took a break at the exit node of the route through the parking area will always dominate labels which took a break at an entry node. The amount of labels being propagated therefore does not increase significantly.


\subparagraph{Methodology.} All experiments are run sequentially. We conduct experiments regarding the preprocessing time of the core CH and the running time of queries on the extracted routing graph. If not stated otherwise, preprocessing running times are average over \num{10} runs, running times of $s$-$t$ queries are averaged over \num{1000} queries with $s$ and $t$ being chosen uniformly at random for each query. We use the $C_{EU}$ $\restr_1$ with $\restr_1^d = \SI{4.5}{\hour}$ and $\restr_1^b = \SI{0.75}{\hour}$ and $\restr_2$ with $\restr_2^d = \SI{9}{\hour}$ and $\restr_2^b = \SI{11}{\hour}$ to approximate the regulations of the EU.

\section{Algorithms}
We evaluate the different algorithms of Chapter~\ref{ch:Algorithm} and the backward pruning of Section~\ref{section:impl}.

As Table \ref{tbl:extensions_runtime} shows, on the German road network, the baseline Dijkstra's algorithm with our amendments for driving time constraints averages at about \SI{30}{\second} of running time. Its bidirectional counterpart without goal-direction almost cuts this running time in half. The goal-directed, unidirectional algorithm on the other hand performs two orders of magnitude better than the baseline, the bidirectional variant of the goal-directed search even manages to improve the running time by another two orders of magnitude. The goal-directed core CH exhibits the best running times of all algorithms, improving the baseline by a factor of about \num{10000} and even slightly outperforming the bidirectional goal-directed algorithm. The non-goal-directed core CH variant falls back significantly behind its goal-directed counterpart. The running time of the goal-directed search for the TDRP-1DTC seems to be very long, especially compared to the performance for the TDRP-2DTC. This is caused by outliers from which the goal-directed variant suffers which cause running times for queries which are orders of magnitude longer than the mean. We address this issue further below.

On the European road network, we omitted the baseline and the TDRP-2DTC run of the goal-directed variants without a core CH since they are too slow or suffer from outliers and would render the experiment impracticable. It appears that the goal-directed variant of the algorithm does not scale very well with longer routes which need an increasing amount of necessary breaks. Most of the performance gain of the goal-directed search in comparison to the baseline originates from the very tight lower-bound given by the CH potentials. If the shortest travel time between two nodes $s$ and $t$ is much larger than $\distance(s,t)$ due to necessary breaks and detours to parking nodes on the route, then the performance of the goal-directed search degrades. The bidirectional variant can mitigate this disadvantage to a certain degree since it connects two routes which each are shorter and have fewer breaks.

Both core CH algorithms scale better. The simple core CH algorithm scales the best of all algorithms and the goal-directed core CH variant again shows the best result. Both variants also remain below the mark of one second for both, the TDRP-1DTC and the TDRP-2DTC.

\begin{table}[btp]
	\centering
	\input{gen/eval_running_times_all.tex}
	\caption{Average running times of random queries on a German and European road network with one or two driving time constraints.}
	\label{tbl:extensions_runtime}
\end{table}

We also provide the median running times in Table~\ref{tbl:extensions_runtime_median} since the average running time can be skewed significantly due to a few outliers which especially is the case for the goal-directed variants without a core CH. While the running times of non-goal-directed variants improve a little, the median of the running times of goal-directed variants is much smaller than the average in all cases in which the average was not already in the millisecond range. The core CH shrinks the maximal possible search space in the worst case from the entire graph to a set of much fewer nodes which are reachable via upward edges or are core nodes. Therefore, the outliers are not as bad as for the variants without a core CH. The median running times of the goal-directed core CH on Europe still are much lower than the average.

\begin{table}[hbtp]
	\centering
	\input{gen/eval_median_running_times_all.tex}
	\caption{Median running times of random queries on a German and European road network with one or two driving time constraints.}
	\label{tbl:extensions_runtime_median}
\end{table}

Furthermore, we investigate the impact of an increased route length and amount of necessary breaks on a route. For this, we plot the running times of queries to target nodes of increasing Dijkstra rank on the European road network. The Dijkstra rank is obtained from the sequence in which a standard Dijkstra search without driving time constraints settles its nodes. The Dijkstra rank of a node is the position of the node in that sequence. We plot running times to nodes of rank $2^{10}$, $2^{11}$,\dots,$2^{\log(|V|)}$ where $|V|$ is the number of nodes in the graph. The plot is shown in Table~\ref{fig:rank_times} with a side-by-side comparison of the unidirectional goal-directed and the goal-directed core CH algorithms.

We first compare the running times with one driving time constraint (TDRP-1DTC) in Figure~\ref{fig:rank_times_1dtc}. The goal-directed algorithm shows an increase of running time of multiple orders of magnitude for large Dijkstra ranks. Starting at Dijkstra rank $2^{20}$, a significant amount of very slow queries occurs which stretches the interquartile range. The median remains low, almost at the first quartile. The median of the running time jumps from about \SI{2}{\milli\second} at Dijkstra rank $2^{22}$ to about \SI{230}{\milli\second} at Dijkstra rank $2^{23}$. This coincides with the median travel time of the route crossing the mark of \SI{4.5}{\hour} which is the maximum allowed driving time without a break of the driving time constraint being used. Therefore, most queries to target nodes with a Dijkstra rank of $2^{23}$ need at least one break while most queries to target nodes of Dijkstra rank $2^{22}$ do not need to pause on the route yet. The goal-directed core CH variant scales better with longer queries. It falls slightly behind the goal-directed algorithm for lower Dijkstra ranks due to a larger overhead. While the algorithm suffers from the same general problem of an increasing running time with an increasing route length and number of breaks, the median of its running time increases only by one order of magnitude for the longest queries. It only exceeds \SI{10}{\milli\second} at a Dijkstra rank of $2^{24}$ and never exceeds \SI{12}{\milli\second} at all.

The running times for two driving time constraints (TDRP-2DTC) show a similar picture. In general, the median rises earlier and higher due to a higher number of labels that must be handled by the algorithm in the label sets since at each parking node, a label is tripled instead of doubled. Nevertheless, the median of the goal-directed core CH never exceeds \SI{100}{\milli\second} and there is no single query which ran longer than about one second. Another difference is the point at which the median of the goal-directed core CH variant yields a better running time than the median of the pure goal-directed variant. With one driving time constraint, this happens at the Dijkstra rank of $2^{23}$ when most queries need a break on their route for the first time. For two driving time constraints, this happens earlier at Dijkstra rank $2^{21}$.

\begin{figure}[hbtp]
	\centering
	\subfigure[Goal-Directed and Goal-Directed Core CH Algorithms (TDRP-1DTC)]{
		\includegraphics[width=.95\textwidth]{plots/thesis_rank_times-csp-parking_europe_hgv.png}
		\label{fig:rank_times_1dtc}
	}
	\subfigure[Goal-Directed and Goal-Directed Core CH Algorithms (TDRP-2DTC)]{
		\includegraphics[width=.95\textwidth]{plots/thesis_rank_times-csp_2-parking_europe_hgv.png}
		\label{fig:rank_times_2dtc}
	}
	\caption[Running times of queries to target nodes of increasing Dijkstra rank, logarithmic scales.]{Running times of queries to target nodes of increasing Dijkstra rank, logarithmic scales. The box represents the interquartile range (IQR) from the first quartile Q1 to the third quartile Q3. The horizontal line within the IQR is the median. The whiskers represent the range from $\text{Q1} - \text{IQR} \cdot 1.5$ to $\text{Q3} + \text{IQR} \cdot 1.5$ which contains $99.3\%$ of the data points.}
	\label{fig:rank_times}
\end{figure}

The running times of Figure~\ref{fig:rank_times} to increasingly distant target nodes support the median running times of Table~\ref{tbl:extensions_runtime_median}, but they cannot fully explain the high average running times of Table~\ref{tbl:extensions_runtime}. The reason for this is that many of the outliers are queries for which no route is found. In fact, when exemplarily investigating the slowest $10\%$ of the random queries of the goal-directed algorithm on the European road network and with one driving time constraint, we find that over $90\%$ of those did not find a route. These queries are naturally left out when plotting queries to nodes for which a Dijkstra rank exists. The remaining slow queries are long queries with a large number of breaks on the route. To complete the evaluation of the different variants of the algorithm, we provide the running times on the European road network of the queries for which no route was found in Table~\ref{tbl:times_no_path}. It becomes visible that the goal-directed algorithms suffer the most. In comparison to the average and the median of all queries, the non-goal-directed core CH handles queries in which no path can be found the best.

\begin{table}[hbtp]
	\centering
	\input{gen/eval_running_times_no_path.tex}
	\caption{Comparison of running times of queries which failed to find a feasible route.}
	\label{tbl:times_no_path}
\end{table}

Finally, we evaluate the backward pruning as defined in Algorithm~\ref{alg:bw_pruning} in use with the goal-directed core CH algorithm on the European road network. For this experiment, we average running times of \num{10000} queries. Table~\ref{tbl:opt_runtime} shows that the pruning can lead to a small improvement of the average running time but cannot improve the median.

\begin{table}[hbtp]
	\centering
	\input{gen/eval_running_times_opt.tex}
	\caption{Comparison of running times of the goal-directed core CH algorithm with and without the backward pruning of Section~\ref{section:impl}.}
	\label{tbl:opt_runtime}
\end{table}

\section{Influence of Parameters and Data}
In this section, we investigate how varying parameters for the query and the preprocessing influence the running time of our algorithms. The European road network is used for all experiments. We compare the non-goal-directed and goal-directed core CH variants to be able to observe the effect of the goal-direction.

\subsection{Driving Time Constraints}
We investigate how different driving time limits and break times influence the running time of the goal-directed core CH and non-goal-directed core CH algorithms. We use only one driving time constraint $\restr$ (TDRP-1DTC) to be able to change one parameter at a time and observe the consequences. Figure~\ref{fig:eval_driving_time} shows the running times for an increasing maximum allowed driving time $\restr^d$. We plot the median of 1000 random queries for one value of $c^d$ and increase the driving time limit stepwise. Additionally, the plot is smoothed using a rolling window mean to increase readability. To ease the comparistion of both plots, the scaling of the y-axis is the same in both plots.

The goal-directed core CH variant behaves differently compared to the core CH variant, except for very small driving time limits when both variants fail to find a path and terminate early. When increasing the driving time limit, the search radius first increases equally for both. This is because the goal-directed variant presents no advantage over the non-goal-directed variant if a route from $s$ to $t$ is not found because of the driving time constraint. The goal-directed algorithm can exclude nodes $v$ from the search only if the target node $t$ is not reachable from the $v$ at all in the graph, since the CH-Potentials yield an infinite distance value in this case. It fails to do so if $t$ is reachable from $s$ in the graph, but the driving time constraint prohibits finding a feasible route. In this case, both algorithms settled the same labels, just in a different order. This behavior changes when the driving time limit increased enough that a route can be found and the advantage of the goal-directed algorithm becomes apparent. In the optimal case, if a route from a node $v$ to $t$ exists without the need for any break, the CH-Potentials yield the exact distance values $\distance(v,t)$. Therefore, the goal-directed algorithm knows the shortest path to $t$ and does not search aside the shortest route at all.

\begin{figure}[hbtp]
	\centering
	\subfigure[Core CH Algorithm]{
		\includegraphics[width=.48\textwidth]{plots/thesis_driving_times-csp-parking_europe_hgv-core_ch-time_ms.png}
		\label{fig:eval_driving_time_core_ch}
	}\hfill
	\subfigure[Goal-Directed Core CH Algorithm]{
		\includegraphics[width=.48\textwidth]{plots/thesis_driving_times-csp-parking_europe_hgv-core_ch_chpot-time_ms.png}
		\label{fig:eval_driving_time_gd_core_ch}
	}
	\caption{Running time means and IQR of the core CH and the goal-directed core CH algorithms with increasing maximum allowed driving time.}
	\label{fig:eval_driving_time}
\end{figure}

Second, we vary the break time $\restr^b$ of the driving time constraint in the same way which is shown in Figure~\ref{fig:eval_break_time}. If the break time is exactly zero, there never are multiple labels at a parking node. When duplicating a label at a parking node to represent the two options of taking a break and not taking a break, the label $l$ which took the break will always dominate the other label $l'$ since it resets the distance since the last break to zero without adding any break time to its travel time.

In the non-goal-directed case, the labels in the label queue are sorted using their travel time. A label $l$ at a parking node $v$ which takes the break is inserted into the queue at a position further back than the label $l'$ that does not take a break. The search does not settle $l$ at all if the break time which has been added to its travel time increased its travel time over $\traveltime(s,t)$. If the label $l$ is part of the shortest route, this is not the case and the algorithm spends unnecessary time with propagating labels which have taken fewer breaks and therefore yield a smaller travel time, but will not reach $t$ because they exceed the driving time limit at some point. The longer the break time, the more of such labels are settled before $l$ which increases the running time. The running time stops to increase when no more labels with fewer breaks exist which the algorithm can propagate before $l$. In this case, the algorithm first propagates all labels which take zero breaks, then all labels which take one break and so on until a feasible route to $t$ can be found. As Figure~\ref{fig:eval_break_time_core_ch} shows, this is already the case after a small increase of the break time from zero. Many break time values from real-world regulations fall into this range in which the running time increases significantly with an increasing break time. For example, the US HOS regulations include a break time of \SI{30}{\minute} and the EU driver's working hours regulations include a break time of \SI{45}{\minute}.

In the goal-directed case, the labels are sorted in the queue using the sum of their travel time and the potential towards the target node. If a label is positioned further back in the queue, it takes a longer detour from the route, which the CH-Potentials have determined to be the shortest route to $t$ without regard to driving time constraints. Detours arise from the need to deviate from the direct route to reach a parking node because the direct route exceeded the driving time limit. As a consequence, the algorithm starts to propagate labels along the direct route until either $t$ is found or the driving time limit is exceeded. It then continues to do so with the label that took the smallest detour. If a label takes a break, it only gets positioned further back in the label queue if the break is not useful, i.e., if the break does not spare a break on the remaining route. Such labels cannot be part of a shortest route. Therefore, the break time has no influence on the running time of the algorithm, a finding which is also supported by the large IQR which is shown in the plot.

\begin{figure}[hbtp]
	\centering
	\subfigure[Core CH Algorithm]{
		\includegraphics[width=.48\textwidth]{plots/thesis_break_times-csp-parking_europe_hgv-core_ch-time_ms.png}
		\label{fig:eval_break_time_core_ch}
	}\hfill
	\subfigure[Goal-Directed Core CH Algorithm]{
		\includegraphics[width=.48\textwidth]{plots/thesis_break_times-csp-parking_europe_hgv-core_ch_chpot-time_ms.png}
		\label{fig:eval_break_time_gd_core_ch}
	}
	\caption{Running time means and IQR of the core CH and the goal-directed core CH algorithms with an increasing break time.}
	\label{fig:eval_break_time}
\end{figure}


\subsection{Car and Truck Speeds}
RoutingKit assumes speeds for different categories of OSM ways reaching from \SI[per-mode = symbol]{5}{\kilo\meter\per\hour} for walking speed to \SI[per-mode = symbol]{130}{\kilo\meter\per\hour} on highways. The assumed highway speeds are sometimes faster than the possible or allowed speed of HGVs. In this experiment, we measure the running time of the goal-directed core CH algorithm in multiple iterations in which we cap the maximum speed at the values \SI[per-mode = symbol]{130}{\kilo\meter\per\hour} (standard RoutingKit setting), \SI[per-mode = symbol]{100}{\kilo\meter\per\hour}, \SI[per-mode = symbol]{80}{\kilo\meter\per\hour} (common maximum truck speed), \SI[per-mode = symbol]{50}{\kilo\meter\per\hour}, \SI[per-mode = symbol]{30}{\kilo\meter\per\hour}, and \SI[per-mode = symbol]{15}{\kilo\meter\per\hour} and observe the change in running time. We plot the average running time of \num{10000} random queries in each iteration.

First, the running time does not change significantly when the maximum assumed speed is capped at lower speeds. The running time then increases and reaches a peak at a maximum speed of around \SI[per-mode = symbol]{50}{\kilo\meter\per\hour}, after which it decreases towards very low values. This is especially the case for the TDRP-2DTC and is caused by queries which fail to find a feasible route. For lower assumed speeds, the driving times to parking nodes from any node in the graph increases while the maximum allowed driving time remains the same. More and more queries therefore fail to find a route. The running times increase since in general, queries which do not find a feasible route due to driving time constraints are slow. We have discussed this in the context of Table~\ref{tbl:times_no_path}. The decrease of running times for very low speed caps are caused by the same effect as in Figure~\ref{fig:eval_driving_time}. Instead of lowering the maximum allowed driving time, we lower the speed of the vehicle and the search radii become smaller.

\begin{figure}[hbtp]
	\centering
	\includegraphics[width=.95\textwidth]{plots/thesis_speed_cap.png}
	\label{fig:truck_speed_limit}
	\caption{The running time of goal-directed core CH queries increases with a decreasing speed cap, i.e., a decreasing assumed maximum speed of the vehicle until it reaches a high point and decreases again fir very low speed caps.}
\end{figure}

\section{Core Contraction Hierarchy}
In Section~\ref{section:impl}, we mentioned the possibility of including more nodes than the parking nodes in the core of the core CH. Parking nodes are not necessarily important nodes according to the computed node order of the CH, but we define them as the most important nodes of the road network regardless. This reduces the quality of the core CH. For certain sets of parking nodes, it might be beneficial to also include the most important nodes according to the node order in the core. In the following, we will analyze the impact of different core sizes on the running time of queries of the goal-directed core CH algorithm on the European road network. The choice of the core size also significantly impacts the construction time of the core CH.

In Figure~\ref{fig:preprocessing_time_core_ch}, we plot the construction time of the core CH for increasing core sizes in relation to the number of nodes in the graph. The construction time begins to increase drastically for a core size smaller than $0.01\%$ of the nodes. Figure~\ref{fig:query_time_core_ch_sizes} shows that the average running time of a query decreases with a decreasing core size, but the benefit of contracting more nodes becomes much smaller for very small core sizes. This observation can be used to lower the preprocessing time significantly by including more non-parking nodes in the core without loosing much of the performance of the goal-directed core CH queries. A good trade off in the example with the European road network with HGV parking nodes would be a core size between $0.1\%$ and $0.01\%$ of the graph's number of nodes. Certain sets of core nodes can cause high node degrees at an early stage during the contraction of nodes. Allowing additional nodes in the core might be the only feasible approach to build a core CH in those cases since the node degrees become too high to be able to finish the contraction of all non-parking nodes in practicable time.

\begin{figure}[hbtp]
	\centering
	\subfigure[Construction Times]{
		\includegraphics[width=.48\textwidth]{plots/thesis_core_sizes-csp-parking_europe_hgv-constr_time.png}
		\label{fig:preprocessing_time_core_ch}
	}\hfill
	\subfigure[Running Times of the Query]{
		\includegraphics[width=.48\textwidth]{plots/thesis_core_sizes-csp-parking_europe_hgv-time_ms.png}
		\label{fig:query_time_core_ch_sizes}
	}
	\caption{The running times of goal-directed core CH queries increase with an increasing core size relative to the number of nodes in the graph while the construction times decrease.}
	\label{fig:core_ch_sizes}
\end{figure}