The open vehicle routing problem with time windows

The open vehicle routing problem with time windows

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics, programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.