Vehicle Routing with Time Windows: Two Optimization Algorithms

Marshall L. Fisher, Kurt Jörnsten and Oli B. G. Madsen
Additional contact information
Marshall L. Fisher: University of Pennsylvania, Philadelphia, Pennsylvania
Oli B. G. Madsen: The Technical University o f Denmark, Lyngby, Denmark

Operations Research, 1997, vol. 45, issue 3, 488-492

Abstract: We describe two optimization methods for vehicle routing problems with time windows. These are a K-Tree relaxation with time windows added as side constraints and a Lagrangian decomposition in which variable splitting is used to divide the problem into two subproblems—a semi-assignment problem and a series of shortest path problems with time windows and capacity constraints. We present optimal solutions to problems with up to 100 customers.

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

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.3.488 (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:488-492

Access Statistics for this article

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