Models and network insights for edge-based districting with simultaneous location-allocation decisions

We introduce two edge-based districting optimization models with no pre-fixed centers to partition a road network into a given number of compact, contiguous, and balanced districts. The models are applicable to logistics applications. The first model is a mixed-integer programming model with network flow-based contiguity constraints. Since this model performs poorly on medium-to-large instances, a second model with cut set-based contiguity constraints is introduced. The full specification of the contiguity constraints requires substantial computational resources and is impractical except for very small instances. However, paired with an iterative branch-and-bound algorithm with a cut generation scheme (B&B&Cut), the second model tends to outperform the first computationally. We show that the underlying problem is NP-hard. Moreover, we derive network insights, from which cutting planes that enable a reduction in the solution space can be generated. The cuts are tested on road networks with up to 500 nodes and 687 edges, leading to speed up in computational time up to almost 27x relative to the computational time of solving the second optimization model exactly with only B&B&Cut.