Multi-agent simulation to support water distribution network partitioning

In managing water supply, engineers often need to divide a water distribution network (WDN) into smaller clusters. Commonly, they work with District Meter Areas (DMA), a discrete part of the system in which the quantities of water entering and leaving the area are metered. The division of a WDN into a collection of DMAs can be considered a graph partitioning problem which is NP-Hard. Additionally, this problem is constrained by the physical nature of the WDN including the geographic location of the elements in the network, the hydraulic features of the network, the topography of the area, the demand patterns of the consumers, and other factors. This research shows how to solve this factoring problem by using a two-step algorithm. It uses a k-means graph clustering algorithm to partition the network geographically into a predefined number of clusters. It then applies a multi-agent system negotiation mechanism to adjust graph nodes on the boundary of all clusters to account for the hydrological constraints. Despite the fact that we do not consider all the necessary hydraulic factors, the application of our method on a case study shows promising results.