Crop Transport Routing
CAPACITATED VEHICLE ROUTING
Agriculture · Distribution · Operational Canonical method: CVRPDuring the ten-day corn harvest window on a 1,200 ha Châteauguay-valley grain-oilseed farm, a fleet of grain trucks runs continuously between the combine-filled field edges and the central silo. Each truck has a finite capacity; each field has a known tonnage ready to move. The operational question — which truck visits which fields, in what order — is the Capacitated Vehicle Routing Problem (CVRP), an NP-hard generalization of TSP that admits strong heuristics (Clarke-Wright savings) and exact methods (branch-cut-price) for the scales typical of a single farm.
Why this decision matters
Three verified facts on agricultural transport
Where this decision fits
Agriculture sector decision chain · operational, in-season horizon
Problem & formulation
Classical CVRP with Miller-Tucker-Zemlin subtour elimination
Sets & indices
| Symbol | Meaning | Domain |
|---|---|---|
| \(V = \{0, 1, \ldots, n\}\) | Nodes: 0 = central silo (depot), \(1..n\) = field pickup points | \(|V| = n+1\) |
| \(A = V \times V\) | Directed arcs between every pair of nodes | \(|A| = (n+1)^2\) |
| \(K\) | Homogeneous truck fleet available during the harvest day | finite |
Parameters
| Symbol | Meaning | Unit |
|---|---|---|
| \(d_{ij}\) | Road distance from node \(i\) to node \(j\) | km |
| \(q_i\) | Tonnes ready to collect at field \(i\) (\(q_0 = 0\)) | t |
| \(Q\) | Payload capacity per truck | t |
Decision variables
| Symbol | Meaning | Domain |
|---|---|---|
| \(x_{ij}\) | 1 if some truck traverses arc \((i,j)\), 0 otherwise | \(\{0,1\}\) |
| \(u_i\) | Cumulative load when a truck arrives at node \(i\) (MTZ) | \([q_i, Q]\) |
Objective
Minimize total distance travelled by the fleet:
Constraints
Each field is visited exactly once; the depot is entered and left by each vehicle; capacity is respected; subtours are eliminated:
MTZ combines capacity and subtour elimination in \(\mathcal{O}(n^2)\) constraints. Stronger DFJ cuts or set-partitioning + column generation scale further.
Solution methods at a glance
Up to ~25 fields, MTZ solved by a MIP solver is practical. Beyond that, the Clarke-Wright savings heuristic (1964) is the classical first line: merge routes whenever the savings \(s_{ij} = d_{0i} + d_{0j} - d_{ij}\) of joining them is positive and capacity allows. State-of-the-art metaheuristics (LKH-3, HGS-CVRP) close the gap to optimum to under 1% on benchmark instances.
Real-world → OR mapping
Harvest-day vocabulary translated to the CVRP
| On the farm | In the CVRP model |
|---|---|
| Central silo / grain elevator at the farmyard | Node \(0\) (depot) |
| Each harvestable field waiting for pickup | Node \(i \in V \setminus \{0\}\) |
| Road distance along gravel / country roads | \(d_{ij}\) |
| Tonnes of corn, soy, or wheat ready in the field | \(q_i\) |
| Grain-trailer payload (20–25 t typical) | \(Q\) |
| Available truck-drivers that day | \(|K|\) |
| Does truck \(k\) drive from \(i\) to \(j\)? | \(x_{ij}\) |
| Total km driven by the fleet | Objective |
Interactive solver
Clarke-Wright savings on a representative Québec farm instance
How Clarke-Wright works
Start with a “one field per truck” plan: \(n\) trivial routes \(0 \to i \to 0\). For each pair of fields, compute the savings \(s_{ij} = d_{0i} + d_{0j} - d_{ij}\): distance saved if a truck visited \(i\) and \(j\) in sequence instead of two separate round trips. Sort the savings descending; greedily merge route-endpoints whenever the merged route still fits within capacity. Output routes are typically 5–15% shorter than the baseline and within a few percent of the proven optimum.
Reading the solution
What the route map tells the farm manager
Three patterns to watch for
- Cluster routes vs. radial routes. When field yields are small, Clarke-Wright merges many adjacent fields into long “cluster” routes. When yields approach capacity \(Q\), routes become near-radial (one trip per field).
- Truck count vs. makespan. Total distance is weakly sensitive to an extra truck — the real cost driver is per-km fuel and driver-hour. But more trucks in parallel shorten the harvest-day makespan.
- Close-to-depot fillers. Fields near the silo become opportunistic “short-hop” fillers when a truck has capacity left after longer legs.
Sensitivity questions the solver answers instantly
- Capacity drops (older trucks, wet corn adding weight)? Reduce \(Q\) — watch route count grow.
- Add a far-off rented field? Use a larger seed / re-spatialize to see how the extra 5–10 km reshapes routes.
- One field much bigger than the others? Raise max yield — a dedicated near-full truck is likely.
Model extensions
Natural agricultural generalizations of the base CVRP
Time windows (VRPTW)
If trucks can only arrive during a combine's unload window (say, every 90 minutes), the problem becomes VRPTW. Sharper constraints, tighter solutions, but materially harder to solve.
See the fertilizer-routing VRPTW →Stochastic demand
Actual tonnage depends on local yield variance (wet spots, uneven emergence). Stochastic CVRP with chance-constrained capacity or two-stage recourse prevents routes from running short by one or two tonnes.
See the operational cell →Heterogeneous fleet
Mixing a 22 t tandem with a 15 t single-axle trailer makes vehicle assignment part of the decision. The LP relaxation + branch-and-price approach (SDVRP, VRPHF) is standard.
Related applications →Key references
Cited above · DOIs and permanent URLs