（电力系统及其自动化专业论文）变电站选址定容优化规划.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 l lu r g e n tw o r k 。i np l a n n i n gt h e u r b a np o w e rs y s t e m s ，i ti sa ni m p o r t a n ts t a g eb e t w e e nl o a df o r e c a s ta n dn e t w o r k p l a n n i n gt oa c q u i r eb o t ht h el o c a t i o n sa n ds i z e sf o rs u b s t a t i o n s i t sr e s u l tw i l la f f e c t m a n ya s p e c t sd i r e c t l ys u c ha sp 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 k i n v e s t m e n t , o p e r a t i o ne c o n o m yl e v e la n dp o w e rs u p p l yr e l i a b i l i t y f o c u s i n go nt h el o wq u a l i t yo ft h es o l u t i o nd e h v e df r o me x i s t i n gm e t h o d s ，a m o r ee f f i c i e n to p t i m a lp l a n n i n gm e t h o df o rs u b s t a t i o nl o c a t i n ga n ds i z i n go nt h e e n g i n e e r i n gb a c k g r o u n di sp u tf o r w a r di nt h i st h e s i s ，w h i c hd i v i d e st h ep r o b l e mi n t o t w os u b p r o b l e m s ，i e t h es o n r c e sl o c a t i n go n ea n dt h ec o m b i n a t i o n a lo p t i m i z a t i o n o n e s of a r , t h ec o m m o ns o l u t i o n st ot h ep r o b l e mo fs o u r c e sl o c a t i n ga r ea l t e r n a t i v e l o c a t i o n - a l l o c a t i o n ( a l a ) m e t h o da n dg e n e t i ca l g o r i t h m ( g a ) 1 1 圮m e t h o do f a l ah a st h ea d v a n t a g e so fs i m p l ep r i n c i p l ea n df a s tc o m p u t a t i o n ；b u t 嬲al o c a l o p t i m i z a t i o na l g o f i t h m , i tc a n n o tg u a r a n t e et h eq u a l i t yo f t h es o l u t i o nt h a tv a r i e sw i t h t h ec h o i c eo ft h ei n i t i a ll o c a t i o n a l t h o u g hg ap r o v i d e saw a yt or e a c ht h eg l o b a l o p t i m a ls o l u t i o n , h o w e v e r , i ts u f f e r sf r o ms l o wc o n v e r g e n c e - - a sm a n yf u t i l es t e p s d u et ot h ep o o rl o c a ls e a r c h i n ga b i l i t y b e s i d e s ，i ns o l v i n gt h es o u r c e sl o c a t i n g p r o b l e m , c r o s s o v e ro p e r a t o ro fo r d i n a r yg a w i l lm a k et h ec h i l d r e nl o s es o m ef i n e c h a r a c t e r i s t i c so ft h e kp a r e n t s t h u st h ee f f i c i e n c yo fg ai sm t h e rp o o ra si ti sq u i t e u n c e r t a i nf o rt w oe x c e l l e n ti n d i v i d u a l st op r o d u c eac h i l dw i t ha l le q u i v a l e mg o o d q u a l i t y t o a v o i ds u c hd i f f i c u l t i e s ，t h et h e s i s f i r s t l yd e s i g n s as p e c i a l i z e d p a r t h e n o - g e n e t i ca l g o r i t h m ( p g a ) t h a ti ss u i t a b l et ot a c k l et h es o u r c e sl o c a t i n g p r o b l e m s e c o n d l y , t h et h e s i sc o m b i n e st h ec o m p l e m e n t a r yp g a a n da l at oi m p r o v e t h ec o m p u t a t i o ne f f i c i e n c y h y b r i dp g ab a s e do na l am e t h o da n da p p r o x i m a t e h y b r i dp g a b a s e do na l am e t h o da r ep r o p o s e dt od e a l 埘t l lt h es o u r c e sl o c a t i n g p r o b l e m so f s m a l l - s c a l ea n dl a r g e - s c a l er e s p e c t i v e l y a st h es o u r c e sl o c a t i n gs u b - p r o b l e mi ns u b s t a t i o np l a n n i n gi so fl a r g e s c a l e e n g i n e e r i n ga t t r i b u t e ，t h ep r o p o s e da p p r o x i m a t e dp g ai s e f f e c t i v ei ns u c h c i r c u m s t a n c e s i na d d i t i o n ，s i m u l a t i o n e x a m p l e ss h o wt h a t t h ec o m b i n a t i o n a l o p t i m i z a t i o ns u b - p r o b l e mi sn o n - c o n v e xa n dn o n c o n c a v e ，t h u st h eb r a n c ha n d b o u n d ( b & b ) t e c h n i q u ei sa d o p t e di nt h i sp a p e rt oo b t a i no ra p p r o x i m a t et h eg l o b a l o p t i m a ls o l u t i o n t oi m p r o v et h ee f f i c i e n c yo ft h eb & bt e c h n i q u e ，s o m eh e u r i s t i c p r i n c i p l e sa r ep r o p o s e dt oc u tt h o s eb r a n c h e st h a tm a yg e n e r a t eg l o b a lo p t i m i z a t i o n s o l u t i o n 诵ll o wp r o b a b i l i t y f i n a l l y , t h es o r w a r ep a c k a g ed e v e l o p e db a s e do nt h i sm e t h o di sa p p l i e dt ot h e h i 曲v o l t a g es u b s t a t i o np l a n n i n gp r o c e s sf o ra na c t u a lc i t y t h er e s u l t sv e r i f yt h a tt h e p r o p o s e da l g o r i t h mp o s s e s s e ss 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 、析t hf a s ts p e e d a n d1 2 【g hs o l u t i o nq u a l i t y k e yw o r d s ：o p t i m a lp l a n n i n gf o rs u b s t a t i o nl o c a t i n ga n ds i z i n g , s o u r c e s l o c a t i n gp r o b l e m ，a l t e r n a t i v e l o c a t i o n - a l l o c a t i o na l g o r i t h m ，p a r t h e n o g e n e t i c a l g o d t h m , b r a n c ha n db o u n dt e c h n i q u e ，c o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盎垄盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：、；如永任 签字日期：上。口石年月脂日 学位论文版权使用授权书 本学位论文作者完全了解盘盗盘堂有关保留、使用学位论文的规定。 特授权垂洼盘璺可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：3 卜永诬 签字日期：删z 年月3 日 i 导师繇幺延磊 签字日期：2 0 0 彳年月，日 天津大学硕士学位论文 第一章绪论 1 1 城市电网规划概述 第一章绪论 1 1 1 城市电网规划的内容和目的 根据i e e e 的c i g r e c i r e d 联合工作组的新分类标准，城市电网分为次输电 网( 电压为2 5 k v 2 7 5 k v ) 和配电网【l j ，我国也称为高压配电网( 电压为3 5 k v 、 6 6 k v 、l l o k v 和2 2 0 k v ) 、中压配电网( 电压为2 0 k v 、1 0 k v ) 和低压配电网( 电 压为3 8 0 v 、2 2 0 v ) 1 2 j 。城市电网规划是电力系统三大规划任务( 电力系统能源与 发电规划、输变电规划、配电系统规划) 之一。 按照规划电压等级的不同，城市电网规划任务可分为城市高压配电网规划和城 市中低压配电网规划，它是在城网供电的电源点给定的前提下进行的，其内容主要 包括【3 】： ( 1 ) 系统和空间电力负荷预测； ( 2 ) 高压变电站、中压柱上变压器、开闭所和配电站的优化规划： ( 3 ) 配电网络规划和无功优化； ( 4 ) 调度通讯及自动化规划。 按规划时间的不同，城市电网规划分为近期( 1 5 年) 、中期( 5 1 5 年) 和 长期( 1 5 3 0 年) 规划。长期规划属于战略规划，它主要决策城市电网发展的重 大问题和发展方向( 如建立新的电压等级、确定新的城市电网电源点、论证规划期 末的城市需电量以及城市可能发生的改造和扩展方向等) ，为中期和近期规划制定 目标。中期和近期规划属于战役规划，主要为长期规划的任务和目标如何实施确定 时间表。长期规划要求中期和近期的城市电网建设和改造是长期电网发展目标的一 部分，并保证近期和中期投入的设备在规划期间不发生拆除现象。 城市电网建设和改造的目的是在满足城市电力需求的前提下，保证电网扩展和 运行的经济性与安全性。 1 1 2 新形势下城市电网规划的意义和挑战 城市电网既是电力系统的主要负荷中心，又是城市基础设施建设的重要组成部 分，其建设、改造以及运行的经济性和安全性直接影响到整个电力部门的经济效益 和广大电力用户的供电质量。在城市电网的建造、改造过程中，对其进行科学规划 天津大学硕士学位论文第一章绪论 和设计可以获得巨大的经济效益和社会效益。这主要体现在以下几个方面： ( 1 ) 城市电网的薄弱导致有电送不出和供电质量差的问题。在我国历史上， 长期存在着严重的电能供需矛盾。因此，在电力系统建设中出现了“重 发、轻送、不管用”的现象，这造成了我国城市电网普遍比较薄弱。在 当前电力供需趋于缓和后，城市电网有电“送不进、落不下、用不上” 的矛盾充分暴露出来，具体体现为：电网建设滞后于城市建设，网络供 电能力不足，缺乏事故下的互带能力，用电高峰期间设备过负荷严重， 变电站个数偏少，位置不尽合理，线损率偏高及电压质量难以保障等。 这些问题随着城市负荷的快速增长而变得日益突出，不仅给电力企业和 众多的电力用户造成了巨大的经济损失，而且影响了人民的生活质量， 阻碍了国民经济的发展。造成这些问题的重要原因是目前配电网建设、 改造过程中缺乏科学规划和不合理建设等。 ( 2 ) 城市配电系统工程投资巨大，发达国家配电工程投资占整个电力系统投 资的5 3 ，而在各区域( 或城市) 电力公司中配电系统投资通常占预 算的6 0 ，配电系统的运行费用占总运行费用的2 0 n 。在我国，“八 五”以来配电系统工程投资占整个电力系统投资的3 1 5 ，最近几年国 家更是投入上千亿元资金对城乡电网进行重点改造。如何合理有效地使 用这大量资金，以取得最大的经济和社会效益是决策者和执行者都十分 关心的问题。从另一个角度讲，如此大量的资金，即使节约很小的比例， 其绝对数量也是巨大的。 ( 3 ) 目前我国城市电网线损率偏高，1 9 9 5 年达8 7 7 ，1 9 9 7 年为8 2 0 1 s l ， 而日本，德国、法国等国家约为5 6 ，和这些国家相比我国的城市电 网线损率大约高出2 3 个百分点，按照1 9 9 7 年水平计算我国相当于多 损耗了l g o 亿k w h 电量。将如此惊人的电能损耗降下来，使有限的电 能发挥更大的作用，乃是城市电网优化规划的重要任务之一。 由上述材料可见，为了提高配电网安全性和可靠性，满足国民经济发展对电力 的需求，改善我国配电系统的现状，研制高效、方便、实用的具有智能决策功能的 城市配电网自动化系统、短期运行优化规划系统和中长期规划系统是合理利用基本 建设投资、提高配电网运行经济性、提高供电质量和供电安全性、可靠性的基本科 学手段。 进入新世纪后，城网规划面临着新的形势，其地位和目的发生了重大变化，主 要表现在以下两个方面： ( 1 ) 外部环境的变化。新世纪中国城市发展逐渐与国际接轨，城市发展总体 规划的编制法制化成为潮流和必然趋势。最近几年的新形势表明，沿海 天津大学硕士学位论文第一章绪论 开放城市和内陆的部分经济发达城市，已制定和正开始制定城市发展总 体规划。与过去不同的是，此次城市总体规划由专家在科学论证与充分 听取公众意见的基础上编制，强调了城市的长远定位和各个功能区域的 最终布局，并上升为法律文件，正在和将在城市的发展过程中严格执行。 这样，作为电网规划依据的城市总体规划变得相对稳定和具体，为制定 比较稳定和详细的城市电网规划创造了条件。同时，城市的发展使得未 来的土地资源越来越稀缺，根据规划法规规定只有得到城市规划的认 可，电力系统的变电站用地和线路走廊才能得到保证。因此与城市规划 的配合成为目前城网规划中必须考虑的一个重要因素。 ( 2 ) 电力企业内部的变化。随着电力企业改革和现代企业制度的建立，电力 公司内部投资主体多元化，电网建设项目经费不再单独由国家投入，而 是由企业本身通过各种融资手段筹集，因此企业在电网规划建设的决策 中更加注重经济效益和投资回报，以充分保障投资人( 股东) 的利益。科 学的电网规划将是保证电网投资回报的前提，这一点更体现在规划对项 目决策的作用上。电网规划将产生大量的待建项目，而由于投资预算的 限制，只能允许建设部分项目。规划的失误将直接导致经济利益的损失， 例如不准确的空间负荷预测可能导致某些区域新建电力设施利用率低 下，而某些区域又无法满足负荷增长的情况。从经济学角度看，这样不 仅浪费了有限的投资，还付出了机会成本的代价。因此，电力公司不得 不把电网规划工作提到非常高的地位。 上述两方面的变化，既为城市电网规划工作创造了有利条件，又使之成为一项 迫切任务。因此，结合国情系统深入地研究满足实际要求的城市电网规划理论，开 发研制高效、方便、实用的具有计算机智能决策功能的城市电网规划计算机辅助决 策系统脚0 1 ，既是我国城市电网建设当前的迫切需要，也是今后长期发展的必要的 科学手段。 城市电网规划和设计工作是一项非常复杂而艰巨的工程系统( 经典的规划流程 见附录一) ，它具有规模大、不确定因素多且涉及领域广的特点嘲，在新形势下该 领域的研究面临着更多的困难和挑战。确定变电站位置与容量是城市电网规划中介 于电力负荷预测和网络结构优化之间的关键环节，其结果直接影响未来电力系统的 线路走线、网络结构、电网投资、运行经济性及供电可靠性，所以变电站选址定容 优化规划是一项十分重要的基础规划工作。这是一类复杂的大规模、非线性的混合 整数优化问题，至今未得到很好的解决。 鉴于上述城市电网规划领域面临的难题，本文对变电站选址定容问题进行了针 对性研究。 天津大学硕士学位论文 第一章绪论 1 2 变电站规划概况 1 2 1 变电站规划的内容 在城市各小区负荷密度已知的基础上，确定出目标年待建变电站的地理位置和 容量，以满足未来负荷发展需要，同时使所需投资及运行费用最小。由于新建交电 站的地理位置、供电范围、容量及投入时间均未知，各个变量之间相互影响、相互 制约，它们的组合方案数大得惊人，再加上还必须综合考虑变电站的进出线走廊以 及地形、交通、防洪、地质等条件，所以整个问题变得十分复杂。 1 2 2 变电站规划的意义 ( 1 ) 变电站位置的优劣对电力系统网络结构起决定性作用。良好的变电站位 置，可以保证电力系统网架强健，且不容易受到小干扰的影响，从而能 够经济、稳定地运行；反之，电力系统中的小扰动就有可能逐渐放大， 造成灾难性后果，甚至导致系统崩溃。 ( 2 ) 变电站位置的优劣对电力企业的服务质量有重要影响。相关法则规定变 电站站址应尽可能靠近负荷中心，否则部分负荷到变电站的馈线过长， 使电压质量降低。 ( 3 ) 变电站的位置对馈线系统( 或下级输电系统) 有较大影响。变电站是馈线 系统( 或下级输电系统) 的电源点，其位置对馈线系统( 或下级输电系统) 的费用有较大影响。如果变电站位置选的不合适，将导致输电线和馈线 更长，费用更高，而且出线走廊的选择也会随之出现问题。这种决策错 误即使可以修正，费用往往也很高。只有变电站位置决策正确，才能保 证电力系统长远的经济性。 1 2 3 变电站规划模型的分类 变电站规划模型的分类方法主要包括如下四种； ( 1 ) 按照规划阶段数的不同，变电站规划可分为单阶段优化和多阶段优化。 单阶段优化是针对将来某个特定年限( 规划目标年) 进行规划，因此只 需考虑建设方案满足规划目标年的要求，通过优化计算使其在目标年达 到最优，而不需考虑中间阶段的建设过程。多阶段优化不仅要确定规划 目标年的建设方案，还要合理安排中间各阶段的建设步骤，避免重复建 设以减小费用开支。为使计算量在工程实际允许范围之内，一般采用多 阶段的准动态技术来解决这一问题。第一步，在满足目标年负荷情况的 天津大学硕士学位论文 第一章绪论 条件下，采用优化技术确定目标年变电站站址和站容的最优方案；第二 步，将规划的中间年分成若干阶段，以目标年优化出的站址和站容作为 候选站址和站容，排列出满足相应要求的各阶段建设方案。 ( 2 ) 按照规划对经济性和可靠性指标的不同处理方法，变电站规划模型可分 为经济性指标模型和可靠性指标模型两种。经济性指标模型是从节省供 电方投资的角度出发，其目标函数只考虑经济性指标，如投资回收费用、 设备折旧维修费用和电能损耗费用等，而以可靠性指标，如一1 原则、 电压稳定问题等为约束条件。可靠性指标模型【9 】是从减少用户方停电损 失的角度出发，在目标函数中考虑投资费用、发电成本费用、网损费用 和停电损失费用等。但如何合理估算停电损失是规划中起步不久的一个 方面，还需要继续深入研究。 ( 3 ) 按照对不确定因素的不同处理方法，变电站规划可分为确定性规划和不 确定性规划( 又称为灵活规划) 。在变电站规划中，存在许多不确定因 素，主要有：未来负荷值、设备投入时间和利息率等。确定性规划以确 定的环境因素为基础，数学模型中的变量都具有确定的数值。灵活规划 计及各种不确定因素，并采用随机数、模糊数和区间数等形式来表示这 些因素，以使规划方案能适应未来环境的变化。但是灵活规划从数学上 来讲是一个更为复杂的优化问题，虽然已经取得了一定进展，但仍处于 起步阶段，尚存在许多不足。 ( 4 ) 按照数学模型对网络处理的不同，变电站规划的求解方法可分为两种， 一种是对变电站和网络同时进行优化，另一种是将变电站和网络的优化 问题进行分解，在变电站的优化模型中近似考虑线路投资和损耗。由于 前一种方法的复杂性随网络规模的扩大而呈指数增长，耗时长且费用巨 大，目前难以满足配电网规划人员的要求。而采用先进行变电站优化规 划再进行配电网络规划的方法在实际中更为可行。因此实际中采用解耦 一协调方法较为可取，即采用后一种规划方法，然后通过变电站优化规 划和网络优化规划的几次迭代优化选出综合费用最小的规划方案。虽然 从确定性的意义上说，后一种优化方法似乎不如前一种方法，但由于后 者不仅可节省规划工作的时间和费用，而且便于计及众多不确定与不精 确因素，因此更符合工程实际。 本文的研究内容是：采用站网分解优化方法进行变电站规划，其数学模型采用 单阶段的确定的经济性指标模型。 天津大学硕士学位论文 第一章绪论 1 2 4 变电站选址定容问题研究的综述 对于变电站位置、容量和供电范围的优化问题，国内外的一些学者已进行了广 泛和深入的研究，并结合定位理论的研究提出了许多模型和方法。 传统的规划方法是以方案比较为基础，由有关专家指定若干可行方案，通过技 术经济比较进行决策。然而参加比较的方案往往由规划人员凭经验提出，不可避免 地包含着很多主观因素，带来了一定局限性。近三十年来，随着计算机技术和优化 理论的迅速发展，许多电力系统专家致力于应用计算机技术来解决电网规划问题， 从而大大提高了规划的速度和质量，给传统的电网规划工作注入了新的活力。 文献 1 0 提出了一种交互式的确定变电站容量和投入时间的计算模型，虽然该 模型能够方便地与规划设计人员进行对话，但是它还不能确定变电站的地理位置。 后来经过人们的不断完善。采用了自动估计负荷转移费用的方法【1 1 1 ，提高了计算精 度，但是，也相应地增加了计算时间。文献 1 2 1 以负荷距最小为目标函数，以运输 问题为基本求解方法，提出了一种新的变电站位置和容量的数学优化技术，但是， 由于该方法要求有候选的变电站站址，因而降低了实用性。文献【1 3 】将数字图像处 理技术应用于变电站选址问题，提出了一种新颖的计算模型，但是该方法只适用于 新建地区( 即没有已有变电站) 的变电站规划，而且还不能对变电站的容量进行优 化选择，同样存在局限性。文献 1 4 】用分支定界运输问题模型优化变电站的位置， 虽然取得了一定的成果，但是随着问题规模的扩大，分支定界法的计算时间呈指数 增长，因此，该模型还不能解决大规模的工程实际问题。文献【1 5 】提出了一种求解 变电站和馈电线位置的简单目标函数，但没有考虑费用的时间特性，并忽略了网损 对变电站和网络选择的影响。文献 1 6 】提出了一种优化变电站和馈电线位置的改进 方法，该方法以变电站和网络投资及网损的时间特性之和为目标函数，考虑了近似 的网络结构，并引入了电压降约束。文献 1 7 】通过考虑负荷在不同变电站间转移的 费用，采用负荷聚类的方法给出了确定变电站位置的一种方法。文献 1 8 提出了待 建变电站的容量分级问题，但没有考虑不同容量变电站之间的费用差别问题。文献 【1 9 】提出了优化变电站容量和近似考虑配电线路网损的模型和算法，但变电站的位 置和数量必须人为给定。文献 2 0 】和【2 1 】将遗传算法用于变电站规划问题，但它们 需要给定候选站址1 2 0 l 或候选站容1 2 1 1 ，而且由于遗传算法通常收敛速度较慢，局部 寻优能力差，因此计算时间较长，解的质量不高。 上述文献给出的方法普遍存在两个问题：第一，变电站选址是基于平均负荷分 布假设上的。实际上，负荷的分布是不均匀的，地区间差异很大。这时，如果假设 负荷平均分布进行变电站选址，有可能得到不合理的布点方案。第二，需要事先给 定待选变电站的站址和数量。这一假设有一定优越性，它可以在提出候选站址时把 城市地理状况、建筑条件及进出线走廊等因素都考虑进去，然而，这有限个站点中 天津大学硕士学位论文 第一章绪论 不一定包含最优站址，而且当候选站址不确定时，就无法进行计算，因此它不能满 足实际的大规模电网的变电站选址要求。 文献 2 2 1 将变电站优化问题分为平面中位子问题和组合优化子问题，在此基础 上首次提出了一种求解变电站优化问题的大规模自动寻优的方法，该方法在小区负 荷预测完成的基础上，无需事先指定目标年候选变电站的位置和数量、也无需负荷 均匀分布的假定，就能在工程允许的时间内大范围快速寻找到问题的最优解，满足 了工程实际的要求，并已用于天津大学开发的城市电网规划计算机辅助决策系统 ( 简称c n p 2 5 ) 软件包中，完成了国内多个城市和地区的城市电网优化规划任务 。但是，该文献求解平面中位子问题所采用的交替定位分配( a l a ) 法，对初 始位置的选择敏感 2 4 1 ；求解组合优化子问题时采用试探组合算法，所得解的满意 程度有待进一步提高，且对大规模问题计算用时较长。文献 2 5 1 在文献 2 2 】研究的 基础上，提出了更加完善的、考虑线路投资影响的优化模型，并采用三角连续分割 算法求解组合优化子问题，但由于该文献仍采用川l a 法求解平面中位子问题，因 而也具有与文献 2 2 1 n 样的缺点。文献 2 6 1 用贪心算法求解变电站规划的组合子问 题，用h o p f i e l d 神经网络求解平面中位子问题，由于其采用贪婪算法，因而在提高 求解速度的同时，也使求解质量难以保证。 因此，提出一种工程上更为实用的变电站选址定容优化规划方法是十分必要 的。 1 3 本文工作及结构 1 1 3 1 本文主要工作 针对现有变电站优化规划方法存在的不足，本文沿用文献f 2 2 】的思路，将变电 站优化规划问题分为平面中位子问题和组合优化子问题，并将以此为基础重点进行 如下的研究工作： ( 1 ) 求解平面中位问题的常用方法主要有a l a 法和遗传算法，但是这两者 都存在一定的缺点。鉴于常规遗传算法的交叉算子使其在求解该问题时 效率低下，本文将设计一种新的遗传算法。然后，为了弥补遗传算法固 有的局部寻优能力差的缺点，研究把本文设计的遗传算法和局部最优算 法a l a 法结合的可行性以及结合方法，从而得到求解变电站规划的平 面中位子问题的高效方法。 ( 2 ) 为了更好地了解变电站规划的组合优化子问题，本文将通过实例仿真研 究其目标函数的形状，以期在此基础上，提出一种能兼顾运行时间和求 解质量的有效方法。 天律大学硕士学位论文第一章绪论 最后，利用依据上述算法开发的工程应用软件，对某城市的高压配电变电站的 站址和容量进行优化规划，以研究本文方法的应用效果。 1 3 2 本文结构 本文第二章主要介绍平面中位问题和组合优化问题的基本概念及求解方法，分 支定界法的基本概念与步骤以及单亲遗传算法的基本概念；第三章介绍本文提出的 求解平面p 中位问题的单亲遗传算法；第四章介绍本文提出的变电站选址定容优化 规划算法：第五章介绍应用本文提出的算法进行变电站选址定容工作的步骤，并通 过与传统变电站规划方法的比较，阐述了本文算法的优势；第六章为总体结论和研 究工作的展望。 天津大学硕士学位论文 第二章理论基础 第二章理论基础 作为对本文研究工作的准备，本章主要介绍平面中位问题和组合优化问题的 基本概念及求解方法，分支定界法的基本概念与步骤以及单亲遗传算法的基本概 念。 2 1 平面中位问题 选址问题，即给需要建设的设施选择最优位置的问题。例如，在一个系统中 新建一个或若干个工厂、车站、仓库、商店、变电站、电话交换台、医院、急救 站、消防队，自然都应考虑建在什么位置才能使得系统的运行效能达到最佳 的问题。在工程设计管理中，存在许多这样的系统，它们的设计或者本身就是一 个典型的选址问题，或者以选址问题作为一个子问题。这种一般意义下的选址问 题可能非常复杂，涉及到自然的、社会的、时间的和空间的等各种复杂条件，对 不同的实际问题可能有根本不同的优劣衡量标准。即使对于同一个实际问题，从 不同角度考虑，衡量标准也可能不同。当涉及到政治、军事和美学等因素时，甚 至难以用数量表示其衡量标准。这些复杂的选址问题已脱离了单纯的数学范畴， 不在本文的讨论范围之内。本文仅限于讨论一种有明确数学模型和切实可行解法 的典型选址问题，即平面中位问题。 平面中位问题可表述为：给定片个顾客的位置和需求，要求选择p 个新设施 的最优位置，使得“运输”总费用最小。 平面中位问题的分类方法主要包括如下三种： ( 1 ) 根据待建设施个数的不同，分为平面单中位问题和平面p 中位问题。 ( 2 ) 根据距离度量方式的不同，分为平面欧式距离中位问题和平面矩式距 离中位问题。 ( 3 ) 根据是否事先指定新建设施的候选位置，分为连续型平面中位问题和 离散型平面中位问题。连续型平面中位问题假定所考虑区域中任意点 均可建设新设施，因而数学上有无限多可能的位置存在；离散型平面 中位问题则是假定只有有限多个事先指定的位置可以建设新设施。本 文主要讨论连续型平面中位问题，如果未特殊指明，均指的是连续型 平面中位问题。 天津大学硕士学位论文 第二章理论基础 下面主要介绍几种有代表性的平面中位问题及它们的解法。 2 1 1 平面欧氏距离单中位问题 该问题司描述为：设n 个颇答的全体记为j 2 1 ，2 ，1 ) ，给定它们的平面坐 标q ，y j ) 和权w j ou ，) ，确定单个设施q 的位置( ，) ，使其到各个顾客 的赋权距离之和最小。记作： 。m 。i n 旷一嘭 ( 2 - 1 ) ( f ) f 舒。 、7 式中，t ：( x - x j ) 2 + ( y - y j ) 2 1 ”。式( 2 1 ) 的最优解( x q , y q ) 称为中位点。 一般地，顾客的“权”可以理解为它要求设施提供服务或为设施提供服务的 量；“距离”指提供单位服务所需的费用( 一般这个费用与两者间距离成比例， 所以称之为距离) 。 这一无约束最优化问题的目标函数为厂= e w j e , ，当各顾客不共线时是严格 凸的，而共线时是非严格凸的。因此，f 的局部最小点也就是全局最优解。各顾 客共线时是下文将要介绍的平面矩式距离单中位问题的特例。假定行个给定顾客 不共线，则厂在各个顾客点( ，乃) u d 处不可微，其余点处均可微。中位点 落在某个已知顾客点( ，乩) 上的充要条件是2 7 1 瞻孚 2 + c 毛叶等孵 式中，叱= f ( _ 一) 2 + ( 乃一) 2 经。因此，可以利用式( 2 2 ) 检查一个顾客点 中是否存在中位点。如果它们都不是中位点，则中位点应该是一个逗留点，如 ( ，丘) ，且应满足下式； 沁丢叶等 ， 乳= ；一半= 。 一 即 矿( 否_ _ 心) 爬啪 t e jj i d， ：( 妻_ 乃， ，( 砉一，吒) 。4 y q2 罾j y j 雷泓心 从任意初始点( ，圮) 开始，按如下公式迭代： 天津大学硕士学位论文第二章理论基础 = ( 若_ 吒 ( 吾一爵j o) | i a， 疗1 = ( 若心乃吒 ( 吾m 吒i “， j e j， ( 2 - 5 ) 式中，上角标t 表示迭代进行到第t 步。当迭代过程中遇到某个t 和 ，使得 ( ，以) = ( ，乩) 时，目标函数的梯度方向可表示为 瓦= ( ，三靠寻，点y j 叱- y j o ， 并可按如下公式继续迭代： 譬= 一 。一赢 丢磐。x 爿j - - x j o 一形：丝：厉x j 笠- x j o w j y ，。- “y j 。一业商w ；y j l - y 。 ( 2 - 7 ) 当( ，蜡) 和( ，虻) 充分接近时，迭代停止 选取初始点( ，以) 的一种非常方便的方法是取各个顾客点坐标的加权平均 数，即 一_ 砖。舒z j ： ( 2 8 ) _ 乃 ”7 瑶2 钉 该初始点选取方法还县比较有效的嘲。 2 1 2 平面矩氏距离单中位问题 在式( 2 1 ) 中，若将距离4 改为 弓； x 剪 + i ，i ( 2 9 ) 就得到平面矩氏距离单中位问题。这类问题也可以在任意m 维空间里讨论，且 比较容易求解，同时其最优解相对于不同的距离度量方式差异不大。因此，即使 有时矩氏距离模型不比欧氏距离模型更合理，但为了计算简便，也采用矩氏距离 模型。 天津大学硕士学位论文 第二章理论基础 由于该类问题的目标函数中两个变量可分离，因此可以将其分解成对z s u y 分别求解的两个独立问题。我们只需讨论其中的一个，譬如：n 曲一lz 一_ i 。 ，j 它的目标函数是凸的、分段线性的，最小点一定在某个而处，并且在每个而u 力 处不可微，但在而的左侧和右侧导数都存在： a o - i w , i x 一_ i ) 凼一= m 一吩 d ( 蔓吣刮+ ：蔓哆一薹一 ( 2 _ 1 0 ) d ( 一i z 一一1 ) 出+ = 哆一一 卜7 i日ljt i i 在最优点而处应有 d ( w ji x 一_ i ) 出一 0 ( j e j ) ，从置个容量等级中确定p 个设施的容量s 和位置 ，只) ，i = 1 , 2 ，护，使得各设施的建设费用及运输费用之和最小，记作： m i n c = q ) + _ 吻 l l - i ，e s t 厂( 墨) ( 2 - 1 5 ) j * - j l p口 n z = o ，0 以= j z = lj = l 式中，g ( s ) 表示容量为昂的设施的建设费用；z 表示设施f 服务范围内顾客的 集合；k = 1 , 2 ，。 如果每个设施的建设费用远大于其为顾客提供服务的运输费用，则该问题可 分解为如下两个子问题： ( 1 ) m i n c = g ) 一组合优化问题 f - l ( 2 ) m i n c = 一嘞一平面中位问题 t = l “ 如果x 个容量等级的设施费用差别较大，且每个目标的建设费用与其为顾 客提供服务的运输费用差别很小，则该问题是一个组合优化问题和平面中位问题 天津大学硕士学位论文第二章理论基础 综合求解的优化问题。 变电站选址定容优化规划问题属于后者，本文将其分为组合优化子问题和平 面中位子问题，对两个子问题进行综合优化。 2 2 组合优化问题 2 2 1 组合优化问题的概念 组合优化问题又称离散优化问题，它是相对基于连续变量求解的函数优化问 题进行讨论的。随着计算机科学、管理科学和现代化生产技术的日益发展，这类 问题与日俱增，越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学 科的高度重视。组合优化问题在规划、调度、资源分配以及决策等问题中有着非 常广泛的应用。 该问题可描述为：在离散的、有限的数学结构上，寻找一个满足给定约束条 件并使其目标函数值达到最大或最小的解。目标函数最小值的组合优化问题记 作： m i nr f n x t f 佗1 6 ) s t x f ，f z 式中，为费用函数或映射；z 是基本空间；f 为可行解的集合，它是离散变量 的一些组合的集合。 使目标函数取得最优值的解称为全局最优解。 2 2 2 组合优化问题的求解方法 组合优化问题的特点是可行解集合为有限点集。只要逐_ 比较有限个点的目 标函数值的大小，该问题的最优解就一定可以得到。但是枚举是以时间为代价的， 有时枚举时间还可以接受，有时则不能接受。设问题的规模为刀，如果存在一个 多项式烈功，使得算法最多执行烈打) 个基本步骤便可得到解答，则这种算法称为 多项式时间算法。 多年来，人们一直试图寻找解答各种组合优化问题的多项式时间算法。这种 研究工作在一些问题上已取得成功，其中包括最短路问题、最小支撑树问题、网 络最大流，最小费用流问题以及运输问题等等。但随着实践的发展，人们发现越 来越多的组合优化问题很难找到求得最优解的多项式时间算法。这一类组合优化 问题归为所谓的n p 难问题。求解这类问题时，除了枚举一部分解空间之外，没 有更好的解法【3 3 1 。目前求解这类组合优化问题的方法大体可以分为以下几类： 天津大学硕士学位论文第二章理论基础 ( 1 ) 运筹学的经典方法。在己知没有多项式时间算法得到最优解的情况 下，尽可能地改进简单的穷举搜索法。为了减少搜索工作量，使用最 广泛的方法是分支定界法( 将在下节中详细介绍) 或动态规划法。分 支定界法在对一个树形结构的搜索过程中生成许多“部分解”，通过 有效的定界方法识别出那些不可能扩充成最优解的“部分解”，从而 剪去这一步搜索的所有分支。动态规划法也是十分有效的方法，它往 往可以得到一些伪多项式时间算法。除此之外，割平面法和