A probabilistic analysis of tour partitioning heuristics for the Capacitated Vehicle Routing Problem with unsplit demands

In the Capacitated Vehicle Routing Problem with unsplit demands, a customer’s demand may not be divided over more than one vehicle. The authors analyze the asymptotic performance of a class of heuristics called route first-cluster second, and in particular, the empirically well-studied. Sweep algorithm and Optimal partitioning heuristic, for any distribution of the demands and when customers are independent and identically distributed in a given region. They show a strong relationship between this class of heuristics and the familiar Next-Fit bin-packing heuristic.