Graph Theory Modeling Approach for Optimal Operation of Water Distribution Systems

A graph theory-based algorithm is demonstrated for optimal pump scheduling of two example application water networks. The hydraulic part of the problem is solved using a dedicated and efficient hydraulic solver. The pump scheduling part of the problem is solved using a skeletonized operational graph, representing only the basic logic operational relations existing in the network required for pump selection: the pumping units (with nominal operating costs), water tanks and clustered demand nodes. The hydraulic solver advances one time step at a time. After each time step advance, the nodes of the model are checked to see if satisfy minimum service pressure and minimum water tank level. For nodes not satisfying the service constraints, the Dijkstra’s shortest path algorithm is applied to the skeletonized graph to determine the optimal pumping unit to be activated and then updating the pumps operation pattern in the model. The hydraulic solver is then reinitialized to resolve and recheck the time steps one by one. The algorithm ends when the solver reaches the last time step with all nodes meeting service constraints. The algorithm returns an optimal minimal cost pump-scheduling pattern under greater-than constraints over the examined time period, such as (1) minimal consumer service pressure, and (2) water balance closure at the water tanks. The algorithm returns discrete pump operation scheduling with minimal pump switching and minimal water age in the tanks, demonstrating short solution times (28 s to schedule 11 pumps over a 168-hour period). The algorithm may be applicable for real-time pump scheduling. Future research may include water quality constraints and variable frequency drive pump scheduling. Pump selection is based on the assumption that the optimal pump operation order is not affected by changes in the network’s hydraulic conditions, such as water tank levels and location along the pump efficiency curve (assuming constant efficiency). If hydraulic conditions change the optimal activation order, then the pumps’ working points must by updated after each time step solution, which is not addressed in the current work.