A TSSP-ROUTING PROBLEM(1 DECOMPOSITION STRATEGY FOR THE VEHICLE)

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.