Garbage Collection Routing
Chinese Postman · CARP · Edmonds-Johnson / Golden-Wong
Every street segment that requires service must be traversed by a collection truck. The classical Chinese Postman Problem finds the minimum-cost traversal of all edges in a graph; Edmonds & Johnson (1973) gave the polynomial-time algorithm that solves it via minimum matching on odd-degree vertices. The Capacitated Arc Routing Problem (Golden & Wong, 1981) adds vehicle capacity and a depot, and is NP-hard — the canonical arc-routing problem for municipal fleet planning.
Problem context
Traversing every street, at minimum cost
Unlike the classic vehicle-routing problem (customers at nodes), waste collection is arc routing: the service requirements are on edges (streets), not vertices. A truck must traverse each required street segment at least once to collect the refuse along it. The objective minimises total distance / time — which decomposes into service time (traversing a required edge with collection) and deadheading (traversing an edge without collecting, just to reach the next required edge or return to depot).
The unconstrained problem with one truck is the Chinese Postman Problem. Edmonds & Johnson (1973) showed it reduces to finding a minimum-weight perfect matching on the set of odd-degree vertices; both undirected and mixed variants admit polynomial algorithms. Adding capacity and a depot gives the Capacitated Arc Routing Problem (CARP), which Golden & Wong (1981) proved NP-hard. For real-city instances, hybrid heuristics like route-first cluster-second (give one giant tour, then split by capacity) dominate; modern exact methods use branch-and-cut-and-price, e.g. Belenguer & Benavent (2003).
Multi-stakeholder framing
Mathematical formulation
CPP polynomial, CARP NP-hard
| Symbol | Definition | Domain |
|---|---|---|
| G = (V, E) | Street network (edges are street segments) | undirected or mixed |
| ER ⊆ E | Required edges (must be serviced) | |
| ce | Traversal cost (time / distance) of edge e | ℝ⁺ |
| qe | Demand (trash volume) on required edge e | ℝ⁺ |
| K | Number of collection trucks | ℕ⁺ |
| Q | Capacity per truck | ℝ⁺ |
| d | Depot vertex | d ∈ V |
| xe,k | Number of times truck k traverses edge e | ℕ (≥ 0) |
s.t. xe ≥ 1 ∀ e ∈ ER // required edges serviced at least once
even degree at every vertex in the multigraph formed by x // Euler-tour condition
// Polynomial via Edmonds-Johnson 1973: min-weight matching on odd-degree vertices
Capacitated Arc Routing (CARP, Golden-Wong 1981) min Σk Σe ce xe,k // total routing cost
s.t. Σk (xe,k serviced flag) = 1 ∀ e ∈ ER // each required edge serviced by exactly one truck
Σe qe (serviced by k) ≤ Q ∀ k // capacity per truck
tourk starts and ends at depot d // closed tours
tourk connected multigraph over traversed edges
Complexity CPP polynomial (Edmonds-Johnson 1973); CARP NP-hard (Golden-Wong 1981). Modern exact: branch-cut-and-price (Belenguer-Benavent 2003; Martinelli et al. 2013). Heuristics: route-first-cluster-second, path-scanning, merge-based CW-savings.
Interactive solver
Eulerian augmentation + route partitioning on a small street grid
Collection-Route Solver
Solution interpretation
Deadhead ratio, truck load, route equity
Deadheading is the distance travelled without collecting — a pure-waste metric you want to minimise. CPP solutions with many odd-degree vertices or long dead-end streets force more deadheading; you can see this visually when the optimal tour doubles back.
Adding trucks in the CARP variant reduces per-truck distance (good for workers and shift length) but increases total distance (each truck has deadheading to/from depot). The cost-vs-equity tradeoff is visible in the per-truck load metric: CARP solutions can be load-balanced or efficient but not both.
Capacity binding when truck capacity Q is tight, trucks return to depot mid-shift to offload, adding to deadheading. Relaxing Q (bigger trucks) reduces dead distance but has operational limits (truck size, street maneuvering).
Limitations & Critique
Cost-efficient routes aren't the whole story
Coverage-equity disparities
Lower-income neighbourhoods have historically received less frequent collection, later-day pickup, or degraded service quality — documented in multiple US cities. A purely cost-minimising CARP with cheap rural-area collection at the end of the day embeds such disparities if they aren't explicitly constrained against.
Sanitation-worker safety and health
Collection is one of the most dangerous US jobs (per BLS OSHA data): traffic collisions, lifting injuries, and heat-stress. Cost-minimising routes can implicitly extract more work per unit time — a labour-impact dimension that pure CARP ignores.
Recycling and organics are separate problems
Modern waste systems have separate trucks for landfill, recycling, organics, and hazardous waste — each with its own schedule. Joint optimisation is a much larger problem than single-stream CARP, and ignoring the interaction misses where the actual savings are.
Demand is variable and weather-dependent
Seasonal surges (yard waste, holiday volume) and weather events disrupt steady-state routes. Production systems use rolling re-optimisation, not fixed weekly schedules — something the textbook CARP rarely reflects.
Contracts fragment the optimisation
Many cities contract portions of collection to private firms with jurisdictional boundaries. Optimising across the whole city is impossible when different operators own different routes; each contractor optimises independently, losing system-level efficiency.
Emissions are not in the cost function
Diesel-truck emissions contribute disproportionately to urban air quality in low-income neighbourhoods (environmental justice literature). Electrification, route-length minimisation for CO2, and time-of-day constraints to avoid peak ozone require explicit model extensions.
Extensions & variants
Mixed, periodic, electric, dynamic
Mixed-graph CARP
Both directed and undirected edges (one-way streets + two-way). Wøhlk (2008) review.
Periodic CARP
Multi-day / multi-week schedules with per-arc frequency requirements. Mourão & Pinto (2017).
Electric-truck routing
Battery-range constraints plus charging-station siting. Feillet et al. (2014) EV routing family.
Node-routing hybrids
Cluster residential streets into centralised bin locations; converts partly back to VRP. Seoul, Tokyo models.
Smart bins + dynamic routing
IoT-fill-level sensors trigger dynamic re-optimisation; only full bins get visited. Malakahmad et al. (2014).
Location-arc routing
Joint depot-site + arc-routing MILP. Ghiani-Laporte (2000).
Equity-constrained CARP
Explicit load-balance or pickup-time-window equity constraints. Less studied, more applied in municipal RFPs.
Hybrid with disposal-site routing
Multiple landfills / transfer stations with capacity limits; multi-depot / multi-disposal CARP variant.
Key references
Cited above · DOIs where available
Related applications
Routing siblings