07--FABIAO枚举和动态规划法在污水管网布局优化中的应用.doc

枚举和动态规划法在污水管网布局优化中的应用陈国栋 尹士君 汤金如 王颖 （沈阳建筑大学市政与环境工程学院，辽宁，沈阳，110168）摘要：用VB语言编写污水管网布局优化计算程序，由污水有向网络图出发，以污水管网系统费用最低为优化目标，并结合图论理论知识，应用枚举法将污水管网的所有可能布局形式全部列出，同时利用水力参数优化计算，进行动态规划剪枝，选出污水管网最优的布局形式及其水力参数。应用结果表明,该方法可节省约11.9%的工程总投资,对实际工程设计具有重要的指导意义。关键词：污水管网；有向网络图；枚举法；动态规划法；布局优化The Optimized distribution of Sewage network with Enumeration Algorithm and Dynamic ProgrammingChen Guodong ,Yin Shijun, Tang Jinru , Wang Ying (School of Municipal and Environmental Engineering, Shengyang Jianzhu University, Shengyang, China, 110168) Abstract: Based on VB language that programmes the optimized distribution of sewage network, form directed graph of sewage network ,optimal aim is minimal cost, link graph theory knowledge ,apply Enumeration Algorithm to list all sewage network distribution form and use optimized calculation of hydraulic parameter , make use of dynamic programming to cut away disadvantage programs and select the optimized distribution as well as hydraulic parameters of sewage network . The results indicated that the method is more economical than other optimized programs about 11.9%, has important guiding significance for design of actual engineering. Key word: sewage network; directed graph; enumeration algorithm; dynamic programming; distribution optimization污水管网平面布置的优化设计原则是使管线短，管道工程量最小，水流通畅且节省能量。正确的定线是合理经济地设计污水管道系统的先决条件，对不同的定线方案的优化选择更具实用价值。目前国内在平面布局优化方面已有的研究，大部分是利用图论知识，给图中的线段赋予不同的权值(通常是管道的费用)，运用Dijkstra算法和Kruskal算法求得管网布局的最优方案。这些研究的不足之处在于：对污水管网系统，在布局方案没有确定的情况下，下游管道的费用权值会随上游管道形式的改变而改变，所以它属于变权值问题。而图论中，对于变权值问题现在还没有一个令人满意的解决方法。因此本文利用枚举法和动态规划法，避开了费用权值的问题，提出了布局优化的新方法。1模型分析及建立根据污水的排水区域的情况，可以用有向网络图表示污水的流向关系。污水管网的布局形式是枝状的，并且是有向网络图的子图；由图论理论知识，一个有向图的子图的形式是不唯一的，也就是说污水管网可行的布局形式是多个的，而且其数目的大小与图的大小成同一增大趋势。布局优化的方法是利用枚举法找出有向图的所有子图，目标就在这些子图中利用参数优化选择最优的一种，也就是管网布局的最优方案1。1.1 优化的思想本程序需要解决两个关键问题：（1）用枚举法把污水管网有向图中所有可行的布局形式全部列出，对每一种布局形式逐个进行参数优化，而在参数优化中把污水管道每一管段所有可行的方案全部列出，对这些方案逐个进行水力计算。（2）利用动态规划法对不优的方案进行剪除，并对剩余的优化方案进行经济技术综合比较，从中列出工程造价最低的方案就是最优布局形式下的最优设计方案2。该方法既可以在所有可行的污水管网布局形式下选出最优的布局以及管道的水力参数，又可以节省计算机的内存，从而使普通的PC就可以满足计算要求。1.2 枚举布局方案根据污水管网有向图的关系对原始数据作如下假设：(1)管网中检查井都抽象为节点，保留有流量汇入的节点和地势状态改变处的节点，其它节点不计；(2)各节点汇水面积、集中流量、比流量、地面标高已知；(3)相邻节点之间的地面坡度是常数；以其两点的平面距离作为管道的长度，且为已知量。对于有p条边的污水管网有向图如图1，根据图论中树的性质，有q个节点的树，由q-1条边组成。根据这个性质，在污水管网有向图中的所有可能的下游节点数目如图2，它生成的污水管网布局应由8根管道组成，而污水管网所有布局形式的个数为24=16。运用计算机求解时，要把污水有向网络图的信息储存起来，有向图的关联矩阵M 是表示图中节点关系的图表。关联矩阵M=( )是一个mn阶矩阵，m和n分别是上游节点数和下游节点数。其中Aij= 0 上游节点i和下游节点j不相接；Aij= 1 上游节点i和下游节点j第一个节点相接；Aij= 2 上游节点i和下游节点j第二个节点相接；Aij= 3 上游节点i和下游节点j第三个节点相接； 图1 污水有向网络图 图2 节点关联矩阵图 Fig1 Directed graph of sewage network Fig2 Graph of node incidence matrix （1）由图2可以看出节点1，2，4，5这四个节点各有两个下游节点，由于污水管网的性质，一个节点下游只能有一根管段与之相连接，根据这个性质和节点关联矩阵可以把污水管网所有布局形式列出，然后把污水有向网络图（图1）相应的节点编号与Aij 相对应，得出污水管网的所有布局形式下的上下游节点编号；同时可以根据每一种布局的上游节点编号的个数求得节点上游接管数。（2）对每一种布局形式的管网节点，在遵循下游节点的编号要大于其上游所有节点编号的原则的基础上进行重新编号，使编号符合参数优化计算的需要。首先从第一个节点开始遍历，如果节点的上游接管数为0或者其下游节点的上游接管数是1，可以从小到大依次编号，如果上游接管数大于1时，则跳过该节点，暂不对该节点编号，直到遍历所有节点；然后再从第一个节点开始遍历，对上游接管数大于1的节点，接上次的编号逐个进行节点编号，直到遍历所有节点；最后对没有编号的节点依次进行编号，直到最后一个节点。（3）对每一种布局形式的管长、汇水面积、集中流量、地面标高等原始参数，使之与新节点编号进行对应。对于某种平面布置方案是否最优，取决于该平面布置方案优化设计计算结果，因此已定管线下的参数优化设计计算是平面优化布置的基础。1.3 优化计算方案污水管网是一种重力流的枝状结构，污水管道设计计算是从上游管段开始，逐渐向下游递推的。对于每一种布局形式下每一根设计管段，先选出一个最小的标准设计管径；计算当前管段的设计流量，按最大充满度进行水力计算，如果流速、埋深、水力坡度等条件不符合要求时，则进行参数调整，计算出管段的第一个设计方案，如此循环不断增加管径计算新方案，直至新方案的设计参数管径D、流速v、埋深h、造价c都不如以前计算的方案为止，中止循环。用这种方法可以把每一种布局形式所有管段的所有可行方案全部计算出，为最终选出最优布局提供了可能。如图3所示：图3 污水管网计算程序流程图Fig3 Flow chart of sewage network 1.4动态剪枝由于污水管道的设计管段多在几十根甚至上百根，进行枚举布局时有许多可行布局形式，而每一个布局形式的全部设计管段储存专用数据变量已经远大于计算机内存，因操作系统和计算程序还需占用一定的内存。因此必须解决计算机内存不够的问题。根据动态规划理论，总体最优的方案一定是由局部最优的方案所组成。但是污水管道设计的最优化，是以整个污水系统的造价作为判别标准。因为污水管道设计的特殊性，当前管段局部造价最低的方案，并不一定是整个系统造价最低的方案。所以根据对影响管段造价各项因素的分析结果，将管径D、流速v、造价c、埋深h作为方案取舍的择优条件。把每一种布局形式的所有可行方案在任何一个方面处于有利条件下的所有方案都保留，将每一管段的四个方面同时处于不利条件下的方案进行剪除，从剩余的优化方案中选择这种布局的最优方案，并释放其它不优方案占用的内存；然后把所有布局形式的最优方案全部选出，再根据管网的总造价从中选出最优布局。这样不仅减少计算机的计算内存的占有量，而且减少了计算的时间，解决了计算机内存不足的问题，可见动态剪枝的必要性。1.5污水管道目标函数 本文主要考虑管道的造价，由于设计管径和管道埋深是决定污水管道造价的直接因素，故本设计程序采用的目标费用函数关系如下： X = 4.0 , D 0.55 X 0.55 X 4.0 , D 4.0 , D 0.55式中：D为管径/m；X为管段平均埋深/m；L为管长/m。 2. 程序实现与应用实例根据上述的计算原则，用VB 语言编写污水管网优化计算程序。程序中原始数据输入内容有节点上游和下游编号、管段长度、汇水面积、地面标高、节点上游接管数和比流量。计算程序能根据各节点的衔接关系，自动检查计算节点上游各管段每个方案终点的水力参数，根据设计原则确定下游管段各方案起点的水力参数，并进行水力计算和造价计算；如此循环，遍历所有管段的所有方案。此程序可一次计算完整个污水管网，计算出所有布局的优化方案，克服了单个可行布局的计算和单条管段计算及节点处人工调整，以及多次重复计算等繁琐和困难，避免了管网系统中难以确定控制点的缺点，并使污水管网的设计更趋合理和经济。某小区进行污水管网规划，其污水系统的有向网络图及原始数据如图4所示。图4 某污水系统有向网络图Fig4 The directed graph of sewage network布局方案编号管径(mm)最后管段埋深(m)总造价(万元)布局方案编号管径(mm)最后管段埋深(m)总造价(万元)14001.88349.789294001.96750.802424001.97549.7808104001.92450.880734001.77346.6537114501.41846.814444001.73346.4549124001.51846.924854001.87251.5022134001.88852.504464001.94351.6374144002.07252.747574501.55348.4525154001.54348.801384001.81848.503164001.6248.9254表1 污水管网所有布局形式下最优计算结果 Table 1 Optimal calculation result of all sewage network layout 图5 最优管网布局图 图6 最劣管网布局Fig5 The optimal sewage network layout Fig6 The tenth-rate sewage network layout程序优化总共得出197个方案，其中每个布局形式的最优方案，计算结果如表1所示。而最优布局形式为第4布局方案如图5所示，投资费用为46.4549万元；最劣布局形式为第14布局方案如图6所示，投资费用为52.7475元。从优化的结果可得出，利用管网布局优化模型得到的最优布局与最劣布局的投资费用相差达6.2926万元，相当于最劣布局形式投资费用的11.9左右。说明采用该方法进行污水管网布局优化是有效的、经济的。3结论（1）结合图论和枚举法的理论，提出了一种新的优化模型。从污水管网的有向网络图出发，采用枚举法可以选出污水管网所有布局和参数的所有可行方案，从而实现布局优化的目的；（2）利用动态剪枝的方法，将造价、埋深、流速和管径作为剪枝的限定条件，保留下可能成为最优化的设计方案，并且可以解决计算机内存不足的问题；（3）该优化模型比其他已有布局优化方法更全面，更能节省工程造价，且设计管段愈多，效果愈明显；（4）该方法同样也适用于雨水管道和合流制管道的设计。参考文献：1 杨宏军、吴学伟. 改进单亲遗传算法应用于污水管网的布局优化J.广州大学学报，Vo1.4. No.2 20052 尹士君.利用枚举和动态规划法实现污水管道的最优化设计J.给水排水,Vol.30. No.12.20043 严煦世、刘遂庆.给水排水管网系统M.北京:中国建筑工业出版社