1.
Blum, J., Storandt, S.: Computation and Growth of Road Network Dimensions. In: Wang, L. und Zhu, D. (hrsg.) COCOON. S. 230–241. Springer (2018).
There is a plethora of route planning techniques which work remarkably well on real-world road networks. To explain their good performance, theoretical bounds in dependency of road network parameters as the highway dimension \($h$\) or the skeleton dimension \($k$\) were investigated. For example, for the hub label technique, query times in the order of \($\mathcalO(p \log D)$\) and a space consumption of \($\mathcalO(np \log D)$\) were proven for both \($p=h$\) and \($p=k$\), with \($D$\) denoting the graph diameter and \($n$\) the number of nodes in the network. But these bounds are only meaningful when the dimension values \($h$\) or \($k$\) are known. While it was conjectured that \($h$\) and \($k$\) grow polylogarithmically in \($n$\), their true nature was not thoroughly investigated before -- primarily because of a lack of efficient algorithms for their computation. For the highway dimension, this is especially challenging as it is NP-hard to decide whether a network has highway dimension at most \($h$\). We describe the first efficient algorithms to lower bound the highway dimension and to compute the skeleton dimension exactly, even in huge networks. This allows us to formulate new conjectures about their growth behavior. Somewhat surprisingly, our results imply that \($h$\) and \($k$\) scale very differently. While \($k$\) turns out to be a constant, we expect \($h$\) to grow superpolylogarithmically in \($n$\). These observations have implications for the future design and analysis of route planning techniques.
2.
Blum, J., Storandt, S.: Scalability of Route Planning Techniques. In: de Weerdt, M., Koenig, S., Röger, G., und Spaan, M. (hrsg.) ICAPS. AAAI Press (2018).
In this paper, we thoroughly analyze the scaling behavior of several state-of-the-art route planning techniques for road networks, all of which rely on preprocessing. One goal is to determine which technique is most suitable to be used on huge networks. To be able to conduct scalability studies in a clean way, we first describe a new kind of road network generator that allows to produce road networks even larger than that of our planet with similar properties as real networks. We then carefully implement several preprocessing-based route planning techniques, as contraction hierarchies, hub labels and transit nodes, to study their space consumption as well as their search spaces in different sized networks. This allows to derive functions that describe their empirical scaling behavior for the first time. We also compare our functions to existing theoretical bounds. We show that several of our results can not be sufficiently explained by the theoretical investigations conducted so far. Hence our results encourage a further look for road network models that allow for better predictions.
3.
Blum, J., Funke, S., Storandt, S.: Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks. In: McIlraith, S. und Weinberger, K. (hrsg.) AAAI. S. 6119–6126. AAAI Press (2018).
Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in e.g. road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. But for many of these techniques it is not fully understood why they perform so remarkably well and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. But these parameters tend to be large (order of \($\Theta(\sqrt n)$\)) when the network contains grid-like substructures -- which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. For graphs with a large highway or skeleton dimension, our results turn out to be superior. Furthermore, our preprocessing methods are close to the ones used in practice and only require randomized polynomial time.
1.Blum, J., Storandt, S.: Computation and Growth of Road Network Dimensions. In: Wang, L. und Zhu, D. (hrsg.) COCOON. S. 230–241. Springer (2018).
