Hierarchy Decomposition for Faster User Equilibria on Road Networks

Abstract

The road traffic of an entire day for a certain region can be understood as a flow with sources and sinks on the road network. Traffic has the tendency to evade regularly clogged roads and other bottlenecks, especially with modern on-board navigation devices that are able to interpret traffic information. Assuming perfect knowledge for all drivers, one might suspect traffic to shape itself in a way such that all used routes between any two points on the road network have equal latency. Although these traffic patterns do not or very seldom occur in real life, they are a handy tool to predict the general traffic situation. For small networks, these patterns can be easily computed, but road networks that model entire countries are still a hurdle, because Dijkstra’s algorithm does not scale. Thus the known techniques have only been applied to either small networks or small extracts of a much larger network. We solve this problem for country sized road networks by combining a gradient descent method to the problem with current research on fast route planning by exploiting the special properties of a routing algorithm called Contraction Hierarchies. The computation of the gradient needs a large number of shortest paths computations on the same weighted graph, which means that the expense for preprocessing can be amortized if the number of shortest paths computations is sufficiently large. This leads to dramatic overall speedup compared to running Dijkstra for each demand pair. Also, our study shows the robustness of Contraction Hierarchies on road networks at equilibrium state.

Partially supported by DFG grant SA 933/5-1.