An improved simulation-based iterated local search metaheuristic for gravity fed water distribution network design optimization

Abstract

O problema de otimização do projeto de redes de distribuição de água (WDND, do inglês water distribution network design) alimentadas por gravidade consiste em determinar os diâmetros dos tubos de uma rede de água de forma que as restrições hidráulicas sejam satisfeitas e o custo total seja minimizado. Tradicionalmente, essas decisões de design são feitas com base na experiência de especialistas. Quando as redes aumentam de tamanho, no entanto, as regras práticas raramente levam a decisões quase ideais. Nos últimos trinta anos, um grande número de técnicas foram desenvolvidas para resolver o problema de projetar de forma otimizada uma rede de distribuição de água. Este trabalho aborda o problema NP-difícil de otimização do projeto de redes de distribuição de água em um cenário multiperíodo no qual ocorrem padrões de demanda variáveis no tempo. É proposta uma nova metaheurística de busca local iterada (ILS, do inglês iterated local search) baseada em simulação aprimorada que explora ainda mais a estrutura do problema na tentativa de obter soluções de alta qualidade. Mais especificamente, quatro novidades são propostas: (a) uma estratégia de busca local para dimensionar de forma inteligente tubos nos caminhos mais curtos entre os reservatórios e os nós com maiores demandas; (b) uma técnica para acelerar a convergência com base em um esquema de redução agressiva do diâmetro do tubo; (c) um novo mecanismo de perturbação concentrada que permite escapar de soluções ótimas locais muito restritas; e (d) um conjunto de soluções para alcançar um bom compromisso entre intensificação e diversificação. Experimentos computacionais mostram que a abordagem é capaz de melhorar uma metaheurística estado da arte para a maioria dos testes realizados. Além disso, converge muito mais rápido para soluções de baixo custo e demonstra um desempenho mais robusto na medida em que obtém menores desvios das melhores soluções encontradas.

The gravity fed water distribution network design (WDND) optimization problem consists in determining the pipe diameters of a water network such that hydraulic constraints are satisfied and the total cost is minimized. Traditionally, such design decisions are made on the basis of expert experience. When networks increase in size, however, rules of thumb will rarely lead to near optimal decisions. Over the past thirty years, a large number of techniques have been developed to tackle the problem of optimally designing a water distribution network. This work tackles the NP-hard water distribution network design (WDND) optimization problem in a multi-period setting where time varying demand patterns occur. A new enhanced simulation-based iterated local search (ILS) metaheuristic is proposed which further explores the structure of the problem in an attempt to obtain high quality solutions. More specifically, four novelties are proposed: (a) a local search strategy to smartly dimension pipes in the shortest paths between the reservoirs and the nodes with highest demands; (b) a technique to speed up convergence based on an aggressive pipe diameter reduction scheme; (c) a novel concentrated perturbation mechanism to allow escaping from very restrained local optima solutions; and (d) a pool of solutions to achieve a good compromise between intensification and diversification. Computational experiments show that the proposed approach is able to improve over a state-of-the-art metaheuristic for most of the performed tests. Furthermore, it converges much faster to low cost solutions and demonstrates a more robust performance in that it obtains smaller deviations from the best known solutions.