Expanding Neighborhood Tabu Search for facility location problems in water infrastructure planning

Facility location problems (FLPs) are commonly encountered in water infrastructure planning. They pertain to the optimal siting of facilities, e.g. water and wastewater treatment plants, groundwater pumps, sensors to detect water contamination, chlorine booster stations along water distribution pipes, etc. In this paper, an improved Tabu Search (TS) algorithm, the Expanding Neighborhood Tabu Search (ENTS) is proposed for solving large FLPs. ENTS incorporates elements of Variable Neighborhood Search where the search neighborhood is systematically varied; specifically, the search neighborhood is expanded as the search progresses according to a ranking of the potential locations to site the facilities. Solutions involving just top-ranked locations are searched first, then those involving lower-ranked ones as well, then even lower-ranked ones in addition, and so on, until finally, all locations are included in the search. The ranking of potential locations is carried out using a simple TS but with the stopping criterion set such that it terminates prematurely. Preliminary results comparing ENTS and a simple TS for four cases of the uncapacitated FLP shows ENTS to be the more efficient algorithm for large problems. More research is needed to prove the feasibility of ENTS for solving actual water infrastructure FLPs.