A TSSP + 1 decomposition strategy for the vehicle routing problem

The basic, capacity-constrained vehicle routing problem (VRP) is to determine a set of capacity-feasible vehicle routes with minimum total travel cost so that all customers are visited by exactly one vehicle. In this paper, we introduce a new decomposition strategy for the VRP which separates the decisions of a dispatcher from those of the individual 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 with the given travel costs, each vehicle driver is responsible for choosing 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 decomposition is based on a Lagrangian relaxation and is capable of producing valid lower bounds for the VRP. The best bound attainable is shown 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 collection of problems from the literature.