PROBABILISTIC ANALYSIS OF THE CAPACITATED VEHICLE-ROUTING PROBLEM WITH UNSPLIT DEMANDS
成果类型：
Article
署名作者：
BRAMEL, J; COFFMAN, EG; SHOR, PW; SIMCHILEVI, D
署名单位：
Columbia University; AT&T; Nokia Corporation; Nokia Bell Labs
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.6.1095
发表日期：
1992
页码：
1095-1106
关键词：
摘要：
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.