（电力系统及其自动化专业论文）基于分区加权voronoi图的变电站选址研究.pdf

a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fe x p a n s i o na n dr e f o r mf o ru r b a np o w e rs y s t e m si n c h i n a ，u r b a np o w e rs y s t e mp l a n n i n gh a sb e c o m ea nu r g e n tw o r k s u b s t a t i o nl o c a t i n g a n ds i z i n gi sa ni m p o r t a n ts t e p ，w h i c hw i l la f f e c tm a n ya s p e c t sd i r e c t l y , i n c l u d i n g p o w e rl i n er o u t i n g ，n e t w o r ks t r u c t u r e ，p o w e rn e t w o r ki n v e s t m e n t ，p o w e rs u p p l y r e l i a b i l i t ya n do p e r a t i o ne c o n o m yl e v e l i n s t e a do ft h et r a d i t i o n a ls u b s t a t i o no p t i m i z a t i o np l a n n i n gm e t h o db a s e do n g e o m e t r yc o o r d i n a t e ，t h i sp a p e rp r e s e n t san o v e lw a yf o rs u b s t a t i o np l a n n i n gb a s e do n d i v i s i o n a lw e i g h t e dv o r o n o id i a g r a m , w h i c hc a no p t i m i z et h e q u a n t i t i e s ，s i z e s ， l o c a t i o n sa n dp o w e rs u p p l ya r e a so fs u b s t a t i o na c c o r d i n gt od i f f e r e n ts u b s t a t i o n s e c t o r d u r i n gt h ew h o l ep r o c e s s ，am a t h e m a t i cm o d e li sp r o p o s e dt og e tt h ec a p a c i t y c o m b i n a t i o n so fn e ws u b s t a t i o n s f i r s t l y , i nw h i c ht h eo p t i m u ms o l u t i o na n d s u b o p t i m u ms o l u t i o n sc a l la l s ob eo b t a i n e ds i m u l t a n e o u s l yb yi n t e g e rp r o g r a m m i n g t ot a k ea c c o u n to ft h ea f f e c t i o n s ，as u b s t a t i o n o p t i m i z a t i o nm e t h o db a s e do n d i v i s i o n a lw e i g h t e dv o r o n o id i a g r a mi sp r o p o s e dt oa u t o m a t i c a l l yd e c i d et h ep o w e r s u p p l ya r e a so fe a c hs u b s t a t i o na n do p t i m i z et h el o c a t i o n so fn e ws u b s t a t i o n s t h i sp a p e ra l s om a k e sac l e a rd i v i s i o no ft h es e c t o r sa n dab e t t e rd e f i n i t i o no ft h e w e i g h i n gc o e f f i c i e n t t h er e s u l t sv e r i f yt h a tt h ep r o p o s e dm e t h o ds a v e so p e r a t i o na n d l i n e l o s sc o s t s f u r t h e r m o r e ，i ti m p r o v e st h es c i e n t i f i c a i n e s sa n da d a p t a b i l i t yo f s u b s t a t i o no p t i m i z a t i o np l a n n i n gr e s u l tw i t hs i g n i f i c a n te n g i n e e r i n gp r a c t i c a b i l i t y k e yw o r d s ：s u b s t a t i o no p t i m i z a t i o np l a n n i n g ，w e i g h t e dv o r o n o id i a g r a m ， d i v i s i o n a lw e i g h t e dv o r o n o id i a g r a m ，a l t e r n a t i v el o c a t i o na l l o c a t i o n ，i n i t i a ll o c a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨注盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者繇甭芬粉签字嗍洲年石月严日 学位论文版权使用授权书 本学位论文作者完全了解丞鲞盘堂有关保留、使用学位论文的规定。 特授权墨盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 躲孝弓翩躲，诊物 签字日期：厶彳年月严日签字日期：力“年二月厂日 第章绪论 1 1 引言 第一章绪论 电力工业是国民经济的重要部门之一，电力系统要满足日益增长的电力需求 必须不断扩大其规模，合理地进行电力系统规划可以使电力企业获得巨大的经济 利益。随着电力企业改革的逐步深入，提高规划质量对电力企业具有重大的意义。 根据i e e e 的c i g i 也c i i 也d 联合工作组的新分类标准，城市电网分为次输电 网( 电压为2 5 k v - - - , 2 7 5 k v ) 和配电网【lj 。我国将高压配电网的电压等级分为3 5 k v 、 6 6 k v 、1 1 0 k v 和2 2 0 k v ；中压配电网的电压等级分为2 0 k v 和1 0 k v ；低压配电网 的电压等级分为3 8 0 v 和2 2 0 v 【2 j 。城市电网规划是电力系统三大规划任务( 电力 系统能源与发电规划、输变电规划、配电系统规划) 之一。 按照规划电压等级的不同，城市电网规划任务可分为城市高压配电网规划和 城市中低压配电网规划，它是在城网供电的电源点给定的前提下进行的，其内容 主要包括【3 】：( 1 ) 系统和空间电力负荷预测；( 2 ) 高压变电站、中压柱上变压器、 开闭所和配电站的优化规划；( 3 ) 配电网络规划和无功优化；( 4 ) 调度通讯及自 动化规划。 变电站是电网中交换电压、汇集和分配电能的设施，主要包括不同电压等级 的配电装置、电力变压器、控制设备、保护和自动装置、通信设施和补偿装置等。 变电站选址研究是电力系统规划工作的一个重要环节，在电网规划中起承上启下 的作用。它是在负荷预测的基础上进行的，其结果直接影响着未来电网的网络构 架、运行经济性以及无功电源的配置等问题，而且变电站对于整个电网的供电安 全和供电质量也起着重要的作用。 总之，变电站站址、站容优化规划是在小区负荷预测之后的一项十分重要的 基础的工作。合理地对变电站进行规划可以获得很大的经济效益，相反，变电站 规划失误则会给国家的经济建设和人民生活带来不可弥补的损失。 1 2 变电站规划简介 变电站选址是电力系统规划最重要的内容之一，尤其是考虑变电站规划项目 的整体成本时更是如此【4 1 。 在城市各小区负荷密度已知的基础上，确定出目标年待建变电站的地理位置 和容量，以满足未来负荷发展需要，同时使所需投资及运行费用最小。 第章绪论 由于新建变电站的地理位置、供电范围、容量及投入时间均未知，各个变量之 间相互影响、相互制约，它们的组合方案数非常巨大，再加上还必须综合考虑变 电站的进出线走廊以及地形、交通、防洪、地质等条件，所以整个问题变得十分 复杂。 变电站站址规划意义重大，变电站位置的优劣对电力系统网络结构起决定性 作用，良好的变电站位置，可以保证电力系统网架强健，且不容易受到小干扰的 影响，从而能够经济、稳定地运行；变电站位置的优劣对电力企业的服务质量有 重要的影响；变电站位置对馈线系统( 或下级输电系统) 有较大影响。只有变电 站位置决策正确，才能保证电力系统长远的经济性。 变电站选址要遵循以下原则： ( 1 ) 变电站的选址在考虑与现状变电站( 包括2 2 0k v 与1 1 0k v 变电站) 的 结合情况下，尽可能接近主要用户，靠近负荷中心。 ( 2 ) 符合城市总体规划用地布局要求； ( 3 ) 考虑对周围环境和邻近工程设施的影响和协调，如：军事设施、通电台、 电信局、飞机场、领( 导) 航台、国家重点风景旅游区等； ( 4 ) 应避开易燃、易爆区和大气严重污秽区及严重盐雾区； ( 5 ) 便于各级电压线路进出线的布置，进出线走廊与站址同时决定； ( 6 ) 考虑安全运行，站址地势应高而且尽可能平坦，不宜设于低洼地带，以 免洪水淹没或涝渍影响，满足防洪标准要求：2 2 0k v - - 一5 0 0k v 变电站的站址标 高，宜高于1 0 0 年一遇的洪水位；3 5k v - - - 1 l o k v 变电站的站址标高，宜高于5 0 年一遇的洪水位； ( 7 ) 应满足抗震要求：3 5 k v 一- - 5 0 0 k v 变电站所抗震要求，应符合国家现行标准 2 2 0 2 5 0 k v 变电所设计规程和3 5 1 1 0 k v 变电所设计规范中的有关规定； ( 8 ) 应有良好的地质条件，避开断层、滑坡、塌陷区、溶洞地带、山区风口 和易发生滚石场所等不良地质构造； ( 9 ) 交通运输方便，适当考虑职工生活上的方便。 1 3 国内外变电站规划发展现状 对于变电站位置、容量和供电范围的优化问题，国内外的些学者已进行了 广泛和深入的研究，并结合定位理论的研究提出了许多模型和方法。 传统的规划方法是以方案比较为基础，由有关专家指定若干可行方案，通过 技术经济比较进行决策。然而参加比较的方案往往由规划人员凭经验提出，不可 避免地包含着很多主观因素，带来了一定局限性。近三十年来，随着计算机技术 第一章绪论 和优化理论的迅速发展，许多电力系统专家致力于应用计算机技术来解决电网规 划问题，从而大大提高了规划的速度和质量，给传统的电网规划工作注入了新的 活力。 文献 5 提出了一种交互式的分支定界一运输模型来解决变电站选址问题和 投入时间的计算模型，虽然该模型能够方便地与规划设计人员进行对话，取得了 一定的成果，但是随着问题规模的扩大，分支定界法的计算时间呈指数增长，它 还不能确定变电站的地理位置。因此，该模型还不能解决大规模的工程实际问题。 后来经过人们的不断完善，采用了自动估计负荷转移费用的方法【6 】，提高了计算 精度，但是，也相应地增加了计算时间。文献 7 以负荷距最小为目标函数，以 运输问题为基本求解方法，提出了一种新的变电站位置和容量的数学优化技术， 但是，由于该方法要求有候选的变电站站址，因而降低了实用性。文献 8 】中w i l l i s 和a n a t o o s 将数字图像处理技术应用于变电站选址问题，提出了一种新颖的计算 模型，但是该方法只适用于新建地区( 即没有已有变电站) 的变电站规划，而且 还不能对变电站的容量进行优化选择，同样存在局限性。文献 9 提出了解决配 电变电站的大小、位置、兴建时间及供电区域的模型，其优化目标函数中包括了 变电站不同费用分量，考虑了电压、容量、能量平衡和辐射状供电约束。该模型 的主要特点是考虑固定费用分量时没有引入o 1 决策变量，而且也没有将模型作 线性化的近似处理，因而使用了非线性规划方法中的广义既约梯度法作为优化方 法。文献 1 0 提出了一种求解变电站和馈电线位置的简单目标函数，但没有考虑 费用的时间特性，并忽略了网损对变电站和网络选择的影响。文献 1 1 】提出了一 种优化变电站和馈电线位置的改进方法，该方法以变电站和网络投资及网损的时 间特性之和为目标函数，考虑了近似的网络结构，并引入了电压降约束。文献 1 2 通过考虑负荷在不同变电站间转移的费用，采用负荷聚类的方法给出了确定变电 站位置的一种方法。文献 1 3 提出了待建变电站的容量分级问题，但没有考虑不 同容量变电站之间的费用差别问题。文献 1 4 提出了优化变电站容量和近似考虑 配电线路网损的模型和算法，但变电站的位置和数量必须人为给定。文献 1 5 和 1 6 将遗传算法用于变电站规划问题，但它们需要给定候选站址或候选站容，而 且由于遗传算法通常收敛速度较慢，局部寻优能力差，因此计算时间较长，解的 质量不高。文献 1 7 将变电站位置坐标的寻优视为一个非线性规划问题，由于难 ，以得到目标函数关于决策变量导数的解析表达式，故文中采用非线性优化技术中 的步长加速法求解。 近年来，专家系统l l 引、模糊理论【l9 等也都广泛地运用于变电站规划工作中， 这些方法虽然能够避免无待选站址方法所确定的变电站坐落在湖泊、街道、繁华 地段等不适宜建站的区域等问题，但从根本上来说，仍然属于有待选站址方法， 第章绪论 具有很大的局限性。 文献 2 0 首先提出了一种变电站规划大规模自动寻优的方法，该方法在小区 负荷预测的基础上，无需事先制定水平年候选变电站的位置和数量，可以通过大 范围的搜索，求得新建变电站的站址、站容和供电范围，满足了工程实际的要求。 该方法针对电网结构复杂、变电站数目较多、计算量庞大等特点，采用了试探组 合和平面多中位选址等算法，可以在工程允许的计算精度下，求得较好的方案， 大大降低计算工作量，并已用于天津大学开发的城市电网规划计算机辅助决策 系统( 简称c n p 2 5 ) 软件包中，完成了国内多个城市和地区的城市电网优化规 划任务【2 l 】。 文献 2 2 是在文献 2 0 研究基础上，提出了一种更加完善的，考虑投资影响 的优化模型，并采用三角连续分割算法( t s p m ) 来解决组合优化子问题，并引 入加速因子改善了旋址计算的收敛特性，更好的满足了工程实践的要求。 上述方法都是基于坐标几何的变电站选址优化求解方法，考虑到v o r o n o i 图 建立了一种并不依赖于坐标几何的空间邻近模型，在解决空间剖分问题上具有一 定的优势，具有划时代的意义。文献 2 3 、 2 4 禾u 用d e l a u n a y 三角网的影响范围 特性、最大空心圆特性和局部动态特性，可以保证变电站位于负荷中心，实现新 增变电站的自动优化选址和各变电站供电范围的最佳划分。但是，该方法是在假 设负荷均匀分布，新增变电站的容量和台数一定的前提下提出的，没有考虑到供 电范围与变电站负载率的合理性，只解决了变电站优化规划的一个子问题。 文献 2 5 运用普通加权v o r o n o i 图，通过权值来改变常规v o r o n o i 图的性质， 从而对变电站选址进行优化。但是，该方法只考虑到了不同变电站的v o r o n o i 图 扩展速度因素，没有考虑到同一变电站因为扇区负荷密度等因素差异形成的不同 方向( 扇区) 的不同扩展速度问题，而这将对变电站供电范围的划分产生重要影 响，所有文献 2 5 1 仍然具有一定的局限性。 分区加权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 ，图中则是把每个生成元的周围分为若干个扇区，并给每个扇区赋以实数权重值 ( 同一生成元的不同扇区的权重值可以相同，也可以不同) 。文献 2 6 】将分区加 权的思想应用在移动通信系统中，解决基站天线发射的信号的覆盖问题。本文认 为，分区加权v o r o n o i 图方法具有更好的工程实用性。 第一章绪论 1 4 本文工作 针对变电站优化规划方法中存在的不足，本文在文献 2 5 的基础上进行了如 下方面的研究工作：提出了一种基于分区加权v o r o n o i 图的变电站选址规划方法。 方法流程为：首先给出了一种确定新建变电站容量组合的数学模型，并采用优化 技术同时得到其最优解和几组次优解，进而产生初始站址。最后，通过对v o r o n o i 图进行分区加权来进行变电站供电范围的整体优化，并确定新建变电站站址。 特别说明上述方法流程中的几个重要环节。本文综合考虑了变电站不同扇区 方向的不同情况，对扇区作出了明确划分、完善了权重定义和确定了清晰的权重 计算流程。 本文的结构：第二章主要介绍分区加权v o r o n o i 图的基本性质和原理、平面 中位问题、a l a 算法的基本原理和决策步骤以及“0 1 ”整数规划思想；第三章 介绍基于分区加权v o r o n o i 图的变电站优化规划方法和算法流程；第四章通过详 细的算例进一步对提出的方法进行分析说明和验证；第五章为总体结论和研究工 作的展望。 第二章理论基础 2 1 基本v o r o n o i 图 第二章理论基础 1 v o r o n o i 图的历史 v o r o n o i 图的历史相当古老，许多自然现象都可用v o r o n o i 图描述。早在1 6 4 4 年，d e s c a r t e s 就使用了类似v o r o n o i 图的结构对太阳系进行分割川。第一个有关 v o r o n o i 图的概念是在p e t eg u s t a v l e j e u n e ( 1 8 0 5 1 8 5 9 ) 与g e o r g e sv o r o n o i ( 1 8 6 8 一 1 9 0 8 ) 著作里出现的。数学家d i r i c h l e t 和v o r o n o i ( 1 9 0 7 ，1 9 0 8 ，1 9 0 9 ) 在正有限二次 型的研究中正式介绍了v o r o n o i 图的概念，d i r i c h l e t 论述了二维和三维的情况，而 v o r o n o i 论述了m 维的情况。从那以后，人们开始考虑在空间中放置一系列点由欧 氏距离决定平面分割的结构，并称之为d i f i c h i e t 音l j 分或是v o r o n o i 图【2 7 】。 v o r o n o i 图首先被应用在晶体学的领域中。1 9 世纪末，2 0 世纪初，德国和俄 国的观察家在气象学上使用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 图的进一 步发展。在1 9 7 5 年，s h a m o s 和h o e 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 图、加权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 图理论成 功地解决了计算机图形学中找最近点，求最短路径，求n 个点地凸包，求最小数 等问题 2 8 - 2 9 1 。因此，v o r o n o i 图在与几何信息相关的许多领域，诸如：地理空间 设施选址分析方面、生态研究、城市规划以及优化配置等许多领域有着广泛的应 用。 2 邮局问题与v o r o n o i 图 邮局问题是v o r o n o i 图的典型模型，该问题是：某城市有n 个邮局，对于一个 新建的楼房，那个邮局距其最近? 用计算几何解决邮局问题的做法是，在平面上 用点表示邮局的位置，在每两个点之间画出它们的垂直平分线，从而将平面分成 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 图的定义。 第二章理论基础 3 v o r o n o i 图的定义 设定平面上n 个点构成的集合s = ( p ，p ：，p 。) ，则由公式 2 1 所给出的对 平面的分割，称为以p = 1 ，2 ，1 ) 为生成元( 或母点) 的v o r o n o i 医 3 1 】。 矿( b ) = a pd ( p ，只) d ( p ，p 朋( f - l ，2 ，) ( 2 - 1 ) j 幽 其中d ( p ，p i ) 为p 和p ，的e u c l i d 距离，区域v ( p i ) 称为p i 的v o r o n o i 区域。 显然，区域v ( p ，) 是由平面上所有到p ，的距离比s 中其它点的距离都小的点组成 的集合。 图2 - 1 ，2 - 2 给出了两个v o r o n o i 图的实例，图中黑点为生成元，折线为v o m o i 边。为方便，也有人将“v o r o n o i 图”简称为“v 图”，类似的将“v o r o n o i 边( 点， 区域) ”简称为“v 边( 点，区域) ”等。 平面上的v o r o n o i 图可以看是点集p 中每个顶点p = 1 ，2 ，聆) ，以相同的速 度向外扩张，直到彼此相遇为止而在平面上形成的图形。这样，除最外层的点形 开放的区域外，其余每个点都形成凸多边形( 如图2 1 、2 - 2 所示) 。 图2 1 常规v o r o n o i 图( 1 ) 图2 - 2 常规v o r o n o i 图( 2 ) 第二章理论基础 这一描述与变电站的定位及供电区域的划分具有极大的相似性。其数学定义 可以描述为：v o r o n o i 图可以理解为对空间的一种分割方式( 一个v o r o n o i 多边 形内的任意一点到本v o r o n o i 多边形中心点的距离都小于到其它v o m n o i 多边形 中心点的距离) ，也可以理解为对空间的一种内插方式( 空间中的任意一个未知 点的值都可以由距离它最近的已知点，即采样点的值来代替) 。这里的v o r o n o i 多边形的中心点其实就是包含于该多边形内的离散点。 4 v o r o n o i 图的性质 v o r o n o i 虱具有许多有趣而惊人的数学特性【3 2 ，如有效作用范围特性( i n f l u e n c e r e g i o n ) 、侧向邻近特性( 1 a t e r a la d j a c e n c y ) 、线形特性( 1 i n e rb e h a v i o r ) 、最大空心圆特 性( l a r g e s te m p t yc i r e l e ) 、局部动态特性( 1 0 e a ld y m m i cc h a r a c t e r i s t i c ) 、与d 三角网对偶 ( d u a lo f d e u a l n a yt r i a n g u l a t i o n ) 等，这些特性为研究解决地理信息空间分析、地学、 计算机科学和数学等领域中一些问题提供了有力的工具。与本文变电站选址优化内 容相关的主要有以下三个性质： 1 ) 空心圆特性 每个v o r o n o i 结点都是三条v o r o n o i 边的交点。若过v 图中的任意结点g ，作 一圆c ，且使c i 过结点q ，所在的v o r o n o i 边所对应的所有顶点( 3 个或更多) ， 则c ，内不包含点集p 中任何其它顶点，是一个空圆：其中，半径最大的空圆g ( c 。，) 称为最大空圆( 如图2 - 3 所示) 。 这一特性为新增变电站选址奠定了基础。在电力系统规划中，空心圆得区域 没有变电站，是变电站的“真空区”，也正是电网中供电能力相对较薄弱的区域， 在电力系统规划中应该有意识的优先考虑加强这些地区的电网建设。空心圆的圆 心在计算几何中被称为生长点，是新建变电站的待选站址。 图2 - 3v o r o n o i 图的空心圆特性 第二章理论基础 2 ) 局部动态特性 对v o r o n o i 多边形来说，应用欧拉规则( e u l e r sr e g u l a t i o n ) 表明，删除或 增加一个顶点，一般只影响不多于6 个左右的相邻空间目标，这一特点符合变电 站选址研究的工程实际特点，并且在第三章的算法思想中得到体现。 3 ) 与d e l a u n a y 三角网对偶 若一个v o r o n o i 图的n 个空间【j sn s 。o ) 生长目标满足非线性条件，将其中 具有公共v o r o n o i 边顶点对相连，则可得到种新的铺盖，如图2 4 所示。如果 全是三角形的话，则称之为d e l a u n a y 三角网。 图2 4v 图及其对偶d 三角网 结合上述图2 4 ，并经过分析可知，d e l a u n a y 三角形与v o r o n o i 多边形是非 退化的( n o n d e g e n e r a t e ) ，则d e l a u n a y 三角形与v o r o n o i 多边形的边也是一一对 应的。 与其它三角网相比，d e l a u n a y 三角网具有如下性质： 1 ) c i r c l e 准则：任意一个d 三角形的外接圆内不能包含点集中的任何其他点。 2 ) 最大最小角性质：在相邻两个d 三角形构成的凸四边形中，在交换凸四 边形的对角线之后，六个内角的最小者不再增大，三角网中所有三角形的最小角 是最大的。 3 ) 最小权三角剖分特性：d 三危网的总边长是最小的。 第二章理论基础 2 2 普通加权v o r o n o i 图 1 加权v o r o n o i 的定义 3 3 】 加权v o r o n o i 图是常规v o r o n o i 图的一种较常用的扩展形式。给定平面上1 1 个点的点集p ，p = p l ，p 2 ，p 。) ，3 n a 0 ，彬( i = l ，2 ，n ) 是给定的n 个正实 数。 则： 咻伊阳朋l 掣掣小1 ，2 ，棚川j ) ( 2 - 2 ) 其中 d b ，p ，) ：点p ，和p 间的欧氏距离，p ，p ，i j ，f ，j 1 ，2 ，1 ) ； x ：为平面上任意点。 将平面分成咒部分，由k ( p i ，彬) ( 江1 ，2 ，”) 确定的对平面的分割称为点上 加权的v o r o n o i 图，称形为p ，的权重，如图2 5 所示。当彬= = = 形时， 即常规v o r o n o i 图是加权v o r o n o i 图在权重相等时的特例。 图2 5 加权v o r o n o i 图 2 加权v o r o n o i 图的分类及意义 加权v o r o n o i 图的加权方式有多种，最常见的有顶点加权和路径加权两种。 顶点加权主要考虑顶点的作用能力大小及其对顶点有效作用范围所产生的影响， 对应于变电选址中节点供电能力的约束，即变电站容量的约束。变电站的主变容 量有大有小，所带负荷能力也就不同，对周围供电区域的影响能力也就有强有弱， 应该考虑这个因素而根据变电站供电能力的大小赋以不同的权重。本文的重点即 为根据变电站不同扇区划分赋予不同的权重的分区加权v o r o n o i 图。 第二章理论基础 路径加权主要考虑每条通路的权重影响，对应于变电选址中考虑地形、出线 走廊等约束。由于各条输电线所遇地形不尽相同，电气距离与空间距离的相差也 不同，路径加权算法就是要计及不同路径对每条输电线路所造成的距离影响，这 实际是障碍v o m n o i 图的一种。 ( 注：本文虽然不涉及路径加权，但作者仍然在文末对路径加权与分区加权 的结合作了展望，希望读者能继续从事这方面研究) 。 2 3 分区加权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 图。 分区加权v o r o n o i 图是在加权v o m n o i 图的基础上扩展而成的。在加权 v o r o n o i 图中，我们给每个生成元都赋以一个权重值，而在分区加权v o r o n o i 图 中则是把每个生成元的周围分为若干个扇区，并给每个扇区赋以实数权重值( 同 一生成元的不同扇区的权重值可以相同，也可以不同) 。该图可用来研究变电站 选址规划中考虑不同扇区方向的不同情况。 2 3 1 分区加权v o r o n o i 图的定义 给定平面上n 个点的集合s = p lp 2 ，p 。 ，对每个生成p i ( i = 1 ，2 ，n ) ， 以只为原点，水平向右为坐标轴的正向，建立极坐标系，将生成元只周围区域分 为m i 个扇区，以0 = ( = 1 ，2 ，m ) 为扇区分界线， 其中， 0 l a i 2 o ( ，) ，从k 个容量等级中确定p 个设施的容量s i 和位置( _ ，y ，) ， i = 1 ，2 ，p ，使得各设施的建设费用及运输费用之和最小，记为： 1 1 1 i n c ：pe ( s ) + p g m 扩s t g ，( s ) ，u pj ；= j ，n pj j ：g ，j 2 1 忙，“， ， ，u 。1h ( 2 1 6 ) 式中 c k ( s ) 。容量点的设施的建设费用； j ；：设施i 服务范围内顾客的集合；后= 1 ，2 ，k 。 第二章理论基础 2 5a l 算法 本节主要介绍与本文提出的基于分区加权v o r o n o i 图变电站选址定容规划方 法相结合的交替定位分配方法( a l t e r n a t i v el o c a f i o na n da l l o c a t i o n ) ，不仅是求解 平面p 中位问题的较好方法，同时也很适合变电站分区加权v o r o n o i 图求解。 交替定位分配算法证明了目标函数既不是凹的也不是凸的，并存在着许多局 部最优解。这一结论也得到了许多学者的论证。 a l a 算法的进行步骤是： 第一步：分配步骤 对于给定的p 个设施的位置( ，略) ，i = 1 ，2 ，p ，确定顾客的分配集合 ，把各顾客分配给与它邻近的设施。 第二步：选址步骤 分配步骤中己将顾客分成了p 个组，对每一组用平面单中位问题求解最优的 中位点位置( 1 ，y 善1 ) ，i = 1 ，2 ，p 。 以上两步交替进行，当前后两次迭代的目标函数值之差小于之前给定的精度 时就停止。 a l a 法的求解是一种所谓单调下降的收敛过程，即应用这种方法每做一次循 环，所得解总比前一次循环求得的解要好一些，或者至少一样好。当无法使目标 函数下降时，停止计算。a l a 法的分配步骤是一个典型的运输问题，可以采用运 筹学的经典方法求解；而选址步骤就是求解多个平面单中位问题，可以采用数学 优化方法中的迭代方法求解。 a l a 法求解平面p 中位问题时的优点是简单快速；缺点本质上是一种局优算 法，其最终解依赖于初始位置的选择，并且不能保证所得解接近全局最优解 3 7 。 a l a 法依赖于初始位置的选择，表现在三个递进的层面上： 各设施的迭代初始位置不同时，一般会收敛到不同位置；当设施容量不 同时，由于迭代过程中各设施位置上的相对关系一股不会发生变化，将导致最终 解依赖于不同容量设施间的初始相对位置；当存在已有设施时，由于迭代过程 中新建设施和已有设施位置上的相对关系般也不会发生变化，将导致最终解还 依赖于新建设施和已有设施间的初始相对位置。 2 6 “0 1 ”整数规划 i 整数规划 任何具有极大和极小目标的决策问题都可以归结为一个整数最优化问题，其 第二章理论基础 中( 可量化) 决策变量必须假定为非分数或离散值。整数规划对解决实际问题的 重要性逐渐在运筹学领域令人信服地显示出来。 整数规划领域中多数研究集中在线性函数，为标准化起见，线性问题被写成 【3 8 】： m a x ( o ，m i n ) z = c ，z ， ( 2 - 1 7 ) n a o x j + s j = b i ，i ms j 乞 2 ， j e n s j 0 ，i m x ，0 n 工，i n t e g e r ，icn 其中 s ，：松弛变量 g ，：线性函数，f o ) u m 如果约束本来就是等式的情况下，则不需要辅助的松弛变量。 2 0 - 1 型整数规划的定义 o 1 型整数规划是整数规划的特殊情形，它的应用很广，如土木工程系 的最优工程配置问题，城建规划中的居民点、给水点、加油站和商业网点的最优 布局问题，均可应用0 1 型整数规划求得最优解。 0 - 1 型整数规划变量薯仅取值0 或者1 ，这时五称为0 1 变量，或者二进制 变量，它的一般形式为： m a x ( m i n ) z = c l 玉+ c 2 x 2 + + q 毛 a 1 1 x 1 + 以1 2 恐+ + 口l 。x n ( = ，) 6 l a 2 1 x 1 + 口2 2 恐+ + 口2 。( = ，) 6 2 a m l x l + 口。2 x 2 + + 口。，吒( = ，) 五，x 2 ，x n = 0 ，1 ( 2 1 8 ) 0 1 型整数规划问题的应用非常广泛，它是运筹学中的一个重要的问题。关 于它的算法很多，如穷举法，隐枚举法等。 3 0 1 型整数规划问题的算法 步骤 步骤 步骤 步骤 行解； 生成给定问题的变量取值为0 或1 的所有可能组合； 利用每一约束条件剔除非可行解( 保留可行解) ； 生成剩余的解； 重复进行步骤2 、3 ，我们可以排除所有的非解，从而得到问题的所有可 第二章理论基础 步骤5 ：比较各可行解对应的目标函数值，进而得到最优解。 在本文第三章中，“o 1 ”整数规划应用于确定新建站容量组合的这一子问题。 2 7 小结 本章主要介绍本文主要应用的三大理论基础：分区加权v o r o n o i 图、a l a 算 法、“o - l ”整数规划。分区加权v o r o n o i 图适用于各发生元不同扇区扩展速度有 较明显差别情况下的空问剖分，利用权重来反映各种因素对变电站供电范围的影 响。a l a 算法直观简单，易于实现，计算速度快，是求解选址问题的一种较高 效的方法。“0 1 ”整数规划应用于确定新建站容量组合的这一子问题。 第三章基于分区加权v o r o a o i 图的变电站选址研究 3 1 引言 第三章基于分区加权v o r o n o i 图的变电站选址研究 确定变电站的位置与容量是电力系统城市电网规划工作的一个重要环节，其 结果直接影响着未来电网的网络结构、供电质量和运行经济性。 变电站的优化选址中，其主要目标是使变电站的分布合理，不单要合理充分 的利用变压器的容量，保证电网的供电可靠性，还要考虑变电站与