Probabilistic analysis of a capactiated vehicle routing problem—I

Abstract

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

Keywords:

• Bin packing
• Probabilistic analysis of algorithm
• Matching

†This research is in part supported by NSF grant CCR-9000611.

†This research is in part supported by NSF grant CCR-9000611.

Notes

†This research is in part supported by NSF grant CCR-9000611.