Probabilistic analysis of the capacitated vehicle routing problem with unsplit demands

Probabilistic analysis of the capacitated vehicle routing problem with unsplit demands

0.00 Avg rating0 Votes
Article ID: iaor19931363
Country: United States
Volume: 40
Issue: 6
Start Page Number: 1095
End Page Number: 1106
Publication Date: Nov 1992
Journal: Operations Research
Authors: , , ,
Keywords: programming: integer
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. The authors 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. They 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, the authors give a tight bound on the rate of convergence for the case when customers are uniformly distributed in a rectangular region.

Reviews

Required fields are marked *. Your email address will not be published.