Article ID: | iaor19972397 |
Country: | United States |
Volume: | 31 |
Issue: | 1 |
Start Page Number: | 49 |
End Page Number: | 59 |
Publication Date: | Feb 1997 |
Journal: | Transportation Science |
Authors: | Rousseau Jean-Marc, Potvin Jean-Yves, Duhamel Christophe |
Keywords: | vehicle routing & scheduling |
This article describes a tabu search heuristic for the vehicle routing problem with backhauls and time windows. In this problem, the set of customers is partitioned into two subsets: linehaul customers where a given quantity of goods is delivered from a central depot, and backhaul customers where a given quantity of goods is collected and transported to the depot. Mixed routes with both linehaul and backhaul customers are constructed. A variant of this problem is examined where linehauls must precede backhauls on each route. Furthermore, the time of beginning of service at each customer location must occur within a particular time interval. Computational results are reported on a standard set of test problems, and comparisons are made with other heuristic approaches and with optimal solutions.