典型山区供水管网离散优化布置研究——以贵州纳雍金蟾供水工程为例 46页

'三峡大学全日制专业学位硕士学位论文1绪论1.1研究背景与意义按照水质、水量、用水方便程度等指标衡量，目前全国尚有3亿多山区农村人[1]口（中西部地区占80%）饮水未达到安全标准。长久以来，由于山区地形条件复杂，交通不便，经济不发达等原因，导致我国大部分山区农村饮水安全问题特别突3出。贵州省毕节市纳雍县水资源总量8.1亿m，由于受地形地质条件影响，水资源开发利用率很低。农村的用水都是靠山体内蓄存流放出来的地下水，农村缺水面大、难度高。其中纳雍县羊场乡、姑开乡、锅圈岩乡和维新镇都是以农业为主的乡镇，在灌区范围内有耕地137872亩，人口109442人，大牲畜22915头。受地形地势和水文地质条件限制，水低田高，取水十分困难。四乡镇蓄水、引水、提水工程比较少，农田灌溉困难。部分耕地靠山塘供水，用水时段受到很大的限制。靠近河流的耕地由于距河高差较大，依靠电力提灌，成本非常高。耕地由于受用水影响，农作物产量非常低，农业经济发展慢，当地人民生活水平低，每逢大旱年，致使河流断流，大量农作物干死，粮食颗粒无收。四乡镇的居民主要分布在河流分水岭地带、切割较深的台地上，无饮水水源保证和存在饮水水质安全隐患，急需新建灌溉引水水源。输配水管网是山区农村饮水安全工程中供水系统的重要组成部分，在整个供水[2]系统中管网部分的投资最高，一般要占到工程总投资的60%～80%。供水管网的优化布置能减少埋管工程的总投资，也能缩短输水距离、降低输水能耗和减少输水成本。然而，山区供水工程设计中管网布置一直根据经验确定，缺乏科学的理论与方法。供水管网优化布置的首要工作就是求出控制点间的最短曲线线程，即该曲面地形的测地线。由于山区地形复杂而难以用数学函数来表征，导致测地线方程不能得到解析解，管网优化便陷入困境。因此，复杂地形条件下的最短线路问题一直没有得到很好的解决。另外，山区供水管网工程一般布置成树状结构，然而，最小树方法虽然能对平面管网进行最优化处理，但在山区极其复杂的情况下，需考虑过陡的山头或悬崖等地形构造特征，平面最小树方法不再适合这种复杂地形的管网优化布置。本课题将以贵州省毕节市纳雍县灌溉区管网布置为研究对象，采用离散化地形表征技术，生成山区复杂地形条件下的两点最短线程模型，开发复杂地形中的最小树形图生成方法，构建管网优化的Steiner最小树形图模型，以解决复杂地形的部分1万方数据 三峡大学全日制专业学位硕士学位论文输配水节点已确定需增设节点的管线优化问题，完成整个管网布置工程设计工作。本课题为典型山区供水管网浅埋管优化布置提供理论技术依据，有重要的工程意义和科学价值。1.2国内外研究现状管网优化发展至今，已经成为一个比较成熟的理论。各种优化设计理论方法层出不穷。国外从60年代就开始研究线性规划、非线性规划、动态规划等管网优化设[3]计的方法，在这一领域取得了一些成果。随着计算机技术的进步，我国从20世纪80年代开始研究供水管网的系统优化设计问题，供水管网优化研究得到进一步的发展。管网优化的主要内容分为管径优化、工作方式优化和管网布置优化三方面。本文主要研究管网布置的优化方法。布置优化是管网优化的重要内容，对减少运行费和节省管网投资具有十分重要的作用。但由于管网优化布置需要综合考虑地形、作物种植等多方面因素，同时还需要借助设计人员经验，难度大，为此需要从数字地面模型、最短路径以及最小树等方面进行研究。1.2.1数字地面模型研究现状数字地面模型的概念是在1958年由美国麻省里工学院的Milier教授提出，并成[4]功地运用到公路的勘测设计中。在近60年的发展中，DTMs的理论和应用不断地得到发展与完善。特别是在现今的信息社会中，DTMs对社会各行业如城市规划、农业、水利等的重要性日益明显，同时DTMs也是数字地球海量数据库的主要组成部分，是数字地球的数学基础，是三维虚拟现实的基本框架。数字地面模型属于计算机图形学的一个分支，是以数字的形式按一定的结构组织在一起、从离散数据结构出发构造相互连接的网络结构，表示实际地形特征的空间分布，从而建立起相关区域内平面坐标与高程间的映射关系。它是对地形表面在地形采样数据基础上的表[5]面重构。如果采样数据为高程，则为数字高程模型(DigitalElevationModle，DEM)。在数字地面模型的研究早期，由于不规则三角网数据结构复杂，计算机自动生成算法不成熟，数字地面模型多采用规则格网。近年来经过众多学者的不断研究，不规则三角网逐渐成熟，尤其是顾及地物限制的边界一致的三角网格理论和算法有所突破，加上计算机软硬件对三角片的显示支持，三角网数字地面模型的显示速度得到大幅度提高。不规则三角网格模型正在成为数字地面模型的主流。在目前所有的三角化算法中，由于Delaunay三角网具有空外接圆和最小角最大性质，决定了Delaunay三角网具有极大的应用价值，它形成的三角形具有整体最优特性，因而成2万方数据 三峡大学全日制专业学位硕士学位论文为一种最流行的三角剖分方法。作为数字高程模型（DEM）的一种主要表达方式，Delaunay三角剖分的概念最初是由俄国数学家Delaunay为了解决离散数据的剖分问题，在二十世纪四十年代提出来的，并提出了相应三角剖分算法。但是三角剖分技术的快速发展和广泛应用是在80年代以后，伴随着计算机技术的迅猛发展，大规模计算和图像显示问题得到了有效的解决，同时来自计算机图像学技术的需求，三角剖分技术在最近几十年里有了长足的发展，并且被广泛的应用到社会的多个领域。三角剖分问题的实质就是要研究平面上离散数据点之间的相互邻接关系，并且将这种邻接关系以三角网的形式表现出来，所以三角剖分方法按照邻接关系的标准不同，可以被分为许多不同的三角剖分方法。在所有邻接关系表示标准中，Voronio图的标准是应用最为广泛的，Voronio图的对偶图就是一个Delaunay三角网。以Voronio图的相关理论作为理论基础，最初是R.Sibson与P.J.Green等人给出了很多三角剖分算法的纯数学理论研究[6]，这些研究使得三角剖分理论更加的严密。之后又经过A.Bowyer和D.F.Waston提[7]-[8]出了一系列不同三角剖分算法，使得三角剖分领域的研究有了突破性的进展。之后，由于三角剖分在越来越多领域得到广泛的应用，又有更多的三角剖分算法相继被提了出来，这些算法的主要研究重点是在实际应用中如何提高三角剖分算法的效率问题，已经如何解决三维空间复杂实体的三角剖分问题。这期间，很多比较经典的算法被提了出来，如局部变换法，单元生长法，四叉树或者八叉树法等，这些三角剖分算法各有各的优缺点，在实际应用中的话也如果仅仅使用同一个优化标准的话也不能满足不同需求，因此各个领域的研究人员根据各自领域的需求围绕原有算法中存在的一些问题提出了大量的改进算法，以满足特点领域的实际应用问题。[9]宁慧根据DEM数据及视觉中心相关地形简化的特点，提出了一种基于网络划分的实时简化算法。该方法首先将DEM栅格数据分成以视点为中心的数据块，利用视觉相关的误差简化算法实现了DEM数据的快速动态分层与地形平滑，其次利用三角形剖分方法最终消除了裂缝，对实际数据的实验结果验证了算法的有效性。KennethP.[10]Bowman就球面上求解Helmhohz方程的问题提出了一个多重网格有限差分法。该解算方法适用于球面上的一般椭圆型方程，对不宜做均匀网格距求解的一些问题也[11]是有用的。但离散误差较大。刘堃结合等值线的特性介绍了基于规则网格的等值[12]线生成算法，为规则网格的优化提供依据。高艳等选取项目区内的115个离散样本数据，通过选用不同的内插方法以及改变规则网格的大小对DEM精度进行分析，[13]并确定所选用的规则网格大小。半规则网格在视差估计上也有较广泛的应用。但3万方数据 三峡大学全日制专业学位硕士学位论文规则网格不能准确表示地形的结构和细部，需要采用附加地形特征数据,如地形特征点、山脊线、谷底线、断裂线等，以描述地形结构。其另一个缺点是数据量过大，要进行压缩存储，给数据管理带来了不便。等高线模型的应用也较为广泛，它被广泛应用在各种地图和地理信息系统中，是二维手段表示三维物体的常用方法，可以直接利用Delaunay三角形对等高线上的点进行三维地形造型。但由于等高线自身的特点使得到的地表模型具有明显的等高线的台阶痕迹，所以通常不直接采用该方法构造地表模型，而是将等高线数据转换为网格数据，即数字高程模型(DigitalElevationModel,DEM)。不规则三角网模型（即TIN）能够根据地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置,因而它能够避免地形平坦时的数据冗余,又能按地形特征点如山脊线、山谷线、地形变化线等表示数字高程特征，是一种比较理想[14]的地表模型。刘学军等指出，与Grid结构相比，TIN能以更加灵活的方式在不同层次和空间上表达更复杂的地形表面，当地形数据中含有特征线如山脊线、山谷线、[15]断裂线等时，TIN比Grid更能方便地表示之。陈甜甜等针对逆向工程中的三角网格重构问题，提出了一种保持尖锐特征的版规则三角网格模型细分曲面重构算法，[16]充分利用了细分曲面的多分辨特性。在三角网格的优化方面，蒲浩运用数字地面模型，在生成初始三角形后，采用队列及平衡二叉树等数据结构进行三角网的扩展，通过点集分块改进点的搜索方法，减少了搜索时间，并用LOP算法优化网形。这种算法生成的带状数字地面模型已成功地应用于铁路和公路的勘测设计中。本文选取Delaunay不规则三角网模型对山区地面进行离散化表达，为管网优化提供精确地地形要素。1.2.2最短路径问题研究现状在保证供水质量的前提下，管网优化的关键在于寻求一条最短供水管线线路，也就是传统的最短路径问题。最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。1959年Dijkstra对最短路径提出有效算法以来，为提高算法效率，许多研究者由基本问题提出许多子问题。图论与计算机数据结构及算法的有效结合，产生了众多新算法。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。[17]早期的最短路径算法是根据Bellman原理，将最短子路径相加求节点对间的最短路径。标号算法作为研究最为成熟、应用最为广泛的最短路径算法集，其本质是应用Bellman原理求解，它采用顺推的方法，对图的每一边检测一次，没有重复4万方数据 三峡大学全日制专业学位硕士学位论文的回溯搜索，因此标号法是一种最佳算法。目前，绝大多数最短路径算法都是在标号算法基础上，通过采用不同的数据结构、节点选取策略以及生成树更新技术而开发出不同实现形式。根据从集合中选取当前扫描节点的不同，搜索策略分为广度优先搜索、深度优先搜索和启发式搜索3种。广度优先和深度优先搜索不考虑路段的权重，在地理网络路径搜索中意义不大，但在社会关系网络研究中应用广泛；而启发式搜索策略考虑路段权重，它能减少搜索空间，在地理网络路径分析中应用很广。[18][19]李帮义、姚恩瑜提出利用遗传算法求最短路径，可得到问题的满意解；周培德在《计算几何》中对平面中最短路径问题进行了讨论，将其归为“计算几何中运动规划的基本问题”。平面内带障碍物的最短路描述为:给定平面内两点s0和t0及多边形障碍物集合n:{w1，w2，⋯，wk}，求从s0到t0的避开所有多边形障碍物的最短路径。目前在GIS应用领域，对最短路径搜索问题的研究和应用较多，其中最短路径搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题。所采用的算法主要是来源于图论领域中的称为Dijkstra的算法，该算法运行的结果是某一顶点到其它[20]所有顶点的最短路径。刘敏根据Dijkstra算法的基本思想，选择合适的数据结构[21]表示图，实现求解最短路径的Dijkstra算法。鲍培明通过Dijkstra算法在动态权值系统中的应用体现Dijkstra算法在城市交通信息系统中重要性。传统Dijkstra算法在通用性和完备性的意义上无疑是非常优秀的，但基于GIS空间分布特征和GIS中最短路径查找的具体情况，其在算法本身的改进及效率的进[22]一步提高是完全有必要的。李赉年在Dijkstra算法的基础上，通过减少加法与比[23][24]较运算次数来提高计算效率；KubyM和ErkutE在Dijkstra算法的基础上通过极大极小法提出了相异路径求解方法，解决了最短路径的P扩散问题；Ahmed和[25]Mustaq设计一种连续Dijkstra算法，来计算实际地面上两点间的最短下坡距离[26](shortestdescendingpath，SDP)；JozefowiezN研究了航空线路在意外事件发生后[27]的重规划问题，在航空公司费用和乘客满意度之间达到最优平衡；FaramrozeG[28]开发了一种新的动态规划方法来解决固定费用的最短路径问题；Lozano等构建配[29]套约束的最短路径模型，用以解决机组调度和乘务员排班问题；张水舰等分析了网络弧和节点的动态随机特性及其相互关系，定义了动态随机最短路径，给出了动[30]态随机最短路径优化数学模型，提出了一种动态随机最短路径遗传算法。花玲玲结合GIS公路交通的空间分布特征和查找最短路径的具体情况，分析了传统最短路径算法在这种特定应用中的不足和改进的思路，编程实现了一个充分利用了GIS中空间分布特征的改进算法。5万方数据 三峡大学全日制专业学位硕士学位论文1.2.3最小树问题研究现状最小树问题，是一个熟知的有着广泛应用意义的图论问题。在交通、通讯、管道、渠道等系统中，许多最优连接问题都归结为求一个无向连通图的最小支撑树，[31][32]目前已有许多算法。Kruskal算法就是利用MST性质构造最小生成树的算法。[33]杨小影针对Kruskal算法思想及其在网络技术中的应用，对该算法进行分析并改[21]进，并给出该算法的VB实现。王伟等对Kruskal算法进行研究，降低了该算法的时间复杂度，在理论上，介绍了该算法的求解时间。PrimeDijkstra算法是求最短[34][35]路径的最基本和使用最广泛的算法。章永龙、王志和等分别对节点邻居进行处理和采用配对堆结构实现对该算法的优化处理。虽然这两种方法计算所得的结果均比较接近最优解，但它们仅仅适用于平面上最小树优化。而实际情况往往需要求出多个最小树，以便进一步考虑其它优劣指标和约束条件，从中选出既优越又便于实施的方案来。多种最优方案的再选择在实际应用上的重要性，促使我们从数学上提出求全部最小树问题。与此有关的求全部支撑树间题，在电路分析方面极受重视，[36]曾出现过一系列重要的工作。特别是oummins提出树图的概念，并证明了树图的[37]Hamilton性。随后Kamae又给出树图和性的构造性证明，并提供求全部支撑树的[38][39]深探型算法(不同于Mayeda—seshu的广探型算法)。不久后shank给出了树图[40]H-性的一个极短的证明。至于如何求全部最小树，迄今未见文献中讨论。林诒勋仿照树图的定义，证明最小树图的Hamilton性，建立求全部最小树的算法，并得到[41]最小树图的Hamilton圈。权矩阵法是通过权矩阵计算来实现Dijkstra算法的一种方法，该算法在复杂度上比Dijkstra算法更高一些，特别是在大型网络中求最小树[42]时有太多的冗余运算。孙小军针对权矩阵法在大型网络应用中的不足，在提高算法效率方面对其进行改进，降低了其计算复杂度。破圈法是一种相对简单的计算最小树的方法，该方法对于数学知识不多的实际工作者来说，更容易接受，同时计算[43][44]复杂度也较低。但此方法仅限于图纸上工程的计算。蚂蚁算法对于一些度限制极其苛刻且网络图呈稀疏状态的问题方面表现出了相当好的性能，它能克服其它一[45]些方法甚至找不出可行解来的弊病。模拟退火算法是基于蒙特卡罗迭代方法的一种随机搜索算法。它用于求解组合优化问题的出发点是基于物理学中晶体物质的退火过程与一般组合优化问题之间的相似性。该方法在某些参数设定下速度较快，但[46]得到的解并不一定是最优解。在最小树问题的研究中，最经典的还是steiner最小树问题。steiner最小树问题是经典的组合问题，最早可以溯源到17世纪初。以瑞士数学家steiner的名字命名。6万方数据 三峡大学全日制专业学位硕士学位论文经典Steiner树问题大体包括欧氏的、绝对值距离的、图的等几个重要方面。欧氏Steiner最小树是指对给定欧氏平面上的原点集P(也称正则点集)，找出连接P的最[47]短网络。严蔚敏在数据结构一书中给出了有关欧氏Steine最小树的理论。金慧敏[46]分别采用模拟退火法和蚂蚁算法对欧氏Steiner最小树问题作了智能性优化，并通过实验得出两种优化方法都有各自的优点（模拟退火法的速度较快，蚂蚁算法的结[48]果更接近于最优解）。绝对值距离的Steiner最小树问题由Hanan首次提出，1977年，Garey，Graham以及Johnson等人证明了欧氏的和绝对值的Steiner最小树问题[49][50]属于NP难题。因此，GareyM用求点集P的最小生成树来代替求取近似解。图的Steiner树(GraphicalSteinerMinimumTree，简记GSMT)问题由Hakimi和Levin[51]于1971年首次提出。GSMT问题亦为NP难题，无法在多项式时间内得到最优[52][53]解。图的Steiner树问题的精确算法如Hakimi的时间的算法，它枚举所有可能的Steiner点并计算相应的树长。Hakimi算法适于|P|接近于|V|的情况，而动态规划算法则适用于|P|较小时的情形。1.3研究内容、技术路线及创新点1.3.1研究内容本课题研究内容主要分为以下几部分：第一章，绪论。主要介绍本课题研究的背景和意义，国内外关于数字地面模型、最短路径及最小树问题的研究现状以及其研究内容、研究方法、技术路线等。第二章，山区供水管网优化布置方法。从山区管网优化布置的角度，分析山区复杂地形离散化、最短路径以及管网布置最小树等的求解方法，为供水管网优化布置提供理论依据。第三章，供水工程复杂地形离散化表达。主要利用施工测量的地形点坐标，构建三角网来拟合复杂的地表曲面，克服复杂地形无表征函数和不可展开性而使最短路径无法获得解析解的问题，实现复杂地形的格网显示，为最短路径的数值解法建立基础模型。第四章，三角网显示下点对间最短线程计算。为计算格网显示的地面两点间的近似最短线路，将网格模型转化成边权有向网络，计算带权网络上两点间的最短线路，并迭代细分最短线路邻域内的边以构造新的带权网络求解。在细分顶点的基础上，对邻域进行扩展以提高最短线路邻域内的边的细分效率。第五章，管网布置的最小树形图生成与优化。给定空间的配水点的点集，要求在关于拓扑网络边的约束条件下选择边的子集形成使管网极小化的网络，即复杂地7万方数据 三峡大学全日制专业学位硕士学位论文形中的最小树问题。本课题结合山区地形因素，通过引入最小入弧圈概念，来构建山区地形中带约束的最小树生成方法。由于某些地形(悬崖峭壁)不适合进行管网布置，即在其他适合管网布置的地形处增加某些被称为Steiner点的附加点，形成新的管网。这时可能舍弃适合地形不用而绕行会使总的管线更短。第六章，研究结论与展望。通过方法与模型的结合，得到典型山区供水管网布置的优化方法，阐述本文的创新点，并提出相关方面的更深层次值得探讨的问题。1.3.2技术路线本文将以贵州省毕节市纳雍县灌溉区管网布置为研究对象，利用施工测量的地形点坐标，采用离散化地形表征技术，构建三角网来拟合复杂的地表曲面；将网格模型转化成边权网络，生成山区复杂地形条件下的两点最短线程模型；在给定供水端点的条件下求解复杂地形中的最小树形图，构建管网优化的Steiner最小树形图模型，以解决复杂地形的部分输配水节点的管线优化问题。技术路线如图1所示：典型山区供水管网离散优化布置研究工程概况分析地形离散化管网优化最短线程计算地形点数据处理确定管网布线方式采用边权无向网络求采用Delaunay三角网格划解最短线程选择布线已知点分方法对复杂地形进行离散化处理管网优化布置的最小树计算采用分离法计算带约束的管网最小树优化结果加入Steiner点，计算管网的Steiner最小树图1.1论文研究的技术路线1.3.3课题创新点创新点：1)构建山区复杂地形的格网显示模型，开发基于最短管线线程的三角网格划分方法。8万方数据 三峡大学全日制专业学位硕士学位论文2)将山区复杂地形离散化显示后，加入离散点间的距离权值，形成边权网络，求解最短管线线程，提出GIS数据与图论网络之间的转化方法。3)提出复杂地形条件下Steiner最小树的构建方法，解决Steiner树选点困难等问题。1.4论文研究方法⑴文献研究法。通过大量的文献检索，对以往的研究成果进行综述与回顾，从而对相关研究概念甲乙界定。根据研究的需要对现有的研究成果加以总结、归纳与整合，在此基础上提出本研究的框架。⑵模型建立法。主要运用数字地面模型对供水区域地形进行离散化表达；采用图论相关知识对管网布置的优化工作进行分析，结合图论中的最短路径方法，最终确定供水管网管线最短的优化方案，减少供水管网布置工程的用钢量，降低工程成本。⑶案例分析法。本文以贵州纳雍金蟾供水工程为实际工程案例，分析其地形地质条件，采用相适应的数字地面模型和图论优化方法，最终得到适合本工程的供水管网布置的优化方案。9万方数据 三峡大学全日制专业学位硕士学位论文2山区供水管网优化布置方法2.1Delaunay三角网格划分算法概述在计算机应用普遍的当下，数字地面模型的发展也日趋完善，在众多的数字地面模型类型中，离散点三角网数字地面模型是选线设计的最佳选择。这种数字地面模型以原始的地形点为顶点建立不规则的三角网，其建网过程是采用线性内插方法，这种方法具有内插精度高，内插简便，便于考虑地性线的影响等优点。这些优点使得在建模过程中不仅能减少规则建网造成的数据冗余，同时在计算复杂度方面又比基于等高线的建网方法有优势，尤其是在地形坡度较为复杂的情况下。因此，不规则三角网模型是GIS中非常重要的一种用于空间计算的数据模型。目前三角网格优化算法已经很多，且发展日趋成熟。随着技术发展的纯熟，老算法将不断地得到完善，同时也会出现更好的新的算法。所以对所有算法进行分类是不容易的，一般而言，地形数据通常呈规则分布、不规则分布以及等高线数据三种类型，对于不规则地形点数据，Delaunay三角网格划分方法无疑是最合适的选择。2.1.1Delaunay三角网格划分定义Delaunay三角划分是一种特殊的三角划分，它是在一般三角划分的基础上增加对Delaunay边的定义，以此定义Delaunay三角网。1）三角网格划分：假设V是实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段,E为边e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：⑴除了端点，平面图中的边不包含点集中的任何点；⑵没有相交边；⑶平面图中所有的面都是三角面，且所有三角面的合集就是点集V的凸包。2）Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足存在一个圆经过a,b两点，圆内不含点集V中任何的点，这一特性又称空圆特性，则称之为Delaunay边。3）Delaunay三角划分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角划分。由于Delaunay三角网格划分具有最大角最小化和空圆特性等优点，在数字地面模型中应用普遍。10万方数据 三峡大学全日制专业学位硕士学位论文2.1.2Delaunay三角网格划分方法通常情况下，我们将Delaunay的各种算法分为三类：分割—归并算法、逐点插入法以及三角网生长法。[54]1)分割—归并算法该算法是由Lee和Schachter提出的，它的基本思想就是“分离—合并”，即将数据点集划分成两个相互独立的子集，各自生成Delaunay三[55]角网后再合并。考虑到可能有约束条件，Lawson尝试把初始点集划分成小区域的竖条，这些竖条均垂直于X轴，同时问题的约束条件又将其划分为更小的区域，再各自生成Delaunay三角网，最后根据约束条件合并。[56]徐青等提出了基于自适应分块的TIN三角网划分方法，这种算法与Lawson算法的不同在于如何划分源数据上。其优点是能够运用于地形的表达上，山区地形一般较复杂，源数据点的分布也极不均匀。通常情况下，平原等相对平坦的地区点击分布较稀疏，而山地、沟谷等地的点集分布比较密集，若按照Lawson的思想划分成同样的大小的子集，则根据点的密集度计算时间相差就会非常大。TIN三角网格划分方法就是根据实际地形，动态设置子集的大小，灵活变化子集的阈值，控制子集点数的下限值。2)逐点插入法逐点插入法的基本步骤是首先构建一个初始三角网，把不在初始三角网内的数据点根据要求插入到初始三角网内，直到所有点都入网即结束，然后再运用LOP算法优化三角网。LOP算法其实就是一个对角线交换的过程，即对三角网中共边的两个三角形作空外接圆检测，若不满足空外接圆法则，则交换四边形内公共边形成的对角线形成两个新的三角形，新形成的两个三角形一定满足空外接圆准则，如图2.1所示:图2.1LOP优化[57]3)三角网生长法该算法是由Brassel和Reif于1979年提出的。三角网生长算法的的基本思路是首先在点集中距离最短的两点，相互连结形成Delaunay边，然后根据Delaunay边三角网的判别法则寻找包含此边的Delaunay三角形的第三个顶点，对新生成的边再次判别寻找下一个点，直至所有点入网。三角网生长法的实现方法有很多，这些方法的主要不同都是如何寻找第三点。11万方数据 三峡大学全日制专业学位硕士学位论文[58]McCullagh和Ross通过把点进行排序和点集分块，以此改进点搜索方法，减少了[59]搜索时间。凌海滨等对三角网增长算法作出改进，他们提出了封闭点（如图3.2）的概念，即在三角网的生成过程中将封闭点动态地剔除，减少需查找的点集的数量，从而加快三角形生成的速度。P图2.2封闭点P2.1.3基于最短路径的三角网格划分空间数据点的三角划分算法是数字地面模型建立的核心。在管线布置过程中，三角划分算法应能满足线路设计对它的要求，即对地形域数据点适应能力强、占用系统资源少、运行效率高、三角形结构良好等特点。综合分析以上三种算法，本文采用了逐点插入算法。2.1.4算法步骤zkq20150910逐点插入算法的基本步骤可归纳为:1）建立初始三角网：如图2.3所示，求出给定点集的包容盒，将包容盒沿对角线剖分为两个初始三角形，然后按以下步骤迭代，直到所有的数据点入网。（Xmax，Ymin）A1A2（Xmin，Ymin）（Xmin，Ymax）图2.3点集的包容盒2)定位三角形：从点集中取出一点，在已建立的三角网中找到包含该点的三角形，如图2.4(a)。12万方数据 三峡大学全日制专业学位硕士学位论文图2.4逐点插入过程3)确定影响域：从包含该点的三角形开始，根据空外接圆法则，找出外接圆内包含当前插入点的三角形集，三角形集的外边界即为影响域，如图2.4。空外接圆检测方法根据公式2.1计算:图2.5空外接圆特性测试aaaa1xyxybzkqxby20150910bxby1InCircledabc(,,,)（2.1）cccc1xyxydddd1xyxy当计算结果小于0，则表示d点在∆abc外接圆的内测；等于0时，在外接圆上；大于0时，在外接圆外侧。4)影响域内的三角网重构：将影响域内的三角形删除，对影响域内的点集进行三角网重构。重构方法是将以插入点作为公共顶点，将影响域的各边界点与当前插入点顺次连接(如图2.4(c))，得到的三角网即为D-三角网。5)当所有点插入完毕，删除边界上的冗余三角形，完成地形离散化。2.2最短路径概念与算法2.2.1最短路径相关概念1)路径路径是指在一个图GNM(,)中存在从节点V到节点V的点边交替出现序列0n(,,,,,,veveve,,ve)中，如果其中每条边只出现一次，则称之为简单路径，如011223nn1果同一个节点只出现一次，则称其为基本路径。赋权图的任意两点间的最短距离可用一个矩阵表示。设n阶有向或无向连通赋权图GVE(,)，其中顶点集，边集。设两13万方数据 三峡大学全日制专业学位硕士学位论文顶点，间的最短距离为，其中则图G的最短距离矩阵的元素定义为=。2)最短路径最短路径问题是图论中的一个常用的问题，目的是寻找连通图中两节点之间的最短路径。其具体的形式包括：①起点最短路径问题：起始节点是已知的，求最短路径的问题。②终点最短路径问题：与问题①相反，即终止节点已知，求最短路径的问题。③起点终点最短路径问题：已知起点和终点，求两结点之间的最短路径。④全局最短路径问题：求图中所有存在的最短路径。3)网络一个具体的网络可以抽象为一个由节点集和边集组成的图GVE(,)。NV为节点数，ME为边数，集合E中的每一条边都与集合V中的一每一对节点都是一一对应的。由于网络中边的有向性，网络又可分为有向网络（directednetwork）和无向网络（undirectednetwork）。有向网络指的是任意节点对(,)ij和(,)ji对应边是不同的，而无向网络的节点对(,)ij和(,)ji表示相同的边。如果对无向网络的每条边赋予一个权值，那么网络就变zkq20150910成了无向有权网络。如图2.6就是个无向有权网络。图2.6无向有权网络4)邻接矩阵与关联矩阵⑴图的邻接矩阵：设图GVE(,)是一个有向图，其中V包含n个节点，如果各个节点之间存在从到的边，其中1iN并且1jN,ij。则这个图可以用一个NN*的矩阵来表示，如图2.6所示的图，其邻接矩阵可表示为公式2.2。(2.2)由图可知，邻接矩阵是一个主对角线上元素均为0，其余元素为0或1的对称矩阵。14万方数据 三峡大学全日制专业学位硕士学位论文⑵关联矩阵：设图GVE(,)中V=，。令则由元素构成的矩阵为图G的关联矩阵。则图2.6所示的图的关联矩阵为(2.3)图的完全关联矩阵表述的是全部顶点和边的关联关系，这是一个图最基本的关系。2.2.2最短路径计算方法用于解决最短路径问题的算法被称做“最短路径算法”，最常用的路径算法有：A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Dijkstra算法等。A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，在空间最短路径中，该算法是一种最好优先的算法，但准确性较差；Bellman-ford算法主要是用于求解图中含负权的单源最短路径的计算，它的代码编写容易，但计算效率较低，有时会出现循环计算无法终止的情况，无法得出计算结果；SPFA（队列优化）算法和Bellman-ford算法一样，也是求单源最短路径的一种算法，但它在Bellman-ford算法的基础上增加一个队列优化，减少多余的循环操作，提高了计算效率；Floyd-Warshall算法可以求解任意两点间的最短路径。适用于有向图、带负权边的图等任何图，该算法通过研究子路径来得到最短路径，在计算过程中需要用邻接矩阵来储存边，因zkq20150910此对计算机的存储空间要求较高；综合考虑各种方法的优缺点以及适用性，本文选用Dijkstra算法计算供水管线已知点间最短线程。Dijkstra算法是一种经典的单源最短路径算法，主要用于计算一个节点到其他所有节点的最短路径。该算法是目前许多工程中解决最短路径问题的主要方法，但是在实际应用是需要对算法进行改进。Dijkstra算法思想为：设G=(V，E)是一个无向赋权图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个起点，以后每求得一条最短路径，就将新的节点加入到集合S中，直到全部顶点都加入到集合S中），另一组为暂时未确定最短路径的顶点集合（用U表示），按递归算法依次将第二组的顶点加入集合S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度是从源点v到U中任何顶点长度的最小值。2.3最小生成树基本概念与算法2.3.1最小生成树基本概念1）树（tree）我们称一个有k个连通分支且无圈的图为k—树或森林，特别当k等于1时，15万方数据 三峡大学全日制专业学位硕士学位论文1-树又简称为树，因此树是一个无圈连通图。2）生成树（spanningtree）如果一个图的支撑子图是一棵树，则称这棵树为该图的支撑树，也就是生成树（spanningtree），并称生成树中的弧为树弧（treearc）而不属于支撑树中的弧为非树弧（nontreearc）。3）最小生成树（minimunspanningtree，MST）若G(,,NEW)为一个无向网络，W为权函数，即W：E→R（R表示实数集合）。一般将弧e(,)ij上的权记为We()。G中权最小（大）的弧称为最小（大）弧。如果H=（N1，E1）为G的一个子图，子图H的权定义为H所包含的所有弧的权之和，*记为W(H)，即W（H）=We()，如果T是G的一棵生成树，且对G的任何生E1**成树T，有W（T）WT()，则称T为网络G的最小支撑树或最小生成树（minimunspanningtree，MST），简称最小树。2.3.2最小生成树算法（1）Kruskal算法zkq20150910Kruskal于1956年提出了Kruskal算法，其主要思想是将每一条权最小的弧加入子图T中，保留其中使之不成为圈的弧，当子图T中弧的条数为n-1时，就得到了最小树。Kruskal算法的运行时间主要由两部分组成：①对m条弧进行排序，其复杂度为O(m)＝O(m)；②当加入一条弧时判断是否形成圈，其复杂度依赖于算法的实现方法。在计算过程中，T是一个森林，若用单向链表表示森林中的每棵子树，则可以方便地判断是否形成圈。一般情况下，开始有n个单向链表，每个链表对应于一个节点。当弧(,)ij的端点属于同一单向链表，则(,)ij加入T后就会形成圈；反之则不会，因此将这两个链表合并成一个链表。因为处理每一条弧所需要的时间为O(n)，因此该方法的计算复杂度为O(nm)。（2）Prim算法该算法于1957年由Prim提出。其实现的基本思想是从网络G(,,NEW)中的任何一个节点开始，将子树T(,SE)不断扩展，直到所有节点进入集合S中，从而得到0最小树T。由此可见，Prim算法也是一种贪婪算法，即加入T中的弧不再从T中退出。与与Kruskal算法相比，它的不同之处在于算法过程中，Prim算法只保持一棵子树T，而Kruskal算法则保持的多棵子树。16万方数据 三峡大学全日制专业学位硕士学位论文在Prim算法中，有一种特殊的算法，称之为Dijkstra算法，其基本思想就是对每个节点标号（包括距离标号和前驱标号），不断加入最小距离标号，同时更新前驱标号，当所有节点被加入即停止。在Dijkstra算法中，由于每更新一次需要对后续点进行比较，因此该算法的计算2复杂度为On()。（3）Sollin算法该算法是由Sollin于1961年提出的，它其实是Prim算法和Kruskal算法综合而成的。该算法的主要工作量在于寻找最小弧并将其加入和子树的循环交替迭代过程，每次迭代时子树都会长大成为一棵较大的子树，因此循环迭代的总次数为On(log)。综上所述，用于求解最小树主要的方法就是Kruskal算法和Prim算法，由于这两种方法考虑的角度不同，所以适应的问题类型也不同。文在求解中涉及到的是完全图，顶点较多，所以在解决过程中用到了克鲁斯克尔（Kruskal）算法。2.3.3Steiner最小树基本概念Steiner最小树是总目标最小的树，在线路设计中，它的求解思路是通过增加一些“虚设点”，使得设计目标在原基础上进一步优化，而这些“虚设点“称之为Steiner点，生成的最小树即为Steiner最小树。zkq20150910在实际应用中，Steiner树分为欧式距离、绝对值距离以及图的Steiner最小树三种类型。设，为空间P中任意两点，则间的距离可表示为：（2.4）根据d取值的不同，可分为两种情况：即当d=1时，结点间的距离为欧氏距离，此时的问题称为欧氏Steiner最小树(EuclideanSteinerMinimumTree)ESMT)问题；而当d=2时，结点间的距离为绝对值距离，此时称为绝对值距离Steiner最小树(RectilinearSteinerMinimumTree)RSMT)问题。图的Steiner树(GraphicalSteinerMinimumTree,简记GSMT)问题由Hakimi和Levin于1971年首次提出，之后被很好地运用于网络设计中。本文将以图的Steiner树为优化计算工具，对管网进一步优化。2.3.4Steiner最小树算法常见解法在众多求解Steiner最小树问题的算法中，比较常用的有梅尔扎克（Melzak）算法、递增优化算法、插入算法、遗传算法、模拟退火算法禁忌搜索法、人工智能神经网络、蚂蚁算法、微粒群算法等。其中梅尔扎克（Melzak）算法是精确算法。对于已有的精确算法，计算量随着给定点的增多呈指数增长，目前还没有有效的措施降低其计算量。插入算法、递增优化算法等属于启发式算法，而启发式算法常常容17万方数据 三峡大学全日制专业学位硕士学位论文易得到很坏的答案或效率极低，该算法是面向具体问题且不具有通用性。模拟退火算法、遗传算法、蚂蚁算法等属于智能优化算法。近些年来，智能优化算法以其独适用性好、易修改的优点，在最小steiner生成树问题中得到了广泛的应用。模拟退火算法虽发展成熟，但其对图的初始状态要求较高，蚂蚁算法在理论和应用上还处于发展阶段，有待进一步完善。遗传算法以模拟生物进化过程为基本原理，是适用于几乎所有最优化搜索问题的方法。同时由于遗传算法具有既不依赖于问题的具体领域，又对问题的种类没有严格要求的优点，因此本文采用遗传算法计算Steiner最小树。遗传算法的思路主要分成以下四步：第一步：初始化种群，得到初始种群，并计算适应度值，同时设置计算终止条件；第二步：对种群中的个体依次进行选择、交叉和变异操作；第三步：如果满足运算终止条件，则输出适应度值最优的个体，结束程序；如果不满足运算终止条件，则返回到第二步。第四步：输出各Steiner点坐标，计算Steiner最小树。2.4本章小结本章主要从山区管网优化的角度，分析山区复杂地形离散化、最短路径以及管网布置最小树等的求解方法。根据山区地形管网优化的特点，选择适用于复杂地形管网布置的优化方法，改进传统的计算将最短路径的Dijkstra算法，得到便于求解已知点对间最短线程的方法，为供水管网优化布置提供理论依据。18万方数据 三峡大学全日制专业学位硕士学位论文3供水工程复杂地形离散化表达3.1工程概况纳雍位于贵州西北部，毕节地区东南部、乌蒙山系东南麓，东南与织金、六枝，西南与水城，西北与毕节、赫章，东北与大方相连。地势总体为西高东低、南高北低，由西南向东北缓缓倾斜，山地海拔高程一般为1500～2200m，地势起伏大，地形破碎崎岖。金蟾水库灌溉工程的主要任务是向纳雍县羊场乡、姑开乡、锅圈岩乡和维新镇提供灌溉和人畜饮水。灌区涉及纳雍县下属的羊场乡、姑开乡、锅圈岩乡和维新镇等四个乡镇，包括36个村寨，分别为羊场乡12个村寨，姑开乡12个村寨，锅圈岩乡6个村寨和维新镇6个村寨，工程建成后可保证四个乡镇灌溉耕地7.2万亩，5.1万人和1.5万头大小牲口的饮水。灌区耕地主要分布在山间台地、坡地，高程为1250~1700m，主要表现为旁山梯田、梯土，在田坝间有连续的耕地分布。金蟾水库高程为1744m~1778m，灌区大部分处于自流灌溉范围。图3.1纳雍县灌区规划图3.1.1灌区供水及地质分析1）灌区农产业结构19万方数据 三峡大学全日制专业学位硕士学位论文灌区范围内1400～1900m主要是硅铝质黄壤及铁铝质黄壤，旱地以黄泥土为主，水稻类多为淹育型及潴育型亚类；低洼河谷地区1050m～1400m主要分布着黄壤类和石灰土类，旱地多为黄泥土及大土泥土等，水田多为潴育型亚类中的黄泥属，大眼泥属及潮泥属水稻土。灌区主要位于三岔河和六冲河干流的切割台地上，由于缺乏灌溉水源，农业以玉米、薯类、油菜为主，少量水稻。粮食作物占的比重较大，经济作物和其它作物所占比重较低，2007年亩产量约260kg/亩，大于全省的250kg/亩。2）灌区范围根据调查，灌区为纳雍县下属的羊场乡、姑开乡、锅圈岩乡和维新镇四个乡镇。灌区包括36个村寨，分别为羊场乡12个村寨，姑开乡12个村寨，锅圈岩乡6个村寨和维新镇6个村寨。灌区耕地分布高程在1250m～1700m，灌区全为自流灌溉。本工程达到设计灌面后，涉及的四个乡镇的耕地灌溉率可达到52%。3）灌溉面积灌区涉及的四个乡镇2007年末国土面积358.3km²，总人口109442人（农业人口107226人，非农业人口2216人），耕地面积137872亩（其中田8638亩，旱地128234亩）。现状中耕地占总国土面积的26%，耕地多分布在1250～1750m高程，但由于地形限制，耕地较为分散。土壤以黄壤土为主，适宜农作物的耕植。金蟾水库建成后，天然来水通过调节，灌区水量得到很好的调配，灌区内的部分旱地可改为水田。从灌区农业发展和经济效益考虑，并充分尊重现状和服从规划的前提下，本次设计对灌区各种作物种植面积进行了合理调整，计算出2015年灌区耕地面积7.2万亩，其中水田1.1万亩，包括原有田5731亩、土变田5269亩，旱地6.1万亩。4）人畜需水量灌区管道涉及羊场乡、姑开乡、锅圈岩乡和维新镇四个乡镇，其中36个村作为人畜饮水供水范围，供水范围内无工业分布，故无工业用水。2015年灌区将承担5.1万人（其中农村人口4.6万人，城镇人口0.5万人），1.5万头牲畜饮水。本阶段对灌区人畜需水量进行复核，净总需水量181万m³/a，毛总需水量191万m³/a，其中生活需水量168.5万m³/a，牲畜需水量22.5万m³/a。5）灌溉需水量灌溉用水量根据工程的灌溉面积、田土比例及作物组成，采用相应作物相应年份的灌溉定额进行长系列计算。金蟾水库为多年调节，计算时段采用月。2015年灌区设计灌溉面积为7.2万亩（其中水田1.1亩，旱地6.1万亩），播种面积合计10359720万方数据 三峡大学全日制专业学位硕士学位论文亩。6）地质勘查根据地质详细勘查结果，灌溉区内无重大地质缺陷如活动断层、滑坡、泥石流等，对输水线路的选择不存在地质条件制约因素。3.1.2供水管线基本走向确定基于以上情况，管线线路走向大致分为总干管，北干管及其支管，东干管及其支管三大部分。其中，总干管从金蟾水库坝址起沿戈落坝小河左岸向东北方向走至小坪子，总干管沿线地形比较平缓，地面起伏较小，因此大部分采用浅埋布线，其中跨越周家湾、倒回龙、小坪子等冲沟，管道高程在1761～1745m之间。为满足东北灌区和东南灌区的用水需要，总干管在小坪子处分支为两个方向。北干管往法窝南、北灌区延伸后，分级引管至凹书南、北灌区。北干管及其支管不经过深切冲沟和陡峻高山，无重大地形地质制约因素，经本阶段现场踏勘，采用浅埋布线。东干管及其支管主要负责姑开、保猫寨、田家寨及维新镇的供水需求，东干管由总干管末端向东南方向至法猪寨，穿过梯子岩乡，在法猪寨分为支管向各灌区供水。其中，梯子岩乡海拔较高（高程在1820m～2025m范围），高山连绵起伏且有3条比较陡峭的峡谷，姑开支管东干管末端至姑开乡，法猪寨段地形高程在1720m～1850m之间，若沿等高线布线需多次跨越冲沟和峡谷，大型施工机械无法适应这种复杂地形。由于以上施工技术限制，东干管和姑开支管输水线路采用隧洞布线，尽量直线布置，以缩短线长。其它支管段地形平缓，采用浅埋布线。根据以上对山区地形和灌区结构的分析，选定供水管网布线的分水点和蓄水池等已知点情况如表3.1。21万方数据 三峡大学全日制专业学位硕士学位论文表3.1布线经过的已知点坐标编号所属范围控制点坐标（单位：m）备注A坝址（2986483,499983，1754.0）起点B小坪子（冲沟）（2987626,502022,1748.7）分水点C青岗林（2989209,504015,1723.5）分水点D法猪寨（2983654,507844,1750.3）分水点E羊场（2989133,504837,1683.7）分水点F凹书（2988005,507288,1674.5）分水点G保猫寨（2982277,511194,1747.8）分水点H保猫寨（2984255,512057,1673.1）蓄水池I法窝（2991730,504538,1658.4）蓄水池J凹书（2989670,506892,1623.6）蓄水池K姑开（2985774,508554,1615.1）蓄水池L田家寨（2981565,511841,1675.9）蓄水池M维新（2987667,512671,1649.3）蓄水池N法窝北（2995462,502250,1546.8）蓄水池O凹书南（2988602,507257,1583.8）蓄水池P保猫寨（2983856,512007,1786.2）分水点根据以上分析，供水管线大致走向如图3.2。22万方数据 三峡大学全日制专业学位硕士学位论文图3.2供水管线大致走向图23万方数据 三峡大学全日制专业学位硕士学位论文3.2纳雍供水工程地形格网化显示3.2.1数据预处理确定供水管线的基本走向后，采用常规勘测获得布线区域的地形点坐标，获得的地形点数据在建网前还需要预处理，本文根据工程需要，主要运用滤波和压缩两种方法。1)滤波在建网过程中，为防止错误的点或不符合要求的点参与构网，需设置点过滤器，即设置管线的高程合理范围。2)压缩制图过程得到的地形点一般很密集，若直接进行三角网离散化，则计算机所需的计算过程将会很长，因此必须压缩地形数据，降低计算量。本阶段以总干管Z1Z2段为例，总干管部分地区相对平坦，高程在1761m-1745m之间，设置管线高程合理范围为1761m-1745m，剔除超出范围的数据点；同时删除坐标相近点和非特征点，对地形数据进行压缩。3.2.2复杂地形表面三角网显示数据处理完成后，即开始建网工作，步骤如下：1)选择数据点集中的边界点，相邻点连接生成包容盒。图3.3离散点集包容盒3)将以上包容盒沿对角线划分为两个初始三角形。图3.4初始三角形24万方数据 三峡大学全日制专业学位硕士学位论文3)对于点集内不在三角形边界上的任意点，找到其所在的包容盒内三角形，分别连接该点与包容盒内三角形各定点，得到新的三角形划分；4)对于在三角形边界上的点，则需分别连接以该边界为共享边的两个三角形的第三个顶点；5)重复步骤3）、步骤4），直至所有点都成为三角形的顶点；6）剔除边界冗余三角形。3.2.3生成复杂地形网格图形将AutoCAD中的数据以TXT文本格式输出，再运行以上程序，即可得到以下Delaunay三角网图形。图3.5Delaunay三角网格（总干管Z1Z2段）3.3本章小结本章首先将工程测量得到的复杂地形点坐标进行预处理，采用数字地面模型原理对山区复杂地形进行离散化。经比较，本文选择了适用于线路设计的Delaunay三角网格划分方法，得到山区复杂地形的三角网格划分模型，解决山区复杂地形难以用数学函数表达而无法求得测地线的问题，为求解复杂地形点对间最短线程打下基础。25万方数据 三峡大学全日制专业学位硕士学位论文4三角网显示下管线最短线程计算三角网在图论中的概念相当于是一个连通图，本文的思路是将Delaunay三角网转化为连通图，计算连通图各边权值，以此计算最短线程。金蟾水库灌溉工程的主要任务是向纳雍县羊场乡、姑开乡、锅圈岩乡和维新镇提供灌溉和人畜饮水，羊场乡位于金蟾水库东北方向，含法窝和凹书灌区；姑开乡、锅圈岩乡和维新镇位于金蟾水库东南方向，含姑开、保猫寨、田家寨及维新灌区。输水线路从金蟾水库沿下游左岸延伸引出总干管后，向东北和东南方向布置分干管，然后经支管引至各灌区。设计时，应充分利用库区和灌区的地形高差，尽量实现自流灌溉，支管应贯穿主要灌面，以优化田间工程管材，减少下一级田间灌溉工程量。4.1建立边权网络Delaunay三角网形成后，将离散地形转化为图论中的边权网络模型，即首要工作是求出三角网的各边权值。因三角网内各三角形的顶点坐标已知，三角网内每条边的长度即可由公式4.1222SXYZ（4.1）其中，S为两坐标点的空间距离，X为两坐标点X坐标的差值，Y为两坐标点Y坐标的差值，Z为两坐标点Z坐标的差值，单位（m）。在AutoCAD技术中，运用Dist命令即可计算三角网各边权值，求出各边长度后，不规则三角网格模型即转化成无向边权网络模型。如图4.1所示：26万方数据 万方数据三峡大学全日制专业27学位硕士学位论文 三峡大学全日制专业学位硕士学位论文4.2计算最短线程4.2.1改进Dijkstra算法模型建立G(,)VE假设山区供水管线边权网络模型为。其中，V为边权网络模型的节点集合；E为相邻节点连接形成的边集集合。根据Dijkstra算法思想写出加权网络图的邻接矩阵，根据上述邻接矩阵利用标号原理得到的先驱（父）节点，追踪便可得到从起点到终点的最短线路。由于按上述过程要反复地对已标记的顶点进行计算和比较，编程较为麻烦，将上述过程加以改进，即在求解最短线程的过程中，不断修改未标记的距离标号，即可得到易于编程的算法步骤。设M为具有永久标号的顶点集，lv()0为起点距离标号，lv()为M内距离标号，lu()wuv(,)fv()为M外距离标号，为u，v两点间的距离权值，为v的父节点，用W((,))wuv以确定最短线路；输入加权图的带权邻接矩nnnn。Step1初始化，令lv()00Mvv0lv()（4.2）lv()fv()lu()Step2更新，，寻找不在M中的顶点u，使为最小，把u加入到M中，然后对所有不在M中的定点v，根据公式（4.5）：lv()00lv()min(()luwuv(,))（4.3）进行更新，即lv()min(()luwuv(,))fv()u，（4.4）Step3重复Step2，直到所有顶点都在M中为止。计算时按顺序输入边权网络的节点集合以及对应的权值集合，同时输入所需计算的最短线程的起始、终止节点，即得出最短线路边权值以及最短路径所经过的节点。根据以上步骤，采用MATLAB计算软件编程，详细程序如下：将三角网络各边标号以及权值输入，即可输出最短距离以及最短线路所对应的标号。以总干管Z1Z2段为例，采用Dijkstra算法，计算得出最短线路标号为1—3—6—10—12—18—30—37—46—52—58，对应到各坐标点，得到最短线路，如下图，总线路长度为249.9m。28万方数据 万方数据三峡大学全日制专业29学位硕士学位论文 三峡大学全日制专业学位硕士学位论文4.3.3最短线程结果显示根据以上方法求出各管线的最短线程，各管段间的最短线程如表4.1。表4.1最短线程表已知点对管段管长（单位：m）原管长（单位：m）缩短长度（单位：m）AB总干管2276.32586.0309.7BC北干管9086.73482.2695.5BD东干管12052.012052.0隧洞布线CI法窝南支管2335.42983.6648.2CE羊场支管1973.62544.7571.1EN法窝北支管5266.35973.2706.9EF凹书支管3192.73683.9491.2FO凹书南支管3154.53548.5394DK姑开支管3579.43579.4隧洞布线PH保猫北支管3094.23488.4394.2PG保猫南支管2383.62694.8311.2PL田家寨支管2185.32443.5258.2PM维新支管4429.64985.7556.1DP东干管支管3642.63642.6隧洞布线EI羊场-法窝南2984.3——IN法窝南-法窝北3146.5——NF法窝北-凹书6049.3——NJ法窝北-凹书北7294.6——FJ凹书-凹书北4876.2——OJ凹书南-凹书北5632.8——EO羊场-凹书南4516.3——CK青岗林-姑开15665.4——KO姑开-凹书南2658.3——KH姑开-保猫北2512.1——HG保猫北-保猫南2410.2——GM保猫南-维新4217.3——30万方数据 三峡大学全日制专业学位硕士学位论文4.4本章小结本章在山区地形的Delaunay三角网格划分基础上，运用AutoCAD中Dist命令计算出Delaunay三角网的各边权值，将复杂地形转化为赋权网络，运用最短路径原理，采用改进的Dijkstra算法计算管线已知点对间最短线程，求解出所有已知点对间的最短线程后，连接各点对并标出最短线程，即为连通图，为求解管网布置优化的最小树做准备。31万方数据 三峡大学全日制专业学位硕士学位论文5管网最小树形图的生成与优化在计算出各已知点间最短线程后，管线与已知点相连即生成连通图，同时各管线的铺设线程已在上一章给出，管网连通图即为赋权连通图，此时管网的优化布置即可转化成求解赋权图的最小树问题。本文从求解最小树形图的生成以及对最小树优化两方面着手。5.1管网的最小树形图生成5.1.1Kruskal算法模型建立假设管网最短线程的网络模型为N(,VE)，其中V为供水管网的顶点集，E为供水管网最短线程边集，则令最小树的起始状态为只有n个顶点而无边的非连通图T=（V，{}），首先将权值排序，然后选择权值最小的边，若该边的顶点落在图T中不同的连通分量上，则将此边加到图T中，否则舍弃此边而选择下一条代价最小的边。以此类推，直至T中所有的顶点都在同一连通分量上为止。本文给出易于编程的基于MATLAB的Kruskal避圈算法的计算模型。Step1初始化，令i=1，j=0，T=，把E中的边按照权值由大到小的顺序排列，即；Step2判断是否含圈，若含圈，转Step3，否则转Step4；Step3令i=i+1，若，转Step2；否则退出计算；Step4令结束，T是最小树；否则转Step2。5.1.2计算最小树形图总管长根据地形条件和表2计算的各管线的最短线程，作出供水管网布置的连通图。32万方数据 三峡大学全日制专业学位硕士学位论文N3146.5I7294.66049.32984.35266.3J4876.22335.4F1973.63192.73154.59086.7CE5632.84516.3BOA15665.42276.32658.312052.0K3579.4D2512.1H2410.23642.63094.2G4217.32383.6MP2185.3L图5.1供水管网布置的赋权图其中黑色加粗部分为干管，虚线部分为姑开支管，沿隧洞布线，其它为各支管，未连接部分表示地形条件不允许布线。标注计算所得的最短线程，得到供水管网赋权图，如图5.1。由于干管部分已确定为最小树的组成部分，则此最小树称之为带约束的最小树求解。将上述图沿北干管和东干管分为两部分计算最小树，再合并，结果如下：33万方数据 三峡大学全日制专业学位硕士学位论文N3146.5IJ4876.22335.41973.6F3192.79086.7CEBOA2276.32658.312052.0K3579.4D2512.1H2410.23642.6G4217.3MP2185.3L图5.2管网布置的最小树形图计算以上最小树，将各管线长度相加，得出其最小管线长度为64144.6m，即64.1446km。5.2管网的最小树形图优化5.2.1Steiner最小树形图生成模型建立假设=（，{}）为添加管网布置Steiner点后的连通图，其中，添加Steiner点之前的已知点点集，为Steiner点点集，若为连接已知点的Steiner点，则Step1寻找与已知点构成正三角形的点，并代替点；Step2寻找与已知点构成正三角形的点，并代替点，，以此类推，直至所有点集被代替后只剩两个原点，；Step3连结，，其与正三角形相交的点即为Steiner点，重复此步骤，直至找出所有Steiner点。Step4重新建立连通图，计算管网Steiner最小树。5.2.2计算Steiner最小树形图总管长在本文的管网Steiner最小树计算中，除了考虑到算法的精确性即复杂度以外，还需考虑到实际工程中比较难以解决的问题，主要有以下两点：1）复杂地形条件下Steiner点的位置该如何确定；2）供水区域影响因素繁杂，Steiner点的个数该如何确定。34万方数据 三峡大学全日制专业学位硕士学位论文基于以上两个难点，本文从地形和灌区结构方面综合考虑，最终确定Steiner点的个数及方法。在纳雍金蟾水库供水灌溉工程中，干管部分是输水管网，周围居民较少，且基本没有农田和耕地，所以不负责配水，优化工作主要集中在支管部分，而支管部分从地形来看，各蓄水池高差较大，以保猫寨蓄水池和姑开蓄水池为例，二者在地理位置上属于毗邻的，但其三维坐标：姑开蓄水池K（2985774，508554，1615.1），保猫寨蓄水池G（2982277，511194，1747.8）Z坐标相差甚大，若在两者之间添加一个点作为Steiner点，增加蓄水池，则有可能减小管网布线长度。从灌区结构角度分析，灌区2015年灌溉耕地面积7.2万亩，其中田1.1万亩，旱地6.1万亩，田占15.3%，旱地占84.7%，田与旱地比例0.18:1。根据灌区的气候及土壤、作物的耕作习惯，参照《中国农业需水与节水高效农业建设》，根据调查统计分析灌区2015年田的复种指数取1.8，旱地复种指数取2.0，水田在夏季种水稻，秋季种油菜。夏季种烤烟和玉米的旱地，秋季种油菜，其中种植经果林、茶叶的旱地复种指数为1.0。表5.1灌区2015年土地结构表土地面积复种指数土地结构灌区合计水田旱地水田旱地水田/旱地合计7200011000610001.82.00.180姑开5478406114171.82.02.866保猫寨北660735862491.82.00.057田家寨3858112427341.82.00.411维新支管7619299346261.82.00.647保猫寨东11473214112591.82.00.019法窝南245875217061.82.00.441法窝北11051118798641.82.00.120凹书北18374163182111.82.00.009凹书南508214849341.82.00.030经分析，凹书北，法窝北以及保猫寨东灌溉面积较大，均在一万亩以上，将整个灌区分为北灌区和东南灌区，则北灌区较东南灌区总面积大，同时考虑到各灌区的地理位置，本文拟设定北灌区增加Q、R两个steiner点，东灌区增加S一个steiner点，各灌区分别寻找steiner点。以北灌区为例，求解步骤如下：Step1对灌区内的已知蓄水池，得到一个所有蓄水池在内的矩形区域，将此35万方数据 三峡大学全日制专业学位硕士学位论文区域限定为搜索范围；NIJFEC图5.3遗传算法的搜索范围Step2设定steiner点的个数为n=2，随机在矩形区域内生成300个初始点，计算得出添加每个初始点后的最小树；Step3使用选择方法对其进行选择操作，选出结果较优的偶数个初始点作为父节点，本文选择概率取30%；Step4将step3中选择的父节点进行交叉计算得到子节点；Step5对子节点进行变异操作，本文子节点变异操作概率取为2%；Step6输出近似最小Steiner树的权值以及Steiner点的坐标。上述解法通过mathematics7.0编程，在windows7系统中运行通过。对于北灌区给出的8个站点，我们经过多次试验发现，当Steiner点的个数取为2个时效果最好。并且，该解法不但得到最小steiner生成树的权值，还得到了steiner点的坐标、最小steiner生成树的图形。以上计算过程得到Q（2932341,515643,1612.4），R（2986585,501235,1656.4）两个Steiner点，生成的Steiner树图如图5.4（a）。根据以上方法编程计算得到东灌区S点的坐标（2984357,512456,1672.5）。生成的Steiner树图如图5.4（b）。OKNISQRJHGFCEM(a)北灌区Steiner最小树（b）东灌区Steiner最小树图5.4灌区Steiner树局部图36万方数据 三峡大学全日制专业学位硕士学位论文连接总干管与北干管、东干管，建立供水区域管网，并计算权值，如图5.5所示：NI2043.51952.6QJR2651.11824.72132.34876.2F9086.7C1973.6EBOA2276.32658.312052.03579.42414.4KDS1645.23642.6H2163.7G3154.7MP2185.3L图5.5Steiner最小树优化结果5.3结果分析5.3.1管线长度比较根据5.2节优化结果，计算出最短管线长度为62.27km，较5.1节计算结果64.15km小1.88km。而优化前的原管线总长为75.04km，缩短了12.77km。具体结果如下。⑴干管部分总干管从金蟾水库坝址起沿戈落坝小河左岸向东北方向走至小坪子，地形坡度为10°～35°，地层基岩为二叠系下统梁山组（P1L）砂泥岩与P1q+m灰岩，覆盖层厚度为0～2m，局部大于3m；总干管沿线地形比较平缓，地面起伏较小，因此大部分沿等高线布置，其中跨越周家湾、倒回龙、小坪子等冲沟，管道高程在1761～1745m之间，全长2.237km，较原干管全长2.56km缩短了0.323km。东干管沿线地形陡峻，海拔高程在1820m-2025m远高于管线高程，且穿过木槽槽、曾家沟等大冲沟，沿等高线绕线的难度较大，采取隧洞布线，隧洞长度为15.694km，与原管线长度一致。北干管往法窝南、北灌区延伸后，分级引管至凹书南、北灌区。北干管从小坪子起到青岗林止，不经过深切冲沟和陡峻高山，无重大地形地质制约因素，管道高程在1745～1690m之间，全长9.087km，较原管线缩短2.515km。具体结果如表5.2。37万方数据 三峡大学全日制专业学位硕士学位论文表5.2干管部分管线长度比较干管部分总干管东干管北干管结果比较长度建筑物型式长度（km）建筑物型式长度（km）建筑物型式（km）原管线浅埋有压管2.56隧洞有压管15.694浅埋有压管11.602优化管线浅埋有压管2.237隧洞有压管15.694浅埋有压管9.087⑵北灌区支管部分北灌区主要有法窝和凹书两个灌区，法窝灌区高程在1690～1640m之间，为满足田家寨、火烧寨、熊书块等旱地以及箐脚冲沟对岸水稻灌区的灌溉，在法窝灌区新增Steiner点Q处将支管分为四个方向，分别为法窝1、2、3、4支管，各支管长度见表5.3，总长度为7.953km，较之原法窝南、法窝北支管的总长度缩短1.414km。凹书灌区高程在1690～1667m之间，沿线地形平缓，无大的深谷冲沟和高山。凹书灌区管线布置从加入另一Steiner点R处开始，分段为凹书1、2支管，总长度为7.592km，与原凹书南、凹书北支管相比，缩短了1.974km。羊场支管从青岗林起途经苏家屋基到羊场止，高程在1690～1676m之间，满足大部分灌面自流要求，局部灌区考虑人工提灌；管线全长1.973km，较原管线的北干管支管缩短0.571km。具体结果见表5.3。表5.3北灌区支管部分管线长度比较法窝灌区羊场灌区凹书灌区建筑物建筑物长度长度（km）建筑物型式长度（km）型式型式（km）浅埋有法窝南3.174浅埋有凹书南3.783原管线2.544浅埋有压管压管法窝北6.193压管凹书北5.718合计9.3672.5449.501法窝12.132法窝31.953浅埋有浅埋有凹书12.651优化管线压管法窝21.825法窝42.043压管1.973浅埋有压管凹书24.876合计7.9531.9737.527⑶东灌区支管部分东灌区主要包含姑开、保猫寨、田家寨及维新灌区，姑开灌区管线由东干管末端至姑开乡，法猪寨段地形高程在1720m～1850m之间，受施工技术限制，本段与原布线方案一样，采用隧洞布线；因此，姑开灌区的管线长度与原姑开支管相同，均为3.579km。保猫寨灌区高程在1669m～1540m之间，满足大部分灌区自流要求，局部采38万方数据 三峡大学全日制专业学位硕士学位论文用人工提灌。主要供水区域为岩脚寨（北）、龙滩口（西）以及马摆平（东），根据供水需要，保猫寨灌区支管分为保猫1、2、3、4支管段，各管段长度见表5.4，总长度为8.89km，比原保猫寨灌区支管总长度缩短2.884km。田家寨灌区由东干管末端起，沿线有公路贯穿田家寨灌区，末端至田家寨村，管线高程在1669m～1540m之间。经优化计算，田家寨支管长度为2.185m，与原田家寨支管相比，缩短3.004km。维新灌区离坝区最远，原方案维新支管选择从东干管末端开始，沿公路布线至维新镇。而优化方案选择从保猫寨支管末端开始，沿最短线程到达维新镇。优化后的维新支管长度为3.155km，相较于原维新支管，缩短了7.148km。具体结果见表5.4。表5.4东灌区支管部分管线长度比较姑开灌区保猫寨灌区田家寨灌区维新灌区建筑建筑物长度建筑物建筑物长度长度长度（km）物形型式（km）型式型式（km）（km）式浅埋隧洞有浅埋有保猫北6.756浅埋有原管线3.5795.189有压10.573压管压管压管保猫东5.018管合计3.57911.7745.18910.573浅埋隧洞有浅埋有保猫12.658保猫31.645浅埋有压优化管线3.5792.185有压3.155压管压管管保猫22.414保猫42.164管合计3.5798.892.1853.1555.3.2用钢量结果比较用钢量是衡量纳雍金蟾供水工程投资费用的主要指标，因此需要准确计算优化后的管网的总用钢量。本文均选用Q235型管材，用钢量根据以下公式计算2dd2ml()（5.3）42其中，m为管材质量，d为管径，为管壁厚度，依据原供水工程分析取值，3为管长，为Q235钢材的密度，取7.85g/cm，取3.14。根据输水线路、建筑物布置结果，经输水方式以及输水管材比较后，本工程最终采用焊接钢管进行有压管道输水，即利用地形高差，采用无外加动力满流输水方式。管道结构形式分为浅埋压力管、隧洞有压管两种。工程整个输水线路长度总长62.27km，其中浅埋有压管长42.10km（68.6%），隧洞有压管15.27km（31.4%）。根据水力学公式公式计算对管径进行估算：39万方数据 三峡大学全日制专业学位硕士学位论文4QDvp（5.4）Q—设计流量，按各灌面用水量确定；Vp—允许流速，给水管道流速一般取2.5～3.0m/s，不应小于0.5m/s。根据金蟾供水工程规模确定设计流量，类比其他工程，根据不同的取水流量及管材特性，经试算后选择各管管径见表5.5。40万方数据 三峡大学全日制专业学位硕士学位论文表5.5管径试算成果表项目流量管径流速3单位m/smmm/s总干管1.44110001.835北干管0.5806002.051法窝1支管0.0952501.935法窝2支管0.4826001.705法窝3支管0.2474001.966法窝4支管0.2344501.471凹书1支管0.0943001.330凹书2支管0.1403001.981羊场支管0.5736002.026东干管0.8577501.940姑开支管0.3324502.087保猫1支管0.5186501.561保猫2支管0.0683000.962保猫3支管0.4486501.350保猫4支管0.0773001.089田家寨支管0.1114000.883维新支管0.2605501.09441万方数据 三峡大学全日制专业学位硕士学位论文计算出优化后管线用钢量和原管线用钢量结果如表5.6，表5.7。表5.6优化后管网用钢量表5.7原方案管网用钢量管壁管段长管段质管壁管段管段质项目管径项目管径厚度度量厚度长度量单位mmmmKmt单位mmmmKmt总干管100082.237437.6总干管100082.56500.8北干管60069.087798.3北干管60065.372471.9法窝1支管25062.13276.9法窝南支管25063.174114.5法窝2支管60061.825160.3北干管支管60061.518133.4法窝3支管40061.953113.8法窝北支管40066.193360.9法窝4支管45062.043134.2凹书支管45062.077136.4凹书1支管30062.651115.3凹书南支管30063.783164.5凹书2支管30064.876212.0凹书北支管30065.718248.6羊场支管60061.973173.3东干管75088.2441206.2东干管750815.6942296.3姑开支管45064.239278.4姑开支管45063.579235.0东干管1号支管65083.695467.8保猫1支管65062.658253.2保猫寨北支管30066.756293.8保猫2支管30062.414105.0东干管2号支管65080.934118.2保猫3支管65061.645156.7保猫寨东支管30065.018218.2保猫4支管30062.16494.1田家寨支管40065.189302.4田家寨支管40062.185243.9维新支管550810.5731130.0维新支管55083.155337.2总计——75.046145.9总计——62.275826.4根据计算结果可以看出，管网优化后总用钢量为5826.4t，相较于原布线方案的用钢量6145.9t，减少了319.5t，节约了工程材料，减少了工程投资，满足优化目标。5.3.3土石方开挖量本文选用浅埋和隧洞布线两种管道布线形式，其中，隧洞布线走向和布线长度等与原方案一致，因此，过管隧洞结构设计仍沿用原方案，开挖量不变；浅埋管部分与原布置方案在走线上虽有部分改变，但灌区内无特殊地质结构，浅埋管管槽设计方案根据工程经验采用原设计方案，因此隧洞布线部分开挖量不变，浅埋布线部分因管长缩短而开挖量也随之减小。对于浅埋有压管管槽设计，本文根据基础性质分为岩基管槽和土基管槽。当基础为岩基时，边坡开挖坡比为1：0.5，底部铺设20cm厚砂垫层；当基础为土基时，边坡开挖坡比为1：0.5，底板浇筑20cm厚C10混凝土保护层，管道铺设42万方数据 三峡大学全日制专业学位硕士学位论文完毕后上部用碎石土回填密实。管槽结构如图5.6。（a）岩基基础（b）土基基础图5.6浅埋管布置断面当管槽深度不变时，土石方量的计算公式为：a(a2ch)VhL()achhL（5.5）23其中，V—土石方量，m；a—槽底宽度，m；c—放坡系数；h—管槽深度，m；L—管槽长度，m。由于管槽结构有两种不同形式，为计算简便，本文选择采用平均深度计算土石方量。浅埋有压管的埋管深度应不小于0.7m，开挖深度根据浅埋管管径调整，管槽深度在1—2m之间。确定好各已知数据，根据公式5.3，利用Excel表格可以建立以下土石方量的计算表格，如表5.8，表5.9。43万方数据 三峡大学全日制专业学位硕士学位论文表5.8优化方案浅埋管土石方开挖量3管道名称槽底宽度（m）槽底深度（m）放坡系数管槽长度(km)管径(mm)开挖量(m)总干管1.21.80.52.23710008455.86北干管0.81.20.59.08760015266.16法窝1支管0.450.60.52.132250959.4法窝2支管0.81.20.51.8256003066法窝3支管0.60.90.51.9534001845.585法窝4支管0.6510.52.0434502349.45凹书1支管0.50.70.52.6513001577.345凹书2支管0.50.70.54.8763002901.22羊场支管0.81.20.51.9736003314.64保猫1支管0.851.30.52.6586505183.1保猫2支管0.50.70.52.4143001436.33保猫3支管0.851.30.51.6456503207.75保猫4支管0.50.60.52.1643001038.72田家寨支管0.60.90.52.1854002064.825维新支管0.751.10.53.1555504511.65总计57178.035表5.9原方案浅埋管土石方开挖量法窝南支管0.450.60.53.1742501428.3北干管支管0.80.20.51.518600273.24法窝北支管0.60.90.56.1934005852.385凹书支管0.6510.52.0774502388.55凹书南支管0.50.70.53.7833002250.885凹书北支管0.50.70.55.7183003402.21东干管1号支管0.851.30.53.6956507205.25保猫寨北支管0.50.70.56.7563004019.82东干管2号支管0.851.30.50.9346501821.3保猫寨东支管0.50.60.55.0183002408.64田家寨支管0.60.90.55.1894004903.605维新支管0.751.10.510.57355015119.39总计69775.335由表5.8，5.9可知，优化后的布线方案的土石方开挖量随管线长度的缩短而333降低，总开挖量为57178m，较之原方案开挖量69775m减少12597m。对于过管隧洞，开挖隧道后埋设钢管，隧洞为城门洞形。经地质勘察发现，梯子岩乡和法猪寨段岩性较为完整，属II、III类围岩；对Ⅱ、Ⅲ类围岩洞室开挖断面结构如图5.7：44万方数据 三峡大学全日制专业学位硕士学位论文图5.7隧洞布线开挖断面结构图管道直径φ45cm：断面为城门洞形，净尺寸为1.5m×1.8m（宽×高），管道直径φ75cm：开挖断面为城门洞形，尺寸为1.6m×1.8m（宽×高）。根据公式5.4计算隧洞土石方开挖量。2Vahd/8L（5.4）3其中，V—土石方开挖量，m；a—隧洞宽度，m；h—隧洞矩形部分高度，m；d—弧形直径，m；L—隧洞长度，m。3根据公式计算出东干管部分隧洞开挖量为29553m，姑开支管部分开挖量为36427m。由于隧洞部分设计与原方案一致，开挖量不变。因此，总开挖量减少312597m。5.4本章小结本章在第四章的基础上，连接各点对并标出点对间线程权值，问题即转化成求解连通图的最小树，本章首先运用Kruskal算法求解管网布置的最小树，为使得管网布置更加优化，本章再次运用遗传算法寻求Steiner点，求解管网布置的Steiner最小树，进一步缩短管线，优化后将优化结果与原管网布置方案进行比较，从管长、用钢量以及土石方开挖三方面展现优化后的管网布置方案能节约工程投资，满足优化目标。45万方数据 三峡大学全日制专业学位硕士学位论文6研究结论与展望6.1研究结论随着社会的进步，改善农村居民的生活质量已经成为继续解决的问题。在我国，有较大一部分农村居民生活在山区，山区因其复杂的地形因素，使得其饮水问题突出，从而阻碍人们生活质量的提高。为提高山区居民的生活质量，必须解决山区饮水问题。输水管网是山区农村饮水安全工程中供水系统的重要组成部分，在整个供水系统中管网部分的投资最高，一般要占到工程总投资的60%～80%。供水管网的优化布置能减少埋管工程的总投资，也能缩短输水距离、降低输水能耗和减少输水成本。然而，山区供水工程设计中管网布置一直根据经验确定，缺乏科学的理论与方法。本课题将以贵州省毕节市纳雍县灌溉区管网布置为研究对象，采用离散化地形表征技术，生成山区复杂地形条件下的两点最短线程模型，开发复杂地形中的最小树形图生成方法，构建管网优化的Steiner最小树形图模型，以解决复杂地形的部分输配水节点已确定需增设节点的管线优化问题，完成整个管网布置工程设计工作，其中主要结论如下：（1）将工程测量得到的山区地形离散点进行预处理，采用Delaunay三角网格划分方法，得到山区地形的三角网格模型，解决山区复杂地形难以用数学函数表达而无法求得测地线的问题。⑵为将求解离散地形点间的最短路径问题转化为图论中的优化问题，本文采用两点间距离公式计算Delaunay三角网各边权值，将Delaunay三角网转化为赋权网络，并采用Dijkstra算法计算点对间最短线程，为运用图论中的优化方法解决实际问题提供了新的思路。⑶将各点对相连并标出点对间的最短线程值，即将复杂地形管网优化工作转化成求解赋权连通图的最小树问题，同时，采用遗传算法寻找Steiner点，进一步优化管网布置的最小树，得到山区地形供水管网的优化布置方案。6.2展望由于本人的学术水平、知识结构以及时间精力等有限，论文在实际应用中还存在一些问题，主要问题如下：⑴受研究限制，本文在第四章最短线程计算过程中，仅对点对间的最短线程进行一次优化计算，虽然缩短了点对间最短线程，但并非最优结果，若采用迭代邻域边多次迭代计算，结果将会更可观。⑵整片文章主要考虑到山区的复杂地形条件，对实际工程中的地质问题考虑46万方数据'