配电网最佳抢修路径算法研究

《配电网最佳抢修路径算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、维普资讯http://www.cqvip.com第23卷第2期电力科学与工程V01．23．No．2J岫．．2007l52007年6月’ElectricPowerScienceandEngineering配电网最佳抢修路径算法研究王倩，吕林(四川大学电气信息学院，四川成都610065)摘要：配电网最佳抢修路径问题实际上属于城市交通网络中的最短路径问题。针对3种常用最短路径算法——一类是Dijkstra算法；二类是Floyd算法；三类是A算法，概括分析了各类算法的优缺点以及适用的类型，并分析了交通管制条件下的算法。用改进的Dijkstra算法进行了一个算例分析，证实了这种算法的可行性。在此基础上

2、阐述了目前配电网最佳抢修路径算法存在的问题。最后提出了配电网最佳抢修路径算法的研究方向和发展前景。关键词：最短路径；Dijkstra；A；Floyd；交通管制；配电网中图分类号：TM727文献标识码：A都以研究标号设定法的Dijkstra算法作为基础并0引言根据交通网络的特性进行改进，只是不同系统对Dijkstra算法采用了不同的实现方法。求取最短路随着整个国家电网和区域电网的逐渐壮大和复径的算法还有很多，比如A，bellman-ford，k，杂化，配电网发生故障将是不可避免的，这会给社Moore算法等，主要介绍几种有代表意义的算法。会带来巨大的经济损失和不良的社会影响，因此，1．1基于贪心

3、策略的Dijkstra算法当电力网络发生故障时能及时排除故障，恢复供电基于贪心策略的Dijkstra算法的基本思想是：网的正常供电就显得尤为重要了，这就引出了配电对图G=(E)，源点vEV，设置两个顶点的集合网最佳抢修路径问题。配电网最佳抢修路径问题既和V-S，集合中存放已找到最短路径的顶是GIS系统网络分析中的一个研究热点，也是DMS点，集合存放当前还未找到的最短路径的长度最的重要组成部分，其目的是根据发生故障的地点以短的顶点。初始状态时，集合中只包含源点v0，然及抢修队目前所处的位置，及时派出抢修人员到达后不断从集合中选取到顶点v0路径长度最短的现场，从而使停电时间最短。顶点加入到集合中

4、，集合中每加入一个新的顶点目前对于配电网最佳抢修路径技术的研究也大v0，都要修改顶点v0到集合中剩余顶点的最短多集中在最短路径算法的研究上。解决最短路径问路径长度值，集合中各顶点新的最短路径长度值题的算法在诸多工程领域都有较强的实用价值。一为原来的最短路径长度值与顶点u的最短路径长度般来说最短路径问题分为单源最短路径问题和全源值加上u到该顶点的路径长度值中的较小值。此过最短路径，公认的比较好的算法Dijkstra算法比程不断重复，直到集合的顶点全部加入到中为较适合于单源最短路径，而Floyd算法适合用于求止。这样就可以得到最短路径的值。解全源最短路径。在这种基于贪心策略的Dijkstra算法

5、求解过程中，由于Dijkstra在运行时要执行两套嵌套的FOR1常用算法分析语句，因此其总的时间复杂度是D()。它的核心步骤就是从未被确定为最短路径顶点的所有顶点中在针对配电网最佳抢修路径的分析算法中，大选择一个权值最小的弧段，直到比较得到这一顶点收稿日期：2007-03—18．作者简介：王倩098o一)，女，四川大学电气信息学院助理工程师维普资讯http://www.cqvip.com16电力科学与工程2007芷为止，然后在继续前面相同的工作，不断循环反径，大大提高了算法的执行效率。复。这是一个循环比较的过程，如果不采用任何技1．3A算法巧，未被确定为最短路径的点将以无序的形式存放A算法是

6、在人工智能中的一种典型的启发式在一个链表或数组中。那么要选择一个权值最小的搜索算法，它是目前最为流行的启发式路径规划算弧段就必须把所有点都扫描一遍，在有若干个顶点法，它利用状态空间本身的启发信息，通过选择合适的情况下，这无疑是一个制约计算速度的瓶颈。的估价函数，可根据估价函数的值来动态调整搜索1．2改进的Dijkstra算法策略，以求得最佳解。A+算法的估价函数可表示为：本文的改进Dijkstra算法是采用了两个数组来f(jc)=g)+(jc)，其中g)是从起点S到当前顶点存储网络图，一个用来存储和弧段相关的数据(Net．已付出的代价，h()是从当前顶点到目标顶点gArcList)，另一个则

7、存储和顶点相关的数据(Net·的代价估计函数，A+算法优先搜索具有最小)值Nodelndex)。Net·ArcList用一个数组维护并且以的顶点，必须保证()≤h+()。()的选择取决于弧段起点的点号来顺序排列，同一起点的弧段按权路径规划的标准，在搜索最短路径时，可以当前顶点值排序。这个数组类似于邻接矩阵的压缩存储方式，到目标顶点g的直线距离(jc)表示h)，而g(x)其内容则具有邻接多重表的特点，即一条边以