Capacitated Arc Routing Problem¶
Find minimum-cost depot-returning vehicle tours that service demand-bearing network links while each tour stays within vehicle capacity.
Core Idea¶
The capacitated arc routing problem (CARP) seeks a minimum-cost collection of vehicle tours, each beginning and ending at a depot, that services every required demand-bearing edge of a network. The demand assigned to any one tour must not exceed vehicle capacity. The classical graph is undirected; mixed directed/undirected and time-limited versions are distinct extensions.[ref-c345f3e9a111][ref-05e432ce19da]
Scope of Application¶
Street-segment waste collection can map service onto street edges, collected load onto edge demand, a depot onto the route start/end and truck capacity onto the route limit. A Brussels case documents this modeling use, but the accessible abstract does not identify a particular route, yard or numerical result. Winter gritting has been modeled through a dynamic CARP extension, but its extra timing and replenishment rules must be specified rather than attributed to the classical definition.[ref-8d75f4541df4][ref-54c7d0e91c5f]
Clarity¶
Servicing an edge consumes its demand; merely traversing it to reach another edge or return to the depot is deadheading. A required edge may be crossed more than once yet serviced once. Capacity limits service load, while all travel contributes cost. CARP therefore differs from a node-demand vehicle-routing problem and from a single uncapacitated postman walk.[^ref-05e432ce19da]
Manages Complexity¶
Graph, required-edge set, service demands, depot, vehicle capacity and costs turn a messy routing task into explicit feasibility and objective tests. Check depot closure, one service assignment per required edge and per-route load before comparing total cost. An exact or heuristic solver addresses the formulated instance; the optimum is only as operationally useful as the modeled constraints.[^ref-c345f3e9a111]
Abstract Reasoning¶
Total demand divided by capacity supplies a crude lower bound on the number of tours when edge service cannot be split. On a constructed unit-cost cycle \(d-a-b-c-d\) with all four edges requiring one unit and capacity two, tours \(d-a-b-a-d\) and \(d-c-b-c-d\) each service two outward edges and deadhead home, giving a feasible total cost of \(4+4=8\). The single cost-four cycle could service all edges only with capacity at least four; cost eight is not claimed optimal merely from the tour-count bound. Counting travel on every crossing but demand only on service prevents false double loading.[^ref-05e432ce19da]
Knowledge Transfer¶
Waste collection and road treatment can share the link-demand/depot-tour structure, but the consumption that defines capacity changes by setting. The broader parent is Optimization Problem: feasible route collections are ranked by modeled travel cost. Mixed Chinese Postman is a related arc-routing problem, not a strict parent of the classical capacity-bounded form.
[^ref-c345f3e9a111]: Golden and Wong, original 1981 CARP paper, abstract. [^ref-05e432ce19da]: SIAM, Arc Routing, chapter 10, classical CARP and variants. [^ref-8d75f4541df4]: Gelders and Cattrysse, Brussels waste-collection case, original abstract. [^ref-54c7d0e91c5f]: Original dynamic winter-gritting CARP study, abstract.
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 (97th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Stacker Crane Problem — 0.83
- Network Simplex Algorithm — 0.77
- Street Hierarchy — 0.76
- Multi-commodity flow problem — 0.75
- BCMP network — 0.75
Computed from structural-signature embeddings · 2026-10-08