Vehicle routing with a sparse feasibility graph

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