A simple and robust Monte Carlo hybrid local search algorithm for the facility location problem

In this article, a new Monte Carlo hybrid local search algorithm (Hyb-LS) is proposed for solving the uncapacitated facility location problem. Hyb-LS is based on repeated sampling using two local search strategies based on best improvement and randomized neighbourhood search. A major advantage of Hyb-LS for its practical use is that the number of restarts is its only parameter to tune. The algorithm is also simple to reimplement, scalable and robust to changes in coefficients within a problem instance. The stopping criterion for local search is learned automatically. Experimental results are presented for four representative and contrasting cost and distance models. The results obtained by Hyb-LS are compared to the optimal or near-optimal solutions found by a mixed integer linear programming (MILP) solver with a generous time limit. For three out of the four models, Hyb-LS obtains better solutions than the upper bound found by the MILP solver for at least one instance.