Branch and bound e paralelismo na otimização energética em redes de distribuição de água

Abstract

This work presents an approach for the optimization of water distribution systems (WDS) using the Branch and Bound (B&B) algorithm with depth-first search (DFS) and task-based parallelism. The methodology includes the efficient distribution of tasks among multiple cores, aiming to balance workloads and reduce execution times. The algorithm is applied to three operational scenarios, considering one, two, and three maximum pump activations over 24 hours, while respecting hydraulic constraints and minimizing operational costs. The theoretical search space of the problem is on the order of 4²4 possible solutions, equivalent to approximately 281 trillion combinations. The proposed approach utilizes efficient encoding and pruning strategies, reducing this space to simulations that conclude with just over 500 viable solutions. This efficiency, combined with task-based parallelism, reduces computational time by more than 99% in all analyzed scenarios, making the method practical and applicable to real-world operational contexts. The generated solutions enable significant annual savings, reaching up to R$16,400 in the most intensive scenario.