The Edge-based Contiguous p-median Problem with Connections to Logistics Districting

arXiv:2608.11230 · cs.AI, cs.DM · Submitted 2026-07-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "The Edge-based Contiguous p-median Problem with Connections to Logistics Districting".

Jane: The paper was written by Zeyad Kassem and Adolfo Escobedo from Arizona State University and North Carolina State University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title and Authors: Tom: Welcome back to the show, everyone. Today we’re diving into a fresh arXiv paper, and it’s a mouthful — “The Edge-based Contiguous p-median Problem with Connections to Logistics Districting.” Jane, I’m going to need you to help me unpack that title before we even get to the math.

Jane: Happy to, Tom. So the title is basically a recipe. “Edge-based” means we’re talking about the roads themselves, not the intersections. “Contiguous” means each territory has to be one solid, unbroken piece. And “p-median” is a classic optimization problem where you pick a fixed number of centers — that’s the “p” — to serve all the demand points, minimizing total travel distance.

Tom: So instead of the usual setup where customers live at street corners, here the customers are spread out along the streets themselves. That feels way more realistic for delivery trucks, doesn’t it?

Jane: Exactly. Think of a delivery driver. They don’t stop at an intersection and serve everyone from there. They drive down the street and drop packages at houses along the way. So modeling the roads as the units being assigned to a depot just makes sense.

Tom: And the authors — Zeyad Kassem and Adolfo Escobedo — they’re coming at this from Arizona State and North Carolina State. I love that they’re not just solving a theoretical puzzle; they’re clearly thinking about last-mile logistics, which is the most expensive and least efficient part of the whole supply chain.

Jane: Right, and that’s the “logistics districting” part. Once you have these contiguous territories, you can assign each one to a driver or a warehouse. It helps with route planning, with balancing workloads, even with reducing emissions, because drivers aren’t crisscrossing through each other’s areas.

Tom: And the big deal here is that they’re not just proposing a model. They’re actually solving it on real road networks, some with over two thousand seven hundred nodes and nearly three thousand five hundred edges. That’s a real city-sized problem.

Jane: Yeah, and that’s where it gets interesting, because making territories contiguous is notoriously hard to enforce in optimization. It’s easy to say you want them connected, but writing that down as a mathematical rule without blowing up the problem size is the real challenge.

Tom: So we’ve got a practical problem, a realistic model, and a computational hurdle. I’d say we’ve got a full episode ahead of us. Let’s dig into how they actually pulled it off.

Summary of the Paper: Tom: So, Jane, we’ve got the title unpacked. Now let’s talk about what the paper actually does. The authors introduce two different ways to enforce that contiguity we were just talking about.

Jane: Right. The first approach uses something called “cut set” constraints. Imagine you draw a circle around a group of roads. The cut set is the set of roads that cross the boundary of that circle. The constraint says: if you’ve assigned all the roads inside the circle to one center, then at least one road crossing the boundary has to belong to that same center too. Otherwise, you’ve created an island.

Tom: And the problem is there are an exponential number of possible circles you could draw. You can’t write them all down for a big city. So they pair that model with a branch-and-cut algorithm, which starts with no contiguity constraints, solves a relaxed version, finds where the territories are broken, and adds only the cuts that are violated.

Jane: That’s the smart part. They don’t generate all the constraints upfront. They let the solver find the ones it needs. But the second approach is even more elegant. Instead of cut sets, they use shortest paths.

Tom: Shortest paths — so for every road assigned to a center, they force all the roads along the shortest path from that center to that road to also be assigned to the same center. That automatically guarantees the territory is connected.

Jane: Exactly. And the beauty is that this is a polynomial number of constraints. You can write them all down upfront and just hand the model to an off-the-shelf solver like CPLEX. No fancy separation algorithm needed.

Tom: And the results are striking. On the road networks they tested, the shortest-path model was up to seventeen times faster than the cut-set branch-and-cut approach. Seventeen times, Jane.

Jane: That’s a huge speedup. And it’s not just about speed. For the largest road network they tested, the cut-set approach ran out of memory entirely. The shortest-path model solved every instance to optimality in under five hours on average.

Tom: So the simpler-looking constraint set actually wins big. That’s a nice reminder that in optimization, sometimes the most elegant formulation is the one that performs best, not the one with the fanciest algorithm.

Jane: And there’s a bonus. They show that these shortest-path constraints are what they call “supervalid inequalities” for the simpler p-median problem without contiguity. That means you can add them to the basic model, and they’ll cut off some non-optimal solutions without ever cutting off all the optimal ones. So they speed things up even when you don’t actually need contiguity.

Tom: So it’s a win-win. You get contiguity when you need it, and you get faster solving even when you don’t. Let’s talk about what this means for real-world districting in the next segment.

Improvements Suggested by the Paper: Tom: Alright, Jane, so we’ve seen the two models and the speedups. But what really gets me excited is the last part of the paper, where they connect this to edge-based districting. That’s where you add a work balance requirement on top of contiguity.

Jane: Right. Because in real logistics, you don’t just want compact territories. You want each driver to have roughly the same amount of work. Otherwise, one driver finishes in four hours and another is out for twelve. So they add constraints that limit the total demand in each territory to be within a certain tolerance of the average.

Tom: And here’s where it gets wild. They tested the cut-set based districting model — the one from previous work — and it couldn’t find a single feasible solution within twelve hours on any of the test instances. Not one.

Jane: That’s brutal. But the shortest-path version? It solved about sixty percent of those same instances to optimality. And for the ones it couldn’t solve, it still found feasible solutions with small optimality gaps.

Tom: So the shortest-path constraints aren’t just faster on the p-median problem. They’re the difference between solving and not solving when you add the balance requirement. That’s a massive practical improvement.

Jane: And there’s a subtle but important point about the quality of the solutions. With cut-set constraints, you can get a territory that’s technically connected, but the shortest path from the center to some road might leave the territory and come back in. That means the driver has to either leave their assigned area or take a longer route. The shortest-path constraints prevent that from happening entirely.

Tom: So it’s not just about enforcing contiguity. It’s about enforcing a useful kind of contiguity — one where the driver can actually reach every road they’re responsible for without crossing into someone else’s turf.

Jane: Exactly. And that has real consequences for deadhead distance — the miles you drive without doing any work. Less deadhead means lower fuel costs and lower emissions.

Tom: I love that they also tested how the tolerance level affects difficulty. When the balance tolerance is tight — like one percent — the problem gets much harder, and many instances become infeasible because you simply can’t split the demand that evenly. But at fifty percent tolerance, they solved everything quickly.

Jane: That makes sense. It’s like trying to split a pizza into equal slices. If the slices have to be exactly the same weight, you might not be able to do it with the cuts you’re allowed to make. But if you allow some variation, you can always find a way.

Tom: So the paper doesn’t just give you a faster algorithm. It gives you a better understanding of when the problem is even solvable. That’s the kind of insight practitioners need before they commit to a planning model.

Conclusion: Tom: Alright, we’ve covered a lot of ground on “The Edge-based Contiguous p-median Problem with Connections to Logistics Districting.” Let’s wrap it up.

Jane: Yeah, let’s recap the big takeaways. The paper introduces two ways to enforce contiguity in an edge-based p-median model. The cut-set approach is theoretically clean but computationally heavy. The shortest-path approach is simpler, faster, and actually solves real-world-sized instances.

Tom: And the speedups are real — up to seventeen times faster, and it solved instances that the cut-set approach couldn’t handle at all due to memory limits.

Jane: Plus, the connection to logistics districting is huge. When you add work balance constraints, the cut-set model becomes practically unsolvable, while the shortest-path model handles most instances to optimality.

Tom: And the quality of the solution is better too. Drivers get territories where they can actually reach every road without leaving their area. That means less deadhead, lower costs, and lower emissions.

Jane: For anyone working in last-mile delivery, warehouse planning, or even public sector districting, this is a tool that could genuinely change how you plan your service areas.

Tom: And for the researchers out there, the fact that the shortest-path constraints are supervalid inequalities for the simpler p-median problem is a neat theoretical result with immediate practical payoff.

Jane: So we say goodbye to this paper, but we’re definitely taking its lessons with us. Next up, we’ve got another paper that I think is going to push even further into the logistics space.

Tom: Sounds good, Jane. Thanks to everyone listening, and we’ll see you in the next segment.

Zeyad Kassem, Adolfo Escobedo

Arizona State University · North Carolina State University

cs.AI, cs.DM

Submitted: 2026-07-30

Updated: 2026-08-13

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 69/100

The gist: This paper introduces the edge-based contiguous p-median (ECpM) problem, which partitions the roads in a network into a given number of compact and contiguous territories.

Key concepts

p-median problem
A classic optimization problem where a a fixed number of centers (the 'p') are selected to serve all demand points. The goal is to minimize the total travel distance from these centers to the customers.
Contiguous Territory
A geographical area that is one solid, unbroken piece. This ensures that when assigning roads or delivery areas, each assigned territory forms a single connected unit.
Logistics Districting
The process of dividing service areas (districts) to assign them to drivers or warehouses. The paper applies this concept by modeling road networks and ensuring territories are contiguous for efficient route planning.
Shortest-Path Constraints
A mathematical rule that for every road assigned to a center, all roads along the shortest path from that center must also be assigned to that same center. This automatically guarantees the territory is connected.

Terminology

Summary

This paper introduces the edge-based contiguous p-median (ECpM) problem, which partitions the roads in a network into a given number of compact and contiguous territories. The paper states: This paper introduces the edge-based contiguous p-median (ECpM) problem to partition the roads in a network into a given number of compact and contiguous territories.

The paper makes several contributions to territorial design. First, it introduces the ECpM problem and two exact binary formulations to solve it. The formulations partition a road network into a fixed number of compact and contiguous territories by locating centers and allocating roads to these centers, with the objective of minimizing the total distance within each territory. The two proposed formulations differ in how they enforce contiguity: the first requires an exponential number of cut set constraints, while the second utilizes a polynomial number of shortest-path constraints.

As a second contribution, the paper introduces "a separation algorithm that generates only a small number of cut set constraints to solve the first model, namely, a branch-and-cut (B&C) algorithm." The second model is solved using off-the-shelf methods (i.e., branch-and-bound).

As a third contribution, the paper derives three logically equivalent sets of constraints for enforcing shortest-path contiguity (SPC) and compares them using polyhedral techniques. The SPC constraints are also demonstrated to be supervalid inequalities for the simpler edge-based p-median problem (EpM), meaning that they may cut off integer-feasible solutions and some, but not all, of the optimal solutions for this simpler problem.

As a fourth contribution, the paper carries out experiments to test the computational impacts of applying the SPC-based model on road networks with over 2,700 nodes and close to 3,400 edges.

As a final contribution, the paper explores theoretical and computational implications of the proposed p-median models on edge-based districting (EBD).

The paper first introduces the EpM problem, which aims to determine the optimal location of p center nodes and allocation of edges to them. The underlying road network is represented as an undirected planar graph G = (V, E), assumed to be connected. The model minimizes the sum of weighted distances from each facility to its allocated customers, with the objective function: min Σi Σ(j,k) d(i,(j,k)) x(i,(j,k)), subject to constraints ensuring each edge is allocated to exactly one center node, exactly p center nodes are selected, and edges can only be allocated to selected center nodes.

The first contiguous formulation, ECpM-CSC, imposes contiguity by forcing every cut set that separates any pair of nonadjacent edges allocated to a certain territory to allocate at least one edge from the cut set to the same territory. The cut set contiguity constraints, which are exponential in number, are analogous to subtour elimination constraints of the TSP. The constraints ensure that any edge (j, k) allocated to center node i should be adjacent to other edges allocated to the same center node.

The paper pairs ECpM-CSC with "an integer separation scheme, namely a branch-and-cut algorithm (B&C). The algorithm generates only those cut set contiguity constraints that are deemed necessary based on the solution to a relaxed version of ECpM. The procedure begins by solving a relaxed version of the original model in which all contiguity constraints are omitted," then iteratively detects contiguity violations using breadth-first search and adds violated constraints as lazy constraints.

The alternative formulation, ECpM-SPC, uses shortest-path contiguity constraints. The main intuition is that for any connected planar graph with more than one edge, if edge (j, k) is allocated to center node i, then so must all edges along the shortest path that joins them. The paper derives three logically equivalent constraint sets (SPC-1, SPC-2, SPC-3), and through polyhedral analysis demonstrates that SPC-3 induces the tightest formulation. The paper proves that PSPC-2 ⊆ PSPC-1, and this inclusion can be strict and that PSPC-2 = PSPC-3.

The paper proves that the SPC constraints are supervalid inequalities of EpM. Theorem 3.4 states: "Let G = (V, E) be an undirected connected planar graph with E ≥ 2. In an optimal solution to EpM, if edge (j, k) is assigned to center node i (i.e., x(i,(j,k)) = 1), then there exists an optimal solution where all edges in SP(i,(j,k)) are also assigned to i."

The computational tests were performed on 14 real-world road networks located in Denmark, with V ranging from 198 to 2,773 nodes and E ranging from 265 to 3,472 edges. A total of 84 instances were created by fixing one of six numbers of districts, p ∈ 2, 10, 30, 40, 50, 100.

The results show that "for all six instances associated with the largest road network tested, namely RN14, ECpM-CSC ran out of memory. Conversely, ECpM-SPC was able to solve each instance associated with this road network in 4.69 hours, on average. For instances associated with RN1 to RN13, the average and median improvement factors of ECpM-SPC relative to ECpM-CSC (i.e., CSC/SPC) were 6.79 and 5.16, respectively. The improvement factors decrease as network size increases, ranging from 17.31 for RN1 to 2.61 for RN13. Over these thirteen road networks, ECpM-SPC outperformed ECpM-CSC in 83.3% (65 of 78) of all associated instances."

The computational benefits of SPC constraints are more pronounced on instances with more districts. For example, for the instance of RN12 with p = 100, solving ECpM-CSC took 10.88 hours, but solving ECpM-SPC took only 54.7 minutes, yielding an 11.95x improvement.

Regarding the impact of SPC constraints on EpM, for instances associated with RN1 to RN8, EpM outperformed ECpM-SPC, but for all but one instance associated with RN9 to RN13 (each with E ≥ 1,805), ECpM-SPC outperformed EpM by 2.45x, on average. Additionally, EpM ran out of memory for all instances associated with RN 14, but ECpM-SPC solved all of these instances to optimality.

The paper explores how ECpM can be transformed into a logistics districting model by imposing a work balance criterion. The balance constraints are: Σ(j,k) b(j,k) x(i,(j,k)) ≤ b̄(1+τ)w i and Σ(j,k) b(j,k) x(i,(j,k)) ≥ b̄(1-τ)w i, where b(j,k) is the demand along edge (j,k), b̄ is an equal apportionment of demand per district, and τ is the allowed percentage deviation.

The paper contrasts two districting models: EBD-CSC (cut set-based) and EBD-SPC (shortest-path-based). The paper notes that the combination of the SPC and balance constraints forces the allocation of (4, 9) to the second district with center node 7 in the provided example, illustrating how SPC constraints interact with balance constraints differently than cut set constraints.

The computational tests for EBD featured two medium-sized road networks (RN4 and RN5), with 54 instances created by fixing one of nine numbers of districts, p ∈ 2, 4, 6, 8, 10, 20, 30, 40, 50, and one of three work balance tolerance settings, τ ∈ 1%, 10%, 50%.

For EBD-CSC, "two exact methods were implemented: B&C and B&B&Cut, but neither could find a feasible solution within the 12-hour time limit for any of the tested instances. On the other hand, EBD-SPC was able to solve 59.3% (32 of 54) of the instances to optimality."

The results show that average computational times, average relative percentage gap, and maximum relative percentage gap tend to decrease as τ increases from 1% to 50%. Additionally, 72.7% (8 of 11) of the infeasible instances obtained in this analysis arose from the setting τ = 1%.

The paper concludes that "the SPC constraints can expedite the solution of large-scale instances of this problem and the simpler edge-based p-median problems (i.e., ECpM without contiguity), with speedups of up to 17x for the instances tested in this work. The paper also notes that the shortest path-based formulation eliminates a potential drawback in subsequent routing operations by preventing the buildup of deadhead distance and avoiding the need to travel beyond the district boundaries to reach specific customers."

Improvements for AI systems

Based on the paper, here are specific improvements that can be made to AI systems, along with what the improved system can do:

Improvement: Implement the Edge-based Contiguous p-median (ECpM) problem with Shortest-Path Contiguity (SPC) constraints as the core optimization engine, replacing cut-set based approaches.

What the improved AI system can do:

  • Partition road networks (up to 2,773 nodes, 3,472 edges) into compact, contiguous territories up to 17x faster than cut-set based branch-and-cut methods

  • Solve instances with over 9.6 million binary variables that cause competing methods to run out of memory

  • Handle larger-scale logistics districting problems (e.g., last-mile delivery zones) that were previously intractable

Related papers