A Parameterized View on Transportation Networks : Algorithms, Hierarchy, and Complexity

Abstract

Many everyday optimization problems arise in transportation networks, such as vehicle and pedestrian navigation, truck route planning, or facility location problems in logistics. To solve such problems, efficient algorithms are required. To that end, the transportation network is usually modeled as a graph, where the vertices represent locations (e.g., road intersections or train stations) and the edges represent connections between them. To develop efficient algorithms for the corresponding graph problems, it is in many cases beneficial to exploit certain properties of the resulting graph. This motivated the development of several models for graphs representing transportation networks, e.g., the graph parameters highway dimension and skeleton dimension, which capture the structure of shortest paths in a graph, or bounded growth graphs. In this work, we consider different parameters that are commonly used to model transportation networks. We utilize them to develop efficient algorithms, study the relationships between different parameters, and demonstrate the limitations of these models. In the first part, we consider the shortest path problem. Three of the most successful algorithms for this problem in transportation networks are Contraction Hierarchies, Hub Labeling, and Transit Node Routing. First, we investigate these algorithms on bounded growth graphs. A graph has bounded growth if there is a constant g such that for any vertex u and any r>0, the number of vertices at distance r from u is at most g⋅r. We improve upon a previous result of Funke and Storandt [ISAAC '15] and show that in this model, it is possible to achieve a space consumption of O(n log D) for Contraction Hierarchies on unweighted graphs, where D denotes the diameter of the graph. Furthermore, we analyze the search space sizes and space consumption of Hub Labeling and Transit Node Routing on bounded growth graphs, and also consider weighted graphs. We then study variants of Hub Labeling and Contraction Hierarchies, and show that we can lower bound the size of their respective search spaces in terms of the size of minimum balanced separators. This allows us to develop a O(log2 n)-approximation algorithm for the search spaces sizes. In the second part, we consider various graph parameters, including highway dimension, skeleton dimension, and bounded growth number. We study the relationships between different parameters, which allows us to incorporate them into a hierarchy. The third part is concerned with the computational complexity of two graph problems. We show that it is NP-hard to compute the highway dimension of a graph according to the recent definition of Abraham et al. [J. ACM '16]. Moreover, we develop a polynomial time algorithm to compute the highway dimension of a tree.Finally, we consider the k-Center problem. First, we show that for any ϵ>0 it is NP-hard to compute a (2-ϵ)-approximation if the given graph has a skeleton dimension of κ ∈ O(log2 n). Finally, we study the fixed-parameter tractability of k-Center and show that the problem is W[1]-hard if the parameter combines the number of centers, the highway dimension, the skeleton dimension and the pathwidth, even if the given graph is planar and has constant doubling dimension.