Choosing Depots and Contiguous Delivery Territories Together

Delivery companies make two decisions that are usually handled separately. First they decide where to open depots. Then they carve the city into delivery territories, one per depot or vehicle group, and planners want each territory to be a single connected piece of map that does not jump across a river or wrap around a neighbour's zone. Location-routing models already choose depots and customer assignments jointly, but they do not require territories to be connected. Districting models do require connected territories, but they treat depots as fixed. We propose one optimization model that picks depot sites and connected territories at the same time. It scores each candidate territory with a learned estimate of its routing cost, and that estimate depends on where the depot sits relative to the territory.

The first question is how much connectivity costs: how much routing cost do you give up by demanding connected territories, and how much of that loss is recovered by letting depot positions move? The answer decides whether this is a real problem or a cosmetic one. The method is a mixed-integer program, meaning an optimization model with yes/no and continuous decision variables solved by a standard solver. It combines three things: a neural routing-cost predictor embedded as constraints, network-flow constraints that force each territory to be connected and to contain its own depot, and a fast warm start from exact dynamic programming on spanning trees of the map.

Core Claim

On real administrative maps, connected territories are a hard constraint that interacts with depot placement. Our claim is that solving location, connectivity and routing cost jointly beats every two-stage alternative on true routing cost, while producing zero disconnected fragments. Those alternatives are: choose depots and then district, district and then repair, or run unconstrained location-routing and then patch. The key ingredient is a routing-cost predictor conditioned on the depot's position relative to the territory. A fixed-depot predictor cannot express that dependence, and an unconstrained assignment model never needs it.

Grounding in Prior Work

Two papers sit on either side of the gap. Neural Embedded Mixed-Integer Optimization for Location-Routing Problems (NEO-LRP) splits capacitated location-routing into a high-level location-and-assignment model and low-level routing. It embeds a Deep Sets or Graph Transformer routing-cost predictor, trained on 120,000 single-depot vehicle routing instances, directly as constraints in the high-level model. It reports 2x to 120x speedups over metaheuristics at up to 600 customers and 30 depots. Its assignment has no notion of map adjacency, so territories may fragment or interleave. We reuse its embedding technique and add connectivity.

Deep Learning for Data-Driven Districting-and-Routing groups UK census areas (called MSOAs) into connected districts. It uses a graph neural network cost oracle with 2.72% mean absolute percentage error (MAPE), against 5.46% for classical continuous-approximation formulas, and it finds plans 10.12% cheaper on average. Its depots are fixed, and its search is local swap/relocate. We take its dataset and its finding that compactness alone does not predict routing cost, and we make depots decisions.

Approximation work constrains what we can hope to prove. Connected k-Median with Disjoint and Non-disjoint Clusters shows that disjoint connected clustering is $\Omega(n^{1-\epsilon})$-hard to approximate on general graphs, but exactly solvable in $O(n^2k^2)$ on trees. Connected Subspace Clustering shows $\Omega(n^{1/2-\varepsilon})$ hardness on grids with holes. We therefore aim for strong empirical solutions with solver-certified gaps, not worst-case ratios. We use the tree result constructively: exact solutions on sampled spanning trees serve as warm starts. The spanning-tree view echoes the Bayesian partitioning of A Bayesian contiguous partitioning method for learning clustered latent variables.

The approximation algorithms of Improved Approximation Algorithms for Capacitated Location Routing and Inventory Routing Problem with Facility Location build forests and distance balls in a metric space. Neither guarantees connected pieces on an adjacency graph, so we treat them as reference points rather than competitors.

On method, the connectivity encoding follows the root-to-member flow formulation of Pattern Decomposition with Complex Combinatorial Constraints. The "repair inside the loop, not afterwards" principle comes from Hillebrand et al. There, in-loop merging (IterMerge) was best in 73.75% of 160 configurations, and unconstrained clustering produced up to 1,966 fragments for 25 clusters. That result motivates our expectation that post-hoc repair is costly, but it was measured on sea-level data, not logistics, so we test it here.

Research Program

Let $G=(V,E)$ be the adjacency graph of basic map units, let $J\subseteq V$ be the candidate depot units, and let $y_j\in\{0,1\}$ open depot $j$ at fixed cost $f_j$. Let $x_{ij}\in\{0,1\}$ assign unit $i$ to depot $j$, and let $\hat c_\theta(S_j, p_j)$ be the predicted routing cost of territory $S_j=\{i: x_{ij}=1\}$ served from depot position $p_j$. The model is

$$\min_{x,y}\ \sum_{j\in J} f_j y_j + \sum_{j\in J} \hat c_\theta(S_j, p_j)$$

subject to the following conditions. Each unit is assigned exactly once. Assignment is only to open depots, and every open depot is assigned its own unit. Capacity limits hold. Each $S_j$ is connected in $G$. Connectivity is encoded by sending $|S_j|-1$ units of a territory-specific flow out from the depot's unit, over edges whose two endpoints are both in $S_j$, with each member absorbing one unit. This encoding is polynomial in size and forces the territory to be connected and to contain its depot.

The predictor $\hat c_\theta$ is a Deep Sets model, embedded as in NEO-LRP. Its inputs are unit features (demand, area, perimeter, coordinates) expressed relative to $p_j$. It is trained on routing instances where depots are placed off-centre as well as centrally, so it can learn the sweep effect: that off-centre depots can yield cheaper tours than central ones.

To make the model tractable at hundreds of units, we warm-start it. We sample spanning trees of $G$ and solve connected location plus districting exactly on each tree by dynamic programming. The territory cost inside the dynamic program is a linearized version of the predictor, taken around the current solution. The best tree solutions seed the solver.

All final plans are scored the same way, by true routing cost. We run OR-Tools on every territory under sampled demand realizations, never by the predictor. This avoids the optimizer exploiting predictor errors, a failure documented for continuous-approximation formulas in the districting paper.

Baselines

The naive reference point is sequential cluster-first. We run connected Ward's hierarchical clustering, as in Applicability and Interpretability of Ward's Hierarchical Agglomerative Clustering With or Without Contiguity Constraints, to form $k$ connected territories. We place each depot at the candidate site nearest its territory's centroid, then route. This is the "do nothing clever" plan a planner would draw.

The strongest existing method for the location decision is NEO-LRP, retrained on our instances with the same predictor architecture and training budget. Its output is scored by true routing cost and by its count of disconnected fragments. The file reports only speedups for NEO-LRP; no reported result found on Lacuna for NEO-LRP's cost gap to best-known solutions on the P/T/B/S sets. We will therefore establish its numbers ourselves.

The strongest existing method for connected districting is the districting-and-routing iterated local search, fed with NEO-LRP's chosen depots. It is the natural "locate, then district" pipeline, and the relevant published figure for it is the 10.12% average improvement over continuous approximation.

We also run a stronger variant of that search that adds open, close and move-depot steps. This tests whether local search alone captures the joint effect.

For the unconstrained-cost end, we report Tree-Alg, which reports an average 11.64% gap from best-known solutions on Tuzun-Burke and Barreto instances.

All methods get the same instances, the same OR-Tools routing evaluation and the same wall-clock limit, at three budgets: 1, 10 and 60 minutes. Learned components get equal training data. Beating the baselines means lower true cost than every connected baseline at equal time, with zero fragments. For the price of connectivity, it means closing at least half of the cost gap between connected pipelines and unconstrained NEO-LRP.

The two key ablations remove one ingredient each. The first removes depot-relative features from the predictor. The second removes the spanning-tree warm start.

Why not just…?

Why not just run NEO-LRP and repair fragments afterwards? This is the obvious engineering answer. Its quality depends on how fragmented the unconstrained solutions actually are, which nobody has measured on logistics maps. If NEO-LRP territories on MSOA graphs are nearly always connected, repair is cheap and our method is unnecessary. We treat fragment counts from unconstrained NEO-LRP as the first go/no-go measurement. If fragmentation is substantial, we compare repaired NEO-LRP against the joint model at equal time. Hillebrand et al.'s result favouring in-loop over post-hoc merging suggests repair loses, but that was clustering error on climate data, not routing cost.

Why not just fix depots with NEO-LRP and then run connected districting? This is the most direct two-stage competitor. Survey evidence in A concise guide to existing and emerging vehicle routing problem variants puts the penalty of sequential planning at 5–15%. That figure concerns location versus routing in general, not connectivity specifically. The locate-then-district baseline is included precisely to measure the penalty in our setting. A penalty under about 1% would mean depot choice and territory shape barely interact, and we would say so.

Why not just add depot moves to the districting local search? This is a real threat, because local search is simple and scales. Its weakness is that opening a depot forces a large territory reshuffle that single-unit relocate and swap steps cannot reach in one move. We run this variant at all three time budgets. If it matches the joint model, the contribution shrinks to the depot-aware predictor, which we would then isolate through the feature ablation.

Why not just use continuous-approximation cost formulas? The districting paper shows they have roughly double the error of a learned oracle (5.46% versus 2.72% MAPE). It also shows that optimizing over them selects oddly shaped districts. We include a continuous-approximation version of our model for completeness, but expect it to lose.

Proposed Experiments

The primary testbed is the UK MSOA dataset from the districting paper: London, Bristol, Manchester, Leeds and the West Midlands, with 60, 90 and 120 units, where real adjacency is available. We add candidate depot units and fixed costs derived from land-use proxies.

The secondary testbed is the P, T, B and S location-routing benchmarks. We build adjacency graphs for them from Delaunay triangulation of customer coordinates, then delete edges that cross synthetic barriers such as rivers or lakes. This creates holes like those in the sea-level grid, and lets us vary how non-convex the map is.

We report five metrics. The first is true expected routing plus facility cost. The second is fragment count. The third is the price of connectivity, defined as connected cost divided by unconstrained cost, minus one. The fourth is the solver-certified optimality gap. The fifth is runtime.

The decisive checks run in order. First, we measure fragmentation in unconstrained NEO-LRP. If it is negligible, we stop and report that finding. Second, we measure the price of connectivity as barrier density increases. The claim predicts it grows with barriers and is partly recovered by moving depots. Third, we compare the joint model against locate-then-district and against local search with depot moves at equal time. Fourth, we test whether depot-relative features are responsible for any gain. Evidence would be that the ablated predictor places depots centrally and loses the sweep advantage described in the Tree-Alg paper.