Article ID: | iaor20072910 |
Country: | United Kingdom |
Volume: | 58 |
Issue: | 3 |
Start Page Number: | 355 |
End Page Number: | 367 |
Publication Date: | Mar 2007 |
Journal: | Journal of the Operational Research Society |
Authors: | Ioannou G., Tarantilis C.D., Repoussis P.P. |
Keywords: | heuristics, programming: travelling salesman |
In this paper, we consider the open vehicle routing problem with time windows (OVRPTW). The OVRPTW seeks to find a set of non-depot returning vehicle routes, for a fleet of capacitated vehicles, to satisfy customers' requirements, within fixed time intervals that represent the earliest and latest times during the day that customers' service can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns. The model is solved using a greedy look-ahead route construction heuristic algorithm, which utilizes time windows related information via composite customer selection and route-insertion criteria. These criteria exploit the interrelationships between customers, introduced by time windows, that dictate the sequence in which vehicles must visit customers. Computational results on a set of benchmark problems from the literature provide very good results and indicate the applicability of the methodology in real-life routing applications.