What Is the Capacitated Arc Routing Problem (CARP)?

From the Chinese Postman Problem to NP-hard fleet routing — a practitioner's guide to the mathematics behind snow plow optimization. Why CARP is the right formulation, and why most routing software ignores it.

Greg Dogum · 2026-02-15

There's a class of problems that every city deals with but almost no one outside operations research talks about. When a snow plow fleet needs to clear every road in a service zone, or a garbage truck needs to collect from every curb, or a street sweeper needs to pass down every lane — they're all facing the same mathematical challenge. The vehicle must traverse every edge in a road network, it has limited capacity (salt, waste volume, water), it must return to a depot to reload, and the goal is to do all of this in the shortest total distance.

This is the Capacitated Arc Routing Problem, or CARP. It was formally introduced by Golden and Wong in 1981, and despite being over four decades old as a named problem, it remains one of the most practically important — and computationally difficult — optimization challenges in fleet management. In fact, a 2025 paper by Zhao and Xiao achieved the first improvement to CARP's approximation bound since 1993 — a sign that the theoretical frontier is still very much active.

Starting from the basics: edges, not nodes

To understand CARP, it helps to start with a simpler problem and build up.

The most famous routing problem in mathematics is the Traveling Salesman Problem (TSP): given a set of cities, find the shortest route that visits each city exactly once and returns to the starting point. TSP is a node-routing problem — you're choosing which points to visit and in what order.

Now imagine a different job. A postal carrier doesn't need to visit a list of addresses picked from a map. They need to walk down every street on their route and deliver to every mailbox. They don't select which streets to cover — the entire network is the assignment. This is an arc-routing problem. The unit of work isn't a point on the map; it's a segment of road.

The simplest version of arc routing is the Chinese Postman Problem (CPP), formulated by the Chinese mathematician Guan Meigu in 1960 (with an English translation published in 1962). The question: what's the shortest walk that traverses every edge in a graph at least once and returns to the starting point? If the graph has an Euler circuit — a path that visits every edge exactly once — then the Chinese Postman solution is that circuit. If not, you need to duplicate some edges (retrace some roads) to create one. The polynomial-time solution was established by Edmonds and Johnson in 1973.

Here's the critical difference from TSP: the Chinese Postman Problem on undirected graphs is solvable in polynomial time. It's computationally "easy" in the formal sense. TSP is NP-hard. This is one of the rare cases where the arc-routing version of a problem is fundamentally easier than the node-routing version.

But the Chinese Postman Problem makes unrealistic assumptions: a single vehicle, unlimited capacity, and no constraints beyond covering every edge. The moment you add the realities of fleet operations — multiple vehicles, limited carrying capacity, depot returns, and service time windows — the problem becomes CARP. And CARP is NP-hard. Golden and Wong proved this in their original 1981 paper, showing that even finding a solution with deadheading cost less than 5/3 of optimal is NP-hard.

What makes CARP hard

CARP adds four layers of complexity to the Chinese Postman foundation:

Multiple vehicles. Instead of one truck traversing the entire network, you have a fleet. The network must be partitioned among vehicles so that each road is assigned to exactly one truck (no duplication of service) and every road is covered (no gaps). The partitioning itself is a combinatorial problem with an astronomical number of possibilities — for a city with 2,000 road segments and 10 trucks, the number of possible assignments dwarfs the number of atoms in the observable universe.

Capacity constraints. Each vehicle has a finite load — salt for a snow plow, volume for a garbage truck, water for a street sweeper. As the vehicle services edges, its capacity depletes. When it runs out, it must return to a depot to reload before continuing. The timing and location of these returns matter enormously: a poorly timed depot trip can add miles of deadhead (non-productive travel) to the route.

Depot location and returns. Vehicles start and end at depots, and must return to depots when capacity is exhausted. A city might have one central depot or several distributed across service zones. The position of depots relative to the road network fundamentally changes the optimal solution — a depot on the edge of the service area creates different route structures than one in the center.

Service constraints. In real operations, not all edges are equal. Snow plow routes have priority tiers — arterials must be cleared within 2–4 hours, collectors within 6–8, residential streets within 12–24. Waste collection has pickup time windows. Street sweeping has parking restrictions. These constraints further restrict the feasible solution space, often forcing routes that would be suboptimal by pure distance but are required by operational rules.

The combination of these constraints makes CARP NP-hard, meaning there's no known algorithm that can guarantee finding the optimal solution in reasonable time for large instances. The best existing exact algorithms are limited to moderate instances with roughly 140 vertices and 190 edges ¹. A city with 5,000 road segments, 20 trucks, 3 depots, and 3 priority tiers defines a solution space so vast that exhaustive search is physically impossible.

How solvers approach CARP

Since optimal solutions aren't tractable for real-world sizes, CARP solvers use a combination of construction heuristics, local search, and metaheuristics to find high-quality solutions in practical time.

Augment-merge was the first heuristic proposed for CARP, introduced alongside the problem itself by Golden and Wong ². It builds routes by starting with single-edge routes and progressively merging pairs of routes that can be feasibly combined, reducing the number of vehicles while keeping solutions feasible. It's fast and simple, but produces solutions that are far from optimal on complex networks.

Route-first, cluster-second is one of the most effective modern frameworks. First, construct a single giant tour that covers all required edges (ignoring vehicle capacity). Then, split that tour into feasible vehicle routes that respect capacity constraints. The splitting step — first formalized as an optimal procedure by Ulusoy in 1985, later refined by Prins et al. — finds optimal break points in the giant tour where depot returns should occur. This two-phase approach decouples the sequencing problem (what order to traverse edges) from the partitioning problem (which truck handles which edges), and has become a building block for modern metaheuristics ³.

Local search improves solutions by making small modifications — swapping edges between routes, reordering edges within a route, moving depot return points — and keeping any modification that reduces total cost. Common operators include 2-opt (reversing a segment within a route), or-opt (moving a sequence of edges to another position), and cross-exchange (swapping segments between two routes).

Metaheuristics guide the search beyond local optima. Tabu search maintains a list of recently reversed moves to avoid cycling. Genetic and evolutionary algorithms maintain a population of solutions and recombine them. Memetic algorithms combine population-based search with local search intensification. NSGA-II (Non-dominated Sorting Genetic Algorithm II) is particularly useful for CARP because it can simultaneously optimize multiple objectives — minimizing deadhead distance, minimizing clearance time, minimizing workload imbalance across trucks — and produce a Pareto frontier showing the tradeoffs between them.

Constraint programming approaches, like those developed by Kinable, van Hoeve, and Smith at Carnegie Mellon, formulate CARP as a constraint satisfaction problem and use domain reduction and branch-and-bound to find solutions. Their approach found routes 26% shorter than alternative integer programming formulations on Pittsburgh's road network — and 3–156% shorter than what the city was actually running using commercial software ⁴.

PlowPath uses a combination of these approaches: route-first, cluster-second for CARP construction (a priority-weighted giant tour, Ulusoy's split, then local search), greedy nearest-neighbor as a baseline comparison, and NSGA-II for multi-objective Pareto exploration. All solvers run on real OpenStreetMap road networks — not simplified test graphs — with elevation data where terrain matters. The pipeline walks through every stage.

The numbers in practice

When CARP solvers are applied to real road networks, the improvements over naive routing are consistent and significant.

The key metric is the deadhead ratio: the fraction of total distance that is non-productive repositioning (driving with the blade up, between service passes). Across the towns in the gallery (October 2026), a naive greedy approach — each truck drives to the nearest unplowed street — produces deadhead ratios from about 23% to 71%, 45% at the median. On a typical town, close to half of all driving under a greedy strategy accomplishes nothing.

CARP-optimized routing on the same networks, with the same trucks and the same priority constraints, brings the deadhead ratio to between under 1% and 41%, 15% at the median. Here is one town, read live from the gallery:

Brattleboro, VT, 2 trucks: deadhead ratio and blade-up driving, from the gallery
Greedy baseline	55.5%	396 km
CARP	17.6%	68 km

Blade-up driving: 83% less. Open the runs

Marquette, Michigan shows it at every fleet size from one truck to six. That reduction in wasted driving comes with no additional trucks, no additional hours, and no changes to priority policies. The same fleet, doing the same job, just sequencing streets differently.

Published research from other groups confirms the magnitude. The Iowa DOT optimization study measured a 13.2% reduction in deadhead distance versus existing manually-designed routes. A northern Utah study across 12 regions found a 14.8% average reduction in deadhead miles. The CMU Pittsburgh study found that in the worst case, the city's existing routes were 156% longer than the optimized solution — meaning the truck was driving more than 2.5 times the distance it needed to ⁴.

Where CARP shows up in the real world

CARP isn't just an academic exercise. It governs the routing logic behind several large-scale municipal operations:

Snow removal is the canonical application. Every road must be plowed. Trucks carry limited salt. Priority tiers dictate service order. Depots are fixed. This maps directly to the CARP formulation, and it's the domain where the gap between naive routing and optimized routing is most consequential — because deadheading in snow operations directly translates to slower clearance times on residential streets, higher fuel costs, and increased crash risk.

Waste collection is the most extensively studied CARP application. Garbage trucks must traverse every street with curbside pickup, emptying into the truck until it reaches capacity, then driving to a disposal site to offload. Danish researchers applied large-scale CARP solvers to networks with over 6,000 nodes and nearly 4,000 required edges, handling multiple waste fractions and vehicle types with the Multi-Compartment CARP formulation.

Street sweeping follows the same structure — every lane must be swept, the water/debris tank has a finite capacity, and the sweeper returns to base to refill. Parking restrictions add time-window constraints that further complicate the routing.

Power line inspection is a newer application driven by drone technology. Planning flight paths to inspect every segment of a power grid under battery constraints is structurally identical to CARP — and has become an active research area in the 2020s, including work on uncertain-demand CARP variants where inspection times vary.

Mail delivery, utility meter reading, road inspection, herbicide spraying — any operation where a vehicle must traverse every segment of a network under capacity constraints is a CARP instance. The edge weights change (distance, time, fuel, salt), the capacity semantics change (volume, weight, liquid), but the combinatorial structure is identical.

CARP vs. the problems you've heard of

The taxonomy of routing problems can feel like alphabet soup, so here's how CARP relates to the names you might already know:

The Chinese Postman Problem is CARP without capacity constraints and with a single vehicle. It's the theoretical lower bound — the shortest possible traversal if you had one truck with infinite salt. It's solvable in polynomial time and gives you the floor that no practical solution can beat.

The Vehicle Routing Problem (VRP) and its capacitated variant (CVRP) are node-routing problems. They optimize which stops to visit, not which edges to traverse. VRP is what Amazon, UPS, and DoorDash solve. It's a different mathematical structure, and solvers built for VRP don't transfer to CARP — a point we cover in detail in Arc Routing vs. Node Routing.

The Traveling Salesman Problem (TSP) is the single-vehicle, uncapacitated version of VRP. It's the most famous NP-hard problem in computer science, but it's a node problem. It doesn't model edge traversal.

Arc routing is the family that CARP belongs to. The most comprehensive recent survey is by Corberán, Eglese, Hasle, Plana, and Sanchis (2021), covering the full landscape of arc routing variants. Within this family, you also find the Rural Postman Problem (only some edges require service), the Windy Postman Problem (edge costs differ by direction), the Min-Max CARP (minimize the longest route rather than total distance), and the Synchronized Arc Routing Problem (Salazar-Aguilar et al., 2012) for tandem plowing of multi-lane roads. Each variant captures a different real-world constraint.

Why this matters for municipalities

Most cities don't know they have a CARP problem. They know they have a snow removal problem, or a waste collection problem, or a street sweeping problem. The routes were designed years ago by experienced operators, they work well enough, and the political cost of changing them is nonzero.

But "well enough" has a quantifiable cost. When your fleet's deadhead ratio is 50% instead of 31%, that 19-point gap represents thousands of unproductive miles per season. It's fuel, labor, vehicle wear, and — in snow operations — the difference between clearing residential streets in 8 hours versus 12. As we documented in the deadheading article, U.S. agencies spend $2.3–4 billion annually on winter road maintenance. Even modest efficiency gains at that scale translate to real money and real safety improvements.

CARP solvers don't require new trucks, new depots, or new infrastructure. They require the data you already have — your road network (freely available from OpenStreetMap), your depot locations, your fleet capacities, your service priorities — and they produce routes that are measurably shorter while respecting every operational constraint.

The math is four decades old. The road networks are freely available. The solvers exist — the gallery runs them on real road networks. The only thing missing is the willingness to let an algorithm challenge institutional routing habits.

PlowPath solves CARP on real OpenStreetMap networks for every town in the gallery. Explore the results →

References

Baldacci, R. & Maniezzo, V. (2006); Bartolini, E., Cordeau, J.-F. & Laporte, G. (2013); Bode, C. & Irnich, S. (2012). See Corberán et al. (2021) for a comprehensive review of exact CARP algorithms and their practical limits. ↩
Golden, B.L. & Wong, R.T. (1981). "Capacitated Arc Routing Problems." Networks 11(3):305–315. DOI: 10.1002/net.3230110308 ↩
Prins, C., Lacomme, P., & Prodhon, C. (2014). "Order-first split-second methods for vehicle routing problems: A review." Transportation Research Part C 40:179–200. DOI: 10.1016/j.trc.2014.01.011. See also: Ulusoy, G. (1985). "The fleet size and mix problem for capacitated arc routing." European Journal of Operational Research 22(3):329–337. ↩
Kinable, J., van Hoeve, W.J., & Smith, S.F. (2021). "Snow Plow Route Optimization: A Constraint Programming Approach." IISE Transactions 53(6):685–703. DOI: 10.1080/24725854.2020.1831713 ↩ ↩²