Transport: flows, delivery rounds and the savings algorithm

Transport is often the largest item of logistics costs. Decisions range from the choice of mode (road, rail, sea, air) to planning flows between origins and destinations, down to the daily round of a van delivering to thirty customers. In this lesson we look at the transportation problem as linear programming, the travelling salesman problem and its difficulty, the savings algorithm with the proof of the saving and an example, and full-load economics.

The transportation problem

There are plants with capacities , customers with demands and unit costs for shipping from to . We seek the quantities minimising the total cost:

It is a linear programming problem with a special structure: if capacities and demands are integers, there is always an integer optimal solution, and dedicated algorithms find it very quickly even with thousands of origins and destinations.

The delivery round

A van leaves the depot, visits a set of customers and returns: in what order? This is the travelling salesman problem (TSP). With customers there are possible tours: with 20 customers more than , impossible to enumerate. The problem is NP-hard: no algorithm is known that solves it exactly in polynomial time. So one uses:

• exact algorithms with cutting techniques, which solve instances of thousands of points in acceptable times;
• constructive heuristics (nearest neighbour: always go to the nearest unvisited customer), fast but with tours 20-25 % longer than optimal;
• improvement heuristics (2-opt: remove two crossing edges and reconnect the paths without crossing), which come within a few per cent of the optimum.

The savings algorithm

With several vehicles of limited capacity (the vehicle routing problem, VRP) the classic heuristic is Clarke and Wright’s savings algorithm (1964). One starts by serving each customer with a separate trip, out and back from the depot, and merges the tours in pairs.

Theorem. Merging into a single tour the trips to customers and saves

where are distances and 0 is the depot.

Proof. Separately, the two trips cover . The single tour 0, , , 0 covers . The difference is . By the triangle inequality , so the saving is never negative. ∎

Example. With , , km: separately 44 km, merged 27 km, saving . The algorithm computes the savings of all pairs, sorts them from the largest, and merges the corresponding tours if the two customers are at the ends of different tours and the combined load does not exceed vehicle capacity. Customers far from the depot and close to each other have large savings and end up in the same tour, which is exactly what intuition suggests. The result is usually within 5-10 % of the optimum, and is improved with local heuristics.

Real systems add time windows (the customer receives only from 8 to 12), unloading times, drivers’ working-hour limits, traffic varying through the day; route planning software uses metaheuristics and computes solutions in a few minutes every morning.

Load economics

The cost of a trip depends little on how full the vehicle is: driver, fuel, tolls and depreciation are paid anyway. The cost per unit carried is therefore about , with the fixed cost of the trip, the load and a small variable cost per unit: it decreases with the load. Hence consolidation strategies: grouping small shipments into full loads (consolidation hubs, groupage transport), scheduling deliveries on fixed days per area, avoiding empty return trips by finding backhauls. The same economics apply to emissions (lesson on sustainability).