（电力系统及其自动化专业论文）基于gis的城市配电网规划.pdf

a b s t r a c t h o wt of m dt h eo p t i m u mr o u t i n go fc a b l e si sa l li m p o r t a n tp r o b l e ma n dm a i n p a r to f u r b a nd i s t r i b u t i o np l a n n i n g p r e s e n t l y , d e s i g n e r su s u a l l yp e r f o r mt h er o u t i n g d e s i g nm a n u a l l yw i t hc o n s i d e r a t i o no fs u c hc o n s t r a i n t s a sn e t w o r ks t r u c t u r e ，s t r e e t c o n d i t i o n a sar e s u l t 、m o s tf m a lp l a n n i n gd e s i g n sa r ef a rf r o mo p t i m a lm t l ll o n g p l a n n i n gt i m e ，w h i c hs e r i o u s l ya f f e c t st h ee f f i c i e n c y a n dq u a l i t yo fu r b a nn e t w o r k d i s t r i b u t i o np l a n n i n ga n dr e c o n s t r u c t i o n a p r a c t i c a la n de f f i c i e n ta u t o m a t e dt o o lf o ro p t i m i z i n gt h er o u t i n go f c a b l e si s p r e s e n t e di nt h i sp a p e r , w h i c hi sb a s e do na r t i f i c i a li n t e l l i g e n c ea n dn e t w o r kg r a p h t h e o r yc o m b i n e dw i t ld i s t r i b u t i o nn e t w o r kg e o g r a p h i ci n f o r m a t i o ns y s t e m ( o i s ) t h ew o r kd o n ei nt h i sp a p e ri s 鹤f o l l o w s ： 1 t h e a p p l i c a t i o n o fg i si nd i s t r i b u t i o np l a n n i n gi ss t u d i e da n dt h e r e c o g n i t i o n ， a c q u i s i t i o na n dp r e p r o c e s s i n go fs p m i a ld a t ai nt h eg e o g r a p h i ci n f o r m a t i o no f p l a r m i n ga r e a ，a r ec o m p l e t e d 2 t h ea u t o m a t e dr o u t i n gi sd i v i d e di n t ot w op a r t s ：p r i m a r yc a b l er o u t i n ga n d s e c o n d f l r yc a b l er o u t i n g a ) o nt h er e s e a r c ho f p r i m a r yc a b l em u t i n g a na u t o m a t e dp r i m a r yr o u t i n g a l g o r i t h mb a s e d o n d i j k s t r aa l g o r i t h m i sp u tf o r w a r d ，w h i c hc a l lg e n e r a t e a u t o m a t i c a l l yt h ep r i m a r yr a d i a t ed i s t r i b u t i o np l a n n i n gg r a p ho ft h ea r e a t ob ep l a n n e d b ) i nt h e r e s e a r c ho f s e c o n d a r y c a b l e r o u t i n g ，ah e u r i s t i c s e a r c h a l g o r i t l l i n 呻e d u c t i o ns y s t e mr e a s o n i n go fa r t i f i c i a li n t e l l i g e n c ei sp u t f o r w a r di nt h i sp a p e rt os o l v et h ep r o b l e mo fl o a da l l o c a t i o ni no u t l e t c a b l e so f m a i n s u p p l y $ o l , u e s i t se f f e c t i v e n e s si sp r o v e di nt e s tr e s u l t s 3 t h em e t h o da n d p r o c e d u r eo fs o f t w a r ea n a l y s i s a n d d e s i g nm a i n l yo f c o m p l i c a t e da l g o r i t h m sa r ep r e s e n t e di nt h i sp a p e r i nt h es o f t w a r e ，t h r e e 1 a y e r a r c h i t e c t u r ea n dc o m t e c h n o l o g ya r ee m p l o y e d d e s i g np a t t e r n sa r ea p p l i e d t o d e v e l o pt h ec o m p o n e n t so fe a c hl a y e rt or e u s a b l ea n dm o r ef l e x i b l e c o m p o n e n t s ，g r o u pt h e s ec o m p o n e n t si n t op a c k a g e so r g a n i c a l l ya n db u i l d a p p l i c a t i o np r o g r a m ，t h u sr e a l i z ea u t o m a t e dr o u t i n gf u n c t i o n k e yw o r d s ：d i s l r i b u f i o np l a n n i n g ，g e o g r a p h i ci n f o r m a t i o ns y s t e m ( g i s ) ，a u t o m a t e d r o u t i n g , n e t w o r kg r a p ht h e o r y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盘鎏盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：户灵取签字日期：乃2 ) 年，2 ，月西日 ? 。 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘鲎有关保留、使用学位论文的规定。 特授权蠢洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 龇一弛尸更多 签字日期：乃哆年) 月日 导师签名 签字日期：歹嘭年伊月口日 第一章绪论 第一章绪论 城市配电网规划既是城市总体规划的一部分，也是整个电力系统规划的重要 组成部分。随着国民经济的不断发展，城市建设也进入一个日新月异的新阶段， 新兴城市不断涌现，老城市也加快了改造的步伐，新城区及旧城区的配网规划( 包 括用户分区、网络规划、最优设点布线等) 已成为电力工作者的一项越来越重要 任务。 合理的电网结构，是保证电网安全稳定运行的首要条件。分层分区分功能的 构筑各电压等级电网，是现代电网不同于传统电网的主要区别之一，其特点是： 物理概念清晰、电网结构简单，可有效地避免当高电压等级元件或线路故障后， 电磁环网潮流大量涌入低电压等级电网而引发的设备严重过载、保护相继误动、 电网瓦解大面积停电等严重后果，从而显著提高电网供电的可靠性及安全性。 对于每一电压等级的城市配电网，在明确变电站经济合理供电半径区域范围的基 础上，按照城市地理位置，以变电所为中心，以主要街道为界面，根据负荷情况 将城区划分为若干相对独立区块，对每个区块进行配电网布线，使之构成辐射状 网格化供电网络，以便消除自然延伸、无序交叉迂回的供电状况，适应集中检修、 快捷抢修及规范管理与降损的要求。 基于这样一个分区分层的网架结构，配电网规划要解决的问题是：在负荷分 布预测结果已知、或配电变压器布点已知的基础上，根据高压变电站( 3 5 k v 或 l l o k v ) 供电范围，确定1 0 k v 配电线路在城市街区中怎样布线，以及各个变电 站的联络线如何规划，才能满足辐射形网络和经济性最优，并且使具体的方案符 合实际工程要求。目前绝大部分电力部门仍然采用传统手段( 如统筹方法等) ，用 人工或借助于简单的c a d 制图工具来规划与设计配网，这不仅费时、费力，而 且要在数以百万计的可选设计方案中，兼顾网络结构、设备材料、居民便利及障 碍物等各方面的制约因素，挑出一个最优方案是非常困难的，甚至是不可能的。 如何应用计算机技术实现上述过程的自动布线，就是配电网的自动布线问题。， 因此，配电网络自动布线研究，是一个既有理论研究意义，又有很高的实用价值 的研究课题。 配电网自动布线问题是一个不确定性、多阶段的数学优化问题，本文将这一 第一章绪论 问题的解决方案划分成初级布线、次级布线和联络布线三个阶段。其中，初级布 线，要解决使所有的负荷沿着街道走线到高压变电站的初步配电网是辐射形且覆 盖所有负荷，并使总线长最小的一颗树；次级布线，在初级布线的基础上，要解 决怎样把该树根据高压变电站所供的所有负荷点的负荷分布情况分解成多棵树， 每一颗树为一条出线，且分配额定的负荷量，使总造价最小；联络布线，要解决 各个变电站的联络线如何布置以及选择何种联络方式，从而使整个城市配电网网 络满足可靠性和经济性最优。 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，缩写为g i s ) 是利用现代计算 机图形和数据库技术来获取、输入、编辑、查询、分析、决策和显示空间图形及 其性质数据的计算机系统。g i s 的最大特点就在于它能够把现实生活中的各种信 息与反映地理位置的图形信息结合在_ 起。g i s 可根据查询与分析的需要将这些 信息真实地、图文并茂地展示在用户面前，也可将分析决策模型处理的结果提交 各级管理部门作决策参考。 近年来，g i s 和人工智f 毙( a r t i f i c i a li n t e l l i g e n c e ，缩写为a i ) 技术的快速发展， 为配电网络自动布线研究带来了新的机遇。但是，目前这方面的研究主要集中在 初级布线阶段，而对次级布线和联络布线的研究很难达到使自动布线实用化的要 求。文献 3 i n 文献【4 】介绍了基于地理信息系统和遗传算法的自动布线方法。文 献【7 】提出了一种既考虑电力部门的投资，又考虑用户停电损失的多目标优化模 型，也是利用了遗传算法进行线路布置优化。以上文献主要是在初级布线时就应 用启发式搜索算法进行搜索使得到的网络具有辐射性且经济性最优，但是都没有 解决次级布线的负荷分配问题。 本文以人工智能，网络图论为理论基础，引入最短路d i j k s t r a 算法解决初级 布线的优化问题，采用人工智能产生式系统推理方法进行次级布线的负荷分配， 从而建立了完整的配电网自动布线的新思路，并在上述思路的基础上研究和开发 了基于g i s 的配电网自动布线的软件系统，实现了配电网自动布线实用化。 本文在研究和开发配电网自动布线的软件系统中，采用了先进的面向对象的 设计技术和c o m 组件技术。面向对象的设计使得软件具有良好的复用性、扩展 性和健壮性。c o m 组件技术能使得软件各部分接i ：1 的说明和实现完全独立，数 据封装变得更加容易，能增强模块通用性和独立性。 第一章绪论 本文完成的主要工作如下： 1 研究了g i s 系统在配电网规划中的应用，完成了规划区地理信息中空间 数据识别、获得以及预处理。 2 本文把配网规划中的自动布线问题分为两个部分一初级布线和次级布线 来进行研究。 a ) 在初级布线的研究中，本文提出基于最短路d i j k s t r a 算法的自动初级 布线算法，该算法能对一个待规划的城区分片自动形成初步的城区辐 射配电网规划图。 b ) 在次级布线的研究中，本文提出了一种启发式搜索算法一人工智能产 生式系统推理方法用来解决主电源出线中负荷分配的问题。 3 本文提出了以复杂算法为主的软件系统的分析和设计方法和步骤。在软 件中利用三层体系构架和c o m 组件技术。运用设计模式把各个层的组件 设计成可复用、灵活性高的组件，然后把这些组件有机的组合成包构成 应用程序，实现了自动布线的功能。 第二章基于g i s 系统的配电网规划 第二章基于g i s 系统的配电网规划 随着计算机的普及以及地理信息处理技术的发展，g i s 因其强大的功能得到 日益广泛和深人入的应用。网络分析作为g i s 主要的功能之一，在电子导航、 交通旅游、城市规划以及电力、通讯等各种管网、管线的布局规划设计中发挥了 重要的作用。在网络分析中关键的问题是最短路径问题，最短路径不仅仅指一般 地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等， 相应地，最短路径问题就成为最快路径问题、最低费用问题等。 2 1 空间地理数据 g i s 将空间事物抽象成点、线、面等几何要素，点、线、面可组成网络，这 些要素之间也可建立起拓扑关系。如；网络在几何上由线连成，线的端点、交点 为结点，线可围成面，从一条线还可知道谁是左侧多边形、谁是右侧多边形，这 些几何特征与配电系统所面临的客观对象相当吻合，因此，配电系统的拓扑可以 由g i s 系统中的多个要素来构成：首先，可将道路网、输配电网定义为几何上 的“网”，其次，变电站( 所) 、电厂可定义为网上的“结点”，由道路中心线或输 配电线围成的街区可定义为“面”。电力负荷可认为是在街区内产生的，这些负 荷的大小由负荷预测来得到。在实际规划中，某一街区的负荷以负荷设备所在地 的地理点来表示。电力供应能力由变电站、电厂的容量所决定，经输、配电线送 达各街区。这样，电源、线网、负荷之间的关系被抽象成g i s 中的网络、结点、 线、多边形之间的关系。矢量型g i s 中每个几何要素还可定义非几何的属性， 如：结点可以有变电站供电容量，负荷点可以有负荷量、负荷性质等等，这和常 规配电规划考虑的问题也是一致的。在同一个街区内。土地使用是按地块划分的， 地块的边界又是从道路中心线后退一定距离界定的，街区是多边形，其边界为线， 线则组成网，这样，地块内的负荷和供电网之间通过街区这级空间单元的过渡而 建立起联系。 第二章基于g i s 系统的配电网规划 2 2 地理数据的处理 在一个各种地理信息数据量非常庞大的城市g i s 系统中，要高效而且有针对 性地提取符合要求的数据需要相应的处理方法。由于利用地理数据的算法有时是 一些复杂度高的算法，如d i j k s t r a 最短路算法，它们随着搜索的点的增大，其规 模迅速膨大，因此本课题根据电网中分层分区原则来进行配电网分区规划，这样 可以显著地减少搜索点，从而提高规划速度。 2 2 1 数据提取的前期准备 提取准确的道路中心线需要一定的人工干预。目前使用的城市矢量化电子图 中，通常矢量化不能提供该道路中心线。即使对于航拍图象，虽然用矢量化算法 可以获取路心线，但是它可能会产生实体断裂的情形，使得利用各种搜索算法搜 索路段时会出现搜索错误，因而必须通过一定劳动量的人工输入的方式才能从城 市矢量电子图得到具有准确的道路中心线。 提取的方法是对矢量化的g i s 配电系统图输出d x f 格式的图形文件，用计 算机辅助作图软件( 如a u t o c a d ) 强大的编辑功能来添加道路中心线。不过值得注 意的是，即使对于比较熟练的图形操作员，添加路心线也是比较容易出错的，比 如，在a u t o c a d 中，用速度较快的多线段绘制时，可能会在十字路口本该相交 的中心线却不相交而出现搜索错误，因此要求配电规划人员在绘制街道路中心线 时要仔细确保其中心线绘制正确。根据配电网分区规划的原则，我们在绘制中心 线时，对于不同的规划区域要确保在不同的层中，以便程序提取方便。要注意， 在区域之间边界处，要仔细处理横穿区域之间的街道中心线让其在分界处断裂， 使不同的规划区域不会互相影响。 2 2 2 街道中心线的提取 本课题程序实现是以三层架构的软件体系、基于组件的开发模式形成的。三 层架构分别为界面层、中间业务层和数据层。提取街道中心线组件c d a t a f r o m d x f 属于中间业务层。图2 1 所示是实现该组件功能一从街道提取数据的流程图。 具体的开发过程和开发方法详见第五章。 第二章基于g i s 系统的配电网规划 图2 - - 1 街道提取数据的流程图 该组件的功能是从配电网自动布线的背景图( a u t o c a d 图) 的d x f 格式文 件中提取相应规划区域的街道路心线数据，然后存入到数据库中去。图2 2 所 示的是配电网自动布线的背景图，其中l s p 3 8 等编号表示街道点，l o a d l 8 等 编号表示负荷点，图中有一个电源点，街道中心线由街道点连接而成。为方便配 电规划人员，减少人工的操作和干预，该组件中包括以下功能：能创建数据库、 表和主键等等。其数据库名称，表的名称以及数据变量名称，通过存储过程在这 组件中实现。下面分别说明在提取数据时应处理的问题及其处理方法： ( 1 ) 街道中心线交叉点和负荷、电源点的区分 由于街道路心线交叉点一般都在线段的两个端点上，所以起点可以从线段 上取就可以了。一般变电站站址和负荷预测完成以后，其负荷点和电源点的坐 标已经以一定的形式存入文件或数据库中。 第二章基于g i s 系统的配电卿规划 ( 2 ) 图形绘制工具的选择 由于供电区域中的线路不能用曲线画( 这与a u t o c a d 中的曲线概念不同， 与平面几何中的曲线概念相同，即不包含直线、线段的曲线) ，因此在a u t o c a d 图形系统的电子地图中描出街道路心线图要用直线a c a d l i n e 、a c a d l w p o l y 、 a c a d p l o y ，推荐用多线段a c a d p l o y 和a c a d l w p l o y 来，这既能使描画速度快， 而且能避免线路不连续。 图2 2 配电网自动布线的背景图 ( 3 ) 弯曲街道的处理 在文献 9 】中提出了，g i s 中进行最短路径操作时减小几何路径曲率较大的路 线操作结果不确定性的方法是：( 1 ) 提高最短路径经过顶点的定位精度；( 2 ) 减少 最短路径经过顶点数目。因此，如出现弯曲街道路径，则进行适度的分段来解决， 这一般不会影响项目的要求。如图2 - - 3 所示，在街道点l s p 8 3 和l s p 7 9 之间的 曲线被分成两段：线段l s p 8 3 - - l s p 8 4 、线段l s p 8 4 - _ l s p 7 9 。 第二章基于g i s 系统的配电网规划 图2 3 弯曲街道 ( 4 ) 配电网规划人员与自动布线程序的交互。 提示用户输入仅有街道路心线的图层。图层中街道路心线要做到连续，不要 出现断点，建议用多线段来菌出街道线路图；图层中站点负荷点要尽量做到醒目、 清楚，力求用标注。 ( 5 ) 点和线编号的处理 在取出所有的点、单线段、多线段并存入数据库的过程中，为使程序处理方 便，需要妥善处理编号问题。所提出的数据中，其中点可以重复，线不能重复。 取出时要分类，如点，线段、多线段；要有步骤而且要有不同的存储地方( 分属 于数据库中不同的表) 。为使问题力求简单、清晰，可把这一问题分为下面几步。 a ) 处理a e a d l i n e ：当对其线编号时，其相应的点也相应顺序编号。 b ) 处理a c a d p l o y 、a c a d p o l y l i n e ：取出其顶点数，及其顶点坐标，判断此 线是否是封闭的，如封闭，则有边数( 单线段数) = 顶点数；如不封闭， 则有边数( 单线段数) = 顶点数一1 。对于封闭的多线段，其首尾的线段 的点重合，此时要处理其编号问题，即不应该对于同一个点有两个键( 键 为点号) 。 c ) 对所有的街道交叉点所成的集合，删除重复的元素并对其中的元素编号。 对所有的直线编号并根据街道交叉点的编号来决定直线中第一点和第二 点的编号。 第二章基于g i s 系统的配电网规划 2 2 3 提取g i s 数据速度的改进 a u t o c a d 是一种具有高度开发结构的c a d 平台软件，它通过a c t i v e x 自动 化界面技术提供给编程者一个强有力的二次开发环境。由于a e t i v e x 技术是一种 完全面向对象技术，所以许多面向对象化编程的语言和应用程序，可以通过 a e t i v e x 与a u t o c a d 进行通信，并操纵a u t o c a d 的许多功能。而微软对于c o m 组件的应用之一是组件可以同v b a 进行通信。v b a 的最大优点是开发效率高， 其缺点是运行速度低。 v b a 慢的一个基本理由之一是遍历一个大集合中里所有的元素( 如遍历一 个具有几万个实体的大图时) 时效率低下。导致遍历效率不高的原因是遍历函数 i t e m ( ) 。为满足函数i t e m 的随机访问功能，i t e m ( i n d e x ) 的内部( 底层) 操作是从 集合中第一个元素开始进行顺序地遍历到第1 n d e x 个元素。在遍历集合中所有的 元素时，对每一个元素的操作都是从头开始的，则花费在每一个元素的平均时间 相当于在c 语言中利用指针遍历全部元素所发费时间的一半。例如遍历一个具有 二万个实体的大图时，它在c 和卅中的时间( 如在o b j e e t a r x 中) 是 f o r ( i = 0 ；i 2 0 0 0 0 ；i + + ) 空操作； 则在v b a 中的时间是 f o r ( i 2 0 ；i 结论 即表示为矿t h e n 的形式。 其中左半部确定了该规则可应用的先决条件，右半部描述了应用这条规则所 采取的行动或得出的结论。 控制系统或策略是规则的解释程序。它规定了如何选择一条可应用的规则 对数据库进行操作，即决定了问题求解过程的推理路线。 第四章次级布线 4 2 2 次级布线问题的现实目标 从上一节分析可知，目前还没有有效的算法得到该问题的精确解，因此我们 退而求其次，不去寻求最优解，而是寻求一个能满足实际规划要求的近似最优解。 在实际的规划中，要求次级布线满足以下的要求： 1 、每条出线都接近额定负荷； 7 2 、出线的负荷分布不能太散； 3 、总出线条数接近 l o a d ， l o a d e 其中m 表示z 的最大整数，l o a d ，为第f 个负荷的负荷量，l o a d 。为出线的额 定负荷。 在实际的规划中，出线的负荷分布不能太散是很重要的，这是判断一条规划 出来的出线是否良好的重要标志之一。出线的负荷分布良好指的是一条出线的负 荷往往是变电站供电范围内同一个方向的负荷。例如，如图4 1 所示的出线1 比出线2 要好。因为，出线2 比出线i 的负荷分布要分散些( 假定出线长和出线 负荷量相等) 。 + 下， 出鳋l 图4 1 出线所带负荷分布比较 出线2 第四章次授布线 4 2 3 次级布线问题的表示 要用产生式系统来解决一个问题，首先必须建立起问题的产生式系统的描 述，即规定出综合数据库、规则集合及其控制策略。一般来说一个问题可有多种 表示的方式，而选择一种较好的表示是运用人工智能技术解决实际问题首先要考 虑的，而且需要运用一定的技巧。 4 2 3 1 综合数据库一有向最短路树 综合数据库是人工智能产生式系统所使用的主要数据结构，它用来表述问题 状态或有关事实，即它含有所求解问题的信息。针对问题的性质构造适合的综合 数据库对于简化推理演绎过程、提高程序运行速度有着很大的影响。 我们已经求出了所有负荷到街道的最短路，如图4 2 所示是一个简单的负荷 到电源的最短路图。其中t s 表示变电站，l s p 表示街道点，l o a d 表示街道里 的负荷点。每一个负荷到街道的最短路是用迪杰特最短路算法求得，具体可参看 第三章。 。碍 隅 i d o s l s p 7 i s p 9塔弛 ) 一 l o a 】t l s p 4 工s r l l o a ，2 功3 l s p 3 图4 2 简单的负荷到电源的最短路 l o d 4 我们让所有的最短路的方向都是电源到负荷的方向，则所有的负荷的最短路 第四章次级布线 组成了整个系统的有向最短路树。其最短路树所有的边的方向严格是从电源指向 负荷点方向。如图4 - - 3 所示就是图4 - - 2 对应的有向最短路树。 图4 3 有向最短路树 有向最短路树的数据结构能简化次级布线的规划过程，具体体现在以下方 面： 1 、它能使搜索策略一宽度搜索没有回溯过程，减少了程序复杂性，提高了程 序运行速度； 2 、它本身是一个辐射状，因而能满足出线的辐射形要求。 由于要求搜索策略没有回溯，因而在最短路树的点、边必须储存足够的数据 来保证搜索的单向性，反映搜索状态树的状态变化以及结束标志等等。我们把这 些数据作为边、点的属性数据。这主要得益于一个程序库 2 2 1 ( 在b o o s t 里的一个 图库) 。这个图库利用一个设计模式得到这种数据存储方式。它的存储方式有一 个优点，就是能无缝的加入若干个属性( 如边的权值、点的坐标、边所在的直线 方程等等) 于某条边、点上，对图作一致的处理。而常规的存储方式是对每一类 数据都用一个数组存储，并且还要使各个数组的数据保持一致，这增加了程序出 错的机会。 一、有向最短路树点的属性 第四章次级布线 1 、点的属性数据结构由五个属性值组成： ( 1 ) 点的负荷性质：指的是在有向最短路树某一点( 包括该点) 之后子树的负 荷分布情况； 一般来说，在一个类似图4 2 的有向最短路树中有六种负荷分布情况， 它们分别是： 曲、负荷点：如点l o a d l ： 、单个负荷：该点的出度为1 且该点出边的目标点的子树不存在出度数大 于1 的点，如点l s p 2 ： c ) 、单个综合负荷：该点的出度只为l 且该点出边的目标点的子树存在出度 数大于1 的点，如点t s ； d ) 、混合负荷：点的出度大于1 且该点出边的目标点的子树同时存在出度数 小于等于1 和大于l 的点。如点l s p 8 ，它出边的目标点是l s p l 0 、l s p 4 、 l s p 5 ，其中l s p l 0 的子树不存在度数大于1 的点，l s p 4 存在出度数大 于1 的点，所以它的点负荷性质是混合负荷； e ) 、多单个负荷：点的出度大于1 且该点出边的目标点的子树只存在 出度数小于等于l 的点，如点l s p l ； f ) 、多综合负荷：点的出度大于1 且该点出边的目标点的子树只存在出度数 大于1 的点，如点l s p 8 。 ( 2 ) 点的名字属性：在有向最短路树，每一个点的名字都不同，这确定该点的 身份唯一性： ( 3 ) 包含负荷点号：指点的子树里面包含的负荷点号。如果这个点本身是一 个负荷，则包含的负荷点就是它本身； ( 4 ) 总负荷；点的子树里包含的负荷点的总负荷量； ( 5 ) 点的坐标属性。指点在街道的位置坐标。 2 、点的负荷性质的计算： 通过点的负荷性质的定义可知我们需要首先求有向最短路树任一点的子树 的性质，然后才能求有向最短路树中任何一点的负荷性质。 求有向最短路树中任何一点的子树性质的算法，只需从该点起运用宽度搜 索算法，在搜索过程中如果存在点出度数大于1 ，则返回真，或者一直搜索到完 第四章次级布线 毕，如果没有出现出度数大于1 的点，则返回假。其函数表示是； b o o l g e t _ s u b t r e e _ _ p r o p e r t y ( v e r t e x _ d e s c r i p t o r & s 、 其中s 是搜索起始点。 下面是点的负荷性质的算法： 1 如果点s 的出度为0 ，则返回- - 2 ；，表示此点的性质为负荷点 2 如果点s 的出度为l ： 3 求其s 的出边的目标点v ，调用子程序o e t _ s u b t r e ep r o p e r t y ( v ) 4 返回值为bs u b p r o ； 5如果bs u b p r o 为真， 6 则返回0 ：表示此点的性质为包含综合负荷 7 如果b _ s u b p r o 为假， 8 则返回一1 ；表示此点的性质为只包含单个负荷 9 如果点s 出度大于1 ： 1 0声明容器v e c t o r l l 遍历出边，对每一出边的目标点，调用子程序g e t _ s u b t r e e _ p r o p e r t y ( v ) 1 2 返回值为bs u b p r o ； 1 3把bs u b p r o 存入容器v e e t o r ； 1 4 如果容器v e c t o r 里的值都为t r u e ， 1 5 则返回3 ；，表示此点的性质为多综合负荷； 1 6 如果容器v e c t o r 里的值都为f a l s e ， 1 7 则返回2 ；表示此点的性质为多单个负荷 1 8 如果容器v e e t o r 里的值两种都有， 1 9 则返回l ；表示此点的性质为混合负荷 点的属性在搜索开始时就确定了，它决定了宽度搜索时搜索状态树的变化规 律。它是规贝u 产生的主要依据。 有向最短路树与搜索状态树是同构的。有向最短路树搜索过程中某一时刻搜 索到某一点时，所有边的属性值就是一个状态，它对应搜索状态树上某一个节点。 当搜索完某点的出边时，最短路树中属性值的变化只是发生在该边，有向最短路 树其它的边的属性没有变化。从而我们把一条边的属性变化就映射成状态空间中 第四章次级布线 某一个状态向另一个状态转变，也映射成搜索状态树中的一个节点向它的邻接节 点的搜索。由于有向最短路树的图性质跟搜索状态树一样，从而用宽度搜索算法 搜索整个有向最短路树和用宽度搜索策略搜索状态树是同步进行，严格对应的。 当搜索有向最短路树的电源时，也是状态树搜索到起点的时候。所以搜索状态树 与有向最短路树是同构的。 二、有向最短路树边的属性 边的属性数据结构由三个属性值组成： a ) 边的名字属性。在有向最短路树，每一条边的名字都不同，这确定该边的身 份唯一性： b ) 出线条数属性。该属性表示这条边能让多少条出线共同经过。它不一定是一 个整数； c ) 新增加负荷点号。该属性表示该边所包含的出线在搜索该点前已经挂上的负 荷，这个属性确保一条出线里负荷分布良好。 边的属性除了名字属性外，在搜索开始时都没有数据。随着搜索的进行，所 经过的边的属性开始写入和改变。当所有的点都搜索完时，其边属性变化也就停 止。边的属性的每一次变化表示搜索状态树中某一个状态转换为另一个状态。 4 2 3 2 规则集合 ( 1 ) 规则1 ：i f 点的负荷性质为负荷点，t h e n 空操作。 ( 2 ) 规则2 ：i f 点的负荷性质为单个负荷和单综合负荷，t h e n 把这点的入边 边属性值拷贝到该点的出边边属性 ( 3 ) 规则3 规则3 是当点的负荷性质是多综合负荷时，搜索算法需要处理的方式。 当搜索算法遇到一个点的负荷性质时多综合负荷时，它遍历该点的出边，然 后依次处理出边。 在处理每一条出边时，如果该点入边新增加负荷的属性中，负荷的个数小于 7 时，列举所有的负荷组合，使得 m = ( 该点的总负荷属性值l z + 某组合负荷之和l p ) 额定负荷l e 第四章次级布线 刚好为整数( = l z l e ) ，或离此整数最接近。把该点出边的目标点包含的 负荷加上l p 成为此出边的总负荷，出线条数属性为m 。然后从l c 中删除已经选 入的负荷。 如果负荷个数大于等于7 时，只是把这些负荷随机排列，并依次取出若干个 负荷组成的负荷组合，其余处理方法如上。 具体的算法如图4 4 所示。 ( 4 ) 规则4 规则4 是当点的负荷性质是混合负荷时，搜索算法需要处理的方式。 当搜索算法遇到一个点的负荷性质是混合负荷时，它要先统计该点出边的目 标点中，有多少个点负荷性质是单负荷或负荷点的点，得出它们的负荷集l m ，和 负荷量( 折算成出线条数n ) 之后，在这基础上，对