A progressive filtering heuristic for the location-routing problem and variants

Th?e location–routing problem (LRP) unites two important challenges in the design of distribution systems. On the one hand, the delivery of goods to customers needs to be planned as e?ffectively as possible, and on the other hand, the location of depots from where these deliveries are executed has to be determined carefully. In the last years many heuristic approaches have been proposed that successfully decompose the problem into the routing component and the location decision component. In this paper we demonstrate how an e fficient and eff?ective heuristic can be designed based on an existing heuristic to solve the capacitated vehicle routing problem. We propose to fi?rst reduce the solution space to a manageable size by the estimation of an upper bound for the number of open depots, and then to iteratively apply the routing heuristic on each remaining depot con?guration. A progressive ?filtering design, in which the vehicle routing problem is solved to a larger precision at each iteration, is employed to quickly detect unpromising con?gurations and thereby improve the e ciency of the heuristic. Extensive benchmarking shows that, despite its simple design, the heuristic is competitive with the best results in literature for classical LRPs and a truck and trailer routing variant, and outperforms existing heuristics on the largest LRP benchmark set to date, on very large-scale LRPs, and 2-echelon LRPs.