This paper considers a version of the vehicle routing problem in which a non-negative weight is assigned to each city to be visited and where all vehicles are identical and have the same capacity D. The weight assigned to a vehicle on a given route may not exceed this capacity. The problem is formulated as an integer program: integrality is obtained by means of a branch and bound procedure; capacity constraints are first relaxed, and introduced only when they are found to be violated. Three variants of this basic algorithm are examined. Exact solutions are obtained for problems ranging from 15 to 50 cities.