A conceptually simple algorithm for the capacitated location-routing problem

Location-routing problems (LRPs) jointly optimize the loca-tion of depots and the routing of vehicles. The most studied LRP variant, the capacitated LRP (CLRP), has been ad-dressed by a large number of metaheuristic approaches. These methods often decompose the problem into a location stage to determine a promising depot configuration and a routing stage, in which a vehicle-routing problem is solved to assess the quality of the previously determined depot configuration. Unfortunately, the CLRP literature does not shed much light on the important question which algorithmic features have the biggest influence on the solution quality and runtime of such heuristics. The purpose of this paper is to propose a con-ceptually simple (yet reasonably effective) heuristic for the CLRP and to provide some insights on the design of success-ful metaheuristics for this problem. Our algorithm is a hybrid combining (i) a GRASP phase that uses a variable neighbor-hood descent for local improvement in the location stage, and (ii) a variable neighborhood search in the routing stage. We analyze the impact of the algorithmic components on solution quality and runtime. In addition, we find that the suboptimal routing solutions used to assess the quality of the investigated depot configurations in tendency lead to depot configurations with too many open depots. We propose a depot configuration refinement phase that alleviates this drawback, and we show that this algorithmic component significantly contributes to the solution quality of our method, enabling it to provide rea-sonable results in comparison to the state-of-the-art methods from the literature.& COPY; 2023 The Author(s). Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY-NC-ND license (http:// creativecommons .org /licenses /by -nc -nd /4 .0/).