Article ID: | iaor2009327 |
Country: | Netherlands |
Volume: | 178 |
Issue: | 3 |
Start Page Number: | 755 |
End Page Number: | 766 |
Publication Date: | May 2007 |
Journal: | European Journal of Operational Research |
Authors: | Potvin Jean-Yves, Gendreau Michel, Azi Nabila |
Keywords: | optimization, networks: path |
This paper describes an exact algorithm for solving a problem where the same vehicle performs several routes to serve a set of customers with time windows. The motivation comes from the home delivery of perishable goods, where vehicle routes are short and must be combined to form a working day. A method based on an elementary shortest path algorithm with resource constraints is proposed to solve this problem. The method is divided into two phases: in the first phase, all non-dominated feasible routes are generated; in the second phase, some routes are selected and sequenced to form the vehicle workday. Computational results are reported on Euclidean problems derived from benchmark instances of the classical vehicle routing problem with time windows.