A GENERALIZED EXCHANGE HEURISTIC FOR THE CAPACITATED VEHICLE-ROUTING PROBLEM

We consider the problem of dispatching the minimum number of vehicles from a central depot to make deliveries to a set of clients with known demands. The objective is to minimize the total distance travelled, s ubject to vehicle capacity requirements. We present a new heuristic al gorithm for solving this problem. The algorithm is based on generalize d edge-exchange search procedures, and relaxation of the capacity requ irements. Computational results, based upon standard test problems wit h up to 249 customers, indicate that our heuristic compares favourably with known heuristics in terms of solution quality.