董平先 郭放 陳晨 宋曉帆 王輝 白萍萍 齊桓若 錢翌明 張浩杰 韓云昊

摘要針對基于傳統(tǒng)手工設(shè)計的電纜敷設(shè)存在誤差大和效率低等問題，將蟻群算法優(yōu)化的計算機輔助設(shè)計應(yīng)用到電纜敷設(shè)路徑規(guī)劃中．利用蟻群算法在復(fù)雜線路中多端點的線路計算優(yōu)勢，解決電纜敷設(shè)的最短路徑問題．同時，本文將電纜敷設(shè)路徑平面化，進(jìn)一步利用Gompertz函數(shù)從信息素限定和揮發(fā)因子自適應(yīng)調(diào)整兩方面進(jìn)行優(yōu)化，提高了蟻群算法的收斂速度和全局性．仿真實驗表明，優(yōu)化的蟻群算法在變電站數(shù)字化三維電纜敷設(shè)過程能夠快速得出最短電纜敷設(shè)路徑，節(jié)省人力物資成本，提高了設(shè)計精度．

關(guān)鍵詞蟻群算法;電纜敷設(shè);信息素;揮發(fā)因子;收斂速度

中圖分類號

TM757;TP18

文獻(xiàn)標(biāo)志碼

A

收稿日期

2022-01-04

資助項目

國家自然科學(xué)基金（61873159）

作者簡介董平先，女，高級工程師，研究方向為電力系統(tǒng)及其自動化．1224231819@qq.com

韓云昊（通信作者），男，博士，副教授，研究方向為電力系統(tǒng)及其自動化．yunhaoh@126.com

0 引言

為了適應(yīng)我國經(jīng)濟的快速發(fā)展和人們對電力日益增長的需求，電力企業(yè)需要加大電網(wǎng)建設(shè)的規(guī)模和速度．其中電纜敷設(shè)是電廠工程建設(shè)的關(guān)鍵基礎(chǔ)環(huán)節(jié)和最復(fù)雜部分之一［1］．以往傳統(tǒng)人工設(shè)計方案是基于二維設(shè)計圖紙或者Auto CAD等軟件進(jìn)行電纜敷設(shè)以及現(xiàn)場電纜長度計算，但由于人工統(tǒng)計電纜的用量和計算匯總電纜的長度會產(chǎn)生很大的誤差和浪費，很難適應(yīng)現(xiàn)代工程需要．隨著電纜敷設(shè)數(shù)量逐年增多以及電纜敷設(shè)方式的多樣化需求，如何實現(xiàn)節(jié)省成本和高效敷設(shè)的統(tǒng)一成為當(dāng)下需要重點解決的問題［2］．

基于上述問題，考慮將計算機的三維數(shù)字化輔助設(shè)計技術(shù)應(yīng)用于電纜敷設(shè)設(shè)計工作［3］．電纜敷設(shè)系統(tǒng)的核心是計算電纜路徑的算法［4-6］，比較常用的有Dijkstra算法［7］、粒子群算法［8］和動態(tài)規(guī)劃算法等．從傳統(tǒng)算法到啟發(fā)式智能算法在電纜敷設(shè)中的應(yīng)用，有利于精確高效地規(guī)劃電纜敷設(shè)路徑．文獻(xiàn)［9］提出通道容量限制、減少轉(zhuǎn)彎數(shù)量等方面改進(jìn)的Dijkstra算法，應(yīng)用于抽水蓄能電站的電纜敷設(shè)中，降低了運算耗時．文獻(xiàn)［10］將A-Star算法運用于電纜最短路徑敷設(shè)中，在減輕設(shè)計人員工作量的同時提高了經(jīng)濟效益．文獻(xiàn)［11］將分層序列法的思想運用于電纜敷設(shè)模型中，采用遺傳算法和Dijkstra算法相結(jié)合求解了電纜敷設(shè)最短路徑，但該算法只能求解兩設(shè)備之間的路徑，并且不能考慮多設(shè)備節(jié)點間的電纜敷設(shè)．文獻(xiàn)［12］采用樹狀、網(wǎng)狀搜索算法，精確地計算了電纜的路徑和長度，但是該算法結(jié)構(gòu)簡單，不適用于較大規(guī)模的復(fù)雜電網(wǎng)．

本文針對傳統(tǒng)蟻群算法應(yīng)用于電纜敷設(shè)設(shè)計存在局部最優(yōu)和收斂速度慢等問題，對算法進(jìn)行優(yōu)化，將其信息素限定在一定范圍內(nèi)，避免算法前期舍棄較差路徑．同時將其揮發(fā)因子隨著Gompertz增長函數(shù)自適應(yīng)調(diào)整，提高算法收斂速度．優(yōu)化后的蟻群算法應(yīng)用在電纜敷設(shè)時，能夠以更短的時間得到最短電纜敷設(shè)長度，并且提高算法迭代過程中的正確率，減緩算法運行過程中的停頓現(xiàn)象，提高電纜敷設(shè)效率和質(zhì)量．

1 電纜敷設(shè)

為適應(yīng)電網(wǎng)發(fā)展和傳輸容量的需求，越來越多的電纜和高電壓電纜投入使用．在電纜敷設(shè)過程中，需要將大小不一的電纜按敷設(shè)規(guī)則放置在支架上，如圖1所示，圓圈代表直徑不同、類型不同的電纜，支架各層所需的實際電纜情況有所不同．

電纜是信息與電流傳輸?shù)妮d體，具有嚴(yán)格的內(nèi)部結(jié)構(gòu)．如圖2所示，電纜由絕緣層、保護(hù)層和線芯等組成，線芯是電纜的導(dǎo)電部分，絕緣層將線芯與大地以及不同相的線芯間在電氣上彼此隔離．

電纜敷設(shè)是沿勘測線路布放、安裝電纜以形成電纜線路的過程，事先需要安裝好橋架、電纜溝等輔助配套設(shè)施，有排管敷設(shè)、直埋敷設(shè)、垂直敷設(shè)等多種敷設(shè)方式．電纜有多種類型，比如中壓電纜、低壓電纜和控制電纜．電氣工程設(shè)計可能需要多種類型的電纜，但值得注意的是，在一個通道里只能敷設(shè)同一種類型的電纜，而且要考慮通道的容積率，保留足夠范圍的裕度，以便后續(xù)的檢修工作［13］．電纜敷設(shè)的核心要求是電纜敷設(shè)路徑符合工程設(shè)計需求且長度最短，為此需要引入電纜敷設(shè)的核心算法．

電纜敷設(shè)是一項復(fù)雜的工程（圖3），敷設(shè)開始前需要進(jìn)行絕緣電阻和耐壓等多種試驗，敷設(shè)過程中要考慮周圍環(huán)境及電纜長度等因數(shù)，敷設(shè)完成以后要掛標(biāo)識牌并完成其他檢查驗收任務(wù)．

2 蟻群算法

2.1 蟻群算法原理

蟻群算法（Ant Colony Algorithm，ACA）是一種仿生智能算法，具有分布式計算、信息正反饋和魯棒性強等特征，并且能與其他算法相融合［14］．研究發(fā)現(xiàn)，螞蟻在路徑上會釋放一種叫作信息素的生物荷爾蒙，而且會保留一段時間并不斷揮發(fā)，螞蟻能夠感知到這種荷爾蒙，并且會有更高的概率選擇信息素濃度較高的路徑．路徑較長的信息素?fù)]發(fā)得相對較多，路徑較短的揮發(fā)得相對較少．下一只螞蟻有更高的概率選擇信息素較濃的路徑，如此反復(fù)，較短的路徑上走過的螞蟻越來越多，得到了最優(yōu)路徑［15-18］，如圖4所示．

從N點到M點共有4條路徑NBAM、NBM、NCBAM、NCBM，第1只螞蟻隨機選擇了NBAM路徑到達(dá)M點，隨著外出覓食的螞蟻的數(shù)量增多，4條路徑上均有螞蟻經(jīng)過并留下會隨著時間揮發(fā)的信息素．隨著信息素的揮發(fā)和增加，最短路徑NBM上的信息素越來越多，同時越來越多的螞蟻選擇了這條路徑，最終所有螞蟻都找到了最短路徑．

3.2 優(yōu)化蟻群算法

電纜敷設(shè)問題也是一種路徑尋優(yōu)問題［6］，將傳統(tǒng)蟻群算法應(yīng)用于電纜敷設(shè)中，會存在一定的缺陷：傳統(tǒng)蟻群算法初始信息素相同，選擇下一節(jié)點的概率隨機，需要長時間形成正反饋，導(dǎo)致收斂速度慢;如果初始信息素更新時，正反饋于次優(yōu)解，很容易出現(xiàn)早熟收斂的現(xiàn)象，陷入局部最優(yōu).為此本文對傳統(tǒng)蟻群算法優(yōu)化處理［15-16］．

3.2.1 信息素限定

螞蟻在路徑選擇過程中，會優(yōu)先選擇幾條較好的路徑，如果剩下的路徑長時間沒有螞蟻路過并且信息素已經(jīng)揮發(fā)完，會導(dǎo)致算法陷入停滯現(xiàn)象．本文在算法中引入τ max和τ min兩個信息素界限：

τ min≤τ≤τ max，? （7）

將算法每次迭代過程中的信息素限定在該范圍內(nèi)，可以改善停滯現(xiàn)象，

3.2.2 揮發(fā)因子自適應(yīng)調(diào)整

信息素是傳統(tǒng)蟻群算法的核心，揮發(fā)因子ρ的大小對信息素起著關(guān)鍵作用．信息素?fù)]發(fā)因子過小時，前期信息素濃度差別不大，螞蟻對支路選擇的可靠性降低，需要更長的時間選擇出最優(yōu)路徑，算法收斂時間更長;當(dāng)信息素?fù)]發(fā)因子過大時，較復(fù)雜的路徑上的信息素會逐漸揮發(fā)至0，算法容易陷入局部最優(yōu)．因此，引入Gompertz增長函數(shù)自適應(yīng)調(diào)整揮發(fā)因子，如圖5所示.

Gompertz模型一般用于精算科學(xué)和細(xì)菌生長曲線建模，是一個遞增函數(shù)，剛開始隨著時間增加，ρ

值增長速度快，到達(dá)某個時間點，增長速度就變慢，然后ρ

值會逐漸趨近于某個極限值α

．Gompertz函數(shù)：

ρ=αe-eβ-γx， （8）

該函數(shù)下限值是0，上限值是α

．β

是生長速度，γ

是生長速率，兩者都與函數(shù)因變量變化快慢有關(guān)．本文將Gompertz函數(shù)應(yīng)用于揮發(fā)因子ρ

自適應(yīng)調(diào)整，將迭代次數(shù)t作為自變量．在算法前期，揮發(fā)因子小，對算法的引導(dǎo)能力弱，有利于全局搜索，提高算法準(zhǔn)確性;隨著迭代次數(shù)增加，揮發(fā)因子逐漸變大，算法的收斂速度也隨之增加．面對不同的環(huán)境，函數(shù)系數(shù)α，β，γ

可以自行設(shè)定，提高算法的靈活性．

3.2.3 優(yōu)化蟻群算法實現(xiàn)

對電纜敷設(shè)問題，蟻群算法的求解［17-20］步驟如下：

1）變電站設(shè)備、節(jié)點坐標(biāo)等數(shù)據(jù)處理.

2）參數(shù)初始化．對蟻群系統(tǒng)中螞蟻個數(shù)M

、迭代總次數(shù)N

、信息素影響因子α

、能見度影響因子β

等參數(shù)設(shè)置具體值.

3）將所有螞蟻均勻放在路徑尋優(yōu)的初始設(shè)備上，并將初始節(jié)點記入路徑表內(nèi).

4）利用式（1）計算選擇下一節(jié)點的概率，并用輪盤賭法選擇下一節(jié)點，如果遇到死路，重新開始步驟2），否則將下一節(jié)點記入路徑表內(nèi).

5）利用式（3）更新信息素，迭代次數(shù)N c+1.

6）若迭代次數(shù)N c

7）輸出最優(yōu)路徑解．

算法流程如圖6所示．

4 算法仿真測試

為了驗證優(yōu)化后的蟻群算法在電纜敷設(shè)中的實效性，基于Matlab軟件編寫程序，將變電站的三維電纜路徑圖投影成二維圖進(jìn)行分析，再利用電纜纜道及節(jié)點坐標(biāo)等數(shù)據(jù)，搭建如圖7所示的電纜路徑平面．其中，仿真參數(shù)設(shè)置如表1所示．

考慮到電纜敷設(shè)路徑選擇的多樣性和設(shè)備節(jié)點間的樹狀結(jié)構(gòu)，借助優(yōu)化蟻群算法在最優(yōu)路徑樹選擇方面的優(yōu)勢，進(jìn)行設(shè)備間的路徑擇優(yōu)．Floyd算法也可以用于電纜敷設(shè)路徑尋優(yōu)，求取最短路徑，但它只能計算兩個端點的路徑長度，有其算法固有的局限性．相比于Floyd算法，優(yōu)化蟻群算法更適合于復(fù)雜線路，不僅可以敷設(shè)兩端點之間的電纜，還可以多端點敷設(shè)．

4.1 路徑尋優(yōu)算例分析

在電纜路徑平面圖中，任意選擇兩個設(shè)備節(jié)點，比如設(shè)備3和設(shè)備7．兩個節(jié)點之間共有3條路徑，優(yōu)化蟻群算法得出的路線L k=117，如圖8所示．經(jīng)驗證，該路線符合最優(yōu)路徑原則，滿足電纜敷設(shè)最初的要求．

任意選擇3個設(shè)備進(jìn)行敷設(shè)，尋找其中的最短路徑，如圖9的設(shè)備1、設(shè)備3和設(shè)備7，一共有多種敷設(shè)路徑，各條路徑長短不一．優(yōu)化蟻群算法得出的結(jié)果是L k=167，經(jīng)驗證，符合最短路徑需求．

任意選擇4個設(shè)備進(jìn)行敷設(shè)，尋找其中的最短路徑，如圖10的設(shè)備1、設(shè)備3、設(shè)備7和設(shè)備9，一共有多種敷設(shè)路徑，各條路徑長短不一．優(yōu)化蟻群算法得出的結(jié)果是L k=222，經(jīng)驗證，符合最短路徑需求．

4.2 算例對比分析

在電纜路徑平面圖的基礎(chǔ)上，分別利用傳統(tǒng)蟻群算法和優(yōu)化蟻群算法進(jìn)行多次路徑尋優(yōu)程序運行．面對簡單不復(fù)雜路徑，傳統(tǒng)蟻群算法可以得出實際情況下的最短路徑，但運行在交叉線路較多等復(fù)雜情況下的路徑時，會存在局部最優(yōu)，甚至出現(xiàn)停滯現(xiàn)象．如表2所示，累計進(jìn)行30次實驗，傳統(tǒng)蟻群算法的局部最優(yōu)率為16.67％，出現(xiàn)4次停滯現(xiàn)象;而優(yōu)化后蟻群算法的局部最優(yōu)率為3.33％，只出現(xiàn)1次停滯現(xiàn)象．可見改進(jìn)算法可以較大地優(yōu)化程序運行，為電纜找出最短路徑．

如圖11所示，不考慮信息素濃度限制，分別利用優(yōu)化前后蟻群算法運行10、20、30、40次，記錄并

計算出多次運行總時間的平均值．傳統(tǒng)蟻群算法運

行30次所得時間平均值為0.251 s，優(yōu)化后的蟻群算法為0.147 s．可以看出，相比于傳統(tǒng)蟻群算法，加入Gompertz模型的優(yōu)化蟻群算法迭代時間更短，收斂速度更快．

5 結(jié)語

基于計算機的三維數(shù)字化輔助電纜敷設(shè)平臺，將優(yōu)化蟻群算法應(yīng)用于電纜敷設(shè)設(shè)計中，精確地規(guī)劃了電纜敷設(shè)路徑．本文給出了電纜敷設(shè)的具體過程以及優(yōu)化蟻群算法的數(shù)學(xué)模型，并且針對傳統(tǒng)蟻群算法在電纜敷設(shè)應(yīng)用中存在的問題，在信息素和揮發(fā)因子兩方面對蟻群算法優(yōu)化改進(jìn)．實驗表明優(yōu)化后的蟻群算法可以實現(xiàn)全局最優(yōu)，并且收斂速度更快，提高了電纜敷設(shè)的實效性．

參考文獻(xiàn)

References

［1］ 胡秋野，楊世春，歐景茹.論環(huán)網(wǎng)柜在城市電網(wǎng)中的應(yīng)用［J］.高電壓技術(shù)，2004，30（增刊1）：8-9

HU Qiuye，YANG Shichun，OU Jingru.Discussion on application of ring main in urban distribution system［J］.High Voltage Engineering，2004，30（sup1）：8-9

［2］ 徐俊.電力電纜施工、運行故障案例及分析［J］.高電壓技術(shù)，2004，30（增刊1）：89，93

XU Jun.Analysis of cable fault in construction and operation［J］.High Voltage Engineering，2004，30（sup1）：89，93

［3］ 沙少川，溫杰.基于三維數(shù)字化技術(shù)的光電纜敷設(shè)的方法探討［J］.電子測試，2021（20）：119-121

SHA Shaochuan，WEN Jie.Discussion on the method of laying optical cable based on 3D digital technology［J］.Electronic Test，2021（20）：119-121

［4］ 于洋，魏長江.優(yōu)化蟻群算法在電纜敷設(shè)中的應(yīng)用［J］.青島大學(xué)學(xué)報（自然科學(xué)版），2020，33（3）：65-70，75

YU Yang，WEI Changjiang.Application of ant colony optimization algorithm in cable laying［J］.Journal of Qingdao University （Natural Science Edition），2020，33（3）：65-70，75

［5］ 于洋.基于優(yōu)化蟻群算法的PDMS電纜敷設(shè)設(shè)計路徑方法研究［D］.青島：青島大學(xué)，2020

YU Yang.Research on PDMS cable laying design path method based on optimized ant colony algorithm［D］.Qingdao：Qingdao University，2020

［6］ 鮑偉強.蟻群優(yōu)化電纜敷設(shè)系統(tǒng)的研究［D］.南寧：廣西大學(xué)，2012

BAO Weiqiang.Ant colony optimization for cable laying system［D］.Nanning：Guangxi University，2012

［7］ 朱翰超，杜亞靜，季節(jié).Dijkstra算法在電力電纜敷設(shè)優(yōu)化研究中的應(yīng)用［J］.電氣應(yīng)用，2014，33（24）：115-118

ZHU Hanchao，DU Yajing，JI Jie.Application of Dijkstra algorithm in power cable laying optimization ［J］.Electrotechnical Application，2014，33（24）：115-118

［8］ 劉召朝，張丹，周琛，等.基于改進(jìn)粒子群算法的多分支電纜自動布線技術(shù)［J］.機械制造與自動化，2021，50（1）：177-179

LIU Zhaochao，ZHANG Dan，ZHOU Chen，et al.Automatic routing technology of multi-branch cable harness based on improved particle swarm optimization［J］.Machine Building ＆ Automation，2021，50（1）：177-179

［9］ 黃祖光，朱安平，王凱，等.基于Dijkstra算法的電纜敷設(shè)系統(tǒng)設(shè)計及實現(xiàn)［J］.電網(wǎng)與清潔能源，2020，36（6）：105-110

HUANG Zuguang，ZHU Anping，WANG Kai，et al.Design and implementation of cable laying system based on Dijkstra algorithm［J］.Advances of Power System ＆ Hydroelectric Engineering，2020，36（6）：105-110

［10］ 李旭明.基于A-Star算法的三維電纜設(shè)計系統(tǒng)的設(shè)計與實現(xiàn)［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2018

LI Xuming.The design and implementation of three-dimensional cable design system based on A-Star algorithm［D］.Harbin：Harbin Institute of Technology，2018

［11］ 李治，韓丹，任興龍，等.基于遺傳算法和改進(jìn)的Dijkstra算法的電纜敷設(shè)優(yōu)化研究［J］.數(shù)學(xué)的實踐與認(rèn)識，2016，46（17）：160-167

LI Zhi，HAN Dan，REN Xinglong，et al.Research of the optimization of cable laying with genetic algorithm and improved Dijkstra algorithm［J］.Mathematics in Practice and Theory，2016，46（17）：160-167

［12］ 羅建國，韋思亮.基于樹狀、網(wǎng)狀搜索算法的電纜敷設(shè)設(shè)計與應(yīng)用［J］.熱力發(fā)電，2013，42（3）：103-105

LUO Jianguo，WEI Siliang.Tree and mesh search algorithm based cable laying：design and application［J］.Thermal Power Generation，2013，42（3）：103-105

［13］ 何江濤，焦陽，葉笛，等.電纜不同敷設(shè)方式下溫度場與載流量的仿真計算［J］.電測與儀表，2016，53（3）：99-104

HE Jiangtao，JIAO Yang，YE Di，et al.Simulation and computation of temperature field and ampacity of conduit cable laying in different ways［J］.Electrical Measurement ＆ Instrumentation，2016，53（3）：99-104

［14］ 張徐亮，張晉斌.基于協(xié)同學(xué)習(xí)的蟻群電纜敷設(shè)系統(tǒng)［J］.計算機工程與應(yīng)用，2000，36（5）：181-182

ZHANG Xuliang，ZHANG Jinbin.Ant colony cable laying system based on cooperative learning［J］.Computer Engineering and Applications，2000，36（5）：181-182

［15］ 顏杰，秦飛舟，翟帥華.一種改進(jìn)蟻群算法的移動機器人路徑規(guī)劃［J］.軟件導(dǎo)刊，2019，18（2）：5-8

YAN Jie，QIN Feizhou，ZHAI Shuaihua.An improved ant colony algorithm for mobile robot path planning［J］.Software Guide，2019，18（2）：5-8

［16］ 任紅格，胡鴻長，史濤.基于改進(jìn)蟻群算法的移動機器人動態(tài)路徑規(guī)劃［J］.現(xiàn)代電子技術(shù)，2021，44（20）：182-186

REN Hongge，HU Hongchang，SHI Tao.Mobile robot dynamic path planning based on improved ant colony algorithm［J］.Modern Electronics Technique，2021，44（20）：182-186

［17］ Zhou J Z，Wang C，Li Y Z，et al.A multi-objective multi-population ant colony optimization for economic emission dispatch considering power system security［J］.Applied Mathematical Modelling，2017，45：684-704

［18］ Birattari M，Pellegrini P，Dorigo M.On the invariance of ant colony optimization［J］.IEEE Transactions on Evolutionary Computation，2007，11（6）：732-742

［19］ Deneubourg J L，Aron S，Goss S，et al.The self-organizing exploratory pattern of the argentine ant［J］.Journal of Insect Behavior，1990，3（2）：159-168

［20］ 李奇才，舒遠(yuǎn)仲，洪宇軒.一種蟻群算法與自適應(yīng)機制的路徑規(guī)劃算法優(yōu)化［J］.機械科學(xué)與技術(shù)，2022，41（7）：1095-1101

LI Qicai，SHU Yuanzhong，HONG Yuxuan.Optimization of path planning algorithm based on ant colony algorithm and adaptive mechanism［J］.Mechanical Science and Technology for Aerospace Engineering，2022，41（7）：1095-1101

Cable laying path planning based on optimized ant colony algorithm

DONG Pingxian1 GUO Fang1 CHEN Chen1 SONG Xiaofan1 WANG Hui1

BAI Pingping1 QI Huanruo1 QIAN Yiming2 ZHANG Haojie2 HAN Yunhao2

1Economic and Technological Research Institute of State Grid Henan Electric Power Company，Zhengzhou 450002

2School of Electric Power Engineering，Shanghai University of Electric Power，Shanghai 200090

Abstract

To address the large error and low efficiency of traditional manual design in cable laying task，the computer-aided design optimized by Ant Colony Algorithm （ACA） is applied to cable laying path planning.The shortest path for cable laying is solved via the ACAs multi terminal path calculation for complex path planning.Furthermore，the planarized cable laying path is optimized via Gompertz function in aspects of pheromone restriction and self-adaptive adjustment of volatilization factor，thus improves the ACA in both convergence speed and global performance.The simulation results show that the optimized ant colony algorithm can quickly obtain the shortest cable laying path in the task of substation digital 3D cable laying，which saves the cost of manpower and materials，and improves the design accuracy.

Key words ant colony algorithm （ACA）;cable laying;pheromone;volatilization factor;convergence rate