輸電線路貨運(yùn)路徑規(guī)劃算法?

秦 劍 張飛凱 劉中書 劉 晨

（1.中國電力科學(xué)研究院有限公司 北京 100055）（2.國網(wǎng)陜西省電力公司建設(shè)分公司 西安 710065）

1 引言

一般情況下儲存或加工輸電線路施工物料的物料站位于交通便利、便于物料裝卸的交通要道，而待建的鐵塔則多處于偏僻的山區(qū)，遠(yuǎn)離已有公路，僅依靠公路運(yùn)輸無法將物料從物料站運(yùn)送到遠(yuǎn)離公路的在建鐵塔。針對公路運(yùn)輸?shù)亩贪?，可在路邊和鐵塔附近分別設(shè)置上料點(diǎn)和下料點(diǎn)，在上下料點(diǎn)間架設(shè)臨時(shí)貨運(yùn)索道，實(shí)現(xiàn)物料轉(zhuǎn)運(yùn)。該方法是當(dāng)下實(shí)現(xiàn)輸電線路施工物料運(yùn)輸?shù)闹髁鞣椒ā?/p>

由于公路交通網(wǎng)的特性和山區(qū)地形的復(fù)雜性，將輸電線路施工物料從物料站運(yùn)輸?shù)借F塔位置有多個(gè)可供選擇的公路運(yùn)輸路徑和索道架設(shè)方案。但如何根據(jù)三維地理信息數(shù)據(jù)、公路信息和鐵塔與物料站位置搜索出這些備選路徑和方案，并通過對比研究篩選出最佳的公路運(yùn)輸和索道運(yùn)輸路徑一直是困擾工程人員的難題。

針對公路交通的路徑規(guī)劃算法較為成熟，大量學(xué)者采用改進(jìn)的蟻群算法［1］、遺傳網(wǎng)絡(luò)神經(jīng)算法［2］、蒙特卡洛模擬和遺傳算法［3］、改進(jìn)的Floyd 算法［4］、Dijkstra 或優(yōu)化的Dijkstra 算法［5～8］、A*或改進(jìn)的A*算法［8～12］對公路交通的路徑規(guī)劃問題進(jìn)行了研究。然而，針對索道運(yùn)輸?shù)穆窂揭?guī)劃算法研究鮮少有人涉足。因此，工程中只能進(jìn)行人工路徑規(guī)劃，路徑的優(yōu)劣在很大程度上依賴技術(shù)人員的經(jīng)驗(yàn)，且規(guī)劃過程中需多次前往現(xiàn)場進(jìn)行勘測，耗費(fèi)大量的時(shí)間和人力。在進(jìn)行公路運(yùn)輸和索道運(yùn)輸協(xié)同路徑規(guī)劃時(shí)，需充分考慮地理信息對物料運(yùn)輸?shù)目茖W(xué)性和經(jīng)濟(jì)性的影響，依賴技術(shù)人員的經(jīng)驗(yàn)進(jìn)行人工路徑規(guī)劃的方式很難選出最優(yōu)化的路徑，會(huì)在很大程度上影響施工物料運(yùn)輸?shù)男逝c成本。

在輸電線路施工領(lǐng)域，亟需一種新的路徑規(guī)劃算法，以運(yùn)輸效率和成本為約束條件，根據(jù)地理信息數(shù)據(jù)自動(dòng)化協(xié)同規(guī)劃公路運(yùn)輸和索道運(yùn)輸路徑，從而降低物料運(yùn)輸路徑規(guī)劃的時(shí)間消耗，減小工程人員戶外勘測等工作強(qiáng)度，響應(yīng)現(xiàn)代化線路施工對貨物運(yùn)輸?shù)慕当驹鲂б蟆?/p>

2 路徑規(guī)劃主要流程

2.1 輸電線路施工物料運(yùn)輸路徑規(guī)劃問題

圖1 所示的是一個(gè)輸電線路施工物料運(yùn)輸路徑規(guī)劃問題的示意圖，物料站位于市郊的交通干道附近，施工現(xiàn)場的鐵塔位于遠(yuǎn)離城市的山區(qū)，且鐵塔與最近的公路還有一段距離。因此需要借助傾斜攝影等技術(shù)對實(shí)際地理信息數(shù)據(jù)進(jìn)行采集和處理。

圖1 物料站與鐵塔位置示意圖

2.2 輸電線路施工物料運(yùn)輸路徑規(guī)劃流程

受地理信息的影響和索道架設(shè)條件的限制，以部分公路沿線附近的點(diǎn)為上料點(diǎn)可能無法架設(shè)合理的索道實(shí)現(xiàn)物料的運(yùn)輸。因此，在進(jìn)行路徑規(guī)劃時(shí)，需要先進(jìn)行索道運(yùn)輸?shù)穆窂揭?guī)劃工作，確定備選的索道架設(shè)方案及上料點(diǎn)位置，再進(jìn)行公路路徑規(guī)劃工作，最終通過對比篩選，規(guī)劃出最佳物料運(yùn)輸路徑。

在索道運(yùn)輸路徑規(guī)劃時(shí)，為保證索道負(fù)載運(yùn)行過程中貨物不與地面發(fā)生接觸，應(yīng)先搜索出所有滿足架設(shè)要求的空載索道路徑，確定索道路徑的架設(shè)參數(shù)，在此基礎(chǔ)上計(jì)算貨物運(yùn)動(dòng)軌跡，通過優(yōu)化支架優(yōu)化篩選出負(fù)載索道運(yùn)輸路徑。

因此提出輸電線路施工物料運(yùn)輸路徑規(guī)劃流程，如圖2所示，該流程的主要步驟如下所示。

圖2 輸電線路施工物料運(yùn)輸路徑規(guī)劃流程

1）搜索空載索道運(yùn)輸路徑：在索道規(guī)劃區(qū)域選出上/下料點(diǎn)，得到備選索道運(yùn)輸路徑與對應(yīng)的地形剖面；然后模擬空載條件下的索道承載索并采用干涉點(diǎn)搜索法確定支架位置；最后根據(jù)架設(shè)要求挑選空載索道路徑。

2）優(yōu)化負(fù)載索道運(yùn)輸路徑：遍歷所有空載索道路徑，采用工作索結(jié)構(gòu)耦合方法計(jì)算貨物運(yùn)動(dòng)軌跡，對空載條件下索道支架進(jìn)行優(yōu)化。

3）搜索公路運(yùn)輸路徑：根據(jù)公路信息數(shù)據(jù)、物料站位置和所有篩選出的負(fù)載索道路徑的上料點(diǎn)位置，規(guī)劃出從物料站到索道上料點(diǎn)的最佳公路運(yùn)輸路徑并計(jì)算各路徑的公路運(yùn)輸成本。

4）計(jì)算物料運(yùn)輸成本并輸出最佳路徑：以運(yùn)輸效率和成本為條件，選出最佳運(yùn)輸路徑組合。

3 索道運(yùn)輸路徑搜索

圖3展示了規(guī)劃索道運(yùn)輸路徑的主要步驟。

3.1 篩選備選上/下料點(diǎn)

在路徑自動(dòng)規(guī)劃時(shí)，需要先在公路和鐵塔附近分別選出備選上料點(diǎn)和備選下料點(diǎn)。

為便于貨物運(yùn)輸且又不影響道路交通與鐵塔施工，上/下料點(diǎn)與道路/鐵塔距離不能太遠(yuǎn)和太近，將與公路或鐵塔的距離為10m～20m 之間的點(diǎn)選出，作為上/下料點(diǎn)的備選點(diǎn)。

在地面平整度方面，通過計(jì)算備選點(diǎn)及其周邊區(qū)域的最大梯度smax和梯度的均方根w篩除地形不平緩的備選上/下料點(diǎn)。區(qū)域梯度的均方根的表達(dá)式如式（1）所示：

式中：Ω 為備選區(qū)域；AΩ為Ω 面積；s(x,y)為(x,y)處梯度。

當(dāng)w>0.5 或smax>1 時(shí)，地面平整度不滿足要求，需要?jiǎng)h除對應(yīng)的備選上/下料點(diǎn)。

3.2 獲得索道地形剖面

根據(jù)備選上/下料點(diǎn)位置，在三維高程上雙線性插值獲取索道地形剖面。

三維高程（地理信息）為(xj,yk,gjk)，j=1,2,…,nx，k=1,2,…,ny，xj為水平面x軸坐標(biāo)、yk為水平面y軸坐標(biāo)，gjk為高程坐標(biāo)，nx為x軸采樣點(diǎn)數(shù)量，ny為y軸采樣點(diǎn)數(shù)量。

如圖4（a）所示，將上料點(diǎn)和下料點(diǎn)間連線在水平面的投影，將投影線段均分n份，投影線段各點(diǎn)的水平面坐標(biāo)分別為(xi,yi)，i=1,2,…,n+1。其中：

圖4 地形剖面獲取示意圖

式中：x1，xn+1分別為上料點(diǎn)、下料點(diǎn)的水平面x軸坐標(biāo)；y1，yn+1為上、下料點(diǎn)的水平面y軸坐標(biāo)。

當(dāng)連線投影點(diǎn)坐標(biāo)滿足xj

建立局部坐標(biāo)系ouz，u坐標(biāo)軸方向由上料點(diǎn)投影指向下料點(diǎn)投影，z坐標(biāo)軸方向向上。投影線段各點(diǎn)的水平面坐標(biāo)(xi,yi)在坐標(biāo)系ouz下的坐標(biāo)為ui。其中：

根據(jù)二維地形下插值點(diǎn)(ui,gi)，可擬合得到剖面地形曲線的vg(u)，如圖4（b）所示。

式中：φi(u)為擬合曲線的基函數(shù)；ci為擬合曲線的擬合系數(shù)。

在地形剖面上，只有滿足式（6）的水平坐標(biāo)的集合（即地形剖面上凸點(diǎn)的集合）才適合選做索道支架的架設(shè)點(diǎn)。

3.3 搜索索道支架位置

多跨索道的支架將承載索分割為若干索段，不考慮索段間的相互影響，可將每個(gè)索段近似為如式（7）所示的拋物線：

式中：vc(u,l,C)為u 處的拋物線高度；l為拋物線起點(diǎn)和終點(diǎn)的水平距離（跨距）；C為拋物線起點(diǎn)和終點(diǎn)的高差；f為跨中垂度，取為0.05。

然后根據(jù)索道路徑的二維地形剖面和中間支架選取原則，提出干涉點(diǎn)搜索法，為備選上/下料點(diǎn)組合出的備選索道路徑設(shè)置中間支架。

首先在上料點(diǎn)和下料點(diǎn)分別設(shè)置一個(gè)支架，上料點(diǎn)處的支架編號為1，下料點(diǎn)支架編號為2。

然后，執(zhí)行下列程序即可自動(dòng)計(jì)算中間支架坐標(biāo)(uα,vg(uα))，在此下標(biāo)α表示支架編號。

其中k表示中間支架的循環(huán)更新次數(shù)；m為支架數(shù)量；p(u)表示承載索與地面高度差隨u變化的函數(shù)；up為承載索與地面最大干涉位置的水平坐標(biāo)。

完成索道中間支架自動(dòng)設(shè)置之后，判斷索道合理性，即判斷是否滿足總長度小于3000m、相鄰支架跨距大于20m且小于400m、總支架數(shù)量不大于9個(gè)、弦傾角小于45°等架設(shè)條件。

4 索道運(yùn)輸路徑優(yōu)化

4.1 貨物運(yùn)動(dòng)軌跡計(jì)算

使用索道進(jìn)行物料運(yùn)輸時(shí)，在貨物載荷的作用下，空載時(shí)不與地面接觸的承載索可能會(huì)與地面接觸，且貨物所在位置始終是承載索最容易與地面接觸的位置。

求解負(fù)載索道的載荷位置時(shí)，需考慮不同跨間的承載索之間以及承載索與牽引索之間的相互作用。

因此，定義所有支架和載荷為節(jié)點(diǎn)，節(jié)點(diǎn)間的索段為僅受自重作用的懸鏈線段，其表達(dá)式為［13］

式中：L為懸鏈線起點(diǎn)和終點(diǎn)的水平距離；h為懸鏈線起點(diǎn)和終點(diǎn)的高差；H為懸鏈線水平張力；q為懸鏈線的線密度；s為懸鏈線未受張力時(shí)的長度；EA0為懸鏈線的彈性模量與截面積之積；VA為懸鏈線左端外力的垂直分量；TA為懸鏈線左端外力的切向分量；TB為懸鏈線右端外力的切向分量。

根據(jù)式（8）可由s、H和VA計(jì)算得到L、h、TA等參數(shù)。因此，每個(gè)索段的懸鏈線有且僅有3個(gè)未知量。

設(shè)索道的索段數(shù)為N，整條索道的承載索和牽引索共由2N個(gè)索段組成，即共有6N個(gè)未知量。由文獻(xiàn)［14］可建立6N個(gè)工作索結(jié)構(gòu)耦合方程，通過求解該非線性方程組即可得到所有索段的懸鏈線參數(shù)。

通過計(jì)算載荷在索道各跨間行進(jìn)過程中的位置，即可得到貨物的運(yùn)動(dòng)軌跡曲線vr(u)。

4.2 索道運(yùn)輸路徑優(yōu)化流程

對空載索道運(yùn)輸路徑進(jìn)行負(fù)載優(yōu)化是不斷在貨物運(yùn)動(dòng)軌跡與地形的最大干涉位置處添加新的支架的過程，可通過與空載時(shí)的支架設(shè)置程序類似過程實(shí)現(xiàn)。只需將程序中承載索與地面高度差函數(shù)p(u)替換為貨物運(yùn)動(dòng)軌跡與地面的高度差函數(shù)q(u)，即

5 公路運(yùn)輸路徑規(guī)劃

5.1 主要流程

在確定索道運(yùn)輸路徑后，根據(jù)公路信息數(shù)據(jù)、物料站位置和索道運(yùn)輸?shù)纳狭宵c(diǎn)位置，可規(guī)劃出從物料站到上料點(diǎn)的最佳公路運(yùn)輸路徑。

使用A*算法進(jìn)行路徑規(guī)劃，主要流程如圖5所示，主要包括以下步驟：

1）公路骨架提取：對公路的柵格地圖進(jìn)行處理，提取公路的骨架（中心線）［15］，以減少后續(xù)路徑規(guī)劃的計(jì)算量；

2）公路路徑起點(diǎn)和終點(diǎn)搜索：在公路上分別選取距離物料站和上料點(diǎn)最近的點(diǎn)，作為公路運(yùn)輸路徑的起點(diǎn)和終點(diǎn)；

3）基于A*算法進(jìn)行路徑規(guī)劃：計(jì)算啟發(fā)函數(shù)和估價(jià)函數(shù)，引導(dǎo)整個(gè)路徑搜索過程，快速找到從起點(diǎn)出發(fā)到達(dá)終點(diǎn)的最小通行成本和其所對應(yīng)的最佳路徑。

4）判斷是否已經(jīng)遍歷所有索道路徑：若是，完成公路運(yùn)輸路徑搜索；若否，選擇下一條索道路徑的上料點(diǎn)并返回第2）步。

5.2 基于A*算法的公路運(yùn)輸路徑規(guī)劃

A*算法輸入的公路信息數(shù)據(jù)為柵格地圖，每個(gè)柵格對應(yīng)地圖上的一個(gè)采樣點(diǎn)，柵格的取值表示該采樣點(diǎn)的狀態(tài)，當(dāng)取值為1 時(shí)，表示該采樣點(diǎn)是公路上的點(diǎn)，當(dāng)取值為0 時(shí)，表示該采樣點(diǎn)不是公路上的采樣點(diǎn)。

借助通行成本估價(jià)函數(shù)f(n)引導(dǎo)整個(gè)路徑搜索過程，快速找到從起點(diǎn)出發(fā)到達(dá)終點(diǎn)的最小通行成本和其所對應(yīng)的最佳路徑。f(n)可表示為

式中：g(n)為起點(diǎn)到柵格n的實(shí)際通行成本，可根據(jù)已經(jīng)搜索的路徑進(jìn)行實(shí)際計(jì)算；h(n) 為柵格n到終點(diǎn)的通行成本估算值，即為啟發(fā)函數(shù)。

由于公路上的柵格與其周邊的八個(gè)柵格都是連通的，本文選用式（11）所示的切比雪夫距離［16］作為A*算法的啟發(fā)函數(shù)。

式中：xn和yn分別為柵格n的x和y坐標(biāo)值；xd和yd分別為終點(diǎn)d的x和y坐標(biāo)值。

6 算例

針對圖1 所示的典型輸電線路施工物料運(yùn)輸問題，使用本文所提出的路徑規(guī)劃方法對其進(jìn)行公路運(yùn)輸與索道運(yùn)輸?shù)膮f(xié)同路徑規(guī)劃，篩選出如圖6所示的最佳運(yùn)輸路徑。

圖6 圖1的算例的路徑規(guī)劃結(jié)果

針對多個(gè)貨運(yùn)路徑規(guī)劃問題進(jìn)行求解，得到的路徑規(guī)劃結(jié)果如表1 所示，平均每個(gè)模型約搜索出48 條空載索道路徑和6 條滿足索道架設(shè)要求的負(fù)載索道路徑以及對應(yīng)的公路運(yùn)輸路徑，平均耗時(shí)64.3min。

表1 貨運(yùn)路徑規(guī)劃問題計(jì)算結(jié)果

與傳統(tǒng)依靠人工的路徑規(guī)劃相比，該方法可以快速地遍歷所有可選的物料運(yùn)輸路徑，并能夠選出最優(yōu)結(jié)果，顯著提高了路徑規(guī)劃的效率與效果。

7 結(jié)語

本文提出了一種輸電線路物料運(yùn)輸路徑規(guī)劃算法，結(jié)合索道路徑搜索及優(yōu)化、公路運(yùn)輸路徑規(guī)劃等方法，以運(yùn)輸效率和成本為約束條件，根據(jù)地理信息數(shù)據(jù)自動(dòng)化協(xié)同規(guī)劃聯(lián)合運(yùn)輸路徑。

在貨運(yùn)索道方面，以三維地理信息數(shù)據(jù)為基礎(chǔ)，提出承載索、貨物與地面接觸的判斷方法、索道路徑中間支架設(shè)置的干涉點(diǎn)搜索方法，給出了具體算法。結(jié)合地形剖面和支架點(diǎn)選取原則，實(shí)現(xiàn)了索道路徑和支架的自動(dòng)篩選。

在公路運(yùn)輸方面，以公路的柵格地圖為基礎(chǔ)，進(jìn)行公路骨架提取、路徑起點(diǎn)與終點(diǎn)搜索，最終基于A*算法實(shí)現(xiàn)了公路運(yùn)輸路徑規(guī)劃。

與人工方法相比，該方法更加經(jīng)濟(jì)高效，能夠降低物料運(yùn)輸路徑規(guī)劃的時(shí)間消耗，減小工程人員戶外勘測等工作強(qiáng)度，響應(yīng)現(xiàn)代化線路施工對貨物運(yùn)輸?shù)慕当驹鲂б蟆?/p>