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

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.