VEHICLE-ROUTING WITH A SPARSE FEASIBILITY GRAPH

In this paper we introduce the concept of a feasibility graph for vehi cle routing problems, a graph where two customers are linked if and on ly if it is possible for them to be successive (adjacent) customers on some feasible vehicle route, We consider the problem of designing veh icle routes when the underlying feasibility graph is sparse, i.e. when any customer has only a few other customers to which they can be adja cent on a vehicle route. This problem arose during a consultancy study that involved the design of fixed vehicle routes delivering to contig uous (adjacent) postal districts. A heuristic algorithm for the proble m is presented and computational results given for a number of test pr oblems involving up to 856 customers. (C) 1997 Elsevier Science B.V.