THE MULTISTART DROP-ADD-SWAP HEURISTIC FOR THE UNCAPACITATED FACILITY LOCATION PROBLEM

The uncapacitated facility location problem aims to select a subset of facilities to open, so that the demands of a given set of customers are satisfied at the minimum cost. In this study, we present a novel multistart Drop-Add-Swap heuristic for this problem. The proposed heuristic is multiple applications of the Drop-Add-Swap heuristic with randomly generated initial solutions. And the proposed Drop-Add-Swap heuristic begins its search with an initial solution, then iteratively applies the Drop operation, the Add operation or the Swap operation to the solution to search for a better one. Cost updating rather than recomputing is utilized, so the proposed heuristic is time efficient. With extensive experiments on most benchmarks in the literature, the proposed heuristic has been shown competitive to the state-of-the-art heuristics and metaheuristics.