A GRASP for the vehicle routing problem with time windows

This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window constraints. A secondary objective is to minimize the total distance traveled. Each node requires a predetermined amount of service in the form of pickups and deliveries. The fleet is homogeneous and is located at a common depot. Vehicle capacity is finite and split service is not permitted. A greedy randomized adaptive search procedure (GRASP) is used to obtain feasible solutions. Results are reported for standard 100 node data sets as well as for a number of real-world problems with up to 417 customers. The findings indicate that, in general, the proposed procedure outperforms current techniques and requires only a small fraction of the time taken by exact methods. To gauge the quality of the solutions, three different lower bounding heuristics were developed. The first considers the ‘bin packing’ aspect of the problem with regard to vehicle capacity; the second is based on the maximum clique associated with the customers' incompatibility graph; the third independently exploits the time window constraints. Using these heuristics, it is empirically demonstrated that the optimum is found in almost all cases involving balanced service and tight capacity constraints and a significant proportion of the remainder.