Using Heuristic Techniques to Account for Engineering Aspects in Modularity-Based Water Distribution Network Partitioning Algorithm

This paper shows how heuristic techniques can be used to account for engineering aspects in the application of a water distribution network (WDN) partitioning algorithm. In fact, being based on graph-theory concepts, most WDN partitioning algorithms fail to consider explicitly such aspects as the number of boundary pipes and the similarity of district metered areas (DMAs) in terms of number of nodes, total demand, and total pipe length, which are often considered by water utility managers to make their decisions. The algorithm considered is the fast-greedy partitioning algorithm (FGPA), based on the original formulation of modularity as an indicator of the strength of WDN partitioning. This algorithm operates by merging the elementary parts of the WDN in sequential steps until the desired number of district metered areas is reached. Two heuristic optimization techniques were combined with FGPA to propose different merging combinations: the former reproduces some specific features of the simulated annealing algorithm while the latter is based on the multiobjective genetic algorithm. Applications were carried out on a real WDN considering the actual system of isolation valves. The partitioning solutions obtained by the traditional FGPA without heuristics and by a literature algorithm based on spectral clustering were taken as benchmark. The results proved that the former heuristic can help in obtaining numerous WDN partitioning solutions with high modularity. The performance of these solutions can be evaluated in terms of practical engineering aspects to help WDN managers make an informed choice about the ultimate solution. If the trade-off between engineering criteria needs to be thoroughly analyzed in the context of WDN partitioning, the latter heuristic, in which FGPA creates DMAs through information encoded in proper weights, can be effectively used. Compared to the benchmark solutions, the FGPA with the latter heuristic can yield solutions with fewer boundary pipes and better demand uniformity over the DMAs.