A simple filter-and-fan approach to the facility location problem

The design of effective neighborhood search procedures is a primary issue for the performance of local search and advanced metaheuristic algorithms. Several recent studies have focused on the development of variable depth neighborhoods that generate sequences of interrelated elementary moves to create more complex compound moves. These methods are chiefly conceived to produce an adaptive search as the number of elementary moves in a compound move may vary from one iteration to another depending on the state of the search. The objective is to achieve this goal with modest computational effort. Although ejection chain methods are currently the most advanced methods in this domain, they usually require more complex implementations. The filter-and-fan (F&F) method appears as an alternative to ejection chain methods allowing for the creation of compound moves based on an effective tree search design. This paper reports the first implementation of the F&F approach to the uncapacitated facility location problem (UFLP). We examine a simple version of the F&F method in this study, and explore two search strategies under this framework. The results obtained on a set of 105 standard benchmark problems from the literature demonstrate that this simple but well-structured approach is highly effective for providing optimal and near-optimal solutions for the UFLP in a very short computation time, and indeed can be advantageously compared with the most advanced metaheuristic procedures in solving these problems. (c) 2005 Elsevier Ltd. All rights reserved.