基于改進蟻群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

中央高?；究蒲袠I務項目(2015QN85)

蘇海鋒(1977—)，男，河北石家莊人，華北電力大學講師，博士，主要從事電網規劃及智能配電網方面的研究. E-mail：hfsups@163.com

許道林(1966—)，男，重慶人，國網重慶市電力公司工程師，主要從事電氣自動化、輸電線路規劃研究. E-maill:17732663282@163.com

TM726；TP301

A

1000-1565(2017)01-0092-09