Equipment Routing
Capacitated Vehicle Routing · NP-Hard
Heavy equipment transport costs construction firms €800–€2,500 per move, with idle equipment costing €400–€1,200 per day — poor routing decisions waste 15–20% of the annual equipment budget. Every week, a logistics coordinator must route flatbed trucks to deliver excavators, cranes, and compactors across active job sites. This is the Capacitated Vehicle Routing Problem — NP-hard — where vehicle capacity (tonnage) and site delivery windows must be respected.
Where This Decision Fits
Construction operations chain — the highlighted step is what this page optimizes
The Problem
From construction yards to optimization theory
A central equipment yard serves as the depot for a construction fleet. 12 active job sites across the region each need specific heavy equipment deliveries — excavators, cranes, compactors, and pile drivers. The yard dispatches 3 flatbed trucks, each with a 45-tonne capacity. The objective is to minimize total travel distance while ensuring every site receives its equipment and no truck exceeds its weight limit.
This maps directly to the Capacitated Vehicle Routing Problem (CVRP): given n customers with demands, a depot, and a fleet of identical vehicles each with capacity Q, find routes starting and ending at the depot that visit each customer exactly once without exceeding vehicle capacity.
subject to
Σk Σj xijk = 1 // each site visited exactly once
Σj x0jk = Σi xi0k = 1 // each truck starts & ends at depot
Σi qi · Σj xijk ≤ Q // truck capacity not exceeded
xijk ∈ {0, 1} // binary routing variables
Where dij is the distance between locations, qi is the equipment tonnage for site i, Q is the truck capacity, and xijk indicates whether truck k travels from i to j.
The CVRP is NP-hard — it generalizes both the Traveling Salesman Problem (single vehicle, no capacity) and the Bin Packing Problem (assignment only, no routing). With 12 sites and 3 trucks, brute force would evaluate billions of feasible route combinations.
See full CVRP theory and all algorithmsTry It Yourself
Route flatbed trucks across construction job sites
Equipment Routing Optimizer
12 Sites · 3 Trucks · 45t CapReady. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Distance | Routes | Time |
|---|---|---|---|
| Click Solve & Compare All Algorithms | |||
The Algorithms
Constructive heuristics for vehicle routing
Clarke-Wright Savings
O(n² log n)Start with each site on its own route (depot → site → depot). Compute savings for merging every pair of routes: s(i,j) = d(0,i) + d(0,j) − d(i,j). Sort savings in descending order and greedily merge route pairs whenever the combined load does not exceed truck capacity. The algorithm produces high-quality solutions quickly and is the most widely used CVRP heuristic in practice.
Nearest Neighbor
O(n²)Build routes one at a time. Starting from the depot, repeatedly visit the nearest unvisited site whose demand fits within remaining truck capacity. When no more sites can be added, return to the depot and start a new route. Simple and fast, but tends to produce longer routes due to greedy local decisions that ignore the global picture.
Sweep Algorithm
O(n log n)Compute the polar angle of each site relative to the depot. Sort sites by angle and sweep through them, accumulating sites into a route until the truck capacity is reached. Start a new route and continue sweeping. Works particularly well when sites are distributed around the depot, producing non-crossing routes with good geographical clustering.
Real-World Complexity
Why construction routing goes beyond the basic CVRP
Beyond Standard CVRP
- Time windows — Sites have restricted delivery hours due to permits, noise bylaws, or crane availability; late arrivals mean idle crews
- Heterogeneous fleet — Flatbeds, lowboys, and crane trucks differ in capacity, speed, and cost; not all can carry every equipment type
- Pickup and delivery — Equipment must be collected from one site and delivered to another, not just outbound from the yard
- Multi-trip routing — A single truck may return to the depot, reload, and depart again within the same shift
- Oversized load permits — Wide loads require specific highway routes and escort vehicles, adding regulatory constraints
- Setup and teardown time — Loading a 40-tonne excavator takes 45–90 minutes; this service time affects route feasibility
- Weather and traffic — Dynamic travel times due to congestion, road closures, or weather events require re-optimization
Key References
Foundational works in vehicle routing
- (1959). “The truck dispatching problem.” Management Science, 6(1), 80–91.
- (1964). “Scheduling of vehicles from a central depot to a number of delivery points.” Operations Research, 12(4), 568–581.
- (1974). “A heuristic algorithm for the vehicle-dispatch problem.” Operations Research, 22(2), 340–349.
- (2004). “A simple and effective evolutionary algorithm for the vehicle routing problem.” Computers & Operations Research, 31(12), 1985–2002.
- (2014). “Vehicle Routing: Problems, Methods, and Applications.” 2nd ed., SIAM.
Need to optimize your construction logistics?
From equipment routing to project scheduling and resource allocation, mathematical modeling can transform your construction operations. Let’s discuss how Operations Research can work for you.