## 6.4.12 Single-Depot VRPWe shall examine next the following version of the vehicle routing
problem. Let there be n demand points in a given area, each demanding a
quantity of weight Q Obviously, the words "supply" and "quantity supplied" can be substituted for "demand" and "quantity demanded," in which case the depot becomes a collection point. Thus, the VRP applies equally well to solid waste collection from a specific set of points and to parcel delivery to a set of points. A notable recent application, for instance, has been in routing of newspaper distribution vehicles delivering editions of a well-known newspaper to newsstands in an urban area [GOLD 77]. We also note that in specific applications of the VRP, either the maximum weight or the maximum route-time constraints may be relaxed. However, both usually play a role. For instance, in the newspaper delivery problem just mentioned, one constraint, in addition to the maximum number of newspapers that a vehicle can carry, was that all deliveries to newsstands must be made within an hour of press time. When neither constraint applies, the VRP reduces to a traveling salesman problem: if the objective is simply to minimize total distance, it is a 1-TSP [from (6.10)]; if the number of vehicles to be used is specified, it is a m-TSP. It can thus be seen that TSP's can be viewed as special cases of VRP's. By inference, VRP's can be expected to be more difficult than TSP's as far as optimum solutions are concerned. Indeed, although several versions of VRP's have been formulated as mathematical programming problems by various investigators, the largest vehicle routing problems of any complexity that have been solved exactly reportedly involved less than 30 delivery points [CHRI 74]. By contrast, the heuristic approaches that we shall describe next can be used even with thousands of delivery points.
If now we use a single vehicle to serve two points, say i and j, on a
single trip, the total distance traveled is reduced by the amount
The quantity s(i, j) is known as the "savings" resulting from combining points i and j into a single tour. The larger s(i, j) is, the more desirable it becomes to combine i and j in a single tour. However, i and j cannot be combined if in doing so the resulting tour violates one or more of the constraints of the VRP. The algorithm can now be described as follows.
As the reader may have already surmised, the Clarke-Wright algorithm can be programmed to run very efficiently and, since it involves very simple manipulations of the data set, it can be used with large problems. Because nodes are added to routes one or two at a time, an additional advantage of the algorithm is that it is possible to check whether each addition would violate any set of constraints, even when that set is quite complicated. For instance, besides the constraints on maximum capacity and maximum distance, other constraints might be included, such as a maximum number of points that any vehicle may visit. On the other hand, there is no guarantee that the solution provided by such a naive algorithm will be anywhere close to the optimum. While experience has shown that the algorithm performs quite well most of the time, it is possible to devise "pathological" cases for which the Clarke-Wright solutions are very poor indeed. However, it is often possible to improve considerably, by inspection, a set of VRP tours produced by the savings algorithm. In fact, a powerful interactive "man-machine" approach has been developed for that purpose [KROL 72. In this approach, a computer "suggests" a solution using the savings algorithm and projects that solution on a television screen. The human operator then attempts to improve on this solution using his/her knowledge of the problem as well as such geometrical properties of good tours as those we have already discussed for the Euclidean TSP (Section 6.4.8). The operator, using a light pen, suggests these improvements to the computer, which, in turn, comes up with a new solution to the VRP; and so on.
Several alternatives to the Clarke-Wright algorithm have been proposed. One that seems to produce good solutions to VRP,s can be summarized as follows [GILL 74b].
Assume that polar coordinates are available for all points to be visited by
the vehicles (the depot, for instance, might be used as the origin in the
coordinate system). The points then can be ordered in terms of increasing angle
by sweeping (clockwise or counterclockwise) a ray initially drawn from the depot
to some arbitrary point--known as the
The major disadvantage of the sweep algorithm is that it does not generate the vehicle tours as it processes the nodes. This is done only after the nodes that constitute each tour have been specified and thus becomes a time-consuming procedure. In addition, whenever there are constraints on the maximum tour lengths as well, some clusters may prove to lead to tours that are unacceptably long. Finally, the algorithm requires Euclidean distances and satisfaction of the triangular inequality throughout. In general, the Clarke-Wright algorithm seems to enjoy an advantage in terms of both efficiency and flexibility over other available VRP algorithms and has been used extensively. The method has been programmed as the VSPX (Vehicle Scheduling Program) package by IBM and is thus available commercially. The algorithm can be rendered even more powerful through a simple modification that forces the algorithm to generate several alternative solutions and through careful organization and storage of the information it utilizes [GOLD 76]. |