Capacitated Arc Routing Problem¶

Find minimum-cost depot-returning vehicle tours that service demand-bearing network links while each tour stays within vehicle capacity.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13042
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Combinatorial Optimization, Vehicle Routing → Mathematics
Aliases: CARP, Classical capacitated arc routing problem

Core Idea¶

The capacitated arc routing problem (CARP) asks how to service demand on links of a network using depot-returning vehicle routes that have limited carrying capacity. In the classical undirected form, a connected graph has nonnegative traversal costs, a depot vertex, and a subset of required edges with positive service demands. Choose a collection of closed depot tours so that each required edge receives service on one tour, the sum of serviced demand on every tour does not exceed vehicle capacity, and total travel cost is minimized.^[1]^[2]

Servicing an edge and merely traversing it are different actions. A truck may pass over an edge without collecting its demand to reach another required edge or return to the depot; this is deadheading. A required edge can even be crossed again as deadhead travel after its single service assignment. Capacity constrains assigned service load, not every traversal. It may force several tours even when one uncapacitated walk could cover all required edges.^[2]

The title names a reusable optimization problem, not a particular route or heuristic. Golden and Wong introduced formal formulations and complexity analysis; subsequent exact cutting-plane and approximate methods address instances without changing what counts as a feasible CARP solution.^[1]^[3]

Structural Signature¶

Service network: a connected graph whose edges have traversal costs; the classical form is undirected. Directional arcs belong to a mixed or directed variant.^[2]
Required edges and demands: only designated edges require service, and each carries a load demand. Traversing a nonrequired edge can still be useful.
Depot and vehicles: every selected vehicle route starts and ends at the designated depot.
Per-tour capacity: the demand serviced on any one route is no greater than vehicle capacity; demand greater than a vehicle's capacity makes a non-split instance infeasible.
Service assignment: each required edge is serviced once across the route collection, even if traversed more often.
Deadhead connections: a route may travel edges without service to connect its required tasks or return home.
Objective: among feasible collections of routes, minimize summed modeled traversal cost.^[2]

Condensed: required link-demand + depot tours + load bounds + service/deadhead separation + minimum total travel.

Sig role-phrases: graph edges → carry travel costs; required edges → carry service obligations and demand; depot → closes every tour; vehicle capacity → bounds each tour's assigned service; deadhead traversal → connects tasks without servicing them; objective → sums all traveled edge costs.

What It Is Not¶

Not node-demand vehicle routing. A vertex-delivery problem places service at stops; CARP places it along edges. A transformation may relate formulations computationally, but does not erase the original location of demand.
Not the Chinese postman problem or the Mixed Chinese Postman Problem. Their standard all-link single-walk coverage does not include CARP's subset of required links, vehicle-load partition and collection of depot tours. The mixed postman entry also has directed and undirected links, unlike classical undirected CARP.
Not a guarantee of one traversal per required edge. Exactly one service assignment still permits repeat deadhead crossings of the same edge.
Not a route-length or driver-shift cap by definition. Those may be added to a CARP variant. The classical vehicle capacity is the bound on demand serviced by a vehicle; replacing it with a time limit changes the constraint type.^[2]
Not automatically a mixed-graph problem. One-way links yield a mixed/directed CARP extension. The original classical formulation should not be retroactively stated as mixed.^[2]
Not an algorithm or application outcome. A path-scanning heuristic and a municipal route plan are ways to address an instance, not the abstraction itself.^[1]^[4]

Scope of Application¶

For street-segment waste collection, streets or street sides to be served become required graph links, estimated collected load becomes edge demand, a collection yard is the depot and a truck's carrying limit is capacity. Gelders and Cattrysse documented a Brussels waste-collection model based on CARP. Their case supports a modeling application; it does not imply that the bare classical model captures every real turn, crew, disposal-site or time-window constraint.^[4]

Winter road service can likewise put work on road segments rather than house-number stops. A winter-gritting study explicitly formulated a dynamic CARP variant. Whether hopper material, salt application, plowing time or some combination supplies the relevant “capacity” depends on the operation; time dependence and replenishment may require extensions to the classical model.^[5]

Formal graph instances need no physical roads. The defining questions are where the service demand lies, which crossings consume capacity and which alternatives minimize cost under the route constraints.

Clarity¶

CARP separates coverage from movement and local feasibility from global quality. A route can traverse all required edges yet fail because the served-demand sum exceeds capacity. Several individually feasible depot tours can still be globally expensive because of unnecessary connecting travel. A graph with required edges on opposite sides of the depot may need repeated traversal of central edges, which is not duplicate service.^[2]

The seed's phrase “capacity (load, time away from depot or distance)” is too broad for the classical identity. Load or service-consumption capacity is central; duty duration and maximum distance are separately modeled restrictions. Likewise, mixed links are a named variant, not an assumption of every CARP instance.^[2]

Manages Complexity¶

A real service territory has innumerable possible route sequences. CARP converts it into a graph, required-link set, demand vector, capacity and cost objective. This makes an explicit feasibility checker possible: every required edge must be serviced once, every route must return to the depot, and no route may exceed capacity. Only feasible collections are compared by total modeled cost.

The model also exposes its own omissions. If vehicle turn restrictions, disposal trips or seasonal priorities are not encoded, the solver's optimum is an optimum for the modeled problem, not a guarantee of operational superiority. Formal lower bounds and cutting-plane methods can evaluate solution quality, while heuristics may produce useful feasible routes when exact search is difficult.^[1]^[3]

Abstract Reasoning¶

For a proposed solution, list each required edge and its assigned service tour. Sum its service demand by route and compare with capacity; then verify depot closure and legal connectivity. Count every traveled edge in cost, including deadheading and repeated crossings. A service edge's demand is charged once to the route that serves it, whereas traversal cost can be charged on every crossing. Conflating those counts makes a physically feasible tour appear overloaded or artificially cheap.^[2]

A simple lower bound on the number of tours is the ceiling of total required demand divided by vehicle capacity, assuming unsplittable edge service and sufficient vehicles. This bound may not be attainable because of service geography or connectivity and is not a lower bound on total distance by itself. The global optimum must jointly choose task partition and each tour's connecting travel.

Knowledge Transfer¶

The same role mapping transfers from collection to road treatment: graph links are service locations, demand consumes a vehicle resource, and deadhead travel connects tasks. What cannot transfer unchanged is the operational meaning of capacity. Waste loads fill a truck; salting consumes material; plowing without consumable material may instead have route-duration constraints and require a distinct variant.^[4]^[5]

The general Optimization Problem node is the accepted strict parent because CARP instantiates feasible alternatives and a cost objective. The mixed postman problem is a related arc-routing neighbor but not a parent: its all-link single-walk and mixed-direction commitments do not contain the classical capacity-partitioned CARP.

Examples¶

Fully specified four-edge cycle (constructed)¶

Let the undirected graph be exactly the cycle \(d-a-b-c-d\), with depot \(d\). Each of its four edges is required, has unit service demand, and costs one per traversal; each vehicle has capacity two. Tour A is \(d\to a\to b\to a\to d\): service \(da\) and \(ab\) on the outward legs, then deadhead \(ba\) and \(ad\) home. Its load is \(2\) and travel cost \(4\). Tour B is \(d\to c\to b\to c\to d\): service \(dc\) and \(cb\) outward, then deadhead \(bc\) and \(cd\) home. It too has load \(2\) and cost \(4\). All four required edges are serviced exactly once, though each is traversed again, and total travel cost is \(8\). This is a constructed feasible solution, not an optimality claim. The load bound proves at least two tours, but it does not by itself prove that cost \(8\) is optimal; that needs a separate cost lower bound.

Mapped back: graph = four unit-cost cycle edges; required demands = four unit loads; depot = \(d\); per-tour bound = two; service assignments = \(\{da,ab\}\) and \(\{dc,cb\}\); return legs = deadheading; feasible total traversal cost = \(4+4=8\).

Brussels waste collection¶

Gelders and Cattrysse's original Brussels waste-collection case reports use of a capacitated arc-routing model for street service. The accessible case abstract supports that modeling application, but does not expose a particular street graph, route sequence, load or measured cost here; none is invented. Application-specific disposal and labor details must be checked rather than assumed to be represented by the bare CARP definition.^[4]

Mapped back: documented street links = service-task type; collected waste = capacity-consumption type; depot-returning route set = modeled planning form. The source available here does not identify the actual yard or an executed tour, so this is a bounded application mapping, not a worked route.

Mixed-direction near miss¶

If the street network has one-way arcs as well as undirected links, the same broad planning idea remains, but its exact graph domain is a mixed capacitated arc routing variant. Calling that input the classical undirected CARP hides a real feasibility difference.^[2]

Structural Tensions¶

Service versus deadheading is a distinction, not a cost tension. In the cycle case the return legs incur cost but no second unit of demand. Treating them as renewed service would incorrectly overload both tours. Diagnostic: which traversals fulfill demand, and which only connect a legal depot tour?^[2]

Capacity feasibility versus travel cost. The single cycle \(d-a-b-c-d\) costs \(4\) and can service all four links only if capacity is at least \(4\). At capacity \(2\), that shorter service tour is infeasible, while the explicit two-tour plan is feasible at cost \(8\); stricter load feasibility requires extra depot travel. The model does not make over-capacity service a permissible cheap alternative, so this is a constraint-induced cost pressure, not a choice to violate capacity. Diagnostic: how much modeled travel is added when the capacity ceiling forces service partition and repeated return legs?^[2]

Structural–Framed Character¶

CARP sits toward the structural end of the spectrum: once the graph, depot, required edges, demands, capacity and costs are fixed, route feasibility and objective value are mathematical. Its evaluative weight is nevertheless framed by the chosen travel-cost model; a lower number does not automatically settle safety, labor or environmental quality. Human collection practice determines which street segments require service and how a truck's usable capacity is measured. Operations-research institutions developed and circulated the CARP vocabulary for that service-on-links geometry; the formal pattern also travels to winter road treatment when link demand and a consumable vehicle resource are genuinely specified. Importing “arc routing” into a node-delivery problem without link service is only analogy, not recognition of the same identity. Its character: a formally exact, application-framed optimization problem whose answer is only as operationally relevant as its graph, demand and cost encoding.

Structural Core vs. Domain Accent¶

The portable skeleton—minimize an objective over feasible alternatives—belongs to the live Optimization Problem parent. CARP's domain-bound mechanism is service on edges, assignment of that service to depot-returning tours, deadhead traversal costs and per-tour load capacity. The named entry fails the prime bar because node-demand delivery, uncapacitated postman coverage and unrelated scheduling preserve optimization while dropping the service/deadhead or load-partition roles that make CARP identifiable. The abstract optimization skeleton transfers; the full CARP mechanism does not.

This entry is a kind of Optimization Problem.

Optimization Problem is the accepted strict genus: capacity-respecting depot tours form feasible alternatives ordered by traversal cost. Mixed Chinese Postman Problem is an arc-routing neighbor, not a parent. Required-link traversal without service and a heuristic for finding tours are not the problem identity.

Relationships to Other Abstractions¶

Current abstraction Capacitated Arc Routing Problem Domain-specific

Parents (1) — more general patterns this builds on

Capacitated Arc Routing Problem is a kind of Optimization Problem Domain-specific

CARP ranks feasible capacity-respecting service-tour collections by modeled travel cost, specializing an optimization problem.

Hierarchy path (1) — routes to 1 parentless root

Capacitated Arc Routing Problem → Optimization Problem → Optimization

Neighborhood in Abstraction Space¶

Capacitated Arc Routing Problem sits in a sparse region of the domain-specific corpus (97^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Node-demand VRP services stops, not edges. Chinese postman and mixed postman formulations center on a coverage walk, not capacity-bounded multiple service tours. Mixed CARP, open CARP and time-limited CARP are extensions with added or changed conditions. A deadhead traversal crosses an edge without assigning its service demand again. The distinction between route feasibility and optimality remains essential.^[2]