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

Zeyad Kassem and Adolfo R. Escobedo

IISE Transactions, 2023, vol. 55, issue 8, 768-780

Abstract: 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.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2022.2123117 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:55:y:2023:i:8:p:768-780

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2022.2123117

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().