Garbage Collection Routing
Capacitated Arc Routing Problem (CARP) — NP-Hard
A municipal sanitation department must route garbage trucks through a street network so every required street is serviced at least once. The average city wastes 15–25% of collection distance on deadheading — driving empty between service segments. CARP minimizes this waste.
Where This Decision Fits
Municipal operations chain — the highlighted step is what this page optimizes
The Problem
From street networks to arc routing theory
A municipal depot dispatches garbage trucks across a 5×4 street grid. Some streets (arcs) are required — they have residences or businesses that need collection — while others are optional traversal links. Each required street has a waste demand (tonnes) and each truck has a limited capacity. The objective is to minimize total travel distance including deadhead (empty travel between service segments).
This is the Capacitated Arc Routing Problem (CARP): given a graph G = (V, E) with a subset of required edges ER, each with demand qe, and a fleet of vehicles with capacity Q, find routes starting and ending at the depot that service every required edge at least once while minimizing total traversal cost.
subject to
Σk xijk ≥ 1 ∀ (i,j) ∈ ER // every required edge serviced at least once
Σ(i,j)∈ER qij · yijk ≤ Q ∀ k // truck capacity not exceeded
flow balance at each vertex ∀ v, k // continuity of routes
xijk ∈ {0, 1, 2, ...} // traversal count (may cross arcs multiple times)
Where cij is the traversal cost of edge (i,j), qij is the waste demand on required edge (i,j), Q is truck capacity, and yijk indicates whether truck k services edge (i,j).
CARP is NP-hard — it generalizes the Chinese Postman Problem (all edges required, no capacity) and the Rural Postman Problem (subset of edges, single vehicle). Unlike CVRP which routes to nodes, CARP routes along edges, making it the natural model for street-level services like garbage collection, snow plowing, and street sweeping.
See full CARP theory and all algorithmsTry It Yourself
Route garbage trucks through a street network
Garbage Collection Optimizer
27 Streets · 2 Trucks · 30t CapReady. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Total Dist | Deadhead | DH % | Routes |
|---|---|---|---|---|
| Click Solve & Compare All Algorithms | ||||
The Algorithms
Constructive heuristics for arc routing
Path-Scanning
O(|ER|²)Build routes one at a time. Start at the depot and repeatedly extend the current route by selecting the nearest unserviced required edge whose demand fits within remaining truck capacity. When the truck is full or no reachable required edges remain, return to the depot and start a new route. Ties are broken by preferring the edge furthest from the depot (to push outward early). Simple and effective for dense networks.
Route-First / Split
O(|ER|²)Two-phase approach: first, construct a giant tour that services all required edges as if truck capacity were unlimited (using a nearest-neighbor chain). Then split this tour into feasible sub-routes whenever cumulative demand exceeds capacity, inserting depot returns at split points. This decouples the sequencing and partitioning decisions, often producing well-balanced routes.
Random Assignment
O(|ER|)Randomly shuffle all required edges and assign them to routes sequentially, starting a new route whenever capacity is exceeded. Within each route, edges are visited in their shuffled order using shortest-path connections. This baseline demonstrates how much distance is wasted without intelligent routing — typically 30–50% worse than Path-Scanning.
Real-World Complexity
Why garbage collection goes beyond the basic CARP
Beyond Standard CARP
- One-way streets — Directed arcs require trucks to follow traffic rules, turning the undirected CARP into a mixed or directed variant
- Turn penalties — U-turns and left turns add time and safety risk; real solvers penalize or forbid certain turn sequences
- Time windows — Residential areas may restrict early-morning collection; commercial zones may require off-peak service
- Multiple disposal sites — Trucks may dump at different transfer stations, not just the depot, depending on fill level and proximity
- Heterogeneous fleet — Side-loaders, rear-loaders, and front-loaders serve different bin types; not all trucks can service all streets
- Stochastic demands — Waste volumes vary by day and season; routes must be robust to demand uncertainty
- Multi-compartment collection — Recycling, organics, and landfill waste may require separate compartments or separate passes
Key References
Foundational works in arc routing
- (1981). “Capacitated arc routing problems.” Networks, 11(3), 305–315.
- (1995). “Arc routing problems, Part I: The Chinese Postman Problem.” Operations Research, 43(2), 231–242.
- (2004). “Competitive memetic algorithms for arc routing problems.” Annals of Operations Research, 131, 159–185.
- (2003). “A cutting plane algorithm for the capacitated arc routing problem.” Computers & Operations Research, 30(5), 705–728.
- (2015). “Arc Routing: Problems, Methods, and Applications.” SIAM.
Need to optimize your collection routes?
From garbage collection to snow plowing and street maintenance, arc routing optimization can reduce fleet costs by 15–25%. Let’s discuss how Operations Research can work for your municipality.