ClarkeWright

Clarke–Wright, in the context of vehicle routing, refers to the Clarke–Wright savings algorithm, a constructive heuristic introduced by Clarke and Wright in 1964 for solving the vehicle routing problem (VRP). The algorithm is designed to efficiently plan routes for multiple vehicles operating from a central depot to serve a set of customers, aiming to minimize total travel distance or cost.

The method relies on the concept of savings. Let d(i, j) denote the distance between customers i and j, and d(i,0) the distance from the depot to i. The savings of combining two separate routes (depot → i → depot and depot → j → depot) into a single route (depot → i → j → depot) is S_ij = d(i,0) + d(j,0) − d(i,j). The Clarke–Wright procedure computes S_ij for all pairs, sorts these savings in decreasing order, and then iteratively merges routes in that order whenever the merge is feasible, i.e., it does not violate vehicle capacity or other problem constraints and the resulting route remains valid (for example, maintaining the end/start conditions of the respective routes).

The algorithm starts with one route per customer and gradually fuses routes to form longer tours, guided by the largest savings first. It is computationally efficient and widely used to generate good initial feasible solutions, which can then be improved by other optimization techniques. Variants exist to handle additional constraints, such as time windows, multiple depots, or different vehicle capacities. While effective for many VRP instances, Clarke–Wright can be outperformed by more sophisticated methods on complex networks, and its performance depends on problem structure and constraint settings.