Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 202, Issue 3, Pages 756-763Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2009.06.034
Keywords
Vehicle routing; Time windows; Multiple use of vehicles; Elementary shortest paths with resource constraints; Column generation; Branch-and-price
Funding
- Canadian Natural Sciences and Engineering Research Council (NSERC)
Ask authors/readers for more resources
The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows. (C) 2009 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available