A biased¿randomized metaheuristic for the capacitated location routing problem

Abstract

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) de¿ning routes of vehicles departingfrom and ¿nishing at each facility to serve the associated customers¿ demands. In this paper, a two-phasemetaheuristic procedure is proposed to deal with the capacitated version of the LRP (CLRP). Here, decisionsmust be made taking into account limited capacities of both facilities and vehicles. In the ¿rst phase (selectionof promising solutions), we determine the depots to be opened, perform a fast allocation of customers to opendepots, and generate a complete CLRP solution using a fast routing heuristic. This phase is executed severaltimes in order to keep the most promising solutions. In the second phase (solution re¿nement), for each of theselected solutions we apply a perturbation procedure to the customer allocation followed by a more intensiverouting 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 tothe best-known solutions (BKSs) for all tested sets in short computational times.