Acta hydrotechnica 31/54 (2G18), Ljubljana
Open Access Journal
Odprtodostopna revija
ISSN 1581-0267
UDKIUDC: 519.17:628.144
Prejeto/Received: 23.04.2018 Sprej etolAccepted: 17.07.2018
Izvirni znanstveni članek - Original scientific paper
UČINKOVITA PARTICIJA VODOVODNIH OMREŽIJ NA MERILNA OBMOČJA Z UPORABO
TEORIJE GRAFOV
Efficient partitioning of water distribution networks using a graph-
theoretical APPROACH
'Fakulteta za gradbeništvo in geodezijo, Univerza v Ljubljani, Jamova cesta 2, 1000 Ljubljana, Slovenija
V prispevku je predstavljena učinkovita metoda za particijo vodovodnih omrežjih (VO) na merilna območja (MO), ki temelji na teoriji grafov. Algoritem sestoji iz dveh glavnih delov: razbitja VO na MO in njihovega vpetja nazaj v celotno VO. Preizkusili smo ga na primeru realnega VO in med seboj primerjali več različnih utežnih primerov. Učinkovitost predlaganega algoritma za vpetje MO v primerjavi s tradicionalnim kombinatoričnim pristopom smo prikazali za različna števila vzpostavljenih MO. Končno rešitev smo izbrali z uporabo večkriterijskega evalvacijskega modela, ki upošteva hidravlične, stroškovne ter topološke metrike ter izloči subjektivni vpliv na izbiro. Rezultati so pokazali, da je novo predlagana metoda spektralnega razbitja, tj. posplošeni normirani prerez, ustrezna za particijo VO in da lahko z upoštevanjem ustreznih topoloških in cenovnih informacij o VO v fazi razbitja pozitivno vplivamo na dobljeno rešitev.
Ključne besede: vodovodno omrežje, merilna območja, teorija grafov, spektralno razbitje grafov, transportni vodi, večkriterijski evalvacijski model.
We present an efficient graph-theoretical method for partitioning water distribution networks (WDNs) into district metered areas (DMAs). The proposed algorithm consists of two main parts, namely WDN partitioning and DMA connection, and is tested on a real-life WDN, for which different weight cases are compared. The efficiency of the proposed DMA connection algorithm, in regard to the traditional combinatorics approach, is shown for various numbers of established DMAs. The final solution is selected according to the multi-criteria evaluation model, which was developed in order to reduce the subjective influence in the selection process and considers hydraulic, cost, and topological criteria. The results show that the newly proposed spectral partitioning method, namely generalized normalized cut, is appropriate for WDN partitioning and that we can further improve the quality of the obtained solutions by considering appropriate topological and cost-based WDN information in the partitioning process.
* Stik l Correspondence: daniel.kozelj@fgg.uni-lj.si
© Zevnik J. et al.; Vsebina tega članka se sme uporabljati v skladu s pogoji licence Creative Commons Priznanje avtorstva -Nekomercialno - Deljenje pod enakimi pogoji 4.0.
© Zevnik J. et al.; This is an open-access article distributed under the terms of the Creative Commons Attribution - Non Commercial - ShareAlike 4.0 Licence.
https:lldoi.orgl10.15292lacta.hydro.2018.03
Jure Zevnik1, Marjeta Kramar Fijavž1, Daniel Kozelj1'*
Izvleček
Abstract
35
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 35-50, Ljubljana
Keywords: Water Distribution Network, District Metered Areas, Graph Theory, Spectral Graph Partitioning, Water Mains, Multi-Objective Evaluation Model.
1. Uvod
Eden izmed pogostih in učinkovitih ukrepov za identifikacijo vodnih izgub v vodovodnih omrežjih (VO) je vzpostavitev merilnih območij (angl. district metered area, DMA). Merilna območja (MO) so podobmočja VO, katerim simultano merimo vtok in/ali iztok iz območja (Morrison et al., 2007). Njihovo vzpostavitev dosežemo z vgradnjo merilnikov pretoka in zasunov. Poleg meritev hidravličnih parametrov nam vzpostavitev MO omogoči izračun vodne bilance in njenih sestavnih komponent za dano VO (Lambert, 2003).
V dosedanji literaturi na temo zasnove MO lahko zasledimo dva izraza, ki se nanašata na vzpostavitev MO: particija (angl. partitioning) in sektorizacija (angl. sectorization). V primeru particije VO gre za vzpostavitev MO, ki so hidravlično med seboj povezana. Tako lahko govorimo o robnih MO in pretočnih MO, skozi katere voda iz vodnih virov teče proti robnim MO. V primeru sektorizacije VO pa je cilj vzpostaviti med seboj hidravlično neodvisna MO. To dosežemo tako, da vsako MO povežemo na svoj vodni vir ali pa z neposredno priključitvijo MO na transportne vode, ki so izvzeti iz zasnovanih MO (Di Nardo et al., 2013). V tem članku predstavljamo novo metodo za avtomatsko particijo VO, ne da bi pri tem opazno poslabšali hidravlično zmogljivost.
Prvi so problem avtomatske vzpostavitve MO izpostavili Sempewo et al. (2008), ki so iskali ustrezne zasnove MO z večnivojsko rekurzivno bisekcijo in programskim orodjem za razbitje grafov METIS (Karypis in Kumar, 1999). Sledila sta Di Nardo in Di Natale (2010), ki sta poleg razbitja VO obravnavala tudi problem povezave (vpetja) dobljenih merilnih območij nazaj v celoto.
Kasneje je več avtorjev razvilo in predstavilo različne metode za particijo VO. Starejše večinoma vključujejo različne hevristične pristope z upoštevanjem algoritmov iz teorije grafov. Ferrari (2012) je uporabila bisekcijsko metodo Kernighan-Lin in povezanost dobljenih podgrafov preverjala z algoritmom za iskanje v globino. Alvisi in Franchini
(2014) sta predstavila iterativni postopek za določitev nabora možnih rešitev z uporabo algoritma za iskanje v širino in Dijkstrovega algoritma za iskanje najkrajših uteženih poti. Di Nardo et al. (2014) so iskali neodvisne veje v VO z algoritmom za iskanje v globino in nato dobljena območja delili z rekurzivno bisekcijo. Vmesno rešitev so na vsakem koraku optimizirali z uporabo t. i. večagentnega mraveljskega algoritma.
Hajebi et al. (2013) in De Paola et al. (2014) so določili meje MO z uporabo metode fc-sredin (angl. fc-means). Prvi so dobljene rešitve prav tako optimizirali z uporabo večagentnega pristopa, medtem ko so drugi izvedli vpetje s pomočjo iskanja najkrajših uteženih poti med vodnimi viri in MO.
Uporabnost prej omenjenega, prosto dostopnega programskega orodja METIS so potrdili Di Nardo et al. (2013), ki so za vpetje dobljenih grafov predlagali metodo, ki poišče hidravlično ustrezne rešitve z uporabo genetskega algoritma. Ta je bila naknadno dopolnjena z vpeljavo rekurzivnega postopka vpetja (Di Nardo et al., 2016) in z dodatnim upoštevanjem stroškovnih kriterijev (Di Nardo et al., 2017a). Podoben pristop je predstavil Alvisi (2015), ki je v fazo razbitja vključil evolucijski algoritem za izboljšanje dobljenih rešitev.
Učinkovitost algoritmov iz teorije socialnih omrežij za particijo VO so z uporabo hierarhičnega razbitja predstavili Diao et al. (2013), Di Nardo (2015) in Campbell et al. (2016). Slednji so v metodo vključili stroškovne vidike vzpostavitve MO z upoštevanjem negotovosti v procesu iskanja optimalnega vpetja.
Spektralno razbitje grafov so za particijo VO prvi uporabili Kozelj et al. (2017), ki so v procesu razbitja upoštevali kombinirano utež, sestavljeno iz premera cevi in dolvodne hidravlične višine, ter Di Nardo et al. (2017b), ki so med seboj primerjali tri metode spektralnega razbitja grafov in pet utežnih primerov. Rezultati simulacij so pokazali, da v splošnem neuteženi primeri dajejo najustreznejše rešitve. Ta ugotovitev je v navzkrižju z dosedanjimi raziskavami, zato so potrebne dodatne raziskave na
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 36-50, Ljubljana
drugih VO in za več različnih števil vzpostavljenih merilnih območij. Liu in Han (2018) sta predlagala algoritem za spektralno gručenje z združitvijo metode fc-sredin in genetskega algoritma.
Sela Perelman et al. (2015) so v svojem delu primerjali dve hierarhični metodi razbitja grafov in orodje METIS, ki je v splošnem vrnilo najbolj ustrezna razbitja za particijo VO. Primerjavo spektralnega razbitja in programa METIS so izvedli Di Nardo et al. (2018). Ta je pokazala, da METIS rezultira v enakomernejših razbitjih z vidika velikosti ustvarjenih podgrafov, spektralno razbitje pa v rešitvah, ki so primernejše s hidravličnega in ekonomskega vidika.
Pomembnost identifikacije in upoštevanja transportnih vodov pri particiji VO je obravnavalo več avtorjev, ki so predlagali različne metode. Diao et al. (2013) in Ferrari et al. (2014) so uporabili enostaven pristop, v katerem so za transportni vod določili vse cevi s premerom nad 300 mm. Hajebi et al. (2016) so priredili algoritem za iskanje v globino, s katerim so iskali glavne tokovne poti med vodnimi viri in vozlišči. Campbell et al. (2016) so določili pomembnost vsake cevi z izračunom vrednosti akumuliranih najkrajših poti, ki so jih določili z algoritmom za iskanje v širino. Liu in Han (2018) sta glavne tokovne poti upoštevala kot hidravlično utežene najkrajše poti med vodnimi viri in glavnimi vozlišči posameznih MO.
Kakor smo že prej zapisali, v prispevku naslavljamo avtomatsko particijo VO. Uvodu sledi poglavje, ki obsega ozadje iz teorije grafov, na katerem sloni predlagana metoda za avtomatsko zasnovo MO. Ta je skupaj s pripadajočim algoritmom detajlneje predstavljena v tretjem poglavju. Njeno uporabo na primeru realnega VO pa skupaj z rezultati, diskusijo in izbiro končne rešitve vključujemo v četrtem poglavju. Sledi še zaključek, kjer povzemamo opravljeno delo in podajamo končne ugotovitve.
2. Ozadje iz teorije grafov
VO s svojo strukturo ustreza grafu, matematičnemu objektu, ki sestoji iz točk (ali vozlišč) in povezav med njimi. Posledično si lahko pri analizi VO pomagamo s teorijo grafov, pri čemer točkovne elemente, tj. vozlišča, vodne vire in vodohrane,
nadomestimo s točkami grafa, ter linijske elemente, tj. cevi, črpalke, ventile in zasune, s povezavami med danimi točkami. Pri reševanju praktičnih problemov namesto izraza graf pogosto zasledimo izraz omrežje.
Pri opisu teoretičnega dela uporabljamo standardno matematično izrazoslovje. Osnovne pojme na kratko razložimo, za obsežnejšo razlago pa priporočamo učbenik (Wilson in Watkins, 1997).
2.1 Osnove
Obravnavamo povezan graf G = (V,E), kjer V predstavlja množico n vozlišč in E množico neusmerjenih povezav med temi n vozlišči. Graf G je utežen: wvvi > 0 predstavlja utež na povezavi vv' E E med vozliščema v in v'. Utež na vozlišču v E V označimo z wv > 0. Uteženo matriko sosednosti A = (Aij) grafa G definiramo kot:
A
w„
0,
ViV: E E,
sicer,
(1)
za i, j = 1, ...,n. Za neusmeijene grafe velja wvv< = wviv, zato je njihova matrika sosednosti simetrična. Laplaceovo matriko L = (Lc.) grafa G definiramo
IJ
kot L = De — A, kjer je DE = (DE..) diagonalna
IJ
matrika z elementi

.l^ifc, i=j,
I k=1
(2)
0,
sicer,
za i, j = 1, ...,n.
Za neutežene grafe i-ti diagonalni element matrike De predstavlja stopnjo vozlišča Vi, v primeru uteženih grafov pa lahko govorimo o uteženi stopnji vozlišča V(. Laplaceova matrika neusmeijenega grafa ima naslednje lastnosti (Mohar et al., 1991):
•	L je simetrična,
•	L je singularna in pozitivno semidefinitna z lastnimi vrednostmi Ai > 0 za vse i,
•	vsota vsake vrstice in vsakega stolpca matrike L je enaka nič,
36
i-i
n
ij
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 37-50, Ljubljana
•	naj manj ša lastna vrednost A1 matrike L je enaka nič,
•	število povezanih komponent v grafu je enako algebraični večkratnosti A1 = 0.
Definirajmo še diagonalno matriko vozliščnih uteži Dv = (Dv. ) z elementi
Dv
' l 0, sicer,
(3)
za i,j = 1, ...,n. Povezavo vv' v grafu imenujemo most, če njena odstranitev povzroči razpad grafa na dva med seboj nepovezana dela.
2.2 Spektralno razbitje grafov
Naš cilj je razbiti graf G z n vozlišči na p < n podgrafov G1,.,Gp. Naj bo Vk množica vozlišč, vsebovanih v podgrafu Gk. Potem velja
V = V1U ... U Vp, kjer je V^nVj = 0,i ± j.
(4)
Vsak dobljeni podgraf Gk = (Vk,Ek), k = 1, ...,p, je induciran podgraf grafa G, kar pomeni, da so vse originalne povezave iz E med poljubnim parom vozlišč v Vk vsebovane tudi v Ek. Povezava, katere robni vozlišči sta v različnih podmnožicah iz enačbe (4), ni vsebovana v nobenem izmed podgrafov Gk in je imenovana mejna povezava. Množico mejnih povezav definiramo kot
Razbitje P uravnotežimo s pomočjo ciljne funkcije, ki jo imenujemo posplošeni normirani prerez (kasneje GNC, angl. generalized normalized cut):
f
r k=1
voijmj) vol(Vfc) ,
(7)
kjer vol(3(Vfc)) predstavlja vsoto uteži na mejnih povezavah v d(Vk), IVkl število vozlišč znotraj Vk in vol(Vk) vsoto uteži na vozliščih iz množice Vk,
vol(a(Vfc)} = ^
w
vv
w'ed(vk)
(8)
vol(Vfc) = ^
w„
vevk
Ko vozliščne uteži definiramo kot utežene vozliščne stopnje wv. = Dv.., posplošeni normirani prerez postane kar normirani prerez (kasneje NC, angl. normalized cut), kot sta ga definirala Shi in Malik (2000), saj v tem primeru velja
vol(Vfc) =
Z
w
vevk,v'ev,w'eE
(9)
Določitev posplošenega normiranega prereza je NP-poln problem (angl. NP-complete problem) (Shi in Malik, 2000), vendar ga lahko sprostimo in poiščemo zadovoljivo natančne približke. Von Luxburg (2007) je pokazala, da lahko normirani prerez matrično zapišemo kot
d(Vk) ■■= {vv': v EVk in v' g. Vk}.
(5)
LU = DeUA,
(10)
Ločimo torej med dvema vrstama povezav, te so
•	notranje povezave: Et U ...U Ep in
•	mejne povezave: B = d(V1) U ... U d(Vp).
Prve so vsebovane v ustvarjenih podgrafih, medtem ko druge predstavljajo povezave med njimi. Opisano razbitje označimo s P:
P--=[Gi.....Gp}.
(6)
kjer sta matriki U in A podani v enačbi (12). Podobno lahko postopamo v primeru novo vpeljane funkcije posplošenega normiranega prereza, kjer dobimo matrično enačbo
LU = DVUA.
(11)
Enačbi (10) in (11) predstavljata dva različna posplošena problema najmanjših p lastnih vrednosti A1 = 0 < ■■■ < Ap Laplaceove matrike L in njihovih pripadajočih lastnih vektorjev u1,.,up. Lastne
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 38-50, Ljubljana
vrednosti in lastne vektorje zapišemo v matrični obliki kot
A-.= diag{Xi,^,Xv) £ Wxp i
in
(12)
U ■ = [u1,.,up] E RnxP.
Za oba omenj ena prereza lahko enačbi v (10) in (11) zapišemo enotno kot
LU = WU A.
(13)
Tu velja W = DE za normirani prerez in W = Dv za posplošeni normirani prerez.
Vsaka vrstica matrike lastnih vektorjev U predstavlja vozlišče v originalnem grafu G in jo lahko predstavimo s točko v p-razsežnem evklidskem prostoru Rp, ki ga imenujemo spektralni prostor. Naš cilj je razvrstiti vsako izmed danih točk v eno izmed p skupin. Dano razvrstitev lahko opišemo z vektorjem razbitja z n komponentami, ki zavzemajo vrednosti celih števil med 1 in p ter določajo pripadnosti točk posameznim podgrafom. Ker vsaka točka predstavlja vozlišče grafa G, dobljeni vektor razbitja določa tudi pripadnost vozlišč posameznim podgrafom Gi,.,Gp. Točke lahko razvrščamo v skupine na podlagi njihovih medsebojnih razdalj. Vektor razbitja tako lahko dobimo z uporabo metod gručenja, npr. z metodo fc-sredin (angl. fc-means) (Lloyd, 1982), ki spada med tehnike nenadzorovanega strojnega učenj a.
2.3 Vpetje podgrafov
Podgrafe Gx, ...,Gp, ki smo jih dobili po postopku spektralnega razbitja grafa, želimo med seboj povezati oz. vpeti v končni povezani graf. To je možno s katerokoli kombinacijo mejnih povezav iz množice B. Če želimo izpolniti pogoj povezanosti končnega grafa, moramo pri tem uporabiti vsaj p — 1 izmed Nmp = |ß| možnih mejnih povezav. Temu sledi, da je možno število vseh kombinacij vpetja enako T!i=p-i(Nr^p>). Če se osredotočimo na minimalno možno vpetje, ki še zagotavlja končno povezanost, je število kombinacij enako
Velja omeniti, da dobljene kombinacije ne predstavljajo samo topološko sprejemljivih načinov vpetja, ampak vse možne kombinacije. Omenjena metoda je zaradi tega zelo neučinkovita, še posebej pri večjih vrednostih p, ko število kombinacij zelo hitro naraste.
Ker nas pri vpetju podgrafov zanimajo samo topološko sprejemljive rešitve, uporabimo drug, učinkovitejši, pristop, ki tudi temelji na teoriji grafov. Naj bo H = (VH,EH) neutežen graf, kjer je VH = [1,...,p} množica vozlišč, ki predstavljajo p podgrafov, dobljenih iz razbitja P, in EH množica neusmerjenih povezav, ki predstavljajo mejne povezave iz množice B. Topologija grafa H je tako pogojena s spektralnim razbijem grafa G. Temu sledi, da je graf H povezan multigraf, saj lahko dve vozlišči (dva podgrafa) povezuje več povezav (mejnih cevi). Vpeta drevesa grafa H predstavljajo vse topološko sprejemljive načine vpetja podgrafov iz razbitja P z najmanjšim možnim številom povezav. Število vseh vpetih dreves grafa H lahko določimo z Kirchhoffovim izrekom (Mohar et al., 1991) iz enačbe (14). Za dani primer se ta glasi
t(H) 2
(14)
kjer so	neničelne lastne vrednosti
Laplaceove matrike grafa H. Za določitev vseh t(H) vpetih dreves grafa H najprej sestavimo pomožni neusmerjeni enostavni graf H', tako da zamenjamo vse večkratne povezave v H z eno samo. Dobljeni graf H' je tako minor grafa H. Nato z izbranim algoritmom določimo vsa vpeta drevesa v H'. Iz dobljenih vpetih dreves v H' dobimo vsa vpeta drevesa v H, tako da upoštevamo vse možne kombinacije izbire med vzporednimi povezavami v grafu H.
3. Nova metoda za avtomatsko zasnovo merilnih območij
V tem poglavju je predstavljena metoda za avtomatsko particijo VO, ki je sestavljena iz šestih delov: (1) določitve zagonskih vrednosti algoritma, (2) identifikacije transportnih vodov in mostov v VO, (3) zasnove merilnih območij, (4) vpetja
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 39-50, Ljubljana
merilnih območij, (5) evalvacije možnih kombinacij vpetja in (6) izbire najboljše ter izbire končne rešitve. Podrobnejši potek algoritma je prikazan na sliki 1. Pri zasnovi predstavljene metode smo upoštevali naslednje cilje:
•	Dobiti hidravlično ustrezno rešitev, ki je primerljiva s prvotnim VO.
•	Vzpostaviti MO ustreznih velikosti in v skladu z obstoječimi smernicami.
•	Zasnovati primerljiva MO, s podobnimi vrednostmi skupne porabe in dolžine omrežja.
•	Izbrati stroškovno ugodno rešitev.
•	Dobiti rešitev, ki je primerna za neposredno uporabo na VO v realnemu okolju.
Predstavljena metoda je izvedena v okolju MATLAB 2015a (MATLAB, 2015) z uporabo programskega paketa EPANET-MATLAB (Eliades et al., 2016). Programski orodji EPANET 2 (Rossman, 2000) in QGIS 2.18.14 (QGIS, 2018) sta bili uporabljeni za pregled in prikaz rezultatov.
3.1 Določitev zagonskih vrednosti
V okviru zagona algoritma se prebere vhodna datoteka hidravličnega modela obravnavanega VO, ki je zapisana v besedilnem formatu *.inp in je ustvarjena v programskem orodju za hidravlično analizo VO EPANET 2. Uporaba hidravličnega modela je potrebna, ker želimo kasneje dobljene rešitve tudi hidravlično preveriti in ovrednotiti. Podatki iz vhodne datoteke se shranijo v objektni strukturi, katero lahko spreminjamo in kasneje izvozimo nazaj v obliki *.inp. Sledi hidravlična simulacija osnovne topologije, ki lahko predstavlja trenutno ali načrtovano stanje VO. Rezultati simulacije, npr. vozliščni tlaki in pretoki v ceveh, se shranijo kot zagonske vrednosti za uporabo v prihodnjih korakih.
Najprej izračunamo izhodiščni indeks odpornosti Ir1 (Creaco et al., 2016), ki nam bo kasneje služil kot eno izmed meril za hidravlično evalvacijo primerov. Indeks odpornosti Ir je sistemska metrika, ki kaže nivo varnosti pri zagotavljanju standardov oskrbe s pitno vodo v VO v primeru
izrednih dogodkov (npr. pojav požarnega pretoka, loma cevi, zapiranje cevi). V primeru povečanja porabe vode ali loma cevi se povečajo pretoki v omrežju, kar privede do večjih energijskih izgub in posledično nižjih tlakov. Vrednost indeksa Ir se giblje med 0 in 1 ter določa presežek moči v VO oz. pokaže, ali so vozliščni tlaki v omrežju še zadovoljivi za vodooskrbo. Izračunamo ga z enačbo (15), ki je podana v vektorski obliki,
= max[dT(H - Hdes),0] 'r Q0Ho + QpHp - dTHdes
h =
(15)
Tu d predstavlja vektor vozliščnih porab, H in Hdes obstoječe in željene vozliščne hidravlične višine, H0 in Hp hidravlične višine na rezervoarjih (vodni viri in vodohrani) ter na črpalkah, Q0 in Qp pa pretoke na rezervoarjih in črpalkah. Te spremenljivke pridobimo s hidravlično analizo po pristopu s kriterijem porabe (angl. demand driven approach).
3.2 Identifikacija transportnih vodov in mostov
Za identifikacijo transportnih vodov predlagamo pristop, ki prav tako temelji na teoriji grafov. Osnovna ideja je določiti glavna vozlišča v VO, npr. vodne vire, vodohrane, velike porabnike, in nato poiskati glavne tokovne poti med njimi. Iz Darcy-Weisbachove enačbe vemo, da so hidravlične izgube v cevi odvisne tudi od njene dolžine l in premera D. Za dano cev lahko tako definiramo
D5
njeno hidravlično prevodnost — oziroma upornost
D5.
Pričakovati smemo, da bodo imele glavne tokovne poti v VO najvišje vrednosti skupne hidravlične prevodnosti in posledično najnižje vrednosti skupne hidravlične upornosti. Prepoznamo jih lahko z enim izmed ustreznih algoritmov za iskanje najkrajše utežene poti (hidravlična upornost) med dvema vozliščema v grafu. Ker lahko med dvema glavnima vozliščema v VO obstaja tudi več kot en transportni vod, smo v metodo vgradili Yenov algoritem za iskanje k najkrajših poti med dvema vozliščema
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 40-50, Ljubljana
Izračun izhodiščnega indeksa odpornosti !r1
T
Identi fikacija transportnih vodov in mostov
Izračunaj pmax najmanjših lastnih vrednosti in lastnih vektorjev matrike L
Gručenje p najmanjših lastnih vektorjev
Slika 1: Shema predstavljenega algoritma. Figure 1: Scheme of the proposed algorithm.
NE
v grafu (Yen, 1971). Ta nam omogoča, da lahko najdemo vse glavne tokovne poti s podobnimi vrednostmi hidravlične upornosti. Obravnavano VO predstavimo z neusmerjenim uteženim grafom, kjer uteži na povezavah predstavljajo hidravlične upornosti posameznih cevi. Nato določimo glavna vozlišča v VO in poiščemo vse najbolj pretočne poti med vsemi pari prepoznanih točk. Dolžina poti med
dvema vozliščema je dobljena kot vsota hidravličnih upornosti vseh povezav na tej poti. Manjše vsote tako pomenijo krajše razdalje z vidika hidravlične upornosti in tako manjši skupni upor toku.
Poleg transportnih vodov v nadaljnjem postopku upoštevamo tudi mostove v VO. Most je povezava v grafu, katere odstranitev povzroči razpad grafa na
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 41-50, Ljubljana
dva dela in je tako ključnega pomena za njegovo povezanost. Te lahko poiščemo z enim izmed ustreznih algoritmov za iskanje mostov v grafih (Tarjan, 1974).
3.3 Zasnova merilnih območij
Naslednji korak je uporaba algoritma za spektralno razbitje grafa, ki razdeli VO v MO. V razdelku 2 je podrobneje opisana novo predstavljena metoda spektralnega razbitja grafa - posplošeni normirani prerez (GNC). Zasnovana je tako, da poišče uravnotežena razbitja z najmanjšimi prereznimi vrednostmi, tj. vsotami uteži na mejnih povezavah. V primerjavi z ostalimi ciljnimi funkcijami se razlikuje v načinu definicije enakomerne particije. Podobno kot NC tudi GNC vrne razbitja z enakomernimi vsotami vozliščnih uteži v posameznih podgrafih. Prednost predstavljene metode GNC v primerjavi z NC je v tem, da so lahko vozliščne uteži poljubne in niso neposredno vezane na izbiro uteži na povezavah. V primeru uporabe ciljne funkcije NC moramo tako določiti le en niz uteži na povezavah za konstrukcijo utežene Laplaceove matrike L in matrike W, medtem ko moramo v primeru izbire metode GNC določiti še dodaten niz vozliščnih uteži za določitev diagonalne matrike Dv, saj velja W = Dv.
Sledi izbira uteži grafa oz. utežnega primera, ki ga želimo v tej fazi upoštevati. Dva utežna primera, U in D, smo izbrali glede na predhodne raziskave (Di Nardo et al., 2017b). Prav tako smo preizkusili štiri nove uteži, ki jih v dosedanji literaturi še nismo zasledili in vključujejo dodatne informacije o obstoječem VO (obstoječi zasuni, transportni vodi, mostovi, stroški izvedbe). Izbrani utežni primeri potrebujejo še nekaj podatkov za konstrukcijo:
•	Laplaceove matrike LG: neutežen (U), premer cevi (D), minimalni pričakovani strošek ukrepa na cevi (Cmin), trije topološki primeri (wx, w2 in w3),
•	matrike Dv: vozliščna poraba (d).
Podatki o cenah zasunov in merilnikov pretoka so bili za različne premere cevi prevzeti iz Di Nardo et al. (2016). Minimalna pričakovana cena ukrepa na cevi (Cmin) se določi kot nižja izmed cene merilnika pretoka in zasuna, ki ustrezata premeru dane cevi.
Topološke utežne primere w1, w2 in w3 smo preizkusili, da bi ugotovili, če lahko v fazi zasnove merilnih območij z upoštevanjem nekaterih vnaprej znanih lastnosti VO dosežemo boljše končne rezultate. Osnova za vse tri je utežni primer D, vendar je nato glede na lastnost posamezne cevi vrednost uteži wvv< še dodatno pomnožena s koeficientom a iz preglednice 1. Z upoštevanjem koeficienta a tako določenim povezavam vnaprej definiramo večjo težo in tako vplivamo na samo razbitje glede na željeni rezultat.
Preglednica 1: Vrednosti koeficienta a.
Table 1: Values of coefficient a.
Utežni primer	a = 1	a = 5
w1	Zasuni, mostovi, transportni vodi	Ostale cevi
W2	Zasuni, mostovi	Ostale cevi
w3	Zasuni	Ostale cevi
Po izbiri utežnega primera moramo določiti željeni obseg števila ustvarjenih merilnih območij, tako da določimo njegovo minimalno in maksimalno vrednost - pmin in pmax. To lahko določimo vnaprej, glede na velikost in kompleksnost obravnavanega VO ter z ozirom na priporočila za zasnovo MO (Morrison et al. 2007). Zgornjo mejo bi lahko določili tudi dinamično. To bi dosegli z vpeljavo pravil in omejitev, ki določajo še sprejemljive karakteristike ustvarjenih merilnih območij, kot so na primer njihova skupna poraba, število priključkov, skupna dolžina cevi itd. Tako bi se metoda izvedla za vsako vrednost p > pmtn, vse dokler bi razbitje grafa še vrnilo rešitev v skladu z vnaprej določenimi kriteriji.
Za podano vrednost pmax, izbrani utežni primer in metodo razbitja rešimo enačbo (13), da dobimo Pmax najmanjših lastnih vrednosti in njihovih pripadajočih lastnih vektorjev. Nato za vsak p znotraj prej določenega intervala izberemo p najmanjših lastnih vrednosti in pripadajoče lastne vektorje. Te z gručenjem po vrsticah razvrstimo v p skupin z uporabo algoritma fc-sredin++ (Arthur in Vassilvitskii, 2007). Za določitev centroidnih točk
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 42-50, Ljubljana
(voditeljev) uporabimo kosinusno razdaljo, ki je definirana kot (1 — cos0), kjer 0 predstavlja kot med krajevnima vektorjema dane dvojice točk.
Ko je gručenje zaključeno, lahko vsako vozlišče v VO pripišemo enemu izmed p merilnih območij glede na skupinsko pripadnost njihovih predstavljajočih točk v spektralnem prostoru. Nato preverimo notranjo povezanost vsakega MO, da lahko izločimo morebitne topološko neustrezne rešitve. To storimo tako, da sestavimo Laplaceovo matriko za vse ustvarjene podgrafe, ki predstavljajo posamezna MO. Ker je algebraična večkratnost lastne vrednosti A1 = 0 enaka številu povezanih komponent danega podgrafa, je ta torej povezan, če je algebraična večkratnost lastne vrednosti A1 = 0 enaka ena. Po zaključku algoritma spektralnega razbitja lahko izluščimo karakteristike ustvarjenih MO, kot so na primer število vozlišč in priključkov, skupna dolžina cevi in skupna vozliščna poraba.
3.4 Učinkovito vpetje merilnih območij
Po določitvi MO moramo te vpeti nazaj v enotno VO. To dosežemo z vgradnjo merilnikov pretoka ali zasunov na mestu mejnih cevi, tj. na ceveh, ki imajo končni vozlišči v različnih merilnih območjih. Ustrezno vpetje MO je ključnega pomena za hidravlično ustreznost končne rešitve. Ker pri kombinatoričnem pristopu določitve kombinacij vpetja njihovo število zelo hitro naraste, smo razvili metodo, ki temelji na teoriji grafov in je predstavljena v razdelku 2.3. Da bi pridobili rešitve, ki so primerne za neposredno uporabo v realnem okolju, smo to kasneje še dodatno priredili, tako da smo upoštevali dodatne informacije o VO.
Naš cilj je vpeti MO na ekonomičen in hidravlično sprejemljiv način tako, da je novo sestavljeno VO primerljivo s prvotnim nerazdeljenim VO. Pri tem dajemo prednost rešitvam z manjšimi števili odprtih mejnih cevi, saj s tem dosežemo manjše stroške izvedbe, zmanjšamo merilne napake in izboljšamo natančnost izračuna vodne bilance (Morrison et al., 2007). Zaradi omenjenih razlogov iščemo vpetja z najmanjšim možnim številom odprtih mejnih cevi, hkrati pa upoštevamo še transportne vode. Ti namreč predstavljajo glavne tokovne poti v VO, zato morajo ostati odprti, če želimo dobiti
hidravlično ustrezne rešitve, ki so podobne nerazdeljenemu VO. Ohranitev glavnih tokovnih poti je tako dodaten pogoj za določitev topološko sprejemljivih kombinacij vpetja MO.
Kombinacije določimo s prirejeno obliko postopka, predstavljenega v razdelku 2.3. Najprej določimo transportne mejne cevi, ki so hkrati mejne cevi in del transportnih vodov. Te bodo ostale odprte (na njihovem mestu bodo vgrajeni merilci pretoka), zato lahko zapremo (vgradimo zasune) vse ostale mejne cevi, ki povezujejo ista merilna območja. Na tem mestu smo še dodatno zmanjšali število kombinacij z upoštevanjem premerov mejnih cevi med posameznimi pari MO. Upoštevamo, da bo zapiranje večjih, bolj pretočnih cevi v VO bolj poslabšalo hidravlične razmere kakor zapiranje manjših cevi. Zato lahko, ne da bi izgubili hidravlično optimalnejše kombinacije vpetja, vnaprej zapremo vse preostale netransportne mejne cevi med posameznimi pari merilnih območij, D5
katerih pretočnost (—) je manjša od polovice največje prepoznane.
Iz grafa H izločimo povezave, ki predstavljajo v predhodnih dveh korakih zaprte mejne cevi, in določimo pomožni graf H'. Vsa vpeta drevesa grafa H' poiščemo z algoritmom za iskanje vseh vpetih dreves v povezanih neusmeijenih enostavnih grafih (Hotz, 2017). Ker dobljena vpeta drevesa ne vsebujejo nujno vseh prej prepoznanih transportnih mejnih cevi, vsako dobljeno vpeto drevo razširimo z dodajanjem povezav, ki predstavljajo manjkajoče mejne transportne cevi. Rezultat tega so podgrafi grafa H', ki so lahko različnih velikosti (število povezav). Ker nas zanimajo samo kombinacije z najmanjšim potrebnim številom odprtih mejnih cevi, ohranimo samo podgrafe najmanjših velikosti. Iz teh lahko določimo vse pripadajoče podgrafe grafa H, ki tako predstavljajo vse najmanj redundantne in topološko sprejemljive načine vpetja MO, ki hkrati upoštevajo tudi transportne vode v VO.
3.5 Vrednotenje kombinacij in izbira različice
Sledi faza vrednotenja, kjer preverimo vse dobljene kombinacije vpetja MO glede na izbrane kriterije. Za vsako kombinacijo vpetja izvedemo statično
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 43-50, Ljubljana
hidravlično simulacijo za srednjo dnevno porabo in izvedemo kontrolo ustreznosti tlakov. Nato izračunamo indeks odpornosti /r, pretoke na vodohranih in ocenimo investicijske stroške vzpostavitve MO.
Izmed vseh možnih kombinacij izberemo hidravlično najustreznejšo. Izbira temelji na indeksu odpornosti /r in določenih pretokih v vodohrane. Slednji kriterij smo vključili, ker se pretoki na vodohranih lahko razlikujejo med kombinacijami, npr. enkrat se pojavi vtok, drugič iztok iz vodohrana. Ta pojav vpliva na izračun indeksa odpornosti, ki lahko v nekaterih primerih preseže osnovno vrednost /rl nerazdeljenega VO. Do tega lahko pride, ker z zapiranjem nekaterih cevi v procesu vpetja MO spremenimo tokovne razmere v VO, te pa se odražajo tudi v spremenjenih pretokih na vodohrane. V enačbi (15) za izračun indeksa /r so v imenovalcu upoštevani tudi pretoki na vodohranih (Q0), kar lahko privede do popačenih rezultatov. Z upoštevanim kriterijem o spremembi pretoka na vodohranih tako preprečimo napačno izbiro hidravlično najustreznejših rešitev.
Ker je naš cilj najti hidravlično ustrezne rešitve, katerih tokovne razmere so podobne tistim v nerazdeljenem VO, želimo čim manjša odstopanja pretokov na vodohranih. To hkrati sovpada z vrednostmi indeksa odpornosti blizu prvotne /r1.
Hidravlično najustreznejše vpetje bomo poimenovali z izrazom različica. Različica je kombinacija vpetja, ki ima najvišjo vrednost indeksa odpornosti znotraj tistih kombinacij, ki imajo najnižje deviacije pretokov na vodohranih za dano število MO. Odstopanje pretokov na vodohranih je izračunano kot evklidska norma vektorja, ki ga sestavimo iz sprememb pretokov v vodohrane/iz vodohranov, glede na stanje v nerazdeljenem VO. Po izbiri izluščimo relevantne hidravlične spremenljivke o posameznih MO.
(a)	velikost vzpostavljenih MO,
(b)	hidravlična ustreznost razbitega VO,
(c)	strošek izvedbe,
(d)	kakovost zasnove MO.
V	prvo skupino kriterijev - (a) velikost vzpostavljenih MO - je vključena mediana porabe vode v zasnovanih MO. Ta kriterij je pomemben za izbiro rešitve, ki ima ustrezno velikost in porabo MO, s čimer zagotavljamo izboljšano identifikacijo vodnih izgub znotraj MO z uporabo metode minimalnega nočnega pretoka (Lambert, 2003). Razlog za izbiro mediane, namesto povprečne porabe, je, da so povprečne vrednosti pri istih vrednostih p enake in tako ne omogočajo razlikovanja posameznih različic. Za dano vrednost p namreč celotno metodo zasnove MO izvedemo za različne vhodne parametre razbitja (utežni primer, metoda razbitja), kar rezultira v naboru različic.
V	sklop (b) hidravlične ustreznosti različic smo vključili merili indeksa odpornosti /r in odklona pretokov na vodohrane.
Upoštevana sta tudi (c) strošek izvedbe in (d) kakovost zasnove MO. Medtem ko se prva določi na podlagi ukrepa na mejni povezavi, pa slednja vsebuje informacije o enakomernosti porabe (maksimalna poraba MO) in o dolžinah v VO (standardna deviacija dolžin omrežja) v zasnovanih MO. Tudi ti kriteriji bistveno vplivajo na uspešnost identifikacije vodnih izgub in sledijo priporočilom za zasnovo MO (Morrison et al. 2007).
Vrednosti vseh izbranih kriterijev normiramo po enačbi (16) za kriterije pozitivnih in po enačbi (17) za kriterije negativnih vplivov. Matematična zasnova evalvacijskega modela je prevzeta iz aktualne literature (Liu in Han, 2018).
fu -minft,
°y =-T
' maxf

rnnf
(16)
3.6 Izbira končne rešitve
Končna rešitev je izbrana s pomočjo večkriterijskega evalvacijskega modela, ki smo ga izdelali za obvladovanje števila dobljenih različic in izločitve subjektivnega vpliva pri odločanju. Izbrane kriterije lahko razdelimo v štiri skupine:
On =
maxf - f t _
max ft, - min ft,
(17)
Tu indeks predstavlja različice, indeks pa izbrane kriterije. Tako vrednosti /-tega kriterija, ki pripada i-ti različici, / ;, določimo delno oceno Oj ,-. Končno
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 44-50, Ljubljana
oceno posamezne različice Oi določimo kot uteženo vsoto iz enačbe (18)
Oi=^ujoij,
(18)
kjer Uj predstavlja pripadajočo utež posameznega kriterija. Višje vrednosti ocen različice po enačbi (18) pomenijo boljšo rešitev razbitja VO oziroma vzpostavitve MO.
4. Rezultati in diskusija
Predstavljena metoda je bila preizkušena na realnem VO, ki oskrbuje območje Šentvida z okolico v Ljubljani. Hidravlični model obravnavanega VO sestoji iz 812 vozlišč, 1072 povezav, enega vodnega vira in dveh vodohranov. Hidravlični model ima srednjo dnevno porabo 98,3 l/s, skupno dolžino cevi pa približno 98 km. Uporabljeni hidravlični model je umerjen na podlagi stalnih in začasnih merilnih mest, rezultati hidravličnih simulacij pa so uporabljeni za določitev hidravličnega stanja nerazdeljenega VO (Kozelj et al., 2014).
Na sliki 2 so prikazani identificirani transportni vodi (zgoraj) in mostovi (spodaj). Lokacija vodnega vira je označena z modrim, lokacija vodohranov pa z zelenim vozliščem.
Spodnja in zgornja meja za število vzpostavljenih MO sta bili izbrani vnaprej, na pmin = 5 in pmax = 20, glede na velikost in porabo v VO ter z upoštevanjem smernic za zasnovo MO (Morrison et al., 2007).
Spektralno razbitje smo izvedli z novo predstavljeno metodo posplošenega normiranega prereza (GNC). Za vozliščne uteži smo upoštevali srednjo porabo posameznih vozlišč (GNCd), kar nam omogoča neposredno vključevanje enakomernosti srednje porabe med MO že v fazo samega razbitja grafa. Skupaj smo preizkusili 6 predstavljenih utežnih primerov, kar pomeni 6 nizov simulacij oz. 96 različic.
Za enega izmed izvedenih nizov simulacij, GNCWs, v preglednici 2 podajamo rezultate iz faze vpetja podgrafov. Učinkovitost predstavljenega algoritma za vpetje merilnih območij je razvidna iz primerjave
števila vseh možnih kombinacij minimalnega vpetja (Nvk) s številom relevantnih kombinacij (Nrk). Učinkovitost predlaganega algoritma vpetja podgrafov je še posebej izrazita pri večjih številih p.
Slika 2: Rdeče obarvani so prepoznani transportni vodi (zgoraj) in mostovi (spodaj) v VO.
Figure 2: Identified water mains (above) and bridges (below) in the WDN.
j
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 45-50, Ljubljana
Preglednica 2: Podatki o vpetju za niz GNCW3. Table 2: DMA connection data for series GNCW3.
p	Nvk	Nrk	^mc	Nomc	Nzmc
5	210	1	10	4	6
6	21	1	7	5	2
7	1	1	6	6	0
8	792	1	12	7	5
9	3003	1	14	8	6
10	11440	1	16	9	7
11	167960	1	20	11	9
12	293930	1	21	12	9
13	497420	1	22	13	9
14	2,0*106	1	24	14	10
15	17*106	3	27	15	12
16	30*106	12	28	16	12
17	0,1*109	60	30	17	13
18	0,2*109	15	31	18	13
19	4,1*109	15	35	19	16
20	16*109	15	37	20	17
Znižanje števila kombinacij Nvk z izločanjem topološko in hidravlično neustreznih načinov vpetja MO omogoča izjemno pohitritev izvajanja predlaganega algoritma ter uspešno in učinkovito vzpostavitev MO.
V preglednici 2 so za niz GNCW3 podana še števila vseh (Nmc), odprtih (Nomc) in zaprtih (Nzmc) mejnih cevi. Vidimo lahko, da je do p = 11 dobljeno vpetje minimalno (Nomc = p — 1), potem pa je za ohranitev hidravličnega delovanja in zagotovitev ustreznih pretočnih sposobnosti VO potrebna dodatna odprta mejna cev in s tem dodatna namestitev merilnika pretoka.
Pri določanju končnih ocen z evalvacijskim modelom smo uporabili uteži iz preglednice 3. Najpomembnejšemu kriteriju, mediani porabe MO, ki narekuje velikost vzpostavljenih MO, smo določili največjo utež, saj je ravno od tega odvisna uspešnost identifikacije vodnih izgub znotraj MO po izvedeni particiji VO (Morrison et al., 2007). Ostalim trem skupinam kriterijev smo določili enake uteži (0,2). Razlog za nizko utež hidravličnim kriterijem je dejstvo, da so vse različice že določene na podlagi hidravlične evalvacije kombinacij vpetja, ki je bilo izvedeno v fazi vpetja MO, in so
tako že hidravlično ustrezne rešitve. Kriterijema stroška izvedbe in kakovosti razbitja VO smo za namene raziskave dodelili enakovreden prispevek. Velja poudariti, da so izbrane uteži predmet spremembe in se lahko prilagajajo prioritetam, ki jih določi uporabnik metode.
Preglednica 3: Uteži evalvacijskega modela.
Table 3: Weights of the evaluation model.
Kriterij
Utež u-
"J
(a)	Mediana porabe MO	0,40
(b)	Odklon pretokov na vodohranih	0,15
	Indeks odpornosti Ir	0,05
(c)	Strošek izvedbe	0,20
(d)	Maksimalna poraba MO Standardna deviacija dolžin omrežja posameznih MO	0,10 0,10
Skupna ocena
1,00
Preglednica 4: Končne ocene različic. Table 4: The final scores of the alternatives.
Posplošeni normirani prerez (GNCd)
P	W1	W2	W3	U	D	r ^min
5	0,523	0,652	0,532	0,649	0,527	0,534
6	0,663	0,682	0,669	0,681	0,660	0,678
7	0,770	0,770	0,771		0,774	0,774
8	0,735	0,743	0,710	0,723	0,698	0,777
9	0,762	0,766	0,764	0,750	0,758	0,763
10	0,765	0,770	0,773	0,754	0,757	0,746
11	0,790	0,780	0,754	0,768	0,775	0,778
12	0,797	0,798	0,764	0,786	0,755	0,790
13	0,781	0,779	0,782	0,770	0,768	0,775
14			0,787	0,781	0,770	0,770
15	0,714	0,714	0,800	0,794	0,785	0,787
16	0,719	0,723	0,811	0,791	0,796	0,803
17	0,744	0,744	0,820	0,794	0,730	0,736
18	0,744	0,747	0,743	0,788	0,732	0,734
19	0,743	0,746	0,736	0,709		
20	0,728	0,728	0,725	0,701		
Vsota	10,98	11,14	11,94	11,24	10,29	10,45
Povp.	0,732	0,743	0,746	0,749	0,735	0,746
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 46-50, Ljubljana
Končne ocene izbranih različic so podane v preglednici 4. Izmed 96 razbitij je bilo 7 topološko neustreznih (notranje nepovezani grafi), kar je razlog za 7 praznih polj v preglednici 4. Za splošno primerjavo med parametri razbitja dodajamo še vsoto in povprečje končnih ocen za posamezne nize. Prvo lahko upoštevamo kot merilo konsistentnosti, medtem ko drugo kot merilo uspešnosti. Celice v preglednici so za lažjo primerjavo obarvane s trostopenjsko barvno lestvico. Najboljših 10 % vnosov je krepko poudarjenih, medtem ko je najvišja vrednost tudi uokvirjena. Krepko zapisana vrednost v vrsticah z vsotami in povprečji pomeni najboljši vnos za pripadajočo vrstico.
Med seboj primerjamo uspešnost posameznih utežnih primerov. Na podlagi prikazanih vrednosti lahko potrdimo splošno ustreznost novo predstavljenih utežnih primerov. Še posebej izstopa utežni primer w3 (glej preglednico 1), ki se je izmed vseh preizkušenih izkazal za najbolj konsistentnega.
Najvišje povprečje končnih ocen je dosegel neuteženi primer (U), kar potrjuje ugotovitve ostalih avtorjev (Di Nardo et al., 2017b) in s tem njegovo ustreznost za zasnovo MO. Kljub temu pa lahko vidimo, da pri utežnem primeru w3 z dodatnim upoštevanjem lokacij obstoječih zasunov pozitivno vplivamo na postopek razbitja in tako dosežemo boljšo particijo VO.
Za končno rešitev smo izbrali različico z najboljšo oceno. Ta predvideva vzpostavitev 17 MO in je bila dobljena z upoštevanjem utežnega primera w3. V tem primeru znaša povprečna srednja poraba MO 5,8 l/s, povprečna dolžina omrežja v MO pa približno 5,8 km. Strošek izvedbe izbrane različice znaša 65.642 EUR in vključuje ceno potrebovanih merilnikov pretoka in zasunov. Predvidena prostorska razporeditev MO je prikazana na sliki 3, podrobnejši podatki o posameznih MO so podani v preglednici 5.
Slika 3: Izbrani predlog particije VO - barva pokaže pripadnost vozlišča posameznemu MO.
Figure 3: The proposed partitioning of the WDN - the colour shows the corresponding DMA for each node.
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 35-50, Ljubljana
Tu Nvoz predstavlja število vozlišč, Ncev število cevi, vsoto porabe, skupno dolžino omrežja in z povprečno nadmorsko višino vozlišč v MO. Skupna poraba MO zavzema vrednosti med 2,7 l/s in 9,5 l/s, njihova dolžina omrežja pa med 2,2 km in 9,7 km.
Preglednica 5: Podatki o izbrani končni rešitvi.
Table S: Data regarding the final selected solution.
ID	Nvoz	Ncev	1d	11	z
	[-]	[-]	[l/s]	[km]	[m]
MO 1	3S	46	8,4	3,6	313
MO 2	33	40	3,4	3,9	321
MO 3	40	49	5,3	5,2	321
MO 4	51	67	7,5	6,5	310
MO 5	S0	101	6,1	7,6	317
MO 6	37	4S	6,7	4,S	317
MO 7	20	22	3,0	5,7	325
MO S	25	32	5,3	3,S	303
MO 9	69	96	4,9	5,9	309
MO 10	56	71	9,5	6,9	311
MO 11	44	5S	6,S	5,7	309
MO 12	71	100	3,6	7,4	301
MO 13	21	23	5,4	3,6	30S
MO 14	66	S5	2,7	6,S	302
MO 15	91	115	S,2	9,7	316
MO 16	12	12	3,1	2,2	316
MO 17	5S	6S	8,4	4,5	315
5. Zaključek
V prispevku smo predstavili metodo za avtomatsko particijo VO na osnovi teorije grafov in spektralnega razbitja grafov. Slednjega smo izvedli z novo predlagano ciljno funkcijo posplošenega normiranega prereza (GNC), ki poleg uteži na povezavah upošteva tudi vozliščne uteži v grafu. Predlagana metoda je bila preizkušena na realnem VO, rezultati pa so potrdili njeno ustreznost za particijo VO.
Med seboj smo primerjali uspešnost različnih utežnih primerov. Sodeč po rezultatih lahko z ustrezno izbiro uteži pozitivno vplivamo na dobljena razbitja, kar zagotavlja ustreznejše končne rešitve v primerjavi z neuteženim primerom (U). Prav tako smo pokazali, da lahko z upoštevanjem lokacij obstoječih zasunov v fazi razbitja dodatno izboljšamo dobljene rešitve (w3). Glede na rezultate
predhodnih študij (Di Nardo et al., 2017b) lahko sklepamo, da je uporaba stroškovnih in topoloških podatkov v fazi spektralnega razbitja VO ustreznej ša od upoštevanj a hidravličnih parametrov.
Dobljene zasnove MO so bile vpete z uporabo novo predstavljene metode, ki temelji na konceptu vpetega drevesa in prav tako upošteva transportne vode v VO. Njena učinkovitost v primerjavi s tradicionalnim kombinatoričnim pristopom je očitna predvsem pri primerih z večjim številom vzpostavljenih MO, ko število kombinacij vpetja zelo hitro naraste. Z uporabo predstavljene metode tako izluščimo le hidravlično in topološko smiselne kombinacije vpetja, kar nam v nadaljnjem postopku evalvacije omogoči izbiro optimalne končne rešitve.
Viri
Alvisi, S., Franchini M. (2014). Heuristic procedure for the automatic creation of district metered areas in water distribution systems, Urban Water Journal 11.2, 137— 159. https://doi.org/10.1080/1573062X.2013.768681.
Alvisi, S. (2015). A New Procedure for Optimal Design of District Metered Areas Based on the Multilevel Balancing and Refinement Algorithm, Water Resources Management	29,	4397—4409.
https://doi.org/10.1007/s11269-015-1066-z.
Arthur, D., Vassilvitskii, S. (2007). K-means++: The Advantages of Careful Seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, 1027-1035.
Campbell, E., Izquierdo, J., Montalvo, I., Pérez-García, R. (2016). A Novel Water Supply Network Sectorization Methodology Based on a Complete Economic Analysis, Including Uncertainties, Water 8(5), 179. https://doi.org/10.3390/w8050179.
Creaco, E., Franchini, M., Todini, E. (2016). Generalized resilience and failure indices for use with pressure-driven modeling and leakage, Journal of Water Resources Planning and Management 142(8), 04016019. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000656.
De Paola, F., Fontana, N., Galdiero, E., Giugni, M., Savic, D., Sorgenti degli Uberti, G. (2014). Automatic Multi-Objective Sectorization of a water distribution network, Procedía Engineering 89, 1200—1207. https://doi.org/10.1016/j.proeng.2014.11.250.
4S
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 48-50, Ljubljana
Diao, K., Zhou, Y., Rauch, W. (2013). Automated creation of district metered areas boundaries in water distribution systems, Journal of Water Resources Planning and Management 139(2), 184-190. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000247.
Di Nardo, A., Di Natale, M. (2010). A heuristic design support methodology based on graph theory for district metering of water supply networks, Engineering Optimization	43(2),	193-211.
https://doi.org/10.1080/03052151003789858.
Di Nardo, A., Di Natale, M., Santonastaso, G. F., Venticinque, S. (2013). An Automated Tool for Smart Water Network Partitioning, Water Resources Management	27(13),	4493-4508.
https://doi.org/10.1007/s11269-013-0421-1.
Di Nardo, A., Di Natale, M., Greco, R., Santonastaso, G.
F.	(2014). Ant Algorithm for Smart Water Network Partitioning, Procedía Engineering 70, 525-534. https://doi.org/10.1016/j.proeng.2014.02.058.
Di Nardo, A., Di Natale, M., Giudicianni, C., Musmarra, D., Santonastaso, G. F., Simone, A. (2015). Water distribution system clustering and partitioning based on social network algorithms, Procedia Engineering 119, 196-205. https://doi.org/10.1016/j.proeng.2015.08.876.
Di Nardo, A., Di Natale, M., Chianese, S., Musmarra, D., Santonastaso, G. F. (2016). Combined Recursive Clustering and Partitioning to Define Optimal DMAs of Water Distribution Networks. Proceedings of the 8th International Congress on Environmental Modelling and Software, Toulouse, France, 63.
Di Nardo, A., Di Natale, Giudicianni, C., Santonastaso,
G.	F., Tzatchkov, V., Rodriguez Varela, J. M. (2017a). Economic and Energy Criteria for District Meter Areas Design of Water Distribution Networks, Water 9(7), 463. https://doi.org/10.3390/w9070463.
Di Nardo, A., Di Natale, Giudicianni, C., Greco, R., Santonastaso, G. F. (2017b). Weighted spectral clustering for water distribution network partitioning,
Applied Network Science 2, 19. https://doi.org/10.1007/s41109-017-0033-4.
Di Nardo, A., Di Natale, Giudicianni, C., Greco, R., Santonastaso, G. F. (2018). Water Distribution Network Clustering: Graph Partitioning or Spectral Algorithms?. Proceedings of the 6th International Conference on Complex Networks and Their Applications: COMPLEX NETWORKS 2017, Lyon, France. Studies in Computational Intelligence, vol 689, 1197-1209.
Eliades, D. G., Kyriakou, M., Stelios Vrachimis, S., Polycarpou, M. M. (2016). EPANET-MATLAB Toolkit: An Open-Source Software for Interfacing EPANET with
MATLAB. Proceedings of the 14th International Conference on Computing and Control for the Water Industry, CCWI 2016, Amsterdam, Netherlands.
Ferrari, G. (2012). Hybrid graph partitioning approach for dividing a water distribution network into district metered areas. Proceedings of WDSA 2012: 14th Water Distribution Systems Analysis Conference, 24-27 September 2012, Adelaide, Australia, 569-578.
Ferrari, G., Savic, D. A., Becciu, G. (2014). Graph-Theoretic Approach and Sound Engineering Principles for Design of District Metered Areas, Journal of Water Resources Planning and Management 140(12), 04014036. https://doi.org/10.1061/(ASCE)WR.1943 -5452.0000424.
Hajebi, S., Barrett, S., Clarke, A., Clarke, S. (2013). Multi-agent simulation to support water distribution network partitioning. In proceeding of the 27th European Simulation and Modelling Conference - ESM'2013, Lancaster, UK.
Hajebi, S., Ehsan, R., Cardozo, N., Barrett, S., Clarke, A., Clarke, S. (2016). Water distribution network sectorisation using graph theory and many-objective optimisation, Journal of Hydroinformatics 18(1), 77-95. https://doi.org/10.2166/hydro.2015.144.
Hotz, M (2017). generateSpanningTrees(A), MATLAB Central	File	Exchange.
https://www.mathworks.com/matlabcentral/fileexchang e/53787-generatespanningtrees-a- (Pridobljeno 1. 10. 2017.)
Karypis, G., Kumar, V. (1999). A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on Scientific Computing 20(1), 359-392. https://doi.org/10.1137/S1064827595287997.
Kozelj, D., Kapelan, Z., Novak, G., Steinman, F. (2014). Investigating prior parameter distributions in the inverse modelling of water distribution hydraulic models,
Strojniški vestnik - Journal of Mechanical Engineering 60(11), 725-734. https://doi.org/10.5545/sv-jme.2014.1741.
Kozelj, D., Gorjup, M., Kramar Fijavž, M. (2017). Uporaba metode spektralnega razbitja grafov za zasnovo merilnih območij v vodovodnem omrežju, Acta hydrotechnica 30(53), 81-96.
Lambert, A. (2003). Assessing non-revenue water and its components: A practical approach, Water 21 5(4), 50-51.
Liu, J., Han, R. (2018). Spectral Clustering and Multicriteria Decision for Design of District Metered
Areas, Journal of Water Resources Planning and Management	144(5),	04018013.
36
Zevnik J. et al.: Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov - Efficient
partitioning of water distribution networks using a graph-theoretical approach
Acta hydrotechnica 31/54 (2018), 49-50, Ljubljana
https://doi.org/10.1061/(ASCE)WR.1943-5452.0000916.
Lloyd, S. P. (1982). Least Squares Quantization in PCM,
IEEE Transactions on Information Theory 28(2), 129137. https://doi.org/10.1109/TIT.1982.1056489.
Von Luxburg, U. (2007). A tutorial on spectral clustering, Statistics and Computing 17(4), 395-416. https://doi.org/10.1007/s11222-007-9033-z.
MATLAB 2015b (2015). The MathWorks, Inc., Natick, Massachusetts, United States.
Mohar, B., Alavi, Y., Chartrand, G., Oellermann, O., Schwenk, A. (1991). The Laplacian spectrum of graphs.
Graph Theory, Combinatorics and Applications 2, 871898.
Morrison, J., Rogers, D., Tooms, S. (2007). District Metered Areas Guidance Notes, Water Loss Task Force, IWA Publication, 2007.
QGIS Development Team (2018). QGIS Geographic Information System. Open Source Geospatial Foundation Project. http://qgis.osgeo.org
Rossman, L. A. (2000). Epanet2 Users Manual. U. S. Environmental Protection Agency, National Risk Management Research Laboratory, Cincinnati, Ohio, USA.
Sela Perelman, L., Allen, M., Preis, A., Iqbal, M., Whittle, A. J. (2015). Automated sub-zoning of water distribution systems, Environmental Modelling & Software	65,	1-14.
https://doi.org/10.1016/j.envsoft.2014.11.025.
Sempewo, J., Pathirana, A., Vairavamoorthy, K. (2008). Spatial analysis tool for development of leakage control zones from the analogy of distributed computing. Proceedings of the 10th Annual Water Distribution Systems Analysis Conference (WDSA 2008), Kruger National Park, South Africa.
Shi, J., Malik, J. (2000). Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888-905. https://doi.org/10.1109/34.868688.
Tarjan, R. E. (1974). A note of finding the bridges of a graph, Information Processing Letters 2(6), 160-161. https://doi.org/10.1016/0020-0190(74)90003-9.
Wilson, R.J., Watkins, J.J. (1997). Uvod v teorijo grafov. DMFA Slovenije.
Yen, J. Y. (1971). Finding the k Shortest Loopless Paths in a Network, Management Science 17(11), 712-716. http://dx.doi.org/10.1287/mnsc.17.11.712.
36