Large Composite Neighborhoods for the Capacitated Location-Routing Problem

The capacitated LRP (CLRP) jointly takes decisions on the location of capacitated depots and the routing of capacitated vehicles to serve a set of customers with known demands from the opened depots. In city logistics, the CLRP is used for the planning of single-echelon distribution networks. In this application context, large-scale CLRP instances with a high number of potential depot locations (representing concrete candidates for running urban depots) and a high number of customers (as a result of densely populated urban areas) are particularly relevant. We introduce a tree-based search algorithm (TBSA) that explores the space of depot configurations in a tree-like fashion using a customized first improvement strategy. In the routing phase, the multi-depot vehicle-routing problem defined by the depot configuration is solved with a granular tabu search that uses a large composite neighborhood described by 14 operators. In numerical studies, we find that using the large composite neighborhood has a positive impact on the effectivity, efficiency, and robustness of TBSA. We show that the trade-off between run time and solution quality of TBSA can be controlled by the number of total iterations and the strength of the sparsification in the granular search, and we investigate a fast, a basic, and a quality-oriented variant of TBSA. On the commonly used small-to-medium–sized CLRP benchmark sets from the literature, the fast version is able to dominate all previously published heuristic solution methods, that is, it achieves better solution quality within shorter run times. The basic and quality-oriented variants provide outstanding solution quality within reasonable run times; on average, both variants achieve negative gaps to the previous best known solutions. Thus, on the considered benchmark sets, the three variants together form the Pareto frontier of heuristic solution methods for the CLRP. Moreover, TBSA matches or improves the large majority of previous best known solutions in these instances. Finally, TBSA is able to solve newly generated, large-scale instances with up to 600 customers and 30 depots with reasonable run times and convincing scaling behavior and robustness. Additional experiments on open LRP benchmarks confirm the performance of TBSA. Data are available at https://doi.org/10.1287/trsc.2017.0770 .