An Iterated Local Search Algorithm for Multi-Period Water Distribution Network Design Optimization

Abstract

Water distribution networks consist of different components, such as reservoirs and pipes, and exist to provide users (households, agriculture, industry) with high-quality water at adequate pressure and flow. Water distribution network design optimization aims to find optimal diameters for every pipe, chosen from a limited set of commercially available diameters. This combinatorial optimization problem has received a lot of attention over the past forty years. In this paper, the well-studied single-period problem is extended to a multi-period setting in which time varying demand patterns occur. Moreover, an additional constraint—which sets a maximum water velocity—is imposed. A metaheuristic technique called iterated local search is applied to tackle this challenging optimization problem. A full-factorial experiment is conducted to validate the added value of the algorithm components and to configure optimal parameter settings. The algorithm is tested on a broad range of 150 different (freely available) test networks.

Keywords

• water distribution network design
• iterated local search
• metaheuristic
• mixed-integer non-linear programming
• pipe sizing