An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation

Niklas Kohl and Oli B. G. Madsen
Additional contact information
Niklas Kohl: The Technical University of Denmark, Lyngby, Denmark
Oli B. G. Madsen: The Technical University of Denmark, Lyngby, Denmark

Operations Research, 1997, vol. 45, issue 3, 395-406

Abstract: Our paper presents a new optimization method for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a generalization of the Vehicle Routing Problem, where the service of a customer must start within a given time interval—a so-called time window. Our method is based on a Lagrangian relaxation of the constraint set requiring that each customer must be serviced. The master problem consists of finding the optimal Lagrangian multipliers and the subproblem is a Shortest Path Problem with Time Windows and Capacity Constraints. The optimal multipliers are found using a method exploiting the benefits of subgradient methods as well as a bundle method. The method has been implemented and tested on a series of well-known benchmark problems of size up to 100 customers. Our algorithm turns out to be very competitive compared to algorithms considered in the literature, and we have succeeded in solving several previously unsolved problems.

Keywords: programming; relaxation/subgradient; programming; nondifferentiable; transportation; vehicle routing (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (35)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.3.395 (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:45:y:1997:i:3:p:395-406

Access Statistics for this article

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