復雜環境下無人機配送路徑優化

張蓓蓓 靳舒葳 由嘉偉 謝曉迪

摘? 要：針對偏遠地區無人機配送時效差以及配送環境復雜的問題，構建了復雜環境下無人機配送路徑優化模型。模型以配送時間最短為目標，不僅考慮了無人機的續航能力、載重能力、載重變化對路徑選擇的影響，而且還將影響配送時間的環境因素（如風速、風向）考慮在內。為了驗證模型的有效性，以湖北某鄉村為例設計案例，通過蟻群算法對模型進行求解，并對風速、風向的交互作用進行了情景分析。實驗結果表明，在無人機的飛行極限范圍內，風速越大對無人機飛行的影響越大，配送時間整體呈現增加的趨勢；當風速增加到一定程度時，風向角度變化會對無人機飛行時間產生較大影響。該研究可為復雜環境下無人機物流配送提供理論依據，進而為無人機路徑規劃研究提供有力支持和參考依據。

關鍵詞：物流配送；蟻群算法；復雜環境；路徑優化

中圖分類號：TP18；F252 文獻標識碼：A 文章編號：2096-4706（2023）09-0121-06

Abstract： A model for optimizing UAV delivery paths in complex environments is constructed to address the issues of poor delivery timeliness and complex delivery environments in remote areas. The model aims to minimize delivery time， taking into account not only the impact of UAV's endurance， load capacity， and load changes on its path selection， and also taking into account environmental factors that affect delivery time， such as wind speed and wind direction. In order to verify the effectiveness of the model， a case study is designed using a rural area in Hubei Province. The model is solved using ant colony algorithm and scenario analysis is conducted on the interaction between wind speed and wind direction. The experimental results show that within the flight limit range of UAV， the greater the wind speed， the greater the impact on UAV's flight， and the overall delivery time shows an increasing trend; When the wind speed increases to a certain extent， the change in wind direction angle will have a significant impact on the flight time of the UAV. This study can provide theoretical basis for UAV logistics distribution in complex environments， and thus provide strong support and reference for UAV path planning research.

Keywords： logistics distribution; ant colony algorithm; complex environment; path optimization

0? 引? 言

近年來，隨著技術革新與城市發展，我國物流市場不斷擴大，需求量劇增。根據中國年貨物運輸量數據顯示，從2011年至2021十年的時間里，年貨物運輸量整體呈現穩步增長的趨勢，從2011年到2021年年貨物運輸增長了43個百分點。無人機作為低空空域物流運輸的新寵，依托于我國龐大的物流運輸市場，擁有廣闊的市場背景。相較于傳統的物流運輸方式，無人機物流運輸配送的優勢顯著。利用無人機配送可以避免傳統快遞物流運輸路線的局限性，運輸的效率更高，在一定程度上降低了人力資源和時間成本的消耗。無人機在完成農村配送“最后一公里”難題上具有更明顯的優勢。但是對于無人機的物流配送，不能忽略配送過程中的復雜環境，這些復雜環境必然會影響到無人機的飛行速度，從而影響整個配送系統的配送時間。

關于無人機系統優化路徑算法，仍然是國內外的學者研究的熱點，現有路徑規劃算法主要分為經典算法和元啟發式算法，經典算法包括基于搜索的算法如A*算法、D*算法、圖搜索法，這些算法在單無人機路徑規劃問題上表現出良好的性能，但是難以適用于大規模、高維度、非線性的多無人機路徑規劃問題中，部分學者在此基礎上做出了更有深度的研究。例如，宋佳艷利用改進后的蟻群算法解決了自動駕駛多車的協同安全性與軌跡的平滑[1]；趙宏業研究了遺傳算法與蟻群算法相結合解決醫療人力資源的調度問題[2]；毛壽祺利用基于細菌覓食-改進蟻群算法解決了水面無人船全局路徑規劃問題[3]；潘紅麗提出改進的粒子群算法用于垃圾清運車的路徑規劃問題[4]；黃辰[5]、Carabaza[6]等均研究了改進蟻群算法解決路徑優化的最短時間問題和停滯問題，以及最小時間搜索規劃無人機的飛行軌跡；胡丹[7]等研究了改進精英蟻群算法在未知環境下的機器人路徑規劃問題，使得改進后的蟻群算法在搜索時具有更好的收斂性和更優的平滑性；Rivera[8]等研究了一種基于蟻群的超啟發式排列多目標進化算法，偏好融入多目標后進行模型求解；Nie等將蟻群算法與神經網絡算法相融合，提高了解決三維路徑的效率問題[9]。雖然許多學者已經對無人機的配送路徑優化進行了一系列的研究，但是針對無人機在復雜環境下的配送路徑優化的研究相對較少，且實際應用于解決相關行業的路徑優化多是以成本最小為目標，對于要求時間最短的路徑優化來解決實例的較少。

本文將結合無人機物流配送的特點，研究復雜環境下無人機配送路徑的優化，以時間最短為目標建立基于無人機復雜環境下配送路徑優化模型，加入自然風、載重對無人機飛行速度的影響，電池續航能力的限制、配送點的需求量等其他復雜條件。通過改進蟻群算法實現無人機配送路徑的優化，最后利用實例驗證整個物流配送模式的可行性。從而達到高效的配送，提高經濟效益以及物流的便捷性。

1? 問題描述

對于現在已有的配送服務，農村快遞物流配送普遍存在“配送最后一公里”的問題，在農村物流配送中面臨著配送鏈條長、需求分散、配送時間較長的問題，而傳統的配送車體積大、成本高、偏遠地區配送不到，在一定程度上造成了資源的浪費，使用物流無人機則可以在一定程度上解決這些問題?；凇皬碗s環境下無人機配送路徑優化模型”，假設配送中心有四旋翼貨運無人機K架，無人機的載重均為15 kg，最大續航時間為30 min，飛行高度為200 m。對某農村區域需求量不同的L個配送點進行快遞配送，每一條路徑配送完成后，無人機會返回配送中心進行補貨和充電。由于無人機的載重能力和續航能力是有限的，就需要多架無人機進行協同配送。根據各個配送點的需求量，分別選擇最優路徑進行貨物配送。無人機配送模式如圖1所示。

在此過程中，無人機的飛行會受到天氣情況的影響，比如大風天氣會影響無人機的飛行速度；在無人機垂直起落的過程中，載重會大量消耗電池的續航能力，減少續航里程，增長配送時間。隨著載重的改變，無人機的配送時間也會發生改變。這些原因造成的時間損耗都會使得客戶的滿意度和服務體驗下降。因此，為了能夠縮短客戶等待時間，提高用戶滿意度，就需要對物流無人機進行路徑優化研究，建模的優化目標將是無人機物流配送的時間最短。

問題假設如下：

1）假設配送站最多可以用同一型號的無人機K架對L個配送點進行配送，且每個配送站點的總需求量不超過無人機的最大載重量。

2）無人機從配送站出發后，在途中未收到指令的情況下，完成配送后，無人機需要返回配送中心。且所有的配送點都是一站式交付，即無人機在一次飛行工作中同一個站點只訪問一次。

3）無人機在配送中心一次性裝貨，在配送點多次卸貨。

4）需要考慮無人機在配送過程中風力和負載對其速度造成的影響。

5）不考慮無人機的飛行姿態，以及無人機在風力條件下的結構變化。

6）在整個配送過程中，無人機均保持恒定的速度行駛，初始階段的加速與結束階段的減速均不考慮。

7）不考慮配送過程中鳥類和人為因素的影響。

2? 數學模型

無人機路徑優化問題的目標主要有時間最短。即無人機在電池續航時間允許的前提下，能夠在最短時間內完成配送點的目標配送。對于一架無人機來說，在整個配送過程中的總時間可以由以下幾部分相加得到：

其中，式（1）表示總時間的組成部分；式（2）表示無人機在配送過程中的飛行時間；式（3）表示無人機在各個站點起飛和降落的時間；式（4）表示無人機在配送站裝貨的時；式（5）表示無人機在各個配送點的?？啃敦洉r間；式（6）為目標函數時間最小化；式（7）表示從配送站出發的無人機的最大數量為K；式（8）表示被派遣參與配送的無人機最終都要返回配送站；式（9）和式（10）表示每個配送點僅有一架無人機進行配送；式（11）表示配送路線上的配送點貨物需求總和要小于額定最大載重；式（12）表示每一架無人機到達某個配送點p完成配送后就離開該配送點；式（13）表示無人機配送時的剩余電量足夠完成配送；式（14）表示無人機充電后的能量能夠滿足配送的飛行以及交付任務式（15）和式（16）表示路徑選擇。同一地點的客戶只能一次性配送完成，無人機只能從配送站出發，完成若干個配送點的配送后返回配送站。具體符號說明詳見表1。

3? 路徑優化算法設計

3.1? 蟻群算法的原理

經典蟻群算法是DORIGO等[10]通過觀察螞蟻群體覓食行為提出的一種模擬優化算法，主要用于解決最短路徑問題，m只螞蟻中，每一只螞蟻隨機從某個節點出發，或全部從某一選定節點出發，根據輪盤賭法以及信息素濃度來確定螞蟻將去往哪一節點，螞蟻會在路徑上留下信息素，該信息素與節點之間的距離成正比，所有螞蟻遍歷完所有節點并回到各自出發節點后，完成第一次迭代。經過多次迭代后，即可根據信息素濃度來確定最短路徑。

本文的模型涉及類VRP問題，即無人機路徑規劃或派送問題?？紤]無人機裝貨總量的限制，如果使用傳統的蟻群算法，會出現在航程允許的情況下，無人機能夠到達某一配送點并返回配送站，但其攜帶的貨物量無法滿足該配送點的全部需求量。因此，需要對算法進行改進，首先節點期望程度的公式進行改進；其次，更改螞蟻經過路徑時信息素的增長方式為以時間為主。應用改進后的蟻群算法對模型進行求解。在此過程中，每條配送路線都需要綜合考慮無人機的最大航程和最大載重，當無人機的剩余航程或剩余載重無法到達下一配送點，以及到達下一配送點后無法返回配送站時，重新選擇除該配送點之外的其他未訪問配送點，若均無法滿足，則直接返回配送站完成該次迭代。

3.2? 計算規則

螞蟻從i節點移動到j節點的概率計算公式為：

其中，（1-ρ）表示信息素的持久性系數；?τij表示本次迭代中節點i到節點j路徑上的信息素增量； 表示第k只螞蟻在本次迭代中在節點i到節點j路徑上留下的信息素量；m為螞蟻總數；Q為正常數，用以控制螞蟻信息素量的積累；Lk為第k只螞蟻在本次迭代中所走的路徑長度。

3.3? 計算步驟

計算思路如圖2所示。

具體步驟描述如下：

1）初始化參數，令時間t=0，給定螞蟻數目m、節點數目n、最大迭代次數iter_max、信息素濃度重要程度因子α、節點間期望程度重要程度因子β、信息素揮發程度ρ（0＜ρ＜1）、螞蟻（無人機）最大飛行時間TIME和最大載重量CAP。

2）初始化節點位置，以及每個節點的貨物需求量，包括需求件數和每件貨物的質量。計算每兩個節點之間的距離，更新距離矩陣D。此后需要根據距離矩陣計算巡航時間。并計算每個節點的貨物需求總質量，更新總需求量數組Demand。

3）螞蟻每到達一個節點，則更新剩余飛行時間Time_res和剩余載重量Demand_res。根據Time_res和Demand_res，判斷每只螞蟻是否能夠前往下一節點，如果能，則計算下一節點的選擇概率，反之，則下一節點的選擇概率為0。直至所有螞蟻完成所有節點的訪問，記完成一次迭代。

4）記錄本次迭代的最佳路線，即飛行時間（巡航時間+起降時間+起降額外時間）最短的路徑。

5）重置禁忌表、剩余飛行時間、剩余載重量和受載重影響的基礎速度。

6）更新信息素濃度。

7）重復迭代步驟2）～6）。

8）達到最大迭代次數iter_max后，比較每一代最佳路徑，并輸出飛行時間最短的一代路徑，作為最終的最佳路徑。具體步驟如圖2所示。

4? 案例分析

4.1? 案例介紹

以湖北省某鄉村為例，對“復雜環境下無人機配送”的實際情況進行分析。本文選取的鄉村共21戶人家有快遞配送需求，鄉村的配送中心配備飛行速度8 m/s，凈載重15 kg，續航時間30 min的無人機k架，分別自配送中心出發，對該21戶人家進行快遞配送服務。由于當地多為丘陵和山地地形，車輛行駛較為不宜，將其作為研究對象具有一定的代表性，可以使得驗證結果更加具有說服力。該21個配送點的需求量如表2所示，根據配送中心及配送點的位置坐標，取所在方形區域的中心為原點，以東為x軸，以北為y軸，建立坐標系如圖3所示。

4.2? 情景設置

本研究以正北方向為極坐標橫軸，順時針方向為正，建立風向坐標系。其中數字1標注為配送中心，其余數字2至22標注為21個配送點應用MATLAB進行算法編程，設置參數值如下：α=1、β=5、γ=2、ρ=0.5，信息素濃度Q=10，螞蟻總數m=50，迭代次數MAXGEN=100。針對風速和風向對無人機配送的影響，本研究簡單模擬兩種情景，分別為：

1）風速6.5 m/s，風向45°。

2）風速6.5 m/s，風向125°。

在無人機飛行過程中，將風沿無人機機體軸系分解為沿無人機飛行方向和垂直于無人機飛行方向，沿無人機飛行方向的速度會對無人機的飛行速度產生直接的影響，垂直與無人機飛行方向的速度會導致無人機偏航，在本研究中暫不考慮。

4.3? 路徑優化結果分析

有風環境下，風速為6.5 m/s，風向為45°，路徑規劃圖與最優路徑迭代示意圖如圖4、圖5所示。其中第一架無人機的路線為配送中心→配送點18→配送點8→配送點19→配送點7→配送點16→配送中心，配送時間為1 689.2 s，配送總路程為9 505.08 m。其與無人機的路徑規劃詳見表3。在該種情況下，四架無人機的飛行路徑總和為45 939.35 m，四架無人機的飛行時間分別為1 542.18、1 728.72、1 482.33、1 621.72 s，均未超過最大續航時間1 800 s。

有風環境下，風速為6.5 m/s，風向為125°，路徑規劃圖與最優路徑迭代示意圖如圖6、圖7所示。其中第一架無人機的路線為配送中心→配送點3→配送點20→配送點5→配送點18→配送點10→配送點15→配送點14→配送中心，配送時間為1 812.95 s，配送總路程為11 178.14 m。其余無人機的飛行路線如表4所示。在該種情況下，四架無人機的飛行路徑總和為43 328.58 m，四架無人機的飛行時間分別為1 688.80、1 744.01、1 674.52、1 463.07 s，均未超過最大續航時間1 800 s。

根據運行的實驗結果我們可以得出，在風速相同的情況下，通過實驗數據分析與無人機路徑規劃對比，風向125°相較于風向45°的情況對無人機的阻礙更小，通俗來說就是風向45°時無人機飛行更逆風，而在這種情況下無人機配送的時間更長，配送總里程更長；因此本研究可以得出結論，逆風情況更不利于無人機的飛行，增加物流配送的時間和配送里程。

4.4? 環境參數對路徑優化的影響分析

為了綜合分析風速與風向交互作用下對無人機運輸路徑的影響，本研究依據目標函數與案例分析的實驗結果數據，設定風速分別為0、2、4、6、8 m/s。由于當風速大于8 m/s時，環境相對惡劣，本研究使用的物流無人機無法執行飛行任務，故沒有考慮。設定風向從0°到360°，每60°為一間隔，并將參數兩兩組合，進行35組實驗，每組實驗算法運行10次并取均值，結果如圖8所示。從圖中可以看出，在風向保持不變時，無人機配送時間整體呈現隨著風速的增大而增大的趨勢；當風向在0～60°范圍，風速大于6 m/s時，使得無人機順風時巡航速度對航時的影響大于逆風時巡航速度對航時的影響，導致配送時間縮短；當風向在60°～360°范圍時，配送時間隨著風速的增大而增大；當風速大于5 m/s時，隨著風向角度的增大，配送時間呈現增大的趨勢。由此可以得出，在本研究使用的無人機的飛行極限條件范圍內，風速越大對無人機飛行的影響越大，配送時間整體呈現增大的趨勢；當風速較小時，風向對于無人機飛行的影響可以忽略不計，只有當風速增加到一定程度時，風向角度變化會對無人機飛行時間產生較大影響。此外，當風速過大風向對無人機的阻礙過強時，無人機為了保證能夠順利返航，會減少自身的載重來完成配送。因此，在該系統中，風速和風向會對無人機配送路徑的選擇造成較大的影響。

5? 結? 論

無人機配送時效性差、秩序混亂是限制其發展的一大難題，且配送的過程中容易受到環境的影響，使得客戶滿意度降低。本文在傳統路徑優化模型的基礎上，以運輸時間最短為目標，包括無人機配送時間、起飛降落時間、卸貨時間，綜合考慮影響配送的風速、風向、載重等因素，構建復雜環境下無人機配送路徑優化模型。針對環境的復雜性，提出影響無人機運行有關的風速、風向的七種假設情景，使用改良的蟻群算法對模型進行求解，并對無人機配送的優化進行規劃；最后通過實例驗證了模型的可行性。研究結果表明在風向相同的情況下，系統整體呈現出風速越大，配送越耗時越長的趨勢，完成配送任務所需的無人機數量增加；在風速相同的情況下，順風無人機配送的時間更短。

參考文獻：

[1] 宋佳艷，蘇圣超.基于改進蟻群優化算法的自動駕駛多車協同運動規劃 [J].計算機工程，2022，48（11）：299-305+313.

[2] 趙宏業.基于改進蟻群算法的醫療人力資源應急優化調度模型設計與仿真 [J].電子設計工程，2022，30（22）：20-24.

[3] 毛壽祺，楊平，高迪駒，等.基于細菌覓食-蟻群算法的無人船路徑規劃 [J].控制工程.

[4] 潘紅麗.基于改進粒子群算法的垃圾清運車輛低碳路徑規劃 [D].南京：南京信息工程大學，2022.

[5] 黃辰.基于智能優化算法的移動機器人路徑規劃與定位方法研究 [D].大連：大連交通大學，2018.

[6] CARABAZA S P，BESADA-PORTAS E，LOPEZ-OROZCO J A，et al. Ant Colony Optimization for Multi-UAV Minimum Time Search in Uncertain Domains [J].Applied Soft Computing，2017，62：789-806.

[7] 胡丹，黃輝，潘夢莎.改進精英蟻群算法在未知環境下的移動機器人路徑規劃 [J].工業控制計算機，2022，35（11）：119-122+125.

[8] RIVERA G，CRUZ-REYES L，FERNANDEZ E，et al. An ACO-based Hyper-heuristic for Sequencing Many-objective Evolutionary Algorithms that Consider Different Ways to Incorporate the DM's Preferences [J/OL].Swarm and Evolutionary Computation，2023，76：[2023-02-17].https：//doi.org/10.1016/j.swevo.2022.101211.

[9] NIE H B，WANG F C，ZHAO Y. Efficiency Analysis on the Path Optimization of Ant Colony Algorithm Based on Neural Network Optimization [J].Journal of Residuals Science & Technology，2016，13（6）：25-30.

[10] DORIGO A，BIRATTARI M，STUTZLE T. Ant colony optimization [J].IEEE Computational Intelligence Magazine，2006，1（4）：28-39.

作者簡介：張蓓蓓（2002—），女，漢族，湖北十堰人，本科在讀，研究方向：無人駕駛航空器系統工程。