基于改进蚁群A*算法的输电线路路径搜索

苏海锋，许道林，李汶江，黄昊，郑炜

(1.华北电力大学 电力工程系，河北 保定 071003；2.国网重庆市电力公司 基建部，重庆 400001； 3.重庆电力设计院 输电处，重庆 401120)



基于改进蚁群A*算法的输电线路路径搜索

苏海锋1，许道林2，李汶江2，黄昊2，郑炜3

(1.华北电力大学 电力工程系，河北 保定 071003；2.国网重庆市电力公司 基建部，重庆 400001； 3.重庆电力设计院 输电处，重庆 401120)

以GIS作为输电线路路径选择的地理信息采集和分析平台，综合考虑线路走廊区域地形、地貌、地物、环境等方面的影响因素，利用层次分析法得到线路走廊区域的线路综合成本量化值.结合高压输电线路路径选择特点，建立了基于改进蚁群算法的高压输电线路路径自动搜索模型，实现了输电路径的跨越式搜索和障碍的规避.模型引入路径局部成本控制启发策略及A*导向算法，提高了路径搜索效率.用C#2010和ArcGIS 10.0开发了输电线路路径自动选择程序，并采集无人机航拍的现场地理数据,验证了模型和方法的有效性.

输电线路路径搜索；地理信息系统；层次分析法；蚁群算法；A*算法

长距离输电线路路径选择，不仅要考虑地形、地质、水文等自然条件，同时要兼顾施工难度、工程投资及线路运行对沿线环境的影响，是一个涉及施工难度、地理环境、工程投资等诸多因素的空间多目标决策问题.传统人工输电线路路径选择，首先在输电线路路径选择区域的高程图和地形图上按照经验选取几条可行路线，再进行沿线路径情况的实地调查，最终确定路径方案.这种方法受主观因素影响较大，且无法同时顾全多种影响因素.因此，人们不断地尝试借助现代科技手段完善输电线路路径选择工作.

随着地理信息系统(geographic information system，GIS)的发展，其强大的地理信息分析、处理能力在诸多领域得到了成功应用[1-2]，很多人提出了将GIS应用于输电线路路径选择[3-5].文献[3-4]将层次分析法与专家知识相结合建立了输电线路路径综合评价模型，用于备选路径方案的优选.文献[5]提出了使用GIS工具3D化规划区域并使用ArcGIS自带的Dijsktra算法进行输电线路路径搜索，然而Dijkstra算法是以起始点为中心向外层层扩展，缺少启发策略，适用于在小范围区域内进行线路规划.文献[6]以三维可视化的方式直观显示线路走廊内各类型综合图形信息，如电网数据、覆冰区、协议区等，辅助路径的初步规划.文献[7]介绍了将GIS的各种辅助决策功能用于输电线路路径优化设计的优势.文献[8]提出应用卫星遥感图像和GIS 为输电线路选线和杆塔定位提供技术支持，对线路路径进行优化.以上文献主要利用了GIS的数据管理、分析、显示能力，对已有备选路径进行优化，而没有实现在综合考虑大量输电线路路径设计相关空间信息基础上的输电线路路径的自动搜索.另外，高压输电线路路径选择区域范围较大，传统的Dijkstra等算法难以解决在大规模数据中寻找最优路径的问题[9].因此，基于GIS技术和计算机智能技术进行输电线路路径自动搜索具有重要的现实意义，是输电线路路径设计的必然发展趋势.

蚁群算法是一种模拟蚂蚁在寻找食物的过程中获得最优路径的行为，是在图中寻找最优路径的几率型算法[10].蚁群算法在解决路径搜索问题方面具有许多优越性，如可以得到较短的路径、可以规避障碍等.文献[11]应用群智能算法来确定模糊测度，验证了群智能算法的思想可以引入到这个具体问题中，并验证了群智能算法的优势：实现容易，并验证了蚁群算法能够得到更精确的解.文献[12]提出一种基于图解蚂蚁系统的配电网动态重构问题的求解方法，可以有效缩小搜索范围，找到最优解.高压输电线路路径搜索是一种长距离、多约束条件的路径搜索问题.将GIS和蚁群算法相结合是解决输电线路路径自动搜索的有效方法之一.首先，用GIS栅格数据表示的路径选择区域的高程、风速、覆冰等图层信息适合用蚁群算法求解；其次，GIS栅格数据的多要素(每个图层表示一个影响路径选择的要素)综合评价模型，可以方便地得到线路通过某个栅格的综合成本值，从而实现考虑多要素影响的路径自动选择.

本文结合输电线路路径规划特点，以GIS作为输电线路路径选择的地理信息采集和分析平台，用层次分析法量化和整合地理单元中复杂的地理信息.结合输电线路路径选择特点，建立了基于改进蚁群A*算法的路径自动搜索模型.模型引入路径局部成本控制启发策略及A*导向算法，使路径搜索更加快速准确.应用C#2010和ArcGIS 10.0开发了输电线路路径自动搜索程序，采用实际航拍获取地理信息数据，验证了模型和方法的有效性.

1 路径选择区域地理栅格成本评价模型

输电线路路径搜索需要综合考虑路径经过区域地理栅格的众多影响因素，即以输电线路路径通过区域栅格所需代价最小为目标函数.层次分析法(analytic hierarchy process，AHP) 是一种系统分析与精确计量的多准则决策方法，很好地将定性与定量分析相结合[13-15].本文采用层次分析法计算路径经过区域栅格的多要素综合成本评分值.

1.1 栅格分类

输电线路经过的区域较大，周围环境较为复杂.路径选择需要综合考虑路径总长度、经过区域地形地貌、地质、冰区、交通、施工环境等多种问题.根据上述因素，将路径经过区域的栅格分为3类：Ⅰ类，线路可以跨越也可以架设杆塔的栅格(如无限制的平原地区等)；Ⅱ类，线路可以跨越但不能架设杆塔的栅格(如河流、公路等)；Ⅲ类，线路不能跨越也不能架设杆塔的栅格(如自然保护区、飞机场升降区等).

1.2 栅格多要素综合成本评分值计算

输电线路路径经过区域备选栅格(Ⅰ、Ⅱ类栅格)综合成本评分值计算过程如下.

1)建立栅格综合成本评价层次结构模型

根据输电线路路径选择工作内容，将线路路径栅格成本分为2大类，一类是栅格架线成本评分值，另一类是立塔成本评分值.影响这2类成本评分值的子目标有4个，分别为线路基础工程成本评分值、杆塔工程成本评分值、架线工程成本评分值、征地工程成本评分值.最后(右)一层为各成本的影响因素层，是影响各子目标取值的地理信息因素.详细的栅格综合成本评价层次结构如图1所示.

图1 栅格成本评价层次结构

2)路径经过区域地理信息因素等级评分

根据不同地理信息因素对规划路径的影响程度，将栅格成本等级分为：1级，成本最低，较适合电力线路建设；2级，成本较低，适合电力线路建设；3级，成本中等，可以建设电力线路；4级，成本较高，施工难度较大，耗费较多，建设困难；5级，成本很高，建设难度很大.建立不同地理信息因素图层，基于上述等级标准，利用客观数据(GIS高程图、坡度图、土壤、气象情况等)和专家评估数据(如不可行区域、施工困难区域等)得到各图层栅格单要素成本值矩阵.

3)构造比较矩阵

设图1中某一目标层有n个影响因素X={x1,x2,…，xn}，要计算其对上一层某个综合因素的影响程度，需要对本层的因素两两进行比较，aij表示第i个因素相对第j个因素的影响程度，本文利用9级比例标尺建立评价尺度[17]，构造的比较矩阵如式(1)所示.

(1)

4)计算下层因素对上层目标的影响权重

计算矩阵A的最大特征值对应的特征向量，归一化后得出目标函数权向量w=(w1,w2,…，wn)T.

5)计算目标层栅格综合成本评分值

设目标层变量为z，z为下一层n个变量x1,x2,…，xn的线性组合，即

z=w1x1+w2x2+…+wnxn.

(2)

6)计算栅格多要素综合成本评分值.

遍历各图层每个地理信息栅格，将各影响因素图层的成本评分矩阵代入到上述层次分析模型中，计算出每个栅格子目标成本评分值，再将子目标成本评分值代入子目标到总目标的层次分析模型中，计算出栅格多要素综合成本评分值.

2 改进蚁群A*算法的路径搜索模型

2.1 基本蚁群算法路径搜索分析

传统蚁群算法寻找路径的规则由避让规则、移动规则和信息素规则3部分组成.每只蚂蚁在当前位置根据这3个规则，通过轮盘赌的方式从邻居栅格中寻找并确定下一时刻位置，搜索过程如图2所示.

图2 蚁群算法搜索的方式

传统蚁群算法采用的是相邻栅格的搜索形式，用于输电线路路径选择存在其局限性：1) 搜索步长小，不适于长距离搜索；2) 无法做出跨越动作，不符合架空输电线路可以跨越地面障碍物的特点；3) 没有启发搜索策略，容易产生绕路现象，搜索效率低.

2.2 改进蚁群算法路径搜索模型

1)跨越式邻居蚁群搜索模型

为了克服图2所示传统蚁群算法进行输电线路路径搜索时存在的问题，本文在常规蚁群搜索模型基础上，提出了适用于输电线路路径搜索的改进蚁群搜索模型，该模型可实现输电线路的跨越搜索，如图3所示.

在图3b所示的栅格数据模型中，黑色栅格为路径上当前立杆塔栅格位置，灰色栅格为可能的下一立杆塔邻居栅格位置，白色栅格为线路跨越邻居栅格，即架线邻居栅格.

2)变步长搜索机制

由于搜索模型具有跨越特点，为了满足经济性要求，即在符合输电线路设计要求的情况下尽量减少杆塔数量，搜索时首先以最大跨距进行，满足立杆塔和线路跨越校验条件的栅格成为当前栅格的下一立杆塔栅格.若不存在满足校验条件的邻居栅格，则自动拉近搜索步长(图4)，重新搜索判断.

图3 跨越式蚁群搜索邻居模型

图4 变步长机制示意

3)改进蚁群算法与A*算法的结合

由于蚁群搜索模式是广度优先搜索，向四周扩散，没有方向性，容易产生路径迂回现象，在大规模路径搜索时耗时长且难以找到终点.A*算法是一种静态路网中求解最短路径启发式搜索方法，在路径规划中得到广泛应用[16].它利用启发函数来构造任意点到目标点的远近程度来增强搜索的方向性，提高搜索效率.A*算法在数据节点越紧密、分布越规整的规划数据中算法越稳定，而电力线路路径选择中用的栅格数据正好符合这一特点.采用A*导向启发算法后的蚁群搜索趋势对比如图5所示.

图5 采用A*评估函数前后搜索区域比较

可以看出未采用A*导向算法时，搜索过程没有方向性，搜索路径为一系列同心圆；采用了A*导向算法后，搜索方向趋向于终点，增强了搜索的方向性.

2.3 改进蚁群A*算法的输电线路路径搜索

输电线路路径采用点编码方式，从线路路径起点开始，采用跨越式邻居栅格搜索模式，依次搜索出线路路径的立杆塔栅格和可跨越架线邻居栅格，直至终点，最后连接所有立杆塔栅格形成线路路径.

1)栅格状态类型

规划区域内栅格分为3种状态：1)如果在某一时刻该栅格为被选中栅格，那么该栅格状态为“1”；2)如果为被跨越栅格，那么该栅格状态为“2”；3)如果栅格既不是被选中栅格，也不是被跨越的栅格，那么该栅格状态为“0”.状态为“1”和“2”的栅格不可以作为下一时刻所选中或跨越的栅格，状态为“0”的栅格可以作为下一时刻备选栅格.

2)邻居栅格的确定准则

根据输电线路路径选择特点，邻居栅格需要满足以下条件：①在规定的搜索步长范围内；②栅格类型为Ⅰ或Ⅱ类，即该栅格必须为可以设立杆塔的栅格；③栅格状态为“0”，即该栅格必须为未形成路径的栅格；④每次搜索新形成路径不能和已形成的路径重合或交叉.

3)改进蚁群A*算法的路径搜索策略的实现

输电线路路径搜索过程就是一系列邻居栅格确定的过程.路径搜索应在保证输电线路安全性、可靠性的前提下，以经济性最优为目标.本文在路径搜索过程中引入了局部成本最优、A*导向、信息素引导多种启发策略.综合考虑上述启发策略的邻居栅格选择概率模型如下：

(3)

式中，(xi,yi)为第i个邻居栅格的位置；α、γ、β分别为局部成本控制系数a、A*导向控制系数m、信息素浓度控制系数b的控制强度；M为待选邻居栅格数.

各启发策略控制系数的计算表达式如下：

①局部成本最优控制系数

局部成本最优策略即在确定下一时刻栅格的过程中，综合成本评分值低的栅格被选中的概率高，其表达式为

(4)

式中，cL(i) 为被跨越栅格(架线邻居栅格)i的成本评分值；n为被跨越栅格数；cT(x,y)为坐标位置为(x,y)的立塔栅格成本评分值.

由式(4)可以看出，待选邻居栅格成本评分值越高，被选中的概率越小.但单独依靠局部成本控制来确定下一个栅格位置时，很容易选中局部成本评分值较低的栅格，易使输电线路路径偏离了既定走向.因此，本文通过引入A*导向算法来解决上述问题.

②A*导向控制系数

基于A*导向的启发策略会引导蚁群向着目标点的方向搜索，A*导向控制系数表达式如下：

mxy=k/w(x,y→D)，

(5)

由式(5)A*导向控制策略可以看出，邻居栅格的确定考虑了邻居栅格到终点的成本评分值，成本评分值越小，被选中为邻居栅格的概率越大，减小了选择下一个邻居栅格时陷入局部最优的概率.

③信息素浓度控制系数

每只蚂蚁搜索完从起点到终点的路径后，需根据路径成本评分值更新路径经过栅格的信息素浓度，用于引导下次蚂蚁进行有效路径搜索，信息素浓度越大，栅格被选中的概率越高.同时为了避免多次搜索结果累积的信息素浓度过大导致路径过早成熟，引入信息素挥发系数.栅格信息素浓度控制系数表达式如下：

(6)

④被选路径成本评分值计算

输电线路路径成本评分值包括整条路径的架线工程成本评分值和立塔工程成本评分值.设从起点到终点经过了T次搜索，则路径的总成本评分值表达式如下：

w=w1+…+wt+…+wT，

(7)

⑤改进蚁群A*算法的路径自动搜索流程

在高压输电线路路径选择的过程中，由于数据规模较大，如果直接对整个栅格地图数据进行选线，数万阶的邻接矩阵，会耗费大量时间，产生较多路径甚至得不到最优解.本文引入了辅助中间点定位的方法，即在起点与终点之间，标注出一些中间节点作为辅助节点，把对整段路径的搜索转化成分段搜索，从而可以减小搜索范围，节约储存空间，提高搜索效率.每段路径详细搜索流程如图6所示.

3 算例验证

根据以上所述方法，用C#2010+Arcgisengine10.0作为开发平台，开发了输电线路路径自动搜索程序.算例选择测试区域的无人机航拍图，如图7中间部分所示.该图包含地理图像、地形、高程、地质等相关地理信息.该区域南北距离12.75km，东西距离为14.75km，起点为A，终点为B，测试区起点附近的公路(蓝色区域)需要跨越，居民区和工厂(黄色区域)需要避让，下面针对该区域进行具体路径搜索测试.

图6 路径搜索流程

原始图形为矢量图，进行路径搜索前首先利用GIS工具生成栅格地图.补充协议区(不可行区域)、风速、覆冰等其他相关地理信息，判断可行区域并初始化各栅格类型，同时确定各指标因子评分值，生成栅格属性信息表；再利用层次分析法生成各栅格成本评分值；最后，将栅格坐标、栅格类型、栅格成本评分值对应导入路径自动选择功能模块.

为了比较本文方法和文献[5]中的Dijkstra算法的有效性，将上述地图数据生成大小分别为500m×500m(栅格规模为[26×30])和50m×50m(数据规模为[255×295])的栅格，设置初始搜索步长200～300m.分别采用Dijkstra算法和蚁群A*算法对2种精度栅格地图进行路径自动搜索，算法参数取值见表1，搜索获得的路径结果如图7和图8所示，2种算法的搜索结果和用时如表2所示.

表1 算法参数取值 Tab.1 Algorithm parameter value

图7 50 m×50 m精度下蚁群A*算法搜索结果

图8 500 m×500 m精度下2种算法搜索结果

表2 2种算法性能比较 Tab.2 Performance comparison of two algorithms

由于图8采用的是500 m×500 m栅格，地图信息反映很不精确，搜索路线路径时，为避让不可行区域，会出现大幅的避让，因此得到的路径综合成本评分值较大.

将栅格精度改为50 m×50 m后，数据规模为[255×295].采用Dijkstra算法搜索30 min仍未得到搜索结果.采用蚁群A*算法用时91 s搜到结果，拐点数12，综合成本评分值为2 411.38 score.从图7中右侧局部放大图可以看出，算法成功搜索出可行路径，并避让了不可行区域.

4 结语

以GIS作为输电线路路径选择的地理信息采集和分析平台，建立了基于蚁群算法的输电线路路径自动搜索改进模型，通过实例验证得到结论如下：

1)利用层次分析法量化处理输电线路路径规划影响因素，为输电线路路径自动搜索提供了准确的基础数据，使得路径选择更具科学性；

2)改进后的邻居栅格模型，实现了输电线路路径选择中跨越和避让障碍的功能；

3)提出的路径搜索局部成本控制启发策略及A*导向算法，改进了单纯的蚁群算法搜索方向性差的缺点，提高了搜索效率.

[1] 陈昊, 湛燕, 张素芳. 电力智能服务系统的设计与实现[J]. 河北大学学报(自然科学版), 2010,30(4):434-438. DOI:10.3969/j.issn.1000-1565.2010.04.020. CHEN H, ZHAN Y, ZHANG S F. Design and realization of power intelligent service system[J]. Journal of Hebei University (Natural Science Edition), 2010,30(4):434-438. DOI:10.3969/j.issn.1000-1565.2010.04.020.

[2] 罗庆, 吴良良, 寿挺,等. 基于CIM的电网规划管理决策辅助系统[J]. 电力系统保护与控制, 2016(4):111-117. DOI: 10.7667/PSPC150685. LUO Q , WU L L, SHOU T, et al. Decision support system for power grid planning and management based on CIM[J]. Power System Protection and Control, 2016(4):111-117. DOI: 10.7667/PSPC150685.

[3] 朱义中, 陈雄波. 基于GIS的输电线路决策支持系统优选路径[J]. 四川理工学院学报(自然科学版), 2008,21(1):81-84. DOI:10.3969/j.issn.1673-1549.2008.01.027 ZHU Y Z, CHEN X B. Optimum selection of route by means of decision support system of transmission line based on GIS[J]. Journal of Sichuan University of Science & Engineering(Natural Science Edition), 2008,21(1):81-84. DOI:10.3969/j.issn.1673-1549.2008.01.027

[4] 朱义中, 程次来, 陈雄波. 利用基于GIS的输电线路决策支持系统优选路径方案[J]. 电力信息与通信技术, 2008,6(2):80-82.

[5] ABED A D. The Selection of optimum path for electric power transmission towers, high-pressure in Balad City[J]. American Journal of Geographic Information System, 2014, 3(3):135-146. DOI:10.5923/j.ajgis.20140303.03.

[6] 陈海鹏, 冯飞. 基于3维GIS的输电线路辅助初步设计系统实现[J]. 北京测绘, 2013(5):67-69. DOI:10.3969/ j.issn.1007-3000.2013.05.018. CHEN H P, FENG F. Application of 3D GIS in power transmission line preliminary design system implementation[J]. Beijing Surveying and Mapping, 2013(5):67-69. DOI:10.3969/j.issn.1007-3000.2013.05.018.

[7] 牛根良. GIS管道线路优化设计平台[J]. 科技传播, 2010(11): 83-84.

[8] 杨泰平, 唐川, 段永坤, 等. RS和GIS 在高压输电线选线中的应用[J]. 地理空间信息, 2010,8(2):115-117. YANG T P, TANG C , DUAN Y K, et al. Application of RS and GIS to the route selection of the high voltage transmisson lines[J]. Geospatial Information, 2010,8(2): 115-117.

[9] 鲍培明. 距离寻优中Dijkstra算法的优化[J]. 计算机研究与发展, 2001,38(3):307-311. BAO P M. A optimization algorithm based on Dijkstra’s algorithm search of shortcut [J]. Journal of Computer Research & Development, 2001,38(3):307-311.

[10] 夏卫雷, 王立松. 基于MapReduce的并行蚁群算法研究与实现[J]. 电子科技, 2013,26(2):146-149. DOI:10.16180/j.cnki. issn1007-7820.2013.02.038. XIA W L, WANG L S. Research on and implementation of parallel ant colony algorithm based on Mapreduce [J]. Electronic Sci & Tech , 2013, 26(2):146-149. DOI:10.16180/j.cnki.issn1007-7820.2013.02.038.

[11] 宋国际. 群智能算法及其在确定模糊测度中的应用研究[D]. 保定：河北大学, 2011.

[12] 孙元博, 张承学, 胡志坚. 基于图解蚂蚁系统的配电网动态重构[J]. 电力系统保护与控制, 2015,43(12):73-78. SUN Y B, ZHANG C X, HU Z J. Dynamic distribution network reconfiguration method based on graph ant system[J]. Power System Protection and Control, 2015,43(12):73-78.

[13] 黄知超, 谢霞, 王斌. 结合模糊综合评判与决策的电力系统状态估计[J]. 电力系统保护与控制, 2015,43(7):65-69. HUANG Z C, XIE X , WANG B . Power system state estimation combined with fuzzy comprehensive evaluation and decision-making[J]. Power System Protection and Control, 2015,43(7):65-69.

[14] 张春琴, 张玉芬. 模糊综合评判在水田质量评价中的应用[J]. 河北大学学报(自然科学版), 2014,34(4):357-362.DOI: 10.3969/j.issn.1000-1565.2014.04.005. ZHANG C Q, ZHANG Y F. Application of fuzzy comprehensive evaluation in paddy-field quality assessment[J]. Journal of Hebei University (Natural Science Edition), 2014,34(4):357-362. DOI: 10.3969/j.issn.1000-1565. 2014.04.005.

[15] 孙建红, 周慧, 刘红霞. 基于层次分析法的科技成果转化信息服务评价模型[J]. 河北大学学报(自然科学版), 2013, 33(3):236-241.DOI: 10.3969/j.issn.1000-1565.2013.03.003. SUN J H, ZHOU H , LIU H X. Evaluation model of information service in science and technology achievements transform based on analytic hierarchy process[J]. Journal of Hebei University (Natural Science Edition), 2013, 33(3):236-241.DOI: 10.3969/j.issn.1000-1565.2013.03.003.

[16] 秦玉鑫, 王红旗, 杜翠杰. 基于双层A*算法的移动机器人路径规划[J]. 制造业自动化, 2014，36(12):21-25. DOI:10.3969/ j.issn.1009-0134.2014.12(下).06.

(责任编辑：赵藏赏)

Automatic search of the transmission line path based on the improved ant colony and A*algorithm

SU Haifeng1,XU Daolin2,LI Wenjiang2,HUANG Hao2,ZHENG Wei3

(1.Electrical Engineering Department,North China Electric Power University,Baoding 071003,China;2.Infrastructure Department of State Grid,Chongqing Electric Power Company,Chongqing 400001,China; 3.Transmission Line Department,Chongqing Electric Power Design Institute,Chongqing 401120,China)

GIS is used as a platform to collect and analyze the geographic information of the transmission line path selection,and use analytic hierarchy process to quantify and integrate complex geographic information in geographical units.In combination with the characteristics of the transmission line path selection,an improved model of ant colony algorithm search for the path is established.The model uses the heuristic search,integrate the local cost control and the A*algorithm,which makes the path search faster and more accurate.The geographic data is provided by the actual aerial,using the C#2010 and the ArgGis 10.0 to build a transmission line path automatic selection procedures,which verified the validity of the model and the method.

transmission line paths search;GIS;analytic hierarchy process;ant colony algorithm;A*algorithm

10.3969/j.issn.1000-1565.2017.01.014

2016-06-23

中央高校基本科研业务项目(2015QN85)

苏海锋(1977—)，男，河北石家庄人，华北电力大学讲师，博士，主要从事电网规划及智能配电网方面的研究. E-mail：hfsups@163.com

许道林(1966—)，男，重庆人，国网重庆市电力公司工程师，主要从事电气自动化、输电线路规划研究. E-maill:17732663282@163.com

TM726；TP301

A

1000-1565(2017)01-0092-09