Vehicle routing & last mile

A distributor in Pune has 8 vans and 120 kirana stores to deliver to today. Each store orders a different amount, some can only receive goods before 11 am, and each van holds a limited load. Which van visits which stores, in what order?

That is the vehicle routing problem (VRP). Its simplest relative, the travelling salesman problem (TSP), finds the shortest loop through every stop for one vehicle. The VRP adds what real life brings:

• vehicle capacity (weight, volume, crates),
• time windows (deliver between 8 and 11 am),
• driver hours, breaks and shift limits,
• multiple depots, vehicle types and pickup-and-delivery combinations.

The number of possible routes explodes as stops are added, so exact solutions are only practical for small problems. Real systems use heuristics: classic ones like the Clarke-Wright savings algorithm, which starts with one trip per customer and keeps merging the pairs that save the most distance, plus modern search methods that improve routes step by step. They find very good routes in seconds, even if not provably perfect.

The last mile, the final leg to a home or shop, is usually the most expensive part of delivery per unit: many small drops, parking, waiting, and failed deliveries when nobody is home. Companies cut it with route density (more drops per street), delivery time slots, lockers and pickup points, and dark stores close to customers.

The savings idea

Start by serving every customer with its own trip from the depot. Joining customers $i$ and $j$ into one route saves the trip back to the depot and the trip out again:

Sort all pairs by saving, and merge them in that order whenever the merge keeps the route within capacity and joins customers at the ends of their routes.

The method is simple enough to run by hand, which is why it is still taught. Modern routing software starts from solutions like this and improves them with search methods that move and swap stops between routes.

Time windows change everything

If customer B can only receive before 9 am and C only after 2 pm, the B–C route that saved the most may become impossible, or force a long wait. Time windows, driver hours and loading times are added as constraints, and they often matter more to the final plan than distance.

Drops per route drive last-mile cost

A van costing ₹3,000 a day delivers at ₹100 a drop with 30 drops, and ₹50 a drop with 60. Failed deliveries are expensive because they consume a drop slot and come back for another one. Time slots, delivery notifications and pickup points all aim to raise successful drops per route.

A family of problems

Since Dantzig and Ramser framed the “truck dispatching problem” in 1959, the vehicle routing problem has grown many variants:

• Capacitated (CVRP) and with time windows (VRPTW).
• Pickup and delivery, where items are collected and delivered within the same route, as in courier collections.
• Multi-depot and heterogeneous fleet versions.
• Periodic routing, where customers need visits on certain days of the week.
• Dynamic routing, where orders arrive during the day and routes change in real time.

How solvers work

Exact methods, such as branch-and-price, can prove optimality for problems with up to a few hundred customers, given time. Practical systems mostly use metaheuristics (tabu search, adaptive large neighbourhood search, genetic algorithms) that repeatedly destroy and rebuild parts of a solution, reaching near-optimal routes for thousands of stops in minutes. The quality of the input data (road travel times by hour, service times at stops, accurate time windows) usually matters more than the choice of algorithm.

Density beats distance

A classic result in probability (Beardwood, Halton and Hammersley, 1959) says that the shortest tour through $n$ random points in an area $A$ grows in proportion to $\sqrt{nA}$. So the distance per stop shrinks as stops get denser: doubling the number of deliveries in the same area increases total route length by only about 41%. That is the mathematical reason last-mile delivery gets cheaper with density, and why companies fight for more orders per neighbourhood rather than more neighbourhoods.

Dynamic routing for on-demand delivery

Food and quick-commerce deliveries arrive continuously and promise minutes, not days. Dispatch decides, every few seconds, which rider takes which order, whether to batch two orders going the same way, and whether to wait a moment for another order to batch. Waiting improves efficiency but risks the promise, the same consolidation trade-off at a much faster pace.

Plans that drivers follow

Drivers know local realities the model doesn’t: a lane closed for a market, a customer who is only in after lunch, a gate that opens late. Routes that ignore this get overridden. Collecting driver feedback, learning actual service times from tracking data and measuring plan adherence keep plans realistic.