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:

• Sort the vertices by longitude (or latitude, or some linear combination).
• Compute the maximum flow from the first k nodes (forming the source) to the last k nodes (forming the sink).
  
  Return the corresponding minimum cut as an edge separator (or recurse until the resulting subgraphs are sufficiently small).

@inproceedings{SS15,
 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)

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).

Implementations

• Open Source Routing Machine (OSRM), see also Daniel Hofmann's blog post
• RoutingKit

Home → Publications → On Balanced Separators in Road Networks