王非，張洪海，馮謳歌，任真蘋，鐘罡

（南京航空航天大學民航學院,江蘇 南京 211106）

引言

智能化的快速發(fā)展使無人機慢慢走入了大眾的視野，無人機的生產(chǎn)和運行成本低廉、機動性和可操作性高、無需人員隨機運行的特點都使其在諸多領域有著巨大的發(fā)展?jié)撃埽?］。同時，隨著互聯(lián)網(wǎng)時代的到來，網(wǎng)購成為了一種備受歡迎的購物方式，物流配送的需求也越來越大。但由于物流運輸?shù)哪康牡赝^分散，運輸鏈末端“挨家挨戶”式的配送方式耗費了大量的資源，亟需探索低空空域的潛力，改善“最后一公里”的貨物運輸問題［2］。受疫情影響，無接觸配送日漸流行，而無人機的運行特點與無接觸配送的物流需求十分契合，因此研究無人機物流運輸也順應了物流運輸行業(yè)的發(fā)展趨勢。

航路網(wǎng)絡作為無人機在空域內(nèi)實現(xiàn)飛行活動的載體，可以使相同起降點的無人機以規(guī)定的路徑進行飛行，有效躲避障礙物及禁飛區(qū)，確保飛行的安全；同時，限定的飛行路線也使無人機以“流”的形式在系統(tǒng)中運行，便于管理人員在系統(tǒng)運行時對物流無人機進行監(jiān)視和管控。因此，研究物流無人機航路網(wǎng)絡的規(guī)劃方法對推動無人機物流運輸?shù)陌l(fā)展具有重大價值。

對于物流無人機航路網(wǎng)絡的劃設，國內(nèi)外學者的研究多集中于無人機路徑規(guī)劃領域。Damilano等［3］強調(diào)創(chuàng)建路由是無人機任務分配的核心步驟，并以最短時間、最小距離、最小風險等作為無人機飛行路由的優(yōu)化目標。Yang等［4］基于高斯過程，利用快速搜索隨機樹的方法開發(fā)了一種無人機路徑規(guī)劃模型，該模型可用于無人機在未知環(huán)境中進行地形探索和路徑規(guī)劃，但其在大面積規(guī)劃時算法復雜度過高，且輸出路徑并不能確定為最優(yōu)解。Jayaweera等［5］為解決無人機在執(zhí)行偵察探測任務時路徑規(guī)劃的問題，基于改進的人工勢場法建立了一種支持“展望覆蓋”的無人機三維路徑規(guī)劃模型，并驗證該模型在無人機動態(tài)路徑規(guī)劃問題中的優(yōu)越性。吳振等［6］以山區(qū)環(huán)境為模擬場景，考慮到無人機的飛行行為約束，提出精英池的概念以降低最優(yōu)解丟失的概率，采用改進的遺傳算法對無人機進行路徑規(guī)劃。徐晨晨等［7］將A*算法融入到蟻群算法中，開發(fā)出一套可以快速收斂的規(guī)劃方法。Jason等［8］基于A*算法，以最短距離為目標函數(shù)，設計了基于A*算法的無人機路徑規(guī)劃器，并分析了不同啟發(fā)函數(shù)對算法速度和準確度的影響；宋宇［9］對A*算法進行優(yōu)化，通過幾何法將傳統(tǒng)A*算法規(guī)劃的折線拐角優(yōu)化為弧形拐角，并驗證了該方法對縮短路徑長度的有效性。張洪海等［10］考慮到最小步長、無人機飛行行為限制等約束，對A*算法進一步改進，綜合航程代價、高度代價和危險度代價提出了一種城市區(qū)域物流無人機路徑規(guī)劃方法。此外，也有一些研究側重于無人機航路網(wǎng)絡的構建，Mcfadyen等［11］認為構建航路網(wǎng)絡的關鍵是尋找合適的網(wǎng)絡節(jié)點，以無向圖的形式組建了類似于地面道路網(wǎng)的無人機運行網(wǎng)絡；李姍等［12］考慮無人機運行風險，提出了一種基于改進元胞自動機算法的無人機航路網(wǎng)絡，但并未考慮物流倉庫與用戶取貨點這一典型的物流運輸場景。

本文選取“物流倉庫——取貨點”間物流運輸作為典型研究場景，結合城市低空的復雜飛行環(huán)境，以保障物流運輸安全性和高效性為目標，提出一種城市區(qū)域物流無人機航路網(wǎng)絡構建方法，以獲得便于監(jiān)控、易于管制的無人機配送航路。

1 航路環(huán)境建模

1.1 任務假設

針對某城市物流配送區(qū)域，已知物流倉庫與用戶取貨點位置，需規(guī)劃一距離短、沖突少、風險小的無人機航路網(wǎng)絡，供無人機從物流倉庫攜貨物出發(fā)運往用戶取貨點并在卸貨后空機返回。假設無人機為可垂直起降的多旋翼無人機，航路網(wǎng)絡設計時采用分層航路，即除在起降場區(qū)域無人機不調(diào)整其飛行高度層，飛行高度保持不變，如圖1所示。

1.2 運行環(huán)境構建

基于任務假設，無人機僅在其起降區(qū)域進行爬升和下降操作，其余飛行階段均在一二維平面內(nèi)進行。假設該二維平面長度為Length、寬度為Width的矩形，將該矩形以粒度為lg的方形柵格進行分割，可得到u×v個柵格，其中u=int(Length/lg)，v=int(Width/lg)，int()為取整函數(shù)，柵格中心點為可選航路點。

在城市區(qū)域中，存在高大樓宇等地形障礙物禁飛區(qū)、政策性禁飛區(qū)以及事故危害性過高禁飛區(qū)，在規(guī)劃無人機飛行航路時應嚴格避開此類區(qū)域。劃設禁飛區(qū)時應確保實際禁飛區(qū)覆蓋區(qū)域相對嚴格禁飛區(qū)域存在一定的安全裕度，即設定一定范圍的禁飛區(qū)保護區(qū)［13］。同時，為防止物流無人機運行故障導致不必要的損害，在規(guī)劃航路時應盡量避免飛躍人流密集區(qū)及交通主干路等地面活動較多的危險運行區(qū)。為定量描述空域特征，可為不同特殊區(qū)域的柵格賦予不同柵格危險度值，如表1所示。

表1 柵格危險度值

2 基于改進A*的航路網(wǎng)絡協(xié)同規(guī)劃算法

2.1 傳統(tǒng)A*算法原理

由于無人機載重及運輸距離限制，本文所研究的物流倉庫與用戶取貨點間的貨物運輸場景覆蓋范圍較小、地點復雜度較低，可參照多航路協(xié)同規(guī)劃的結果優(yōu)化生成航路網(wǎng)絡。A*算法作為被廣泛應用于路徑規(guī)劃領域的啟發(fā)式算法，通過估價函數(shù)f(x)判斷航跡點的優(yōu)劣，引導算法快速收斂，即：

式中g(x)為實際代價函數(shù)，表示無人機飛行起點S至當前航跡點Px的實際代價；h(x)為啟發(fā)函數(shù)，表示當前航跡點Px至無人機飛行終點E的預估代價。

使用A*算法進行尋路時，無人機僅可由當前柵格中點向周圍8個柵格中點移動，具體的行進方向如圖2所示。

2.2 基于改進A*的航路網(wǎng)絡協(xié)同規(guī)劃算法設計方案

2.2.1 估價函數(shù)

（1）代價函數(shù)

在同一個高度層內(nèi)運行的無人機，假設其起點S坐標為(X0，Y0)，路徑規(guī)劃終點E坐標為(Xn，Yn)，路徑中經(jīng)過某點Px的坐標為(Xx，Yx)，考慮具體代價函數(shù)如下：

式中CL(x)和CD(x)分別表示起點S至當前點Px的實際航程代價及危險度代價，可分別表示為：

式中k為危險度懲罰系數(shù)；di為柵格的危險度；li為無人機在相應柵格內(nèi)行進的距離。

（2）啟發(fā)函數(shù)

歐氏距離常被用來表示兩點間的直線距離，是A*算法中經(jīng)常使用的啟發(fā)函數(shù)形式。本文的啟發(fā)函數(shù)取當前點Px和終點E間的歐式距離，表示為：

式中Xx和Yx分別為當前柵格點的橫縱坐標。

2.2.2 約束條件

（1）最小航段長度約束

無人機在配送貨物的過程中，由于轉彎、機動、氣象等原因其運動軌跡無法與規(guī)劃的路徑嚴格重合，且運輸過程中無人機的地理位置、速度等信息都是實時變化的。但由于監(jiān)視系統(tǒng)的傳輸存在延時，無人機做出姿態(tài)改變也需要一定的時間，因此需要為無人機預留出一段距離使其能在這段時間內(nèi)保持直飛但不至于影響其執(zhí)行運輸任務。這段距離定義為最小航段長度，路徑規(guī)劃的各航段應滿足：

式中l(wèi)i為各航段的長度；lmin為最小航段長度。

（2）最大載重約束

由于無人機的動力有限，物流無人機運輸可配送的貨物重量也需要控制在一定范圍內(nèi)，過重的貨物可能會導致無人機在運輸過程中難以控制飛行軌跡、縮短無人機最大飛行航程，甚至無法正常配送。因此，對于無人機的載重W應滿足：

式中Wmax為無人機的最大載重。

（3）最大飛行航程約束

雖然無人機具有體積小、重量輕的優(yōu)點，但也正因如此，無人機的動力和運行距離是十分有限的。在對無人機進行路徑規(guī)劃時，需要確保無人機有足夠的動力將貨物送達目的地并空機返回。對于飛行航程L的約束如下所示：

式中EUAV為無人機電池容量；WUAV為無人機空重；γ為無人機單位重量單位距離的能耗；ll為送貨去程各航段的飛行航程；lr為送貨返程各航段的飛行航程。

（4）最大轉彎角度約束

在物流配送的過程中，為滿足配送的需求可能會出現(xiàn)無人機轉彎角度過大的情況，但考慮到無人機的真實運行情況，過大的轉彎角度無法在實際運行中成功執(zhí)，因此無人機的轉彎操作應滿足：

式中θmax為系統(tǒng)允許的無人機最大轉彎角。

2.2.3 初始航路協(xié)同規(guī)劃

在對物流無人機航路網(wǎng)絡進行協(xié)同規(guī)劃時為往返航路分配不同的飛行高度層。同時，為便于監(jiān)控管制并防止去程和返程的無人機發(fā)生故障時互相影響，盡量保證往返航路之間存在一定的水平安全距離。因此可按照如下規(guī)則進行航路網(wǎng)絡協(xié)同規(guī)劃：對所有去程航路進行航路規(guī)劃并設置一定寬度的運行保護區(qū)；在規(guī)劃返程路徑時，去程路徑的運行保護區(qū)同樣被視為危險運行區(qū)，應盡量繞飛。保護區(qū)寬度需滿足：

式中Smin為無人機運行的最小水平間隔。

航路保護區(qū)示意圖如圖3所示。

對各起降點使用上述方法進行往返航路協(xié)同規(guī)劃，即可得到物流無人機初始航路網(wǎng)絡。

2.2.4 航路網(wǎng)絡優(yōu)化

（1）航路平滑處理

如圖2所示，由于A*算法尋路的方向限制，輸出的往返航路可能會存在不必要的飛行轉彎，此類轉彎需對其進行平滑處理。在平滑時，應確保平滑后航路的總體走勢與A*算法的輸出結果保持一致，因此僅對受限于A*算法巡路方向導致的不必要轉彎進行優(yōu)化，此類轉彎應符合：

式中Δl為航段的長度；lg為柵格的邊長；Δang為前后兩航段的方向變化。

并且，在對航路進行平滑時，仍要確保每條飛行路徑的運行安全，航路的危險度代價不可增加，表示為：

式中R為所有航路的集合；CrDsmooth為某航路平滑后的危險度代價；CrD為該航路的初始危險度代價。

當航路中的某連續(xù)航段滿足航路平滑條件時可對該彎折航段取其首尾，以一條直線進行連接，如圖4所示。判斷連接后的航段危險度代價是否增加，若危險度代價未出現(xiàn)增加則將此部分更新為平滑航段，若危險度代價增加則仍使用原航段。

（2）航路網(wǎng)絡合并和重規(guī)劃

為簡化航路網(wǎng)絡的結構，對不滿足安全間隔（無人機不可在其內(nèi)并排運行）的航段進行合并處理，此類航段應滿足：

式中Δdmin為兩待合并航段間的最小距離；ΔANG為兩待合并航段的夾角；ANGmin為最小可合并夾角。

在對無人機航路網(wǎng)絡進行合并時可能會犧牲網(wǎng)絡局部的最優(yōu)性來換取網(wǎng)絡的整體優(yōu)化，但過分增加某航路的飛行距離是不可取的，因此應限制：

式中l(wèi)rmerge為合并后的航路長度；α為可接受的航路長度負優(yōu)化最大比重。

一般情況下城區(qū)某區(qū)域內(nèi)存在一物流倉庫與多用戶取貨點，去程/返程航路呈輻射狀分布。在進行航路網(wǎng)絡合并時，對往返航路均進行取貨點至物流倉庫方向的合并條件搜索，如圖5。由于使用此方向搜索時各航路均終止于物流倉庫，因此當某兩航段滿足合并條件時可對其所屬航路的后續(xù)所有航段進行合并。

設兩待合并航段為較短航段m（屬于航路a）和較長航段n（屬于航路b），延伸m-1航段，若其能與n航段相交，則以該點為航路合并交點；若不能相交，則將航段n的起點與航段m的起點連接，以該點為航路合并交點，如圖6所示。對于合并后航路的選取，為防止選擇某一航路的后續(xù)航段導致另一航路的過度負優(yōu)化，本文選擇在交點處再次使用A*算法計算交點至終點的最優(yōu)路徑，將平滑后的計算結果作為合并點的后續(xù)航段。

（3）物流倉庫終端區(qū)處理

無人機在起降場的起降方式也是建立航路網(wǎng)絡時應考慮的重要問題?；谄鸾祱鲈诰W(wǎng)絡中的重要程度和進出起降場無人機飛行活動的復雜度，可將物流倉庫視為高級起降場，將用戶取貨點視為普通起降場。普通起降場的無人機起降需求較少，因此對于普通起降場不需額外規(guī)定起降方向，無人機按照其既定飛行方向即可進行順向起降。高級起降場處無人機起降方向眾多，起降需求較大，但考慮到起降空域有限，不同起降方向的無人機運行時可能會存在互相干擾的情況，導致無人機在終端區(qū)內(nèi)運行混亂。類比民航飛行的進近方法，將高級起降場一定范圍內(nèi)劃設為終端區(qū)，并在終端區(qū)內(nèi)設置多個起降走廊口和起降航線。起降航線應位于不同方向且彼此間隔，無人機根據(jù)其原本飛行航路選擇距離負優(yōu)化最小的起降走廊CORR：

式中disc1～disc2分別為終端區(qū)外待處理航路沿運行方向第一個航路點與可選取的四個走廊點的距離。

終端區(qū)形態(tài)如圖7所示。

將物流無人機航路網(wǎng)絡中各航路終端區(qū)外的第一個航路點與其選用的走廊口進行連接，即可完成對無人機航路網(wǎng)絡終端區(qū)的處理，在航路網(wǎng)絡運行時無人機可在終端區(qū)內(nèi)按照起降航線進行排序起降。

2.2.5 算法實現(xiàn)

基于改進A*的航路網(wǎng)絡協(xié)同規(guī)劃算法主要分為兩部分實現(xiàn)：首先基于不同的無人機物流需求使用改進的A*算法進行多航路協(xié)同規(guī)劃；然后根據(jù)航路平滑、合并等優(yōu)化準則對協(xié)同規(guī)劃的結果進行優(yōu)化從而得到最終航路網(wǎng)絡，算法具體流程如下：

Step1：選擇物流運輸區(qū)域，對區(qū)域內(nèi)的地理環(huán)境進行柵格化處理，標記危險柵格和禁飛柵格，統(tǒng)計物流無人機運輸需求起降點對。

Step2：選取一對未規(guī)劃去程航路的需求點對，以物流倉庫為起點S，以取貨點為終點E，轉向Step3；若無未規(guī)劃點對，轉向Step6。

Step3：對 于 起 降 點S和E，建 立OPEN和CLOSE列表，將起點S作為父節(jié)點，計算起點S周圍各柵格點的g(x)，h(x)，f(x)，并將這些柵格點加入OPEN列表中。

Step4：執(zhí)行下述步驟：

Step4.1：彈出在OPEN列表中f(x)最小的柵格點P，將此柵格點P作為下一路徑點，并放入CLOSE列表中。

Step4.2：判斷P點是否為終點E，若P為終點則轉向Step5，否則轉向Step4.3。

Step4.3：檢查P點相鄰的柵格點，若相鄰柵格點未在OPEN列表中，則將其加入OPEN列表，并將點P作為新的柵格的父節(jié)點；若相鄰柵格點已在OPEN列表中，則檢查當前路徑代價是否最小。

Step4.4：重 新 計 算g(x)，h(x)，f(x)，返 回Step3.1。

Step5：存儲算法得到的最優(yōu)路徑和最終代價，若正規(guī)劃去程航路，則轉回Step2；否則轉向Step9。

Step6：遍歷所有去程航路，對航路網(wǎng)絡進行平滑、合并及終端區(qū)處理。

Step7：若經(jīng)過Step6后航路網(wǎng)絡未發(fā)生變化則轉向Step8，否則轉回Step6。

Step8：為所有去程航路設置寬度為Wprotect的保護區(qū)，統(tǒng)計無人機運輸返程需求點對。

Step9：選取一對未規(guī)劃返程航路的需求點對，以用戶取貨點為起點S，以物流倉庫為終點E，轉向Step3；若無未規(guī)劃點對，轉向Step10。

Step10：遍歷所有返程航路，對航路網(wǎng)絡進行平滑、合并及終端區(qū)處理。

Step11：若經(jīng)過Step10后航路網(wǎng)絡未發(fā)生變化則轉向Step12，否則轉回Step10。

Step12：為往返航路設置不同的飛行高度層并布置到相應場景中，算法結束。

算法流程圖如圖8所示。

3 仿真與分析

3.1 仿真實驗環(huán)境

為驗證本文提出的物流無人機航路網(wǎng)絡規(guī)劃算法的合理性和有效性，選擇南京航空航天大學將軍路校區(qū)為仿真實驗場景，選取校區(qū)菜鳥驛站為物流倉庫，學生宿舍及部分距倉庫較遠處為用戶取貨點，各起降點的地理位置信息如表2所示。

表2 起降點地理位置信息

劃設校區(qū)內(nèi)高樓為障礙物禁飛區(qū)、校區(qū)圖書館為行政禁飛區(qū)、高速公路為事故危害過高禁飛區(qū)，同時劃設人流密集危險區(qū)及主干道路危險區(qū)，各特殊區(qū)域具體劃設情況及起降點分布如圖9所示。圖中紅色區(qū)域為禁飛區(qū)，橙色區(qū)域為危險區(qū)，藍色區(qū)域為可穿越禁飛區(qū)的飛行通道，其余區(qū)域為自由空域。

各仿真參數(shù)設置如表3所示［10，13-14］。

表3 航路網(wǎng)絡仿真參數(shù)

3.2 仿真結果分析

使用基于改進A*的航路網(wǎng)絡協(xié)同規(guī)劃算法對區(qū)域中的1個物流倉庫及7個用戶取貨點進行航路網(wǎng)絡規(guī)劃，算法輸出的優(yōu)化航路網(wǎng)絡如圖10所示。

圖中藍色路線為送貨去程路線，紅色路線為空機返程路線。可以看出，算法生成的航路網(wǎng)絡很好的實現(xiàn)了繞開高大建筑、間隔往返路徑、合并相似路徑、連接起降程序的需求。為進一步驗證航路網(wǎng)絡協(xié)同規(guī)劃方法的有效性和優(yōu)越性，采用A*算法直接規(guī)劃得到的航路結構如圖11所示。

對比表4中使用A*算法直接規(guī)劃的航路與使用優(yōu)化算法協(xié)同規(guī)劃的航路，基于改進A*的航路網(wǎng)絡協(xié)同規(guī)劃算法輸出的各航路長度較A*算法直接規(guī)劃平均減少7.6%，轉彎點數(shù)量平均減少59.3%，航路代價平均減少13.0%。對比圖10和圖11，A*算法直接規(guī)劃輸出的航路構型在物流倉庫處復雜交錯難以區(qū)分，存在多處交叉，且存在“X”型的交叉航路，不同航路的交叉互相影響，不同路線的無人機在其中執(zhí)行任務時易互相干擾，不利于無人機的調(diào)配；協(xié)同規(guī)劃算法輸出的航路結構更為簡單，只存在少量“Y”型匯聚/發(fā)散航路，不同路線的無人機執(zhí)行任務時更易調(diào)配，能夠高效承載無人機在其內(nèi)執(zhí)行物流配送任務。

表4 規(guī)劃航路主要參數(shù)對比

4 結語

為推動無人機物流運輸?shù)陌l(fā)展、保障物流無人機在執(zhí)勤過程中有序運行，本文提出了一種基于改進A*的航路網(wǎng)絡協(xié)同規(guī)劃算法。該算法以協(xié)同規(guī)劃的形式，相比各需求點間獨立規(guī)劃在規(guī)劃航路的長度、轉彎點數(shù)量及運行帶加上都更具優(yōu)勢。仿真實驗表明，使用協(xié)同規(guī)劃算法規(guī)劃的航路長度平均減少7.6%，轉彎點數(shù)量平均減少59.3%，航路代價平均減少13.0%。同時，協(xié)同規(guī)劃輸出的航路網(wǎng)絡結構更為簡潔，不存在相互影響的多交叉航路，易于對在航路網(wǎng)絡中執(zhí)行物流運輸任務的無人機進行管控。