AbstractHierarchical vehicle routing problems, in which the decision to acquire a number of vehicles has to be based on imperfect (probabilistic) information about the location of future customers, allow a natural formulation as two‐stage stochastic programming problems, where the objective is to minimize the sum of the acquisition cost and the length of the longest route assigned to any vehicle. For several versions of this difficult optimization problem, we show that simple heuristics have strong properties of asymptotically optimal behavior.