A matheuristic for the swap body vehicle routing problem

We consider the swap body vehicle routing problem, an extension of the capacitated vehicle routing problem, in which intermediate locations can be used to change the configuration of a vehicle. Possible actions include a parking operation that decouples the semitrailer as well as a swapping operation that switches the swap body with another one, which was previously parked at an intermediate location. Successful ideas that combine mathematical programming and heuristics have been recently presented for several vehicle routing problems. In this line, the contribution of this paper is the development of a column generation-based approach, in which a variable neighborhood search heuristic populates the route pool. A detailed numerical analysis is carried out for 138 instances with up to 1000 customers and at most 100 intermediate locations. Comparisons with existing metaheuristics show that our solution strategy is suitable for solving this problem. It has obtained 42 new best known solutions with a maximal improvement of 18.54% on published benchmark instances.