Water distribution expansion planning with decomposition

In recent years, the water distribution expansion planning (WDEP) problem has become increasingly complex as the demands on water distribution systems have evolved to meet modern requirements. This paper describes an algorithm that combines the strengths of local search with global search to flexibly handle these difficult problems. The algorithm decomposes a WDEP problem into sub problems using a local search procedure called Large Neighborhood Search (LNS). Each sub problem is solved exhaustively (or partially) using global search techniques such as branchand- bound search. The utility of the approach is demonstrated on the problem described in the Battle of the Water Networks II competition.