摘要
为降低供水管网漏损,实现供水管网快速准确分区,提出一种耦合模块度优化与谱聚类的供水管网分区算法。该算法采用快速模块度优化算法对供水管网进行社区划分,以每个社区为节点、社区间连接关系为边,结合各社区内的水力特征和空间区位特征计算差异性作为边权重,构建对偶图。利用谱聚类算法完成供水管网分区。结果表明,该算法求解的管网分区结果相比快速模块度优化和谱聚类算法,将空间上更邻近的管段划分在同一分区,不会产生狭长型无效分区,且在模块度及边界管道数量上表现较为均衡,管网分区方案不仅模块度高,而且边界管道数量少。
在城市化发展进程中,供水管网漏损率居高不下,管理难度越来越大。科学合理地划分独立计量分区(district metering area,DMA)对供水管网漏损控制至关重
在基于模块度优化的管网分区方法中,Diao
本文研究耦合模块度优化与谱聚类的供水管网分区算法(coupling modularity optimization and spectral clustering algorithm,MOSC)。该算法结合管网水力特征和空间布局,对中国某市供水管网分区,以模块度和边界管道数为指标,构建MOSC与Fast-greedy、SC对比实验,验证MOSC有效性。
模块度是衡量网络划分为社区的强度指标,以值的大小来评价社区划分的优劣,值越接近1时,表示对社区结构的划分越好;模块度值越大,社区内部连接越紧密,社区间连接越稀疏,分区效果越
(1) |
式中:为网络的邻接矩阵,节点w相连,则,否则。m为网络的边数,,分别为节点v、w的度,即连接到节点v、w的边数。为节点v所在的社区。若节点v和节点w在同一社区,则,,否则。
边界管道是指连接不同管网分区之间的管道,由于供水管网分区方案是通过在边界管道上安装流量计和闸阀来实现,它的数量决定了分区改造的经济成本,所以从经济成本角度,边界管道数量越少越
针对Fast-greedy和SC的不足,MOSC耦合Fast-greedy和SC,一方面,集成Fast-greedy对网络拓扑紧密连接结构的高模块度社区挖掘能力,另一方面,集成SC对边界管道数量的约束能力,并综合考虑管网的水力特征和空间布局。MOSC包含3个步骤:最优模块度求解、对偶图构建和拉普拉斯特征分解与聚类,如

图1 MOSC流程图
Fig. 1 Flowchart of MOSC
城市供水管网是由相互连接的管道和其他附属设施组成的设施网络,水通过这些管道以及附属设施输送到需水节点,以满足系统的用水需求和压力要
(1)利用Fast-greedy对图G进行社区划分,初始化每个节点为一个社区,初始条件下的社区划分结果为,为第i个节点所在的社区,此时,,,计算初始化条件下的模块度。
(2)遍历图所有连边,分别合并相邻2个社区,得到每一种合并方案并计算对应的模块度,对比初始状态下的模块度。得到模块度变化量
(5) |
式中:为当前社区合并条件下的管网模块度;为合并2个社区之后的模块度。
(3)取合并后最大的合并方案为新的社区划分方案,划分后的结果为其中为划分后的社区。
(4)重复上述社区合并过程,当最大时,停止合并,得到对应的社区划分结果,其中为最终社区。
基于社区划分结果,结合社区内部的水力特征与空间分布特征来描述社区,完成对偶图的构建。如

图2 社区划分对偶图
Fig. 2 Duality map of community division
社区划分对偶图的具体构建步骤为:
(1)以社区划分结果为基础,将社区作为节点,社区之间的连接关系作为边,构建社区划分对偶图,其中为节点集,,为对偶图节点,为边集,,,,为对偶图边。
(2)为了降低水头损失,得到对管网水力性能影响最小的分区布局,提出以下水力特征向量
(6) |
式中:为社区内平均管径;为社区内平均管长;为社区内平均节点高程。
(3)提出以餐饮、购物、医疗服务、住宿、政府机关、休闲娱乐、交通出行和科研教育8个类型的POIs数量来表征社区内部的空间区位特征,得到以下功能结构特征向量:
(7) |
式中分别表示餐饮、购物等8个类型的POIs数量。
(4)拼接水力特征向量和功能结构特征向量得到总的特征向量
(8) |
式中:为第个节点对应社区的总特征向量;为第个节点对应社区的第种类型的POIs数量。
(5)对每个特征向量进行标准化,其中,为中各个特征向量标准化后的特征值,为中的各个特征向量的特征值,为所有中各个特征向量特征值的均值,为所有中各个特征向量特征值的标准差。计算各个社区之间标准化后的特征向量欧氏距离,变化得到相似性作为边权重
(9) |
式中:为的标准差。
采用我国某市管径100mm以上的实际供水管网作为实例分析数据,以模块度和边界管道数为指标,分析MOSC与Fast-greedy、SC的对比实验结果,验证MOSC用于供水管网分区的有效性。管网的基本信息如
对实例管网数据利用Fast-greedy、SC和MOSC求解分区,其中Fast-greedy由开源igraph模块实现,SC由sklearn.cluster模块实现。以模块度作为分区形态指标,以边界管道数量作为分区成本指标构建对比实验。以MOSC作为实验组,以Fast-greedy、管径为边权的SC作为对照组进行分区数量10到50的实验,实验结果如
(16) |

图3 对比实验结果
Fig. 3 Comparison of experimental result
从

图4 MOSC实验结果
Fig. 4 MOSC of experimental result

图5 分区方案综合评价
Fig. 5 Overall merit of partition plan
分析

图6 3种算法分区结果
Fig. 6 Partitioning result of three algorithms
分析

图7 3种算法分区局部结果
Fig. 7 Partitioning local results of three algorithms
利用Fast-greedy对管网的高模块度社区划分能力以及SC对于最小边界管道的识别能力,提出一种耦合模块度优化与谱聚类的管网分区算法MOSC。对比该算法与Fast-greedy和SC在模块度以及边界管段数量的表现,证明MOSC克服了Fast-greedy在处理分区边界较弱以及SC在模块度方面表现较差的缺点。MOSC算法相较于Fast-greedy算法和SC算法,所得分区方案具有模块度高、边界管道数量少的特点,而漏损控制则需要对区域内所有边界管道上的阀门、流量计进行清晰划分。因此,MOSC算法所得DMA分区不仅界限分明,没有出现狭长型无效分区和空间位置上的交叉重叠从而有利于水司进行分区的日常管理和维护,而且较少的边界管道有利于在漏损控制过程中减少阀门、流量计等设备的数量从而节省分区成本。本文提出的MOSC进行管网分区,考虑管径、管长、材质、管段数量等水力拓扑特征,后续可以引入更多诸如节点压力、水龄、用户数等特征,以进一步优化分区结果。
作者贡献声明
杨之江:提出研究选题;设计研究方案;论文撰写、修订。
周煜岷:调研整理文献;实施研究过程;论文撰写。
扈 震:技术支持;指导性支持;终审论文。
曾 文:指导性支持;技术支持。
周 扬:实验验证。
李晓丽:数据获取及加工。
冯 丽:实验验证。
参考文献
代焕芳,刘书明,吴雪.供水管网背景漏失指数研究[J].中国给水排水,2019,35(11):59. DOI: 10.19853/j.zgjsps.1000-4602.2019.11.011. [百度学术]
DAI Huanfang,LIU Shuming,WU Xue.Research on background loss index of water supply network[J].China Water & Wastewater,2019,35(11):59.DOI:10.19853/j.zgjsps.1000-4602.2019.11.011. [百度学术]
李化雨,吴珊,侯本伟,等.供水管网计算分区方法的比较分析[J].哈尔滨工业大学学报,2021,53(5):48. DOI:10.11918/201908144. [百度学术]
LI Huayu,WU Shan,HOU Benwei,et al.Comparative analysis of calculating division methods for water distribution systems[J].Journal of Harbin Institute of Technology,2021,53(5):48.DOI:10.11918/201908144. [百度学术]
DIAO Kegong,ZHOU Yuwen,RAUCH W.Automated creation of district metered area boundaries in water distribution systems[J].Journal of Water Resources Planning & Management,2013,139(2):184.DOI: 10.1061/(ASCE)WR.1943-5452.0000247.2018,34(5):37.DOI:10.19853/j.zgjsps.1000-4602.2018.05.008. [百度学术]
LIU H,ZHAO M,ZHANG C,et al.Comparing topological partitioning methods for district metered areas in the water distribution network[J].Water,2018,10(4):368.DOI:10.3390/w10040368. [百度学术]
HERRERA M,CANU S,KARATZOGLOU A,et al. An approach to water supply clusters by semi-supervised learning[C]//Proceedings of International Environmental Modelling and Software Society. Ottawa:[s.n.],2010:1925-1932. [百度学术]
DI NARDO A,DI NATALE M,GIUDICIANNI C,et al.Weighted spectral clustering for water distribution network partitioning[J].Applied network science,2017,2(1):19.DOI:10.1007/s41109-017-0033-4. [百度学术]
SALINGAROS N A.Complexity and urban coherence[J].Journal of Urban Design,2000,5(3): 291.DOI:10.1080/713683969. [百度学术]
YAO Y,LIU X,LI X,et al.Mapping fine-scale population distributions at the building level by integrating multisource geospatial big data[J].International Journal of Geographical Information Science,2017,31(6): 1220.DOI:10.1080/13658816.2017.1290252. [百度学术]
CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical review E,2004,70(6):066111.DOI:10.1103/PhysRevE.70.066111. [百度学术]
NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E, 2004,69(2):026113.DOI:10.1103/PhysRevE.69.026113. [百度学术]
ZHANG K,YAN H,ZENG H,et al.A practical multi-objective optimization sectorization method for water distribution network[J].Science of The Total Environment,2019,656: 1401.DOI:10.1016/j.scitotenv.2018.11.273. [百度学术]
蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学,2008,35(7):14.DOI:10.3969/j.issn.1002-137X.2008.07.004. [百度学术]
CAI Xiaoyan,DAI Guanzhong,YANG Libin.Summary of spectral clustering algorithms[J].Journal of Computer Science,2008,35(7):14.DOI:10.3969/j.issn.1002-137X.2008.07.004. [百度学术]
SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888. [百度学术]
刘俊,周鹏.谱聚类在给水管网分区优化中的应用[J].土木建筑与环境工程,2016,38(6):142 [百度学术]
LIU Jun,ZHOU Peng.Spectral clustering for optimal design of district metered areas in water distribution systems[J].Journal of Civil Architectural & Environmental Engineering,2016,38(6):142.DOI: 10.11835/j.issn.1674-4764.2016.06.019. [百度学术]
VON LUXBURG U.A tutorial on spectral clustering[J].Statistics and computing,2007,17(4): 395.DOI:10.1007/s11222-007-9033-z. [百度学术]
YAZDANI A, JEFFREY P. A complex network approach to robustness and vulnerability of spatially organized water distribution networks[J].arXiv preprint arXiv:1008.1770, 2010. [百度学术]
LIU J,HAN R.Spectral clustering and multicriteria decision for design of district metered areas[J].Journal of Water Resources Planning and Management,2018,144(5):04018013.DOI: 10.1061/(ASCE)WR.1943-5452.0000916. [百度学术]