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. We 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. We show a strong relationship between this class of heuristics and the familiar Next-Fit bin-packing heuristic.