Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands

Julien Bramel, Edward G. Coffman, Peter W. Shor and David Simchi-Levi
Additional contact information
Julien Bramel: Columbia University, New York, New York
Edward G. Coffman: AT&T Bell Laboratories, Murray Hill, New Jersey
Peter W. Shor: AT&T Bell Laboratories, Murray Hill, New Jersey
David Simchi-Levi: Columbia University, New York, New York

Operations Research, 1992, vol. 40, issue 6, 1095-1106

Abstract: In the capacitated vehicle routing problem with unsplit demands, the demand of a customer may not be divided over more than one vehicle. The objective is to find tours for the vehicles such that the amount delivered by a vehicle does not exceed its capacity, each customer receives its demand, and the total distance traveled is as small as possible. We find the asymptotic optimal solution value of the capacitated vehicle routing problem with unsplit demands for any distribution of the demands when customers are independently and identically distributed in a given region. We also develop polynomial-time heuristics for the problem and show that, under certain assumptions on the distribution of customer locations and demands, the heuristics produce solutions that are asymptotically optimal. In addition, we give a tight bound on the rate of convergence for the case when customers are uniformly distributed in a rectangular region.

Keywords: programming; integer; heuristic; application: probabilistic analysis of algorithms; transportation; vehicle routing: probabilistic analysis of algorithms (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.6.1095 (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:6:p:1095-1106

Access Statistics for this article

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