17-01-2013, 03:46 PM
Clarke & Wright's Savings Algorithm
Clarke & Wright's.pdf (Size: 19.54 KB / Downloads: 147)
Introduction.
In 1964 Clarke & Wright published an algorithm for the solution of that kind of vehicle
routing problem, which is often called the classical vehicle routing problem. This
algorithm is based on a so-called savings concept.
This note briefly describes the algorithm and demonstrates its use by an example.
Problem characteristics.
The vehicle routing problem, for which the algorithm has been designed, is characterized
as follows. From a depot goods must be delivered in given quantities to given customers.
For the transportation of the goods a number of vehicles are available, each with a certain
capacity with regard to the quantities. Every vehicle that is applied in the solution must
cover a route, starting and ending at the depot, on which goods are delivered to one or
more customers.
The problem is to determine the allocation of the customers among routes, the sequence in
which the customers shall be visited on a route, and which vehicle that shall cover a route.
The objective is to find a solution which minimizes the total transportation costs.
Furthermore, the solution must satisfy the restrictions that every customer is visited
exactly once, where the demanded quantities are delivered, and the total demand on
every route must be within the vehicle’s capacity.
The transportation costs are specified as the cost of driving from any point to any other
point. The costs are not necessarily identical in the two directions between two given
points.
The savings algorithm.
The savings algorithm is a heuristic algorithm, and therefore it does not provide an
optimal solution to the problem with certainty. The method does, however, often yield a
relatively good solution. That is, a solution which deviates little from the optimal solution.
The basic savings concept expresses the cost savings obtained by joining two routes into
one route as illustrated in figure 1, where point 0 represents the depot.
The parallel savings algorithm
In the parallel version 1 and 5 are also combined first. Since the parallel algorithm may
build more than one route at a time, points 2 and 4 are also combined. Finally, points 3
and 5 are combined. In this way the algorithm constructs the routes 0-1-5-3-0 and 0-2-4-0
with total transportation costs amounting to 171.
It is worth noting that the number of routes may be reduced during the process of the
parallel algorithm. For example, the two routes 0-1-2-0 and 0-3-4-0 will be combined into
one route if the connection from 2 to 3 is established; in that case the resulting route
becomes 0-1-2-3-4-0.