A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows

Martin Desrochers, Jacques Desrosiers and Marius Solomon
Additional contact information
Martin Desrochers: GÉRAD and École Polytechnique, Montreal, Canada
Jacques Desrosiers: GÉRAD and École des Hautes Etudes Commerciales, Montreal, Canada
Marius Solomon: Northeastern University, Boston, Massachusetts

Operations Research, 1992, vol. 40, issue 2, 342-354

Abstract: The vehicle routing problem with time windows (VRPTW) is a generalization of the vehicle routing problem where the service of a customer can begin within the time window defined by the earliest and the latest times when the customer will permit the start of service. In this paper, we present the development of a new optimization algorithm for its solution. The LP relaxation of the set partitioning formulation of the VRPTW is solved by column generation. Feasible columns are added as needed by solving a shortest path problem with time windows and capacity constraints using dynamic programming. The LP solution obtained generally provides an excellent lower bound that is used in a branch-and-bound algorithm to solve the integer set partitioning formulation. Our results indicate that this algorithm proved to be successful on a variety of practical sized benchmark VRPTW test problems. The algorithm was capable of optimally solving 100-customer problems. This problem size is six times larger than any reported to date by other published research.

Keywords: dynamic programming/optimal control: subproblem modeling; programming; integer: column generation algorithm; transportation: vehicle routing and scheduling (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (211)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.2.342 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:2:p:342-354

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().