（电力系统及其自动化专业论文）基于加权voronoi图的变电站优化规划.pdf

天津大学硕士学位论文第一章绪论 1 1 城市电网规划概述 第一章绪论 随着我国国民经济的发展和人民生活水平的不断提高，人们对电能的需求也 在持续增长。在我国目前状况下，部分地区不仅电力供应与需求在总量上的不平 衡对社会和国民经济的迅速发展产生了制约作用，而且现有的城市电网系统的不 良结构同样给生产发展和人民生活的改善带来了消极的影响，甚至是较为重要的 损失。 城市电网【i j ( 简称城网) 是指在城市范围内，为城市供电的各级电压电网的 总称，包括输电网、高压配电网、中压配电网和低压配电网，连同为其提供电源 的变电站和国内的发电厂。城市电网是电力系统的重要组成部分，又是电力系统 的负荷中心，具有用电量大、负荷密度高、安全可靠和供电质量要求高等特点。 城市电网还是城市现代化建设的重要基础设施之一，其建设、改造及运行的经济 性和安全性既影响整个电力部门的经济效益和广大电力用户的供电质量，又影响 到城市整体功能的正常发挥。城市电网规划( 简称城网规划) 是电力系统规划和 城市规划的重要组成部分，合理进行城网规划是实现未来城市电网经济性和安全 性的先决条件，可以获得很大的经济和社会效益；相反，城网规划的失误则会给 国家的经济建设和人民生活带来不可弥补的损失。 按规划时间的不同，城市电网规划分为近期( 1 - 5 年) 、中期( 5 1 5 年) 和 长期规划。长期规划属于战略规划，它主要决策城市电网发展的重大问题和发展 方向( 如建立新的电压等级、确定新的城市电网电源点、论证规划末期的城市需 电量以及城市可能发生的改造和扩展方向) ，为中期和近期规划制定目标。中期 和近期规划属于战役规划，主要为长期规划的任务和目标如何实施确定时间表。 长期规划要求中期和近期的城市电网建设和改造是长期电网发展目标的一部分， 保证近期和长期投入的设备在规划期间不会发生拆除的现象。 搞好电网规划，加强电网管理是改革形势发展的必然需要，是实现电力增长 方式从粗放型向集约型转变的一个重要环节。搞好城网规划的意义在于： ( 1 ) 科学的城网规划可以用来指导城网建设，通过城网的加强和改造， 使城网结构合理、安全可靠、经济灵活，从而减少停电损失，降 低线损1 2 】，提高供电质量，并为发电领域引入竞争机制提供基础 天津大学硕士学位论文第一章绪论 条件。 ( 2 ) 科学的城网规划是提高系统投资效益的最有效途径。 ( 3 )城网规划是电力企业战略发展规划的重要组成部分，同时也是配 电自动化规划和实施的基础。 城网规划是一个复杂、庞大的系统工程【3 1 ，一般包括以下几个方面内容： ( 1 ) 在研究城市电网负荷分布现状的基础上进行空间负荷预测，确定 目标年各个规划小区的负荷密度及负荷总量。 ( 2 ) 在小区负荷预测的基础上确定各个新建变电站的地理位置、容量 以及所有变电站的供电范围，并确定相关各工程项目的投产时间 等。 ( 3 ) 在以上工作的基础上进行城市电网网络结构的整体优化设计，以 确定所需建设供电线路的规格标准、电压等级、投建时间及其所 需的投资等。 城市电网规划和设计工作具有规模大、不确定因素多且涉及领域广的特点 【4 】，在新形势下该领域的研究面临着更多的困难和挑战。确定变电站位置与容量 是城市电网规划中介于电力负荷预测和网络结构优化之间的关键环节，其结果直 接影响未来电力系统的线路走线、网络结构、电网投资、运行经济性及供电可靠 性，所以变电站选址定容优化规划是一项十分重要的基础规划工作。这是一类复 杂的大规模、非线性的混合整数优化问题，至今未能得到很好的解决。 1 2 变电站规划概述 电力系统要保证安全、优质、经济、高效运行，要保证对千百万用户的正常 供电，必须要有合理的电源配置和网络结构。其中，变电站的规划是最为重要的 环节【5 1 。 1 2 1 变电站规划的内容和意义 变电站规划是在城市各小区负荷密度已知的基础上，确定出目标年新建变电 站的个数、地理位置、容量及所有变电站的供电范围，以满足未来负荷发展需要， 同时使所需投资及运行费用最小。由于新建变电站的地理位置、供电范围、容量 及投入时问均未知，各个变量之间相互影响、相互制约，它们的组合方案数大得 惊人，而且还必须综合考虑变电站的进出线走廊以及地形、交通、防洪、地质等 条件，这使得整个问题变得十分复杂。 变电站规划的意义有如下几点： 天津大学硕士学位论文第一章绪论 ( 1 )变电站选址的优劣对电力系统网络结构起决定性作用。良好的变 电站位置，可以保证电力系统网架强健，从而能够经济、稳定地 运行。 ( 2 ) 变电站选址的优劣对电力企业的服务质量有重要影响。相关法则 规定变电站站址应尽可能靠近负荷中心，否则部分负荷到变电站 的馈线过长，使电压质量降低。 ( 3 ) 变电站选址的优劣对馈线系统( 或下级输电系统) 有较大影响。变 电站是馈线系统( 或下级输电系统) 的电源点，其位置对馈线系统 ( 或下级输电系统) 的费用有较大影响。如果变电站位置选得不合 适，将导致输电线和馈线更长，费用更高，而且出线走廊的选择 也会随之出现问题。这种决策错误即使可以修正，费用往往也很 高。只有变电站位置决策正确，才能保证电力系统长远的经济性。 1 2 2 变电站规划的准则 城市电网规划和城市规划、环境保护、通讯设施等各个方面有着密切的联系， 总体看来，变电站选址要遵循以下准则： ( 一) 要适应城市规划的原则 l 、正确处理好局部与全局的关系，变电站选址需按照城市的统一布局，合 理布点，并必须取得城市规划部门的同意。 2 、正确处理好主体工程与城市景观相协调的关系，以满足城市总体规划以 及景观的视觉要求。 3 、正确处理好保护风景名胜、文物和基本建设的关系，站址选择必须符合 国家风景名胜、文物保护有关法规，尽量避免在风景名胜、文物保护区内选址。 若文物保护单位周围划出一定的建设控制地带选站时，站址内的建筑物的外形、 色调、高度和体量必须和文物保护单位的建筑相协调，其设计方案必须征得文保 单位的同意，并报城市规划局批准。 4 、尽可能地节约用地，并选择城市开发的边角地，保证其它用地的完整性， 给城市的旧城改造留有发展空间。 ( 二) 要符合电力专业的技术要求 1 、尽可能靠近负荷中心，减少输电线路的投资和电能的损耗。 2 、选择良好的地形地质，不得在地震断层带、滑坡泥石流等地区选择变电 站站址，尽量避免在湖泊水域地带选择站址。 3 、选择便于电力发展线路进出的地段，以降低送配线路建设的费用。 4 、尽可能选择在已有或规划的公路等交通线附近，既可以减少交通运输的 天津大学硕士学位论文第一章绪论 投资，又便于安装电力进出线。 5 、尽量避免污秽地段，远离污秽源，以减少对站内电气设备的腐蚀污染。 6 、遵循防洪、地震等有关规定。 7 、符合环境保护，要积极地采取合理措施，消除污染，保护环境。 ( - - ) 要符合经济合理的原则 变电站的站址选择不仅要考虑变电站的投资和运行费用，还要考虑馈线的投 资和电网运行等费用。另外，站址选择应尽量选用工程拆迁量少的地段，以便降 低工程造价。 1 2 3 变电站规划的现状 在进行变电站优化规划时，新建变电站的地理位置、容量组合及供电范围都 是未知的，各个变量之间相互影响、相互制约，它们的组合方案数目巨大，加之 必须综合考虑变电站的进出线走廊以及地形、交通、防洪、地质等条件，所以整 个问题十分复杂。 国内外已经有很多关于变电站规划这一大规模、非线性混合整数规划问题的 研究成果。按照规划的规模划分，这一问题可分为单站址模型和多站址模型。单 站址模型是在某一变电站的供电范围一定的情况下如何确定变电站位置的方法； 多站址模型是在一个规划区内，同时确定几个变电站的站址。目前的规划模型基 本都是对一个区域的规划，属于多站址模型规划。按是否需要预先给定待选站址 划分，这一问题可分为有待选站址方法和无待选站址方法。传统的规划基本都属 于有待选站址方法，待选站址由有关专家指定，通过技术经济的比较进行决策。 随着计算机技术和优化理论的迅速发展，近三十年来，许多电力系统的专家都致 力于应用计算机技术和优化理论来解决变电站规划问题，也就产生了无待选站址 的方法。 文献 6 】、【7 】用分支定界法来进行变电站优化规划，取得了一定的成果，但 是随着问题规模的扩大，分支定界法的计算时间呈指数增长，因此不能解决大规 模的工程实际问题。文献 8 】、【9 是利用混合整数规划方法来解决变电站规划问 题，由于混合整数规划存在与分支定界法相同的缺点，所以只适合于解决小规模 问题。文献 1 0 1 以负荷矩最小为目标函数，以运输问题为求解方法，提出了一种 新的变电站位置和容量的数学优化技术，但是，由于该方法要求有待选的变电站 站址，因此有很大的局限性。文献 1 l 】提出了一种求解变电站和馈电线位置的简 单目标函数，但没有考虑费用的时间特性，并忽略了网损对变电站和网络选择的 影响。文献 1 2 提出了待建变电站的容量分级问题，但没有考虑不同容量变电站 之间的费用差别问题。文献【1 3 提出了优化变电站容量和近似考虑配电线路网损 天津大学硕士学位论文第一章绪论 的模型和算法，但变电站的位置和数量必须人为给定。文献 1 4 将数字图像处理 技术应用于变电站选址问题，提出了一种新颖的计算模型，但是该方法只适用于 新建地区没有已有站情况下的新建变电站优化规划。文献 1 5 】提出了解决配电变 电站的大小、位置、兴建时间及供电区域的模型，其优化目标函数中包括了变电 站不同费用分量，考虑了电压、容量、能量平衡和辐射状供电约束。该模型的主 要特点是考虑固定费用分量时没有引入o 1 决策变量，而且也没有将模型作线性 化的近似处理，因而使用了非线性规划方法中的广义既约梯度法作为优化方法。 文献 1 6 】将变电站位置坐标的寻优视为一个非线性规划问题，由于难以得到目标 函数关于决策变量导数的解析表达式，故文中采用非线性优化技术中的步长加速 法求解。近年来，专家系统【1 7 】、模糊理论【1 8 】等也都广泛地运用于变电站规划工 作中，这些方法虽然能够避免无待选站址方法所确定的变电站坐落在湖泊、街道、 繁华地段等不适宜建站的区域等问题，但从根本上来说，仍然属于有待选站址方 法，具有很大的局限性。 近二十年来，随着随机优化方法的不断发展，许多电力系统的专家学者将禁 忌搜索法( t s ) 1 9 - 2 0 、遗传算法( g a ) 2 1 - 2 3 】、模拟退火法( s a ) 2 4 1 、人工神经 网络法【2 5 。2 6 】等用于变电站选址中，取得了很多研究成果。但是单个智能优化算法 还存在着一些不足，比如，收敛速度较慢，局部寻优能力较差，计算时间较长等。 文献1 2 7 将变电站优化问题分为平面中位子问题和组合优化子问题，在此基 础上提出了一套不需指定水平年候选站址和容量的情况下自动搜索变电站站址、 站容和供电范围的优化技术。该方法针对电网结构复杂、变电站数目较多、计算 量庞大等特点，采用了试探组合和平面多中位选址等算法，可以在工程允许的计 算精度下，求得较好的方案，大大降低计算工作量。这一方法已在天津大学开发 的城市电网规划计算机辅助决策系统中应用。但是，该文献在解决组合优化子问 题时采用的试探组合算法，所得解的满意程度有待更进一步的提高。文献【2 8 是 在文献 2 7 1 研究基础上，提出了一种考虑配电变压器二次侧线路投资费用和运行 费用的中压配电变压器优化模型，并采用三角连续分割算法( t s p m ) 来解决组 合优化子问题。 上述方法都是基于坐标几何的变电站选址优化求解方法，考虑到v o r o n o i 图 建立了一种并不依赖于坐标几何的空间邻近模型，在解决空间剖分问题上具有一 定的优势，文献 2 9 】、【3 0 利用计算几何- - v o r o n o i 图和d e l a u n a y 三角网的影响范 围特性、最大空心圆特性和局部动态特性，可以保证变电站位于负荷中心，实现 新增变电站的自动优化选址和各变电站供电范围的最佳划分。但是，该方法是在 假设负荷均匀分布，新增变电站的容量和台数一定的前提下提出的，没有考虑到 供电范围与变电站负载率的合理性，只解决了变电站优化规划的一个子问题。 天津大学硕士学位论文 第一章绪论 加权v o r o n o i 图是常规v o r o n o i 图一种较常用的扩展形式，是通过权值来改 变常规v o r o n o i 图的性质。一些学者已经将加权v o r o n o i 图引入很多研究领域， 例如文献【3 l 】将加权v o r o n o i 图和扩展断裂点理论相结合解决划分城市经济区域 的问题。 1 3 本文的主要工作 1 3 1 本文研究的主要内容 针对变电站优化规划方法中存在的不足，本文在结合加权v o r o n o i 图和交替 定位分配算法的基础上，进行了如下几个方面的研究工作： ( 1 ) 在解决新建站容量组合的子问题时，本文给出了一种新的确定新 建站容量组合的数学模型，并采用整数规划的优化技术，同时得 到新建站容量组合的最优解和几组次优解，确保最终得到全局最 优解。 ( 2 ) 针对变电站优化规划问题的特点，在确定新建站初始站址时，根 据是否含有已有站，分别给出了利用常规v o r o n o i 图法及综合考 虑规划区域地形特点、区域面积和负荷分布情况的坐标几何方法 产生初始站址。 ( 3 ) 考虑到v o r o n o i 图在空间分割上的合理性以及计算机自动生成的 可行性和快速性，本文利用v o r o n o i 图来确定新建站站址及所有 变电站( 包括已有站和新建站) 的供电范围。通过对v o r o n o i 图 进行加权来反应负荷分布不均匀、各站额定容量和负载率不同对 变电站供电范围的影响，从而进行变电站供电范围的整体优化， 并结合交替定位分配算法，同时确定新建站站址。 1 3 2 本文结构 本文第一章简单介绍了城市电网规划涉及到的基本内容及变电站规划的内 容、意义、准则和现状。第二章主要对变电站选址定容问题进行了分析，给出了 变电站优化规划的基于最小年费用的数学模型；第三章介绍常规v o r o n o i 图和加 权v o r o n o i 图的定义和性质，并初步分析了常规v o r o n o i 图和加权v o r o n o i 图是如 何与变电站选址问题相结合的；第四章介绍本文提出的基于加权v o r o n o i 图的变 电站优化规划方法，最终完成对新建站数量、容量组合及站址的整体优化，同时 优化得到所有变电站的供电范围；第五章给出了实际工作中的两个算例，并针对 天津大学硕士学位论文 第一章绪论 这两个算例将本文变电站优化规划方法与传统变电站优化规划方法进行比较，阐 述了本文算法的优势：第六章为本文的总体结论。 天津大学硕士学位论文 第二章变电站优化规划数学模型 第二章变电站优化规划数学模型 在规划配电网络变电站的初始阶段，已有的条件是负荷预测后各个小区的负 荷数据、各个小区地块的各种属性、规划区域内地理上的各种信息以及现有变电 站的位置和容量。除了现有变电站的位置外，并没有其它变电站的待选站址。因 此，此时变电站选址问题可描述为：在规划水平年负荷分布已知的情况下，为了 满足一定的负荷需求，以最小的投资和年运行费用( 包括变电站的投资，馈线的 投资，变电站的运行费用和网络的运行费用) 为目标函数，确定变电站的数量、 位置、变压器的容量和台数以及变电站的供电范围。 2 1 变电站投资年费用 变电站的投资年费用主要包括变电站的综合投资费用及变电站年运行维护 费用。其中，变电站的综合投资费用包括变压器综合投资、配电装置综合投资以 及土地征用、建筑物拆迁、环境保护等不可预见的附加投资：变电站的年运行维 护费用包括一年内变压器的电能损耗费用、设备检修维护费、设备折旧费等。一 般情况下，各项费用值不是很明确，可以考虑年运行费用按照综合投资费用的百 分比进行计算，通常取1 0 。 在本文的优化过程中，根据变电站类型的不同，给出三种不同的计算变电站 投资年费用的方法，情况如下： ( 1 ) 变电站为新建站：新建站是指在规划水平年中将要投入运行的变 电站，该类型变电站的站址和容量都是未知的，计算时要同时考 虑变电站的综合投资费用及年运行费用。最终优化得到该类型变 电站的站址、容量及供电范围。在计算之前给出的原始数据有新 建站的待选类型数据，包括新建站的待选容量、最高负载率、综 合投资费用和运行维护费用、电压等级等。 ( 2 ) 变电站为已有站：已有站是指规划的基础年就已经存在的变电站， 在规划水平年的站址、站容数据都已知，计算时不考虑投资费用， 只需要最后给出规划水平年的供电范围。 ( 3 ) 变电站为不参加优化站：不参加优化是指在规划水平年其站址、 容量数据均为已知量，但在规划基础年还未投入运行的变电站， 天津大学硕士学位论文 第二章变电站优化规划数学模型 计算时要考虑该类型变电站的投资费用和运行维护费用，最终优 化得到该类型变电站的供电范围，但不能优化重新确定站址及站 容。 2 2 变电站低压侧线路综合投资年费用 当变电站低压侧出线采用电缆线路时，变电站出线的综合投资费用包括电缆 线路投资、电缆沟综合投资等；当变电站低压侧出线采用架空线路时，变电站出 线的综合投资费用主要是架空电线以及架空设备投资等。 变电站g ，y ，) 与负荷点b ，y ，) 之间的线路综合投资费用可以用公式( 2 - 1 ) 来计算。 f e e d e r , j = 叱 ( 2 - 1 ) 其中，口为单位长度线路的投资费用，岛为变电站g ，y ，) 与负荷点x j , y j ) 之间供电线路长度。 为了简化计算，我们采用站网分解的优化方法，在目标函数中近似考虑变电 站出线的影响。变电站( x i ，y ，) 与负荷点b ，y ，) 之间供电线路长度乇的近似计算 方法如下： 乞= ( 2 - 2 ) 其中，k 为线路曲折系数；d u 为第f 个变电站g ，y ，) 与第歹负荷点b ，y ) 之 间的直线距离。 以的计算公式如下： 略= 厄i f 而 ( 2 - 3 ) 考虑到计算模型中，变电站到负荷点的距离采用的是两点间的直线距离，但 由于街道地形、接线形式等因素的影响，线路的实际长度一定会增加，所以在此 采用直线距离与线路曲折系数的乘积来减少计算的误差。 2 3 变电站低压侧线路网损年费用 电能沿线路传输时，线路上不可避免地会产生一定的损耗，将网损费用计入 目标函数的目的就是通过合理选择变电站的位置，尽可能地减少线路上的损耗， 提高整体的经济性。 设负荷点x j , y ，) 的负荷值大小为，第f 个变电站“，y i ) 与第负荷点 b ，y ) 之间的距离乇，变电站g i ，少，) 与负荷点k ，y ，) 之间的线路单位长度电阻 天津大学硕士学位论文 第二章变电站优化规划数学模型 为厉，则该线路上的功率损耗为： 弓= 热 ( 2 - 4 ) 其中，u 为变电站低压侧线路的线电压，c o s q ，为功率因数。 设单位电能损耗折价系数为届，线路年损耗小时数为屈，则线路屯的年网 损费用为： c 鳞= 届屈弓 ( 2 5 ) 在此，令变电站出线网损折算系数：掣堑至，则线路的年网损妄用可 u c o s 谚 以表示为： c g = 哆勺 ( 2 - 6 2 4 变电站优化规划的最小年费用 通过上述分析，可以将变电站最小年费用模型总结如下： m i n z = s t a t i o n + f e e d e r + c q ( 2 7 ) 旺w ，s j e ( s j ) c o s o f _ l ，2 ，n w j ij iu ，2u u ，= j 易r i 其中，s t a t i o n 为折算到每年的变电站年投资及运行费用；f e e d e r 为折算到 每年的变电站低压侧馈线的投资费用；c o 为估算的变电站低压侧线路年网损费 用。三种费用的表达式如下： s , a t 面n ：肥，黼栅 ) 协鼬 凡砌：一糕匿勺 ( 2 - 9 ) 1 ( 1 + ，o ) “一1 j 智怠9 c q = 芝杉2 i v ( 2 - 1 0 ) 其中， ( s ) ：第j 个新建变电站的投资费用； 甜( 墨) ：第i 个新建变电站的年运行费用： 刀：新建变电站的个数； n ：已有和新建变电站的总数； s ：第i 个变电站的容量； 天津大学硕士学位论文 第二章变电站优化规划数学模型 p 例：第f 个变电站的负载率； z ：第i 个变电站所供负荷的集合； 全体负荷点的集合； j ：f ：变电站i 与负荷点之间线路的长度： ：第，点的负荷( 有功负荷) ； ，艚：变电站的折旧年限； m ，：变电站低压侧线路折旧年限； r o ：贴现率； c o s ( p ：功率因数： 足：第i 个变电站供电半径的限制； 口：单位长度线路投资费用； ：线路网损折算系数。 2 5 变电站优化规划数学模型的简化 m 理：令旷= 上 ，其中m 为变电站所供负荷点总数， 矿为变电站供电范围内 的负荷平均值，则： 凡出+ = 4 器高鼹n 喜丢昨岛 协 芳 i 笔篙 善n 丢勺+ 旷喜荟勺 = 悟 黼h 泓岛 进一步令： 刚旷+ 芳 黼 协 且 s 缸砌刀( s ) = 厂( ) 丢鼍譬毒高 + z ，( s ，) c 2 - 3 ， 则表达式( 2 7 ) 可简化为如下的优化问题表达式： m i n z ：窆s t a t i o 刀 ) + y n ，f ，( 2 - 1 4 ) 天津大学硕士学位论文 第二章变电站优化规划数学模型 豇w ，s j e ( s ，) c o s c p f _ 1 , 2 ，n j e j 7 v j j ，j lu j 2u u = j lhsr i 式中y 的物理含义为一年中单位长度线路的费用系数，这一费用包括折算到 每年的线路投资费用以及运送单位负荷时，在线路上产生的损耗费用，y 也是一 个平均值。 2 6 本章小结 变电站优化规划的目的就是根据电源发展及负荷增长情况合理地确定若干 年后的变电站建设方案，使其在保证安全可靠的前提下做到经济上的优化。在规 划配电网络变电站的初始阶段，已有的条件是负荷预测后各个小区的负荷数据、 各个小区地块的各种属性、规划区域内地理上的各种信息以及现有变电站的位置 和容量。除了现有变电站的位置外，并没有其它变电站的待选站址。因此，需要 解决的变电站选址问题可描述为：在规划水平年负荷分布已知的情况下，为了满 足一定的负荷需求，以最小的投资和年运行费用( 包括变电站的投资，馈线的投 资，变电站的运行费用和网络的运行费用) 为目标函数，确定变电站的数量。位 置、变压器的容量和台数以及变电站的供电范围。根据以上问题的分析，本章给 出了考虑最小年费用的变电站优化规划数学模型。 天津大学硕士学位论文第三章理论基础 第三章理论基础 3 1 常规v o r o n o i 图及加权v o r o n o i 图的基本概念 v o r o n o i 图是计算几何中一个被广泛研究的问题【32 1 ，由于v o r o n o i 图与一些 自然结构十分相象，并具有惊人的数学特性。因此，它是解决相关几何问题强有 力的工具，在气象、地质、测绘、考古、分子化学、生态学和计算机科学等领域 中都对v o r o n o i 图进行了广泛而深入的研刭3 3 】。 v o r o n o i 图最早是由俄国数学家gv o r o n o i 在1 9 0 8 年提出的，并将其扩展至 高维空间；荷兰气象学家泰森( a h t h i e s s e n ) 在1 9 1 1 年采用v o r o n o i 划分每一 个气象观测站的最近区域，以改进大范围平均降水量的预测能力【3 4 1 。为了纪念这 些科学家，后人将之称为v o r o n o i 图或泰森多边形( t h i e s s e np o l y g o n ) 【3 引。 简单说来，v o r o n o i 图是在数学上限定了每个离散点数据的有效作用范吲3 6 】。 经过一个多世纪的发展，近年来，专家们对v o r o n o i 图的概念有了新的延伸， v o r o n o i 图理论成功地解决了计算机图形学中找最近点，求最短路径，求n 个点 地凸包，求最小数等问题 3 7 - 3 8 】。因此，v o r o n o i 图在与几何信息相关的许多领域， 诸如：地理空间设施选址分析方面、生态研究、城市规划以及优化配置等许多领 域有着广泛的应用。 3 1 1 常规v o r o n o i 图 设想在一大片林区内设置”个火情观察塔p 。，p ：，p 。，每个观察塔 p 疋= 1 , 2 ，刀) 负责其附近的林区v ( p ，) 的火情及灭火的任务。y ) 由距只比距 其它p u = 1 , 2 ，刀，j f ) 更近的树组成，v ( p ，) 就是关联于b 的一个v o r o n o i 多 边形，而v o r o n o i 图由所有v ( p ；) 组成( 待1 , 2 ，n ) 。 如果把上述刀个观察塔换成刀个火源，这，1 个火源同时点燃，并以相同的速 度向所有方向蔓延，那么燃烧熄灭处所形成的图便是v o r o n o i 图【3 9 1 。 3 1 1 1 常规v o r o n o i 图的定义 平面上的v o r o n o i 图可以看作是点集尸中每个顶点p = 1 9 2 ， ) ，以相同的 速度向外扩张，直到彼此相遇为止而在平面上形成的图形。这样，除最外层的点 形成开放的区域外，其余每个点都形成凸多边形( 如图3 1 所示) 。这一描述与 变电站的定位及供电区域的划分具有极大的相似性。其数学定义可以描述为： 天津大学硕士学位论文第三章理论基础 设平面上的一个控制点集p = p l ，p 2 ，p 。) ，3 n o o ，则任意点的v o r o n o i 图定义【2 9 】为： r ( p f ) = x v ( p f ) id ( x ，p ，) d ( x ，p ，) ，_ = 1 , 2 ，n ，0 ( 3 1 ) 其中，4 p i ，p ，) 表示点p f 和p ，间的欧氏距离，p f p ，i j ，f ，歹o , z ，1 ) ， x 为平面上任意点。区域y ，) 称为顶点p ，的v 多边形，各点的v 多边形共同组成 v o r o n o i 图。 v o r o n o i 图可以理解为对空间的一种分割方式( 一个v o r o n o i 多边形内的任 意一点到本v o r o n o i 多边形中心点的距离都小于到其它v o r o n o i 多边形中心点的 距离) ，也可以理解为对空间的一种内插方式( 空间中的任意一个未知点的值都 可以由距离它最近的已知点，即采样点的值来代替) 。这里的v o r o n o i 多边形的 中心点其实就是包含于该多边形内的离散点。 图3 1 常规v o r o n o i 图 3 1 1 2 常规v o r o n o i 图的性质 v o r o n o i 图具有许多有趣而惊人的数学特性，为研究解决地理学、计算机科学 和数学等领域中的一些问题提供了有力的工具。以下，将重点介绍v o r o n o i 图与变 电站优化规划问题有关的几个性质f 删： ( 1 ) 影响范围特性( i n f l u e n c er e g i o n ) 每一个空间生长点唯一对应一个v o r o n o i 多边形。对一个空间点来说，凡落在 其v o r o n o i 多边形内的空间点均距其最近。因此，该v o r o n o i 多边形在一定程度上 反映了其空间影响范围。若这个空间生长点被删除的话，则其相应的影响范围 ( v o r o n o i 多边形) 也会随之消失。对于二维空间中任意一点来说，除非其位于公 共边上，否则必然落在一个v o r o n o i 多边形之内，即处在一个生长点的影响范围之 天津大学硕士学位论文第三章理论基础 3 1 1 3 构造常规v o r o n o i 图的方法和特点 就v o r o n o i 图生成算法的特点而言，主要分为矢量空间和栅格空间的生成算 法，简称矢量法( v e c t e r - b a s e d ) 4 q 和栅格法( r a s t e r - b a s e d ) 【4 2 1 。 ( 1 ) 矢量方法 构建v o r o n o i 图的矢量方法很多，散见于国内外不同领域的研究刊物和文献 上。常见的矢量方法有增量法( i n c r e m e n t a lm e t h o d ) 、间接法( i n d i r e c t l ym e t h o d ) 和分治法( d i v i d e a n d c o n q u e rm e t h o d ) 等。 ( 2 ) 栅格方法 栅格方法是与矢量方法平行的方法，包括4 领域扩张算法、8 领域栅格扩张 算法、交替采用4 领域与8 领域的扩张方法，动态距离变换方法和新的栅格方法 等。这些方法在概念上是简单的，同时也可以很容易地将点发生元扩展到线状发 生元和面状发生元。 v o r o n o i 图在工程实际中越来越明显的实用性促使研究人员成功地设计出多 种构造v o r o n o i 图的方法，其中，最为重要也最为普遍的方法就是利用d e l a u n a y 三角网来间接构造v o r o n o i 图。 3 1 2d e l a u n a y 三角网 1 9 0 8 年，g v o r o n o i 在数学上限定了每个离散点数据的有效作用范围，即 有效反映区域信息的范围，并定义了二维平面上的v o r o n o i 图，到了1 9 3 4 年， b d e l a u n a y 由v o r o n o i 图演化出了更易于分析应用的d e l a u n a y 三角网【4 3 】。从此， d e l a u n a y 三角网就成了被普遍接受和广泛应用的分析研究区域离散数据的有力 工具，被广泛应用于地学、力学、天文学等诸多2 维和3 维领域之内。 d e l a u n a y 三角网作为v o r o n o i 图的对偶图，其定义】如下：有公共边的 v o r o n o i 多边形为相邻的v o r o n o i 多边形，连结所有相邻的v o r o n o i 多边形的生长 中心所形成的三角网称为d e l a u n a y