On Balanced Separators in Road Networks

Aaron Schild and Christian Sommer
SEA 2015 - 14th International Symposium on Experimental Algorithms (pp. 286-297)

The following algorithm partitions road networks surprisingly well:

 author    = {Aaron Schild and Christian Sommer},
 title     = {On Balanced Separators in Road Networks},
 year      = {2015},
 booktitle = {14th International Symposium on 
              Experimental Algorithms (SEA)},
 pages     = {286--297},
 url       = {http://dx.doi.org/10.1007/978-3-319-20086-6_22},
 doi       = {10.1007/978-3-319-20086-6_22},

Official version
Local version (3.0 MB)
Slides (6.2 MB)

Road Network Partition using Inertial Flow (Aaron Schild and Christian Sommer)
Recursive bisection using our separator algorithm Inertial Flow (with balance 1/4) for the road network of the United States (24M nodes, 29M edges) into 27 regions by cutting a total of 1,413 edges.

Delling, Goldberg, Razenshteyn, and Werneck discovered that road networks have remarkably small separators. Prior to our work, their patented method called PUNCH (Partitioning Using Natural Cut Heuristics) appeared to be the only one capable of efficiently computing these separators (Buffoon, another high-quality partitioner for road networks, uses PUNCH as a subroutine).

Our main contribution is a simple and efficient method to find sparse balanced cuts in embedded graphs such as road networks. The method, which we call Inertial Flow, uses the embedding, initially sorts nodes geometrically (like the well-known Inertial Partitioning), and then computes a maximum flow. The corresponding minimum cut is used as the separator. Inertial Flow is straightforward to implement, yet its partitions are reasonably good.

See also Structured Recursive Separator Decompositions for Planar Graphs in Linear Time.

Applications Hamann and Strasser ran experiments for Customizable Contraction Hierarchies with various partitioners. For our algorithm Inertial Flow, preprocessing the US road network (as above, but directed with 58M arcs) requires 18 minutes (sequential), updates (for example incorporating live traffic for the entire network) take approximately 1 second (parallel, 4 cores), and point-to-point shortest-path queries can be answered in less than 200 microseconds on average (a query returns the cost, travel time, or distance, not the actual path).

HomePublications → On Balanced Separators in Road Networks