輸電線路貨運路徑規劃算法?

秦 劍 張飛凱 劉中書 劉 晨

（1.中國電力科學研究院有限公司 北京 100055）（2.國網陜西省電力公司建設分公司 西安 710065）

1 引言

一般情況下儲存或加工輸電線路施工物料的物料站位于交通便利、便于物料裝卸的交通要道，而待建的鐵塔則多處于偏僻的山區，遠離已有公路，僅依靠公路運輸無法將物料從物料站運送到遠離公路的在建鐵塔。針對公路運輸的短板，可在路邊和鐵塔附近分別設置上料點和下料點，在上下料點間架設臨時貨運索道，實現物料轉運。該方法是當下實現輸電線路施工物料運輸的主流方法。

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

針對公路交通的路徑規劃算法較為成熟，大量學者采用改進的蟻群算法［1］、遺傳網絡神經算法［2］、蒙特卡洛模擬和遺傳算法［3］、改進的Floyd 算法［4］、Dijkstra 或優化的Dijkstra 算法［5～8］、A*或改進的A*算法［8～12］對公路交通的路徑規劃問題進行了研究。然而，針對索道運輸的路徑規劃算法研究鮮少有人涉足。因此，工程中只能進行人工路徑規劃，路徑的優劣在很大程度上依賴技術人員的經驗，且規劃過程中需多次前往現場進行勘測，耗費大量的時間和人力。在進行公路運輸和索道運輸協同路徑規劃時，需充分考慮地理信息對物料運輸的科學性和經濟性的影響，依賴技術人員的經驗進行人工路徑規劃的方式很難選出最優化的路徑，會在很大程度上影響施工物料運輸的效率與成本。

在輸電線路施工領域，亟需一種新的路徑規劃算法，以運輸效率和成本為約束條件，根據地理信息數據自動化協同規劃公路運輸和索道運輸路徑，從而降低物料運輸路徑規劃的時間消耗，減小工程人員戶外勘測等工作強度，響應現代化線路施工對貨物運輸的降本增效要求。

2 路徑規劃主要流程

2.1 輸電線路施工物料運輸路徑規劃問題

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

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

2.2 輸電線路施工物料運輸路徑規劃流程

受地理信息的影響和索道架設條件的限制，以部分公路沿線附近的點為上料點可能無法架設合理的索道實現物料的運輸。因此，在進行路徑規劃時，需要先進行索道運輸的路徑規劃工作，確定備選的索道架設方案及上料點位置，再進行公路路徑規劃工作，最終通過對比篩選，規劃出最佳物料運輸路徑。

在索道運輸路徑規劃時，為保證索道負載運行過程中貨物不與地面發生接觸，應先搜索出所有滿足架設要求的空載索道路徑，確定索道路徑的架設參數，在此基礎上計算貨物運動軌跡，通過優化支架優化篩選出負載索道運輸路徑。

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

圖2 輸電線路施工物料運輸路徑規劃流程

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

2）優化負載索道運輸路徑：遍歷所有空載索道路徑，采用工作索結構耦合方法計算貨物運動軌跡，對空載條件下索道支架進行優化。

3）搜索公路運輸路徑：根據公路信息數據、物料站位置和所有篩選出的負載索道路徑的上料點位置，規劃出從物料站到索道上料點的最佳公路運輸路徑并計算各路徑的公路運輸成本。

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

3 索道運輸路徑搜索

圖3展示了規劃索道運輸路徑的主要步驟。

3.1 篩選備選上/下料點

在路徑自動規劃時，需要先在公路和鐵塔附近分別選出備選上料點和備選下料點。

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

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

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

當w>0.5 或smax>1 時，地面平整度不滿足要求，需要刪除對應的備選上/下料點。

3.2 獲得索道地形剖面

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

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

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

圖4 地形剖面獲取示意圖

式中：x1，xn+1分別為上料點、下料點的水平面x軸坐標；y1，yn+1為上、下料點的水平面y軸坐標。

當連線投影點坐標滿足xj

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

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

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

在地形剖面上，只有滿足式（6）的水平坐標的集合（即地形剖面上凸點的集合）才適合選做索道支架的架設點。

3.3 搜索索道支架位置

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

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

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

首先在上料點和下料點分別設置一個支架，上料點處的支架編號為1，下料點支架編號為2。

然后，執行下列程序即可自動計算中間支架坐標(uα,vg(uα))，在此下標α表示支架編號。

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

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

4 索道運輸路徑優化

4.1 貨物運動軌跡計算

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

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

因此，定義所有支架和載荷為節點，節點間的索段為僅受自重作用的懸鏈線段，其表達式為［13］

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

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

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

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

4.2 索道運輸路徑優化流程

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

5 公路運輸路徑規劃

5.1 主要流程

在確定索道運輸路徑后，根據公路信息數據、物料站位置和索道運輸的上料點位置，可規劃出從物料站到上料點的最佳公路運輸路徑。

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

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

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

3）基于A*算法進行路徑規劃：計算啟發函數和估價函數，引導整個路徑搜索過程，快速找到從起點出發到達終點的最小通行成本和其所對應的最佳路徑。

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

5.2 基于A*算法的公路運輸路徑規劃

A*算法輸入的公路信息數據為柵格地圖，每個柵格對應地圖上的一個采樣點，柵格的取值表示該采樣點的狀態，當取值為1 時，表示該采樣點是公路上的點，當取值為0 時，表示該采樣點不是公路上的采樣點。

借助通行成本估價函數f(n)引導整個路徑搜索過程，快速找到從起點出發到達終點的最小通行成本和其所對應的最佳路徑。f(n)可表示為

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

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

式中：xn和yn分別為柵格n的x和y坐標值；xd和yd分別為終點d的x和y坐標值。

6 算例

針對圖1 所示的典型輸電線路施工物料運輸問題，使用本文所提出的路徑規劃方法對其進行公路運輸與索道運輸的協同路徑規劃，篩選出如圖6所示的最佳運輸路徑。

圖6 圖1的算例的路徑規劃結果

針對多個貨運路徑規劃問題進行求解，得到的路徑規劃結果如表1 所示，平均每個模型約搜索出48 條空載索道路徑和6 條滿足索道架設要求的負載索道路徑以及對應的公路運輸路徑，平均耗時64.3min。

表1 貨運路徑規劃問題計算結果

與傳統依靠人工的路徑規劃相比，該方法可以快速地遍歷所有可選的物料運輸路徑，并能夠選出最優結果，顯著提高了路徑規劃的效率與效果。

7 結語

本文提出了一種輸電線路物料運輸路徑規劃算法，結合索道路徑搜索及優化、公路運輸路徑規劃等方法，以運輸效率和成本為約束條件，根據地理信息數據自動化協同規劃聯合運輸路徑。

在貨運索道方面，以三維地理信息數據為基礎，提出承載索、貨物與地面接觸的判斷方法、索道路徑中間支架設置的干涉點搜索方法，給出了具體算法。結合地形剖面和支架點選取原則，實現了索道路徑和支架的自動篩選。

在公路運輸方面，以公路的柵格地圖為基礎，進行公路骨架提取、路徑起點與終點搜索，最終基于A*算法實現了公路運輸路徑規劃。

與人工方法相比，該方法更加經濟高效，能夠降低物料運輸路徑規劃的時間消耗，減小工程人員戶外勘測等工作強度，響應現代化線路施工對貨物運輸的降本增效要求。