"A Simheuristic Algorithm for the Capacitated Location Routing Problem with Stochastic Demands"
Carlos Quintero-Araujo, Daniel Guimarans and Angel A. Juan
The capacitated location routing problem (CLRP) integrates a facility location problem with a multi-depot vehicle routing problem. In this paper, we consider the CLRP with stochastic demands, whose specificc values are only revealed once a vehicle visits each customer. The main goal is then to minimize the expected total cost, which includes not only the costs of opening facilities, using a fleet of vehicles, and executing a routing plan, but also the cost of applying corrective actions. These actions are required whenever a route failure occurs due to unexpectedly high demands in a route. To solve this stochastic and NP-hard optimization problem, a simheuristic algorithm is proposed. It hybridizes simulation with an iterated local search metaheuristic in order to: (i) propose a safety-stock policy to diminish the risk of suffering route failures; and (ii) estimate both the expected cost as well as the reliability index of each `elite' solution found. The competitiveness of our approach is shown in a series of computational experiments, which make use of classical CLRP benchmarks. These benchmarks are also extended to consider scenarios under uncertainty. Different variability levels for the random demands are analyzed. Moreover, the effect of the safety-stock policy on the solution cost and reliability index is also discussed.