Treffer: 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. [ABSTRACT FROM AUTHOR]

Copyright of IISE Transactions is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)