A simple and robust Monte Carlo hybrid local search algorithm for the facility location problem. Issue 5 (4th May 2019)

• Record Type: Journal Article
• Authors: Chalupa, D.; Nielsen, P.
• Is Part Of: Engineering optimization. Volume 51:Issue 5(2019)
• Page Start: 832
• Page End: 845
• Publication Date: 2019-05-04
• Subjects: Facility location problem -- hybrid local search -- Monte Carlo methods -- metaheuristics -- scalable optimization; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2018.1497618
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: 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.