A generalized exchange heuristic for the capacitated vehicle routing problem

Abstract

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, subject to vehicle capacity requirements. We present a new heuristic algorithm for solving this problem. The algorithm is based on generalized edge-exchange search procedures, and relaxation of the capacity requirements. Computational results, based upon standard test problems with up to 249 customers, indicate that our heuristic compares favourably with known heuristics in terms of solution quality.