Territorial Design for Logistics Applications: Formulations and Network Insights

Dividing a geographical region into a collection of smaller territories according to definite planning criteria, known as territorial design, is prevalent in many real-world situations. For instance, in a logistics context, a city is often divided into non-overlapping service regions containing city blocks of customers, where dedicated vehicles are distributed to serve them. Location-allocation models can be used to design these territories by locating facilities and allocating customers or communities to the chosen locations, with the aim of optimizing one or several decision criteria. The first part of the research focuses on a novel location-allocation problem, specifically edge-based districting. It introduces models that partition edges of a road network into service areas satisfying three desirable criteria: contiguity, compactness, and work balance. These models incorporate node-to-edge network distances, making them suitable for logistics applications. This research formally establishes the NP-hardness of the EBD problem. To reduce the solution space, network insights are leveraged to derive non-valid logic cuts, a method that removes integer-feasible but non-optimal solutions. Computational tests show significant benefits, with computational time improvements of over an order of magnitude for large-scale instances. The second part explores the edge-based contiguous p-median (ECpM) problem, which seeks to partition a road network into compact and contiguous territories. Two binary programming models are introduced. The first model uses an exponential number of cut set-based constraints, and it is paired with a separation algorithm that generates only a small subset of these constraints. The second model uses a polynomial number of shortest-path constraints, and it can be solved with off-the-shelf optimization solvers. Computational tests show that the shortest-path formulation outperforms the cut set-based formulation, solving larger instances and achieving up to 52x speedups. Structural insights and connections between the ECpM problem and the EBD problem are also explored. The third part investigates the interconnections between node-based districting (NBD) and edge-based districting problems. From a modeling perspective, it describes a set of steps to transform any EBD instance so that it can be equivalently solved with NBD districting models. In addition, it explores how the network insights developed for the EBD models can be adapted for two node-based models that incorporate node-to-node network distances.