Vehicle routing

The problem

A depot has a fleet of identical trucks, each able to carry Q units. A list of customers each need some amount delivered. Every truck leaves the depot, visits some customers, and comes back. Plan the routes so every customer is served exactly once, no truck is overloaded, and the total distance, and with it the fuel bill, is as small as possible. That's the capacitated vehicle routing problem.

Real fleets add more rules. Customers have delivery windows or deadlines, drivers have shift limits, some trucks are refrigerated, some stops are pickups. Parcel carriers, grocery delivery, waste collection, school buses and field technicians all solve versions of it every day. UPS has said its ORION route optimizer saves on the order of a hundred million miles a year. This lab includes capacity, optional deadlines and fuel cost.

Formal model

Number the depot 0 and the customers 1 to n, with demands q_i and distances d_ij. Let x_ij = 1 if some truck drives straight from i to j:

The last family says that a group of customers whose total demand is q(S) must be entered by at least ⌈q(S) ÷ Q⌉ trucks. It also rules out little loops that never touch the depot. There's one such constraint for every subset of customers, exponentially many, so exact solvers add them only when a solution violates one.

Deadlines add arrival times. If a truck goes from i to j, its arrival at j is at least the arrival at i plus the service time plus the driving time, and it must not exceed j's deadline. In this lab, trucks leave at 08:00, drive at 30 km/h and spend 5 minutes at each stop.

Why it's hard

With unlimited capacity and a single truck, the problem is the travelling salesman problem, already NP-hard. Vehicle routing adds a second hard decision on top: which customers share a truck, which is a bin-packing problem. A single truck visiting 20 customers can do so in 20! ÷ 2 ≈ 1.2 × 10¹⁸ different orders, before any choice about splitting customers between trucks.

The best exact methods, branch-cut-and-price, can prove optimal routes for a few hundred customers on good days. Real operations with thousands of stops rely on heuristics, and on how quickly they reach "good enough".

Data structures

• Distance matrix. All algorithms ask "how far from i to j?" constantly. Precomputing an (n + 1) × (n + 1) table makes every question O(1); road networks fill it with shortest-path queries instead of straight lines.
• Savings list. Clarke–Wright computes all n(n − 1) ÷ 2 savings and sorts them, which costs O(n² log n) and dominates its running time. A max-heap works too.
• Route ends. Savings can only join routes at their ends. Storing each route as a deque, or a doubly linked list with head and tail pointers, plus a "which route is this customer on" array makes the check and the merge cheap. It's the same bookkeeping as a union-find with ordered sets.
• Polar angles. Sweep sorts customers by atan2(y − y₀, x − x₀) around the depot, then scans that circular list once.
• Nearest-neighbor queries. For large maps, a k-d tree or a grid of buckets answers "closest unserved customer" without scanning everyone.
• Routes as arrays. 2-opt reverses a slice of the route, so a plain array with in-place reversal is all it needs.

The algorithms

Clarke–Wright savings

Start with the worst sensible plan, one truck per customer, then repeatedly merge two routes. Joining a route ending at i with one starting at j saves the two trips through the depot and adds the link between them: s(i, j) = d_0i + d_0j − d_ij. Work through the pairs from the largest saving down and merge whenever the result is still feasible. Customers far from the depot and close to each other produce the largest savings, so routes grow outward first.

Sweep

Picture a radar beam rotating around the depot. Customers join the current truck in the order the beam reaches them, and when the next one won't fit, the truck is closed and a new one starts. Because each truck gets a wedge of the map, routes rarely cross each other. Inside a wedge, the lab inserts each customer where it adds the least distance.

Nearest neighbor

The most human strategy: from wherever you are, drive to the closest customer you can still serve, and go home when nothing fits. It's fast and reasonable early on, but the last customers of each route are often far-flung leftovers, which shows in long return trips.

2-opt polishing

A route that crosses itself is never optimal: uncrossing two edges always makes it shorter. 2-opt tries every pair of edges (a, b) and (c, d) in a route and replaces them with (a, c) and (b, d) when that's shorter, reversing the stops in between. Repeat until nothing improves. It's the simplest local search for routing and fixes most of what construction heuristics leave behind.

Metaheuristics

Construction heuristics build one plan and stop. Metaheuristics keep searching, trading time for quality. The lab includes two of the classics.

Simulated annealing

Start from any plan, here a quick nearest-neighbor one, and repeatedly try a small random change. The moves span both trucks and stops: relocate a customer to another spot or truck, swap two customers between trucks, 2-opt* (exchange the ends of two routes) and 2-opt (reverse a stretch of one route). A change that breaks capacity or a deadline is thrown away. Shorter plans are always kept; a plan that is Δ km longer is kept with probability e^−Δ/T. The temperature T starts high, so early on the search wanders freely, and cools geometrically until only improvements get through. The name comes from metallurgy: cooling metal slowly lets its atoms settle into a low-energy arrangement.

Genetic algorithm

Instead of one plan, keep a population. Each individual is a single visiting order, a "giant tour" through every customer, with no trucks at all. Christian Prins' split procedure turns an order into the best possible set of routes: it treats every way of cutting the order into consecutive feasible routes as a path in a small graph and finds the shortest one by dynamic programming. Children are made by order crossover (copy a slice from one parent, fill in the rest in the other parent's order) and a little mutation, and fitter parents are chosen more often. The best two plans always survive, so the best distance never gets worse.

Both are seeded, so the same map always plays back identically, which keeps share links reproducible. Neither proves optimality, but on these maps they usually beat every construction heuristic.

Beyond this lab

• Stronger metaheuristics. Tabu search and especially large neighborhood search (destroy part of the solution, rebuild it better) power most commercial routing engines. Hybrid genetic search by Vidal and colleagues, a genetic algorithm with local search on every child, is among the strongest published methods.
• Variants. Time windows (VRPTW), several depots, pickup and delivery, mixed fleets, electric trucks that need charging stops, and dynamic routing, where orders arrive during the day.
• Libraries. Google OR-Tools, VROOM and PyVRP solve real instances with these techniques.

A little history

George Dantzig and John Ramser introduced the problem in 1959 as "The Truck Dispatching Problem": delivering gasoline from a terminal to service stations. Geoff Clarke and John Wright published the savings algorithm in 1964, and it remains a standard baseline. G. A. Croes described the 2-opt move for the travelling salesman problem in 1958, and Billy Gillett and Leland Miller's sweep algorithm appeared in 1974.