Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows

Julien Bramel and David Simchi-Levi
Additional contact information
Julien Bramel: Columbia University, New York, New York
David Simchi-Levi: Columbia University, New York, New York and Northwestern University, Evanston, Illinois

Operations Research, 1996, vol. 44, issue 3, 501-509

Abstract: In the Vehicle Routing Problem with Time Windows, a set of customers are served by a fleet of vehicles of limited capacity, initially located at a central depot. Each customer provides a period of time in which they require service, which may consist of repair work or loading/unloading the vehicle. The objective is to find tours for the vehicles, such that each customer is served in its time window, the total load on any vehicle is no more than the vehicle capacity, and the total distance traveled is as small as possible. In this paper, we present a characterization of the asymptotic optimal solution value for general distributions of service times, time windows, customer loads and locations. This characterization leads to the development of a new algorithm based on formulating the problem as a stylized location problem. Computational results show that the algorithm is very effective on a set of standard test problems.

Keywords: transportation; vehicle routing; probability; stochastic models and applications; analysis of algorithms; suboptima algorithms (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.3.501 (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:44:y:1996:i:3:p:501-509

Access Statistics for this article

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