New Models Solve Complex Logistics Districting Problems

This research introduces the Edge-based Contiguous p-median (ECpM) problem, which aims to divide a road network into a specified number of compact and contiguous territories. This problem has significant applications in logistics districting. The paper proposes two binary programming models, both incorporating network distances. The first model uses an exponential number of cut set-based constraints for contiguity, solved with a branch-and-cut algorithm. The second, more innovative model, utilizes a polynomial number of shortest-path constraints (SPC) to enforce contiguity. This SPC-based model demonstrated remarkable performance improvements, achieving speedups of up to 17 times compared to the cut set-based approach when tested on large road networks with thousands of nodes and edges. It was able to solve most instances to optimality, even for models with millions of binary variables. Furthermore, the paper establishes that SPC constraints are "supervalid inequalities" for the simpler edge-based p-median (EpM) model, meaning they can cut off some optimal solutions of the EpM problem while enforcing contiguity. The research also explores connections between ECpM and the edge-based districting (EBD) problem, which adds a work balance criterion. The SPC-based EBD model successfully solved instances that existing cut set-based models could not within 12 hours, highlighting its practical utility for complex logistics and service area planning.