Probabilistic analysis of a capactiated 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 our model, customers locations, as well as their demands are independent identically distributed. Simchi-Levi and Bramel 10] determined the asymptotic value of the optimal solution in this model. We prove here a sharp rate of convergence to the asymptotic value