The basic, capacity-constrained vehicle routing problem (VRP) is to de
termine a set of capacity-feasible vehicle routes with minimum total t
ravel cost so that all customers are visited by exactly one vehicle. I
n this paper, we introduce a new decomposition strategy for the VRP wh
ich separates the decisions of a dispatcher from those of the individu
al drivers. The dispatcher is responsible for assigning a reward value
to each of the customer cities so that each customer will be visited
by exactly one vehicle. Based on the assigned reward values together w
ith the given travel costs, each vehicle driver is responsible for cho
osing which customers to visit and determining an individual feasible
route. The driver's problem is modeled as a Traveling Salesman Subset-
tour Problem with one additional constraint (TSSP + 1). The TSSP + 1 d
ecomposition is based on a Lagrangian relaxation and is capable of pro
ducing valid lower bounds for the VRP. The best bound attainable is sh
own to be at least as good as the bound obtained by solving the linear
programming relaxation of the classic set partitioning formulation of
the VRP. To test the practical value of the decomposition, we present
a decomposition-based heuristic and examine its performance on a coll
ection of problems from the literature.