A biased-randomized metaheuristic for the capacitated location routing problem

The location routing problem (LRP) involves the three key decision levels in supply chain design, that is, strategic, tactical, and operational levels. It deals with the simultaneous decisions of (a) locating facilities (e.g., depots or warehouses), (b) assigning customers to facilities, and (c) defining routes of vehicles departing from and finishing at each facility to serve the associated customers’ demands. In this paper, a two-phase metaheuristic procedure is proposed to deal with the capacitated version of the LRP (CLRP). Here, decisions must be made taking into account limited capacities of both facilities and vehicles. In the first phase (selection of promising solutions), we determine the depots to be opened, perform a fast allocation of customers to open depots, and generate a complete CLRP solution using a fast routing heuristic. This phase is executed several times in order to keep the most promising solutions. In the second phase (solution refinement), for each of the selected solutions we apply a perturbation procedure to the customer allocation followed by a more intensive routing heuristic. Computational experiments are carried out using well-known instances from the literature. Results show that our approach is quite competitive since it offers average gaps below 0.4% with respect to the best-known solutions (BKSs) for all tested sets in short computational times.