##
**Probabilistic analysis of a capacitated vehicle routing problem. II.**
*(English)*
Zbl 0830.90060

Summary: [For part I see the author, Optimization 27, No. 1, 79-87 (1993; Zbl 0820.90038).]

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 it 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 \(X_1,\dots, X_n\) are independent and uniformly distributed over the unit disc. If \(R'(X_1,\dots, X_n)\) denotes the optimal solution with these customer locations, we show that with overwhelming probability we have \[ \Biggl|R'(X_1,\dots, X_n)- {2\over k} \sum_{i\leq n} |X_i|- \xi\sqrt n\Biggr|\leq K(n\log n)^{1/3}, \] where \(\xi\) and \(K\) are constants that depend on \(k\) only.

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 it 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 \(X_1,\dots, X_n\) are independent and uniformly distributed over the unit disc. If \(R'(X_1,\dots, X_n)\) denotes the optimal solution with these customer locations, we show that with overwhelming probability we have \[ \Biggl|R'(X_1,\dots, X_n)- {2\over k} \sum_{i\leq n} |X_i|- \xi\sqrt n\Biggr|\leq K(n\log n)^{1/3}, \] where \(\xi\) and \(K\) are constants that depend on \(k\) only.

### MSC:

90B22 | Queues and service in operations research |

60G17 | Sample path properties |

90B06 | Transportation, logistics and supply chain management |

60D05 | Geometric probability and stochastic geometry |