PROBABILISTIC ANALYSIS OF A CAPACITATED VEHICLE ROUTING PROBLEM II
成果类型：
Article
署名作者：
Rhee, WanSoo T.
署名单位：
University System of Ohio; Ohio State University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/aoap/1177004969
发表日期：
1994
页码：
741-764
关键词：
摘要：
A fleet of vehicles located at a common depot must serve customers located throughout the plane. Without loss of generality, the depot will be located at the origin. Each vehicle must start at the depot, travel in turn to each customer its serves and go back to the depot. Each vehicle can serve at most k customers. The objective is to minimize the total distance traveled by the fleet. In our model, the customers X1, . . . , X-n are independent and uniformly distributed over the unit disc. If R'(X-1, . . . , X-n) denotes the optimal solution with these customer locations, we show that with overwhelming probability we have vertical bar R'(X-1, . . . , X-n) - 2/k Sigma parallel to X-i parallel to - xi root n vertical bar <= K(n log n)(1/3) where xi and K are constants that depend on k only.