A greedy look-ahead heuristic for the vehicle routing problem with time windows

In this paper we consider the problem of physically distributing finished g oods from a central facility to geographically dispersed customers, which p ose daily demands for items produced in the facility and act as sales point s for consumers. The management of the facility is responsible for satisfyi ng all demand, and promises deliveries to the customers within fixed time i ntervals that represent the earliest and latest limes during the day that a delivery can take place. We formulate a comprehensive mathematical model t o capture all aspects of the problem, and incorporate in the model all crit ical practical concerns such as vehicle capacity, delivery time intervals a nd all relevant costs. The model, which is a case of the vehicle routing pr oblem with time windows, is solved using a new heuristic technique. Our sol ution method, which is based upon Atkinson's greedy look-ahead heuristic, e nhances traditional vehicle routing approaches, and provides surprisingly g ood performance results with respect to a set of standard test problems fro m the literature. The approach is used to determine the vehicle fleet size and the daily route of each vehicle in an industrial example from the food industry. This actual problem, with approximately two thousand customers, i s presented and solved by our heuristic, using an interface to a Geographic al Information System to determine inter-customer and depot- customer dista nces. The results indicate that the method is well suited for determining t he required number of vehicles and the delivery schedules on a daily basis, in real life applications.