摘要：輸電線(xiàn)路施工物料運(yùn)輸路徑規(guī)劃是地形復(fù)雜地區(qū)輸電線(xiàn)路架設(shè)的基礎(chǔ)工作，該路徑一般由公路運(yùn)輸路徑和索道運(yùn)輸路徑組成。基于數(shù)字高程模型和Dijkstra算法提出了一種索道-公路聯(lián)合物料運(yùn)輸路徑規(guī)劃算法。通過(guò)基于拋物線(xiàn)的空載索道運(yùn)輸路徑快速搜索方法，實(shí)現(xiàn)了基于懸鏈線(xiàn)的負(fù)載索道運(yùn)輸路徑優(yōu)化，在此基礎(chǔ)上采用Dijkstra算法實(shí)現(xiàn)最佳公路運(yùn)輸路徑搜索，從而實(shí)現(xiàn)公路運(yùn)輸和索道運(yùn)輸路徑的協(xié)同規(guī)劃。將該算法應(yīng)用到某待建特高壓輸電線(xiàn)路鐵塔的物料運(yùn)輸路徑規(guī)劃工程問(wèn)題中，驗(yàn)證表明該索道-公路聯(lián)合路徑規(guī)劃有效縮短了輸電線(xiàn)路物料運(yùn)輸路徑設(shè)計(jì)周期，提高了施工物料運(yùn)輸?shù)男省?/p>

關(guān)鍵詞：輸電線(xiàn)路；物料運(yùn)輸；路徑規(guī)劃；干涉點(diǎn)搜索法；Dijkstra算法

中圖分類(lèi)號(hào)：U18； TM754文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1002-4026（2023）03-0090-10

Abstract∶Path planning for material transportation is the fundamental work for constructing power transmission line in complex terrain areas. Such paths generally comprise road and ropeway transportation paths. Based on the digital elevation model and Dijkstra algorithm， this study proposed a combined material transportation path planning algorithm for road and ropeway. Using the fast search method of no-load ropeway transportation path based on parabola， a load ropeway transportation path optimization based on catenary was implemented. Then， the road transportation path was optimally searched using Dijkstra algorithm， and the coordinated planning of road and ropeway transportation paths was conducted. The proposed algorithm was applied to the material transportation path planning of an ultra-high voltage transmission line′s towers. Results showed that the combined ropeway and road transportation paths can effectively shorten the design period of material transportation path and improve the efficiency of construction material transportation.

Key words∶power transmission line; material transportation; path planning; interference point search method; Dijkstra algorithm

架空輸電線(xiàn)路貨運(yùn)索道主要服務(wù)于輸電線(xiàn)路施工的物料運(yùn)輸，架設(shè)在地形復(fù)雜或者偏遠(yuǎn)山區(qū)的鐵塔遠(yuǎn)離運(yùn)輸公路，需要采用公路運(yùn)輸與索道運(yùn)輸相結(jié)合的方式將物料從物料站運(yùn)輸?shù)绞┕がF(xiàn)場(chǎng)[1-2]，其路徑規(guī)劃是公路-轉(zhuǎn)運(yùn)場(chǎng)-索道的綜合空間優(yōu)化過(guò)程，合理的路徑規(guī)劃可以降低施工成本和減小施工風(fēng)險(xiǎn)。在工程中，由于缺少相關(guān)路徑規(guī)劃方法，山區(qū)公路與貨運(yùn)索道聯(lián)合路徑規(guī)劃工作需要技術(shù)人員進(jìn)行多次的現(xiàn)場(chǎng)勘查，并根據(jù)現(xiàn)有經(jīng)驗(yàn)進(jìn)行人工路徑規(guī)劃，時(shí)間和經(jīng)濟(jì)成本較高，且無(wú)法得到輸電線(xiàn)路物料索道-公路聯(lián)合運(yùn)輸最優(yōu)路徑。

架空輸電線(xiàn)路施工物料公路與索道聯(lián)合路徑規(guī)劃包括公路運(yùn)輸最優(yōu)路徑優(yōu)化，以及確定索道參數(shù)約束下的三維表面最優(yōu)路徑搜索，其中施工較為困難的索道運(yùn)輸路徑是優(yōu)先考慮的部分。最優(yōu)路徑規(guī)劃問(wèn)題廣泛存在于交通設(shè)計(jì)與智能導(dǎo)航領(lǐng)域，常用的方法包括蟻群算法[3]、遺傳網(wǎng)絡(luò)神經(jīng)算法[4]、蒙特卡洛模擬和遺傳算法[5]、改進(jìn)的Floyd算法[6]、Dijkstra算法[7]或優(yōu)化的Dijkstra算法[8]、A*算法[9]或改進(jìn)的A*算法[10]等。其中Dijkstra算法進(jìn)行路徑尋優(yōu)時(shí)需要遍歷所有節(jié)點(diǎn)，廣泛應(yīng)用于各種公路運(yùn)輸路徑規(guī)劃場(chǎng)景[11-12]，能夠很好地解決山區(qū)公路運(yùn)輸路徑規(guī)劃問(wèn)題。而索道路徑規(guī)劃以人工規(guī)劃為主，存在時(shí)間長(zhǎng)、成本高、工作量大的缺點(diǎn)。為了解決這些問(wèn)題，李攀等[13]研究了一種輔助選線(xiàn)系統(tǒng)，輔助工作人員對(duì)貨運(yùn)索道進(jìn)行人工路徑規(guī)劃，一定程度上降低了工作量。秦劍等[14-16]對(duì)貨運(yùn)索道支架位置搜索方法進(jìn)行了研究，并提出了基于地形自適應(yīng)的輸電線(xiàn)路貨運(yùn)索道路徑自動(dòng)規(guī)劃方法[17]，但該方法未考慮公路運(yùn)輸對(duì)索道路徑規(guī)劃的影響，無(wú)法用于公路-索道聯(lián)合物料運(yùn)輸路徑規(guī)劃。

山東科學(xué)2023年第3期秦劍，等：山區(qū)公路與貨運(yùn)索道聯(lián)合路徑規(guī)劃方法本文基于Dijkstra算法和索道設(shè)計(jì)參數(shù)，研究了地形復(fù)雜地區(qū)輸電線(xiàn)路施工物料公路與索道運(yùn)輸最優(yōu)路徑規(guī)劃方法，首先基于數(shù)字高程模型（digital elevation model，DEM）和索道參數(shù)約束條件搜索最優(yōu)索道路徑，然后利用公路、物料站位置和上料點(diǎn)位置搜索最低成本公路運(yùn)輸路徑，實(shí)現(xiàn)公路與索道聯(lián)合運(yùn)輸最優(yōu)路徑規(guī)劃。

1研究方法

公路與索道聯(lián)合路徑規(guī)劃涉及索道和公路兩類(lèi)路徑，公路運(yùn)輸路徑基于已有道路數(shù)據(jù)，索道架設(shè)路徑根據(jù)輸電線(xiàn)路設(shè)計(jì)和施工區(qū)地形地貌特點(diǎn)確定。本研究的思路是首先選擇最優(yōu)索道路徑，然后搜索公路到索道的最優(yōu)路徑，兩個(gè)路徑的交集是索道的上料點(diǎn)。無(wú)論上料點(diǎn)位于公路沿線(xiàn)的何處，索道最優(yōu)路徑確定后，都能通過(guò)相關(guān)算法規(guī)劃出公路運(yùn)輸?shù)淖罴崖窂健?/p>

1.1施工區(qū)建模與數(shù)據(jù)處理

施工區(qū)DEM采用大比例尺高分辨率柵格數(shù)據(jù)建模，并且能夠根據(jù)地形復(fù)雜程度進(jìn)行高斯濾波，減少DEM中的高頻信號(hào)，降低索道支架搜索中干擾信息的數(shù)據(jù)量，提高索道路徑搜索的成功率；同時(shí)根據(jù)路徑規(guī)劃需求對(duì)DEM數(shù)據(jù)進(jìn)行重采樣，降低數(shù)據(jù)的采樣密度，提高索道路徑規(guī)劃的搜索效率。施工區(qū)道路模型為矢量數(shù)據(jù)和以交叉路口為節(jié)點(diǎn)的無(wú)向圖數(shù)據(jù)，用于搜索物料站到上料點(diǎn)的最佳公路運(yùn)輸路徑。因此在進(jìn)行公路與索道聯(lián)合路徑規(guī)劃時(shí)，首先需要對(duì)DEM數(shù)據(jù)進(jìn)行高斯濾波和重采樣處理，并建立施工區(qū)道路模型。在DEM數(shù)據(jù)和道路模型中，物料場(chǎng)、上料點(diǎn)、下料點(diǎn)為點(diǎn)數(shù)據(jù)，上料點(diǎn)位于公路附近，下料點(diǎn)位于輸電線(xiàn)路塔體附近，所有數(shù)據(jù)均基于相同的平面和高程基準(zhǔn)。

1.1.1基于快速傅里葉變換的高斯濾波

數(shù)據(jù)采集、傳輸和處理過(guò)程中不可避免地會(huì)給三維DEM高程數(shù)據(jù)引入高頻噪聲信號(hào)，會(huì)降低后續(xù)索道路徑規(guī)劃的成功率，因此需要對(duì)數(shù)據(jù)進(jìn)行濾波處理，去除噪聲和高頻干擾信號(hào)。

高斯濾波是一種線(xiàn)性平滑濾波，適用于消除高頻高斯噪聲，對(duì)于三維的DEM高程數(shù)據(jù)H0x，y，其高斯濾波的表達(dá)如下所示：

然而，傅里葉變換求解卷積存在邊界誤差。為了減小該誤差的影響，在實(shí)際工程應(yīng)用中需要分別在x和y方向上將計(jì)算域擴(kuò)大5～8倍，進(jìn)行卷積運(yùn)算之后僅保留中心區(qū)域原計(jì)算域的結(jié)果。這種對(duì)計(jì)算域進(jìn)行擴(kuò)張的邊界誤差消除方法會(huì)顯著增加計(jì)算量，降低計(jì)算效率。而通過(guò)對(duì)原計(jì)算區(qū)域進(jìn)行對(duì)稱(chēng)擴(kuò)充能夠在只對(duì)原計(jì)算域進(jìn)行單邊2倍擴(kuò)充的基礎(chǔ)上實(shí)現(xiàn)高效低誤差的卷積運(yùn)算。如圖1所示，該方法首先將大小為M×N的計(jì)算域?qū)ΨQ(chēng)擴(kuò)充為（2M-2）×（2N-2）的臨時(shí)計(jì)算域，然后在該區(qū)域傅里葉變換與高斯權(quán)函數(shù)傅里葉變換之積的逆傅里葉變換結(jié)果中，其對(duì)應(yīng)區(qū)域可得到準(zhǔn)確的卷積結(jié)果。

1.1.2數(shù)據(jù)重采樣處理

受采樣設(shè)備、計(jì)算機(jī)處理能力等的影響，測(cè)量DEM高程數(shù)據(jù)的地形采樣密度與索道路徑規(guī)劃適用的地形采樣密度有較大差別。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，需要采用數(shù)據(jù)插值的方式對(duì)測(cè)量的DEM高程數(shù)據(jù)進(jìn)行重采樣。二維插值計(jì)算的方法有很多，例如最臨近插值、雙線(xiàn)性插值、雙三次插值等。其中，雙線(xiàn)性插值計(jì)算效率較高，差值精度較高，插值結(jié)果連續(xù)變化，是常用的DEM高程數(shù)據(jù)插值方法。

雙線(xiàn)性插值是在x和y兩個(gè)方向上分別進(jìn)行一次線(xiàn)性插值，可以利用插值點(diǎn)xα，yβ周邊最近的4個(gè)原始采樣點(diǎn)xi，yj，xi+1，yj，xi，yj+1和xi+1，yj+1的高程數(shù)據(jù)插值估算該點(diǎn)的高程，計(jì)算公式如下所示：

1.1.3公路的無(wú)向圖

為了便于公路的路徑搜索，在施工區(qū)建模時(shí)，將路網(wǎng)存儲(chǔ)為如圖2（a）所示的無(wú)向圖，每個(gè)交叉路口都具有唯一編號(hào)，任意兩個(gè)交叉路口之間公路段的通行成本（如路段長(zhǎng)度）已知。該無(wú)向圖還可以表達(dá)為圖2（b）所示的通行成本矩陣，矩陣的行列號(hào)表示交叉路口編號(hào)，元素值表示行編號(hào)代表的路口到列編號(hào)代表的路口的通行成本。

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

圖3所示的是索道運(yùn)輸路徑搜索流程，包括備選空載索道路徑集合生成及負(fù)載索道路徑篩選兩個(gè)部分。空載索道路徑搜索根據(jù)備選上/下料點(diǎn)，結(jié)合區(qū)域DEM及地形剖面搜索確定所有可能的空載路徑；負(fù)載索道路徑搜索根據(jù)負(fù)載受力計(jì)算貨物高度，在對(duì)支架進(jìn)行調(diào)整的基礎(chǔ)上對(duì)索道路徑進(jìn)行篩選，最后得到最優(yōu)負(fù)載索道路徑。

1.2.1備選空載索道路徑集合生成

首先在公路沿線(xiàn)選出備選上料點(diǎn)，同時(shí)在鐵塔臨近區(qū)域選出備選下料點(diǎn)，通過(guò)兩兩組合備選上/下料點(diǎn)構(gòu)成備選空載索道路徑集合；然后直線(xiàn)連接各備選空載索道路徑的上料點(diǎn)與下料點(diǎn)，插值生成二維地形剖面，并在地形剖面內(nèi)搜索索道支架點(diǎn)；最后篩選出滿(mǎn)足索道參數(shù)約束條件的空載索道路徑，構(gòu)成空載索道路徑集合。

（1）備選空載索道路徑搜索。利用DEM生成坡度圖，設(shè)定坡度限值提取平緩區(qū)域圖斑，計(jì)算這些圖斑中心到公路和塔體的距離，選取與公路和塔體距離合適的圖斑為備選上料和備選下料點(diǎn)。若不存在滿(mǎn)足要求的圖斑，可根據(jù)DEM和坡度手工選取上/下料點(diǎn)，手工選取上/下料點(diǎn)和自動(dòng)選取的依據(jù)相似，也是在DEM生成的坡度圖上選取坡度小于限值且與公路/塔體距離合適的位置作為上/下料點(diǎn)，手工操作時(shí)技術(shù)人員可以根據(jù)經(jīng)驗(yàn)合理地調(diào)整坡度的限值和合適距離的范圍。由于輸電線(xiàn)路貨運(yùn)索道路徑一般采用直線(xiàn)設(shè)計(jì)，備選上料點(diǎn)與備選下料點(diǎn)的直線(xiàn)連線(xiàn)即為備選空載索道路徑。

（2）索道支架點(diǎn)搜索。根據(jù)DEM數(shù)據(jù)和上/下料點(diǎn)坐標(biāo)，雙線(xiàn)性插值得到備選空載索道路徑的地形剖面。結(jié)合相鄰支架跨距小于400 m、承載索曲線(xiàn)高于地形剖面曲線(xiàn)等支架選取原則，為備選空載索道路徑搜索支架點(diǎn)。空載索道支架點(diǎn)搜索中忽略每個(gè)支架兩側(cè)的承載索的相互影響，將相鄰支架間的索道段視為獨(dú)立的單跨索道，使用拋物線(xiàn)模擬相鄰支架間的承載索。拋物線(xiàn)公式如下：

式中，vc（u，C，L）為單跨承載索的高度坐標(biāo)函數(shù)；u為單跨承載索的水平坐標(biāo)；L為單跨承載索相鄰節(jié)點(diǎn)的水平跨距；C為單跨承載索相鄰節(jié)點(diǎn)的高度差；f為單跨承載索的跨中垂度，取為0.05。干涉點(diǎn)搜索法搜索支架點(diǎn)時(shí)，以上料點(diǎn)和下料點(diǎn)間的拋物線(xiàn)模擬空載狀態(tài)下的承載索；存在拋物線(xiàn)的高度與地形剖面曲線(xiàn)高度之差小于0時(shí)，不斷在差值最小處的地形剖面上添加新的支架點(diǎn)，通過(guò)新的支架點(diǎn)將拋物線(xiàn)分割為更短的拋物線(xiàn)，直至所有拋物線(xiàn)的高度與地形剖面曲線(xiàn)的高度之差均不小于0；然后，通過(guò)在跨距大于400 m的支架點(diǎn)間增加新的支架點(diǎn)以減小索道的最大跨距。

（3）更新備選空載索道路徑集合。將不滿(mǎn)足“總長(zhǎng)＜2 000 m、跨距＞20 m、支架總數(shù)≤9、弦傾角＜45°”等索道參數(shù)約束條件的空載索道路徑從備選空載索道路徑集合中刪除，得到備選空載索道路徑集合。

1.2.2負(fù)載索道路徑篩選優(yōu)化

首先根據(jù)單條空載索道路徑的支架位置，計(jì)算貨物在空載索道路徑上的運(yùn)行軌跡。然后結(jié)合貨物運(yùn)行軌跡、支架高度和DEM判斷貨物運(yùn)行軌跡是否滿(mǎn)足貨物距地面最低高度要求；如果不滿(mǎn)足，通過(guò)在相應(yīng)位置為索道增加新的支架點(diǎn)對(duì)索道路徑進(jìn)行優(yōu)化，直至貨物軌跡滿(mǎn)足貨物運(yùn)行高度的優(yōu)化目標(biāo)要求。若增加支架點(diǎn)后的索道路徑滿(mǎn)足“跨距＞20 m、支架總數(shù)≤9、弦傾角＜45°”等索道參數(shù)約束條件，將該條索道路徑添加到負(fù)載索道路徑集合。

索道一般以不大于60 m/min的低速運(yùn)行，且以很小的加速度緩慢加速啟動(dòng)或減速停車(chē)，不允許急加速或急停。因此，索道正常運(yùn)行過(guò)程可簡(jiǎn)化視為準(zhǔn)靜態(tài)過(guò)程，無(wú)需考慮加速度對(duì)工作索受力狀態(tài)以及貨物運(yùn)動(dòng)軌跡的影響。首先將索道的所有支架和載荷定義為節(jié)點(diǎn)，相鄰節(jié)點(diǎn)間的索道承載索和牽引索都僅受自重作用，節(jié)點(diǎn)兩側(cè)的承載索或牽引索相互影響，且共同受支架支撐力或載荷的作用。將相鄰節(jié)點(diǎn)間的索段視為最小計(jì)算單元，采用懸鏈線(xiàn)對(duì)最小計(jì)算單元的索段進(jìn)行模擬，可根據(jù)下式計(jì)算其高差、跨距、水平張力、垂直張力和索長(zhǎng)等參數(shù)間的關(guān)系：

式中，L為相鄰節(jié)點(diǎn)水平距離（跨距），h為相鄰節(jié)點(diǎn)垂直距離（高差），H為最小計(jì)算單元索段內(nèi)部的水平張力，q為索單位長(zhǎng)度的質(zhì)量，s為最小計(jì)算單元索段未受張力時(shí)的初始長(zhǎng)度，EA0為索的橫截面積與彈性模量之積，VA為索在左端節(jié)點(diǎn)處受的垂直張力，VB為索在右端節(jié)點(diǎn)處受的垂直張力，TA為索在左端節(jié)點(diǎn)處受的切向張力，TB為索在右端節(jié)點(diǎn)處受的切向張力。

公式（8）表明相鄰節(jié)點(diǎn)間索段的高差、跨距、切向張力等參數(shù)都可以由索段的原始長(zhǎng)度s、水平張力H和左端節(jié)點(diǎn)處垂直張力VA計(jì)算得到，故每個(gè)最小計(jì)算單元的索段都只有三個(gè)未知量，且這三個(gè)未知量與其他最小計(jì)算單元的未知量之間具有定量關(guān)系。如果索道被支架和載荷分割成N段，那么承載索和牽引索共被分割為了2N個(gè)最小計(jì)算單元，整個(gè)索道共有6N個(gè)未知量。由文獻(xiàn)[18]的工作索（承載索與牽引索）結(jié)構(gòu)守恒分析和張力平衡分析可建立6N個(gè)工作索耦合作用方程，表示所有工作索最小計(jì)算單元各參數(shù)間的定量關(guān)系。工作索的未知量與耦合作用非線(xiàn)性方程數(shù)量相等，采用牛頓迭代法求解該非線(xiàn)性方程組即可得到所有最小計(jì)算單元的s、H和VA。在此基礎(chǔ)上，可求解出載荷所對(duì)應(yīng)的節(jié)點(diǎn)的位置坐標(biāo)，索道運(yùn)行過(guò)程中貨物在各時(shí)刻位置的集合即為其運(yùn)動(dòng)軌跡vru。

1.3公路運(yùn)輸最優(yōu)路徑搜索

完成索道運(yùn)輸路徑的搜索與優(yōu)化之后，采用Dijkstra進(jìn)行公路運(yùn)輸路徑規(guī)劃，在無(wú)向/有向圖上搜索最優(yōu)公路運(yùn)輸路徑，將物料從物料站運(yùn)輸?shù)缴狭宵c(diǎn)。將公路的每個(gè)路口視為節(jié)點(diǎn)，路口之間的距離或者通行代價(jià)作為節(jié)點(diǎn)間的通行成本。使用Dijkstra算法進(jìn)行公路運(yùn)輸最優(yōu)路徑搜索的流程如圖4所示，主要包括：

（1）路徑起點(diǎn)和終點(diǎn)搜索。搜索出公路上距物料站最近的點(diǎn)作為路徑起點(diǎn)，同時(shí)搜索出公路上距上料點(diǎn)最近的點(diǎn)作為路徑終點(diǎn)；

（2）通行成本矩陣擴(kuò)展。將路徑的起點(diǎn)和終點(diǎn)視為路口，并對(duì)通行成本矩陣進(jìn)行擴(kuò)展，將起點(diǎn)和終點(diǎn)同時(shí)添加到通行成本矩陣；

（3）基于Dijkstra算法進(jìn)行路徑規(guī)劃。使用Dijkstra算法對(duì)通行成本矩陣進(jìn)行計(jì)算，得到起點(diǎn)到終點(diǎn)的最小通行成本路徑。

1.3.1通行成本矩陣擴(kuò)展

根據(jù)輸入的公路矢量數(shù)據(jù)、物料站坐標(biāo)和上料點(diǎn)坐標(biāo)，計(jì)算出距離物料站和上料點(diǎn)最近的公路點(diǎn)作為路徑規(guī)劃的起點(diǎn)和終點(diǎn)。然后將起點(diǎn)和終點(diǎn)添加到通行成本矩陣中，以便后續(xù)對(duì)起點(diǎn)和終點(diǎn)間的最佳路徑進(jìn)行搜索。如圖5（a）所示，在對(duì)矩陣進(jìn)行擴(kuò)展時(shí)，首先將起點(diǎn)和終點(diǎn)視為新的路口，在矩陣上添加兩行和兩列元素，分別表示起點(diǎn)和終點(diǎn)到各路口的通行成本（本研究將起點(diǎn)作為倒數(shù)第二行和列，將終點(diǎn)作為最后一行和列）。然后分別計(jì)算起點(diǎn)和終點(diǎn)到各自相鄰路口的通行成本，將其添加到擴(kuò)展后的通行成本矩陣的對(duì)應(yīng)位置，即可得到如圖5（b）所示的通行成本矩陣。

1.3.2基于Dijkstra算法的最優(yōu)路徑搜索

Dijkstra算法能夠搜索起點(diǎn)到所有路口（包括終點(diǎn)）的最佳路徑，通過(guò)不斷嘗試在已有路徑上插入已知的最近路口來(lái)優(yōu)化現(xiàn)有路徑和增加前往原本不可抵達(dá)的路口的路徑。該方法的主要流程如下：

（1）為起點(diǎn)到各路口的通行成本賦初值并標(biāo)記起點(diǎn)：Ck=Aη-1，k，其中Ck表示起點(diǎn)到路口k的通行成本（k=1，2，3，…， η），η-1表示起點(diǎn)在通行成本矩陣中的編號(hào)，即倒數(shù)第二個(gè)路口。

（2）找到Ck中通行成本最小的非標(biāo)記路口l，提取從路口l出發(fā)到達(dá)各路口的通行成本：Dk=Al，k，并對(duì)該路口進(jìn)行標(biāo)記。

（3）嘗試在起點(diǎn)到各路口的路徑上插入路口l并計(jì)算通行成本Ek=Cl+Dk。如果在路徑上插入路口l的通行成本Ek低于原通行成本Ck，則在已有路徑上插入路口l，并令Ck= Ek；否則，保持原路徑不變。

（4）判斷是否還有未標(biāo)記的路口。如果所有點(diǎn)都已經(jīng)被標(biāo)記，則完成路徑規(guī)劃，并輸出從起點(diǎn)（路口（η-1））到終點(diǎn)（路口η）的最短路徑；否則，返回第2步。

1.4公路與貨運(yùn)索道聯(lián)合路徑規(guī)劃

基于Dijkstra算法搜索出負(fù)載索道路徑集合中每一條索道運(yùn)輸路徑對(duì)應(yīng)的最佳公路運(yùn)輸路徑之后，得到索道-公路聯(lián)合物料運(yùn)輸路徑集合。然后分別計(jì)算每一個(gè)索道-公路聯(lián)合物料運(yùn)輸路徑的索道架設(shè)、運(yùn)行和維護(hù)成本及公路的運(yùn)輸成本，選出最佳索道-公路聯(lián)合物料運(yùn)輸路徑，詳見(jiàn)圖6。

2實(shí)例仿真計(jì)算

圖7所示是某待建特高壓輸電線(xiàn)路通道的局部示意圖，圖中大部分待建鐵塔都位于山區(qū)，距離現(xiàn)有公路較遠(yuǎn)，無(wú)法直接從物料站將施工物料公路運(yùn)輸?shù)剿?，需要架設(shè)貨運(yùn)索道實(shí)現(xiàn)公路到鐵塔施工現(xiàn)場(chǎng)的物料轉(zhuǎn)運(yùn)。以待建鐵塔α為例，其周邊區(qū)域的DEM高程和公路如圖8所示。由于索道總長(zhǎng)度不宜大于2 000 m，圖中僅展示了以待建鐵塔為中心、邊長(zhǎng)4 000 m的方形區(qū)域的DEM高程數(shù)據(jù)，精度為2 m，并在圖中展示了該區(qū)域的公路信息。從圖中可以看出，該鐵塔與最近公路的直線(xiàn)距離約為1 000 m，同時(shí)鐵塔與周邊道路間的地形復(fù)雜，索道運(yùn)輸路徑規(guī)劃難度較大。待建鐵塔α和物料站所在區(qū)域的路網(wǎng)如圖7所示，待建鐵塔和物料站均位于路網(wǎng)圖的中部，以便實(shí)現(xiàn)公路路徑的搜索。

通過(guò)空載索道路徑搜索，在待建鐵塔α與周邊道路之間建立1 638條空載索道路徑，然后使用所提出的干涉點(diǎn)搜索法為所有空載索道路徑搜索支架點(diǎn)，并得到30條滿(mǎn)足索道參數(shù)約束條件的空載索道路徑。對(duì)所有空載索道路徑進(jìn)行負(fù)載篩選，獲得負(fù)載索道路徑集合，負(fù)載索道路徑集合中共有6條滿(mǎn)足貨物運(yùn)行高度要求的索道，其中最短索道路徑如圖9所示。在此基礎(chǔ)上，搜索從物料站到所有負(fù)載索道路徑上料點(diǎn)的公路運(yùn)輸路徑，綜合判斷得到最優(yōu)索道-公路運(yùn)輸路徑如圖10所示。以上施工物料索道-公路運(yùn)輸路徑規(guī)劃工作由計(jì)算機(jī)（計(jì)算機(jī)處理器：英特爾 Core i7-9700 @3.00 GHz八核，內(nèi)存：8 GB）根據(jù)輸入的DEM高程、路網(wǎng)、鐵塔位置和物料站位置等數(shù)據(jù)自動(dòng)完成，共耗時(shí)約25 min，相對(duì)于耗時(shí)數(shù)天的人工路徑規(guī)劃，該自動(dòng)路徑規(guī)劃方法的效率更高。

3結(jié)語(yǔ)

本文運(yùn)用DEM高程數(shù)據(jù)和索道設(shè)計(jì)參數(shù)，實(shí)現(xiàn)了復(fù)雜地形區(qū)域的空載索道路徑搜索；通過(guò)干涉點(diǎn)搜索法，結(jié)合地形剖面和支架點(diǎn)選取原則，實(shí)現(xiàn)了索道支架點(diǎn)的自動(dòng)搜索以及索道路徑和支架的自動(dòng)設(shè)定；通過(guò)計(jì)算負(fù)載索道貨物軌跡，綜合DEM和支架高度，實(shí)現(xiàn)了索道路徑的優(yōu)化與篩選，以及復(fù)雜地形區(qū)域的負(fù)載索道路徑搜索；以路徑長(zhǎng)度為通行成本估值，實(shí)現(xiàn)了基于Dijkstra算法的公路最優(yōu)路徑搜索；綜合考慮公路運(yùn)輸和索道運(yùn)輸，生成了輸電線(xiàn)路物料索道-公路聯(lián)合運(yùn)輸最優(yōu)路徑。該研究可用于復(fù)雜地形區(qū)域輸電線(xiàn)路鐵塔的施工組織，能夠提高路徑規(guī)劃效率，降低施工成本。

參考文獻(xiàn)：

［1］繆謙， 白雪松. 貨運(yùn)索道運(yùn)輸技術(shù)與設(shè)備研究[J]. 電力建設(shè)， 2009， 30（12）： 93-96. DOI：10.3969/j.issn.1000-7229.2009.12.025.

[2]葉建云， 王成波， 鄭力維， 等. 帶轉(zhuǎn)角貨運(yùn)索道研究及應(yīng)用[J]. 工程與建設(shè)， 2015， 29（5）： 701-703. DOI：10.3969/j.issn.1673-5781.2015.05.041.

[3]溫惠英， 徐建閩. 基于改進(jìn)型蟻群算法的車(chē)輛導(dǎo)航路徑規(guī)劃研究[J]. 公路交通科技， 2009， 26（1）： 125-129. DOI：10.3969/j.issn.1002-0268.2009.01.023.

[4]沈永增， 陳瑞， 黃海港. 基于遺傳神經(jīng)網(wǎng)絡(luò)的車(chē)輛導(dǎo)航路徑規(guī)劃[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2013， 22（8）： 210-213. DOI：10.3969/j.issn.1003-3254.2013.08.046.

[5]吳光周， 楊家文. 面向出行時(shí)間可靠性的最優(yōu)路徑規(guī)劃[J]. 公路， 2017， 62（2）： 134-142. DOI：10.3969/j.issn.1673-629X.2014.08.008.

[7]吳紅波， 王英杰， 楊肖肖. 基于Dijkstra算法優(yōu)化的城市交通路徑分析[J]. 北京交通大學(xué)學(xué)報(bào)， 2019， 43（4）： 116-121. DOI：10.11860/j.issn.1673-0291.2019.20180109.

[8]謝建平， 陳治亞， 鄧連波， 等. 改進(jìn)Dijkstra算法在大型城市軌道交通網(wǎng)計(jì)價(jià)系統(tǒng)中的應(yīng)用[J]. 國(guó)防科技大學(xué)學(xué)報(bào)， 2021， 43（1）： 109-116.

[9]楊璐， 汪博涵， 張雪潔. 基于A*算法的AGV路徑規(guī)劃研究[J]. 公路與汽運(yùn)， 2014（4）： 47-49. DOI：10.3969/j.issn.1671-2668.2014.04.014.

[10]聶易彬， 譚明軍， 劉剛， 等. 基于改進(jìn)A*算法的高速公路互聯(lián)網(wǎng)地圖最短路徑搜索研究[J]. 公路交通技術(shù)， 2020， 36（4）： 110-114. DOI：10.13607/j.cnki.gljt.2020.04.020.

[11]王峰博， 崔先國(guó)， 丁琳， 等. 基于Dijkstra算法駕車(chē)導(dǎo)航路徑研究與實(shí)現(xiàn)[J]. 中國(guó)西部科技， 2011， 10（34）： 26-28. DOI：10.3969/j.issn.1671-6396.2011.34.012.

[12]劉亞磊， 李淵， 吳俊麗， 等. 基于改進(jìn)Dijkstra算法的高速公路應(yīng)急疏散路徑規(guī)劃[J]. 交通運(yùn)輸研究， 2016， 2（6）： 54-59. DOI：10.16503/j.cnki.2095-9931.2016.06.009.

[13]李攀， 李志斌， 謝芳毅， 等. 三維GIS輔助山區(qū)輸電線(xiàn)路貨運(yùn)索道選線(xiàn)系統(tǒng)設(shè)計(jì)[J]. 數(shù)字技術(shù)與應(yīng)用， 2016（5）： 173-174. DOI：10.19695/j.cnki.cn12-1369.2016.05.120.

[14]秦劍， 張飛凱， 江明， 等. 基于地形搜索的輸電線(xiàn)路貨運(yùn)索道支架設(shè)置方法及系統(tǒng)： CN113393187A[P]. 2021-09-14.

[15]秦劍， 張飛凱， 江明， 等. 基于干涉點(diǎn)搜索輸電線(xiàn)路貨運(yùn)索道支架設(shè)置方法及系統(tǒng)： CN113343395A[P]. 2021-09-03.

[16]秦劍， 張飛凱， 江明， 等. 一種基于地形自適應(yīng)構(gòu)建輸電線(xiàn)路貨運(yùn)索道的方法及系統(tǒng)： CN113408084A[P]. 2021-09-17.

[17]秦劍， 張飛凱， 江明， 等. 一種輸電線(xiàn)路施工物料運(yùn)輸路徑規(guī)劃方法及系統(tǒng)： CN113393188A[P]. 2021-09-14.

[18]張衛(wèi)東， 秦劍， 陳迪， 等. 工作索耦合作用下多檔多載荷貨運(yùn)索道的分析與計(jì)算方法[J]. 工程設(shè)計(jì)學(xué)報(bào)， 2020， 27（3）： 293-300. DOI：10.3785/j.issn.1006-754X.2020.00.032.