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.