Probabilistic analysis of a capacitated vehicle routing problem-I

A fleet of vehicles located at a service center must serve the demands of a set of customers. The amount delivered by each vehicle cannot exceed its capacity and a customer’s demand may not be split over more than one vehicle. In the present model, customers locations, as well as their demands are independent identically distributed. Simchi-Levi and Bramel determined the asymptotic value of the optimal solution in this model. The paper proves here a sharp rate of convergence to the asymptotic value.