Sectorización de redes de abastecimiento de agua potable basada en detección de comunidades en redes sociales y optimización heurística

Abstract

The partition of Water Supply Networks (WSNs) into sectors can be considered as a management strategy that entails its subdivision into homogeneous subgroups. This subdivision aims to enhance the management in each sub-area (sector) carried out by permanently monitoring the inlet flows of each sector

This thesis presents a series of innovative sectorization methodologies where the sectors are previously defined by means of social networks community detection algorithms. In a second step, the arrangement boundary valves/sector entrance is optimized based upon optimization heuristic techniques. Such techniques include the benefits of sectorization in terms of both, leakage reduction, as a result of reducing pressure, and increasing the capacity to detect new leakage events. To tackle the later, the Monte Carlo technique is used to simulate the occurrence of new leakage events.

WSNs subdivision strategies, must take into account their network topology. In networks dependent on a main conduction network, also called trunk network, any sectorization strategy should avoid closure of its pipes in order to preserve the reliability of the system. The herein proposed trunk network identification method, is based on the concept of Shortest Path from the graph theory, in combination with an analysis of the flows (and their directions) circulating through the network in the pick-demand scenario. As a result, the pipes are graded, and the range of pipes belonging to the trunk network can be selected.

Once the trunk network is identified, it is isolated from the distribution network and sectors are defined on the later, based on three social network based community detection algorithms, namely: Hierarchical Clustering, Multilevel Detection Algorithm or Louvaine Method and Random Walk community detection. After defining the area corresponding to each sector, the arrangement entrance / boundary valves must be established. To this end, heuristic-based optimization algorithms (Genetic Algorithms, Particle Swarm Optimization and Agent Swarm Optimization) are implemented.

The first procedure not only takes into account the benefit of sectorization in terms of reduction of flows associated with background leakage as a result of reducing pressure, but also considers other effects of great relevance. This leads to a more realistic cost-benefit analysis than the one that could be carried out if only the reduction of background leakage flows was considered.

In the second method, multilevel optimization is implemented to optimize the arrangement of boundary valves / sector entrance, in the first level, and to determine the set point of pressure reducing valves located at the entrance of each sector, in the second level.

In the third optimization method, only the boundary valves/sector entrance arrangement is optimized based on an economic analysis that does not take into account the effect on the occurrence of new leakages.

For the application of the proposed methodologies, it is mandatory to count on an appropriately calibrated hydraulic model. Thus, a WSN calibration method which considers emitter coefficients at the nodes was developed.

For exemplification purposes, the proposed methodologies are implemented on a section of the WSN of Managua city, capital of Nicaragua. As a result of the implementation, a net profit of 104,764 $ (American dollars)/year is reported.

La sectorización de las Redes de Abastecimiento de Agua Potable (RDAPs) se puede considerar como una estrategia de gestión que implica su subdivisión en subgrupos homogéneos a fin poder gestionar de mejor manera cada sub-área (sector) mediante el monitoreo permanente de los caudales que ingresan a cada sector.

En esta tesis se plantea una serie de metodologías de sectorización innovadoras en que primero se definen los sectores basados en algoritmos de detección de comunidades en grafos de redes sociales. En un segundo paso, se optimiza el conjunto de entradas y válvulas de cierre (CEVC) de cada sector utilizando técnicas heurísticas de optimización. En dicha optimización se incluyen los beneficios de la sectorización en términos de reducción de fugas producto de la reducción de presión y de la capacidad aumentada para detectar nuevos eventos de fugas. Para el abordaje del segundo aspecto se hace uso de la técnica de Monte Carlo para representar eventos de fugas en cada sector basados en una distribución de probabilidades dada.

Las estrategias empleadas para subdividir RDAPs deben tener en cuenta la topología de las mismas. En redes dependientes de una red de conducción principal, cualquier estrategia de sectorización que se plantee deberá evitar cierres en la misma, a fin de preservar la fiabilidad del sistema. Es por esta razón que dentro de las metodologías que se plantean en este trabajo, se lleva a cabo un proceso de identificación y segregación de la red de conducción principal. El método de identificación de la red troncal propuesto en este trabajo se basa en el concepto de Caminos más Cortos, propio de la teoría de grafos, en combinación con un análisis de los caudales (y direcciones de los mismos) que circulan por la red en el escenario de mayor demanda. Como resultado, se obtiene un ranking de tuberías, a partir del cual se puede seleccionar el alcance de la red de conducción principal.

Una vez identificada la red troncal, la misma se aísla de la red distribución y, sobre esta última, se definen los sectores utilizando tres algoritmos de detección de comunidades en redes sociales: Clústering Jerárquico, Algoritmo de Detección Multinivel y Detección de Comunidades a través de Caminos Aleatorios. Tras definir el área que corresponde a cada sector, se debe establecer el conjunto de válvulas cerradas y el punto de abastecimiento del sector. Para tal fin, se implementan procedimientos de optimización basados en los algoritmos de optimización heurística: Algoritmos Genéticos (Genetic Algorithms), Optimización de Enjambres de Partículas (Particle Swarm Optimization) y Optimización de Enjambres de Agentes (Agent Swarm Optimization).

En el primer procedimiento, no sólo se toma en cuenta el beneficio de la sectorización en términos de reducción de caudales asociados a fugas de fondo, como consecuencia de reducir la presión, sino que también se tienen en cuenta otros efectos de gran relevancia. Esto permite que el análisis coste/beneficio de la sectorización sea más realista que el que se podría realizar si sólo se tuviera en cuenta la reducción de caudales de fugas de fondo.

En el segundo método se emplea optimización multinivel para, además de optimizar el conjunto de válvulas cerradas/entrada de sectores, determinar el punto de ajuste de válvulas reductoras de presión en la entrada de los sectores.

En el tercer método de optimización sólo se optimiza el CEVC mediante un análisis económico que no tiene en cuenta el efecto sobre la aparición de nuevas fugas.

Para la aplicación de las metodologías propuestas es importante contar con un modelo hidráulico correctamente calibrado. Para ello, se desarrolló un método de calibración de RDAPs que tiene en cuenta los coeficientes de emisor en los nodos.

Las metodologías propuestas se implementan sobre una sección de la RDAP de la ciudad de Managua, Nicaragua. Como resultado de la impleme

La sectorització de les Xarxes d'Abastament d'Aigua Potable (XAAPs) es pot considerar com una estratègia de gestió que implica la seva subdivisió en subgrups homogenis. Aquesta subdivisió té com a finalitat poder gestionar de millor manera en cada subàrea (sector) aspectes com ara: fuites, reparacions, aspectes de qualitat, entre d'altres, mitjançant el monitoratge permanent dels cabals que ingressen a cada sector.

En aquesta tesi es planteja una sèrie de metodologies de sectorització innovadores en que primer es defineixen els sectors basats en algoritmes de detecció de comunitats en grafs de xarxes socials. En un segon pas, s'optimitza el conjunt d'entrades i vàlvules de tancament (CEVT) de cada sector utilitzant tècniques heurístiques d'optimització. En aquesta optimització s'inclouen els beneficis de la sectorització en termes de reducció de fuites producte de la reducció de pressió i de la capacitat augmentada per detectar nous esdeveniments de fuites. Per l'abordatge del segon aspecte es fa ús de la tècnica de Monte Carlo per representar esdeveniments de fuites en cada sector basats en una distribució de probabilitats donada.

Les estratègies emprades per subdividir XAAPs han de tenir en compte la topologia de les mateixes. En xarxa depenent d'una xarxa de conducció principal o xarxa troncal (d'aquest punt en endavant els termes són intercanviables), qualsevol estratègia de sectorització que es plantegi d'evitar tancaments en la mateixa, a fi de preservar la fiabilitat del sistema. El mètode d'identificació de la xarxa troncal proposat en aquest treball es basa en el concepte de camins més curts, propi de la teoria de grafs, en combinació amb una anàlisi dels cabals (i direccions dels mateixos) que circulen per la xarxa en l'escenari de major demanda. Com a resultat, s'obté un rànquing de canonades, a partir del qual es pot seleccionar l'abast de la xarxa de conducció principal.

Una vegada identificada la xarxa troncal, la mateixa s'aïlla de la xarxa de distribució i, a aquesta última, es defineixen els sectors utilitzant tres algoritmes de detecció de comunitats en xarxes socials: Clustering jeràrquic, Algorisme de Detecció Multinivell o Mètode Louvain i Detecció de Comunitats a través de Camins Aleatoris. Després de definir l'àrea que correspon a cada sector, s'ha d'establir el conjunt de vàlvules tancades i el punt d'abastament del sector. Per a tal fi, s'implementen procediments d'optimització basats en els algoritmes d'optimització heurística: Algorismes Genètics (Genetic Algorithms), Optimització de Eixams de Partícules (Particle Swarm Optimization) i Optimització de Eixams d'Agents (Agent Swarm Optimization).

En el primer procediment, no només es té en compte el benefici de la sectorització en termes de reducció de cabals associats a fuites de fons, com a conseqüència de reduir la pressió, sinó que també es tenen en compte altres efectes de gran rellevància. Això permet que l'anàlisi cost / benefici de la sectorització sigui més realista que el que es podria fer si només es tingués en compte la reducció de cabals de fuites de fons.

En el segon mètode s'empra optimització multinivell per, a més d'optimitzar el conjunt de vàlvules tancades / entrada de sectors, determinar el punt d'ajust de vàlvules reductores de pressió a l'entrada dels sectors.

En el tercer mètode d'optimització només s'optimitza el CEVT mitjançant una anàlisi econòmica que no té en compte l'efecte sobre l'aparició de noves fuites.

Per a l'aplicació de les metodologies proposades és important comptar amb un model hidràulic correctament calibrat. Per a això, es va desenvolupar un mètode de calibratge de XAAPs que té en compte els coeficients d'emissor en els nodes.

Per a fins d'exemplificació, les metodologies proposades s'implementen sobre una secció de la XAAP de la ciutat de Managua, Nicaragua. Com a resultat de la implementació es reporta