無人機在應急物流配送中的任務分配模型構建

（陸軍勤務學院，重慶 401331）

1 研究背景

信息基礎設施建設的空前部署以及大數據、物聯網、人工智能和云計算等新興技術的不斷進步和深化應用，給無人機帶來了廣闊的應用前景。在技術方面，機載能源技術和基于數字電視（PID）等技術的飛行控制系統是無人機的核心技術，是無人機不可缺少的組成部分［1］；遙感技術、數據鏈技術、避障技術是無人機關鍵技術，三者相輔相成；基于全球定位系統（GPS）、地理信息系統（GIS）、熱成像、多光譜成像、激光雷達等遙感技術可實現對自身的導航定位和對外界的多角度感知［2］；基于數字數據鏈（DDL）、戰術通用數據鏈（TCDL）、Quint 網絡技術（QNT）數據鏈等數據鏈技術，承擔著無人機與終端之間信息上傳和下達的任務［3］，避障技術則在前兩者基礎上完成指定避障動作；為滿足無人機在偵察、監視、打擊、通信、保障、指揮控制等多功能應用，無人機也可以應用載荷技術、區塊鏈、人工智能等拓展技術。

在應用方面，農業領域，無人機開展作物長勢監測、作物產量估測、作物病蟲害監測和作物田間管理，以及通過施藥、澆水等方式實現植物保護［4-5］；測繪領域，無人機通過大比例尺航測、傾斜攝影三維建模等技術，對復雜場景進行大范圍、高重疊度、高精度、高分辨率航攝，生成實景三維模型等數據成果［6］；通信領域，無人機通過物理層網絡編碼技術和自適應調制技術，增強通信系統的兼容性并實現多中繼通信，并通過與測繪應用相結合，應對重大突發公共事件應急測繪保障能力得以增強，無人機應急測繪保障和低空攝影測量領域的應用范圍得以拓寬［7-8］；軍事領域，無人機涉及機動、情報、火力、防護、保障和指揮及控制領域，是提升情報、監視和偵察(ISR)能力和加快包以德循環（OODA 循環）的組成部分，可大幅提高作戰效能，新技術新理念將傳統偵察無人機向多任務、高時效、網絡化方向發展［9-11］。相對而言，當前無人機在物流領域的應用較少，只有小范圍試點，但無人機在物流領域有著豐富的應用場景，將成為未來重要發展領域。

2 無人機在物流領域應用的研究綜述

近年來，物流無人機的探索開始廣泛起來。2013 年電商巨頭亞馬遜公司首次宣布實施無人機配送計劃，并于2017 年實現無人機配送包裹。谷歌公司于2014 年開始實施無人機配送項目開發，實現配送無人機直達目的地并自動完成卸貨的功能。我國順豐速運有限公司（以下簡稱“順豐”）從2017 年6 月啟動無人機物流配送試點；2017 年2 月京東集團（以下簡稱“京東”）與陜西省政府達成合作，打造低空無人機通用航空物流網絡［12］。至今，配送無人機的興起還不到10 年，但各種規模的物流企業都或多或少地開始研究配送無人機的應用，上至配送無人機的配送體系和應用模式等宏觀研究，下至配送無人機的設計和算法等具體研究。

宏觀方面，物流無人機配送體系有兩種模式：一種是以京東為代表的“點對多”無人機物流配送模式，擬打造“干線-支線-末端”三級智慧物流航空體系；另一種是以順豐為代表的“點對點”無人機物流配送模式，著重開展支線無人機的研制與應用［13］。在干線戰略層，可采取有人機與無人機混合編隊運輸模式［14］；在支線戰役層和末端戰術層，可采取無人機與貨車相結合的運輸模式，也可以依靠站點模塊、集群模塊、指控模塊和體系支撐模塊的組成模塊，通過“接收指令—調撥對接—規劃路徑—編隊起飛—編隊飛行—目標確認—卸載物資—編隊返回”8 個環節的運轉流程實現無人機獨自配送模式［15］。針對無人機配送體系的特性，要根據配送無人機的使用環境、客戶群體屬性及其在造型、功能、載重能力、續航時間、安全性等因素設計配送無人機總系統，并根據區域內和區域間等不同層次情況設計配送無人機子系統［16-18］。

微觀方面，無人機應用主要研究任務分配和航跡規劃兩大類問題，而任務分配和航跡規劃是相互耦合的，通?？梢怨餐接?。這兩大類問題通常需要通過算法求解，常用的傳統算法有整數線性規劃、模擬退火算法等，如今可以結合現代啟發式、群智能算法進行求解，如遺傳算法、粒子群算法、蟻群算法和魚群算法等。傳統算法中，有采用局部搜索與動態規劃相結合的算法求解有無人機參與的旅行商任務分配模型［19］；有考慮多目標問題，提出應用線性權重法將其轉化為單目標無人機任務規劃問題，再通過與實數編碼的煙花算法相結合的混合算法求解多目標無人機任務分配問題［20］；有提出用Grid-GSA 進行無人機航跡規劃，即應用柵格法構建環境模型，為相應柵格賦予概率，再通過引力搜索算法實現對返航點數量和位置的尋優［21］?，F代算法中，有針對無人機多目標任務分配問題，提出在量子蟻群算法快速搜索的基礎上，融合克隆選擇算法的交叉和克隆復制因子來提高算法的全局搜索能力，避免搜索過程過早陷入收斂問題［22］；有綜合考慮“貨車+無人機”配送模式、多批次揀選、多配送批次、帶時間窗等因素的任務分配模型，通過PVRPTW-D遺傳算法進行求解［23］；有提出用混合種群RRT 無人機航跡規劃方法以解決航跡的最優問題，在基于環境勢場的快速擴展隨機樹（RRT）算法的基礎上，通過引入自優化種群和協同優化種群改善航跡段，使算法同時具有局部和全局尋優能力［24］；有基于協同粒子群算法和協同函數、協同變量相結合的算法以聯合探討任務分配與航跡規劃問題［25］；有為避免異構無人機協同任務分配產生“死鎖”現象，基于多類型基因編碼的改進遺傳算法進行任務分配，并采用Dubins 路徑協調方法生成無人機最小轉彎半徑的可飛航跡［26］。

綜上所述，目前無人機在配送體系方面已經設計出3 層架構，在戰略層使用大型無人機進行遠距離運輸，在戰役層使用中型無人機進行中短程運輸，在戰術層使用小型無人機進行近距離配送，而且在配送體系的每個層級中也探討了相對應的應用流程和實現基礎。比如在戰術層中，小型無人機可以結合貨車進行協同配送，目前較為常見的協同配送方式是貨車配送內部需求點，無人機配送外部需求點，無人機配送完一個需求點后回到貨車取貨進行下一個配送任務。無人機在配送體系、應用流程和選址設計等方面的研究已較為成熟，并總結出無人機在配送中涉及無人機數據鏈系統、無人機飛行控制導航系統、無人機自主控制技術三大關鍵技術，然而，大多數研究只建立了應用無人機的物流配送體系、應用流程和分析其帶來的好處，并沒有與物流其他環節相結合深刻闡述總體上的變革，這將不能解決局部最優而非全局最優的問題。在無人機任務分配的研究中，主要探討基于燃料補給點模式和基于無人機-貨車聯合配送模式兩大類，國內外相關文獻主要成果包括多旅行商問題模型、混合整數線性規劃模型和多種運輸工具配送模型等，其主要目標包括完成配送任務時間最小、配送成本最低或無人機參與數量最少等。無人機在航跡規劃中主要探討的是環境建模和航跡求解，環境建模主要涉及二維空間和三維空間，目前較為流行的技術方法是柵格圖、拓撲圖、Voronoi 圖法等；航跡求解可使用傳統的Dijkstra 算法和基于Dijkstra 改進的A 算法或現代群智能算法，以滿足隱蔽性、安全性和飛行器限制等目標。無人機微觀方面研究包含大量基于傳統算法和現代智能算法的模型，但卻忽略了較為重要的一個影響參數——無人機載重量。

從宏觀和微觀兩方面的分析中可以看出，無人機在物流配送領域的普適性研究已較為完善，然而要想真正發揮無人機在物流領域的優勢，必須結合具體場景進行具體模型設計。以軍事領域為例，遠程戰略投送和支線戰役車輛運輸等方式已廣泛使用，并且能解決中長距離的物資保障問題，但末端“最后一公里”的物資配送能力仍難以滿足物資按時按量到達需求點。在應急物流中，環境復雜、物資保障具有不可預測性，導致物資的變化量遠遠超過其預測量，這進一步增強了末端“最后一公里”的應急保障特性。在2020 年新冠疫情期間，一架直徑1.2 m 的無人機裝載著送檢標本從浙江省新昌縣人民醫院自動飛向縣疾控中心，實現了24 h不間斷、全方位、全天候配送，邁出了無人機在我國醫藥應急物流配送中的第一步。部分物流企業在疫情期間采取無人機進行無接觸應急物流配送，發現配送效率能提升了60%～70%?，F代物流中較為關鍵的是“最后一公里”配送問題，大多數物品往往積壓在離最終用戶很近的配送中心，普通物品由于配送人員、配送工具不足造成的積壓而導致的價值損失可能很小，但急需品一旦沒按時到達，則會造成難以估量的損失。無人機的應用，將能解決目前應急物流配送中所面臨的高時效性、高安全性和高精確性等瓶頸問題。為解決“最后一公里”點多、線長、面廣的應急物流配送問題，采用小型配送無人機（以下簡稱“配送無人機”或“無人機”）將成為未來可行且高效的一種配送方式。

3 無人機在應急物流配送中的應用創新

應急物流采用無人機的配送方式總的來說有三方面優勢：一是能夠跨越各類障礙、快速響應應急需求，實現精確高效保障；二是成本低、應急能力強，能實現不間斷作業；三是約束條件少、適應高難任務，能實現配送過程零傷亡率。為了更好地在“最后一公里”應用配送無人機，就必須在倉庫中配置適當的配送無人機，這將會引發倉庫布局和運作模式等一系列改革。

目前，倉庫的運作模式有4 種（以取貨為例）：叉車取貨、堆垛機系統取貨、穿梭車取貨和AGV 小車自動取貨［27］。從總的來看，可分為兩大類：“貨到人”模式和“人到貨”模式。隨著人工智能等新興技術的發展，未來倉庫的運作模式將趨于“貨到人”模式的半智能出庫，而本研究認為未來倉庫將可結合配送無人機實現完全無人出庫。本研究在穿梭車取貨背景下，采取結合配送無人機進行物資配送的方式，則無人機與穿梭車的停放空間可以搭配設置在貨架上，以增大物資存儲的面積利用率和空間利用率。先根據實際情況設定具體的貨架層數，然后將貨架在空間上分為3 個區域，由下至上依次為物資存儲區、穿梭車與無人機存儲區、預留區，其空間布局見圖1。物資存儲區與一般貨架相似，預留區是為了應對穿梭車數量與無人機數量未來增長的需要，而穿梭車與無人機存儲區是將一臺穿梭車與一架無人機搭配存儲，穿梭車存放在空間底部、無人機懸掛在空間頂部，這樣無人機在進行配送物資裝載時可以直接通過穿梭車進行接洽，這使得存放與出庫在同一空間得到實現。出庫時，穿梭車將物資從物資存儲區的儲位運到穿梭車與無人機存儲區的所屬儲位中，通過模塊化設計好的接口直接與無人機接洽，然后搭載著無人機到達無人機起飛場所，無人機起飛進行配送作業后，穿梭車返回進行下一任務或在儲位等待接收無人機返回入庫。這種新方式的使用，將可以實現分揀、出庫的全自動化，即不需要人參與任何分揀、出庫作業。

圖1 完全無人出庫模式下的倉庫空間布局

倉庫改革完成后，配送無人機的存儲、裝載物資和起飛等環節將可實現無縫對接，在宏觀方面能更好地滿足應急物流配送的高效性。接下來就要從微觀方面進行具體探討。無人機配送應急物資，一般是通過無人機直接將物資從后勤供應點運往單個前線需求點，即配送無人機的保障目標是單個前線需求點。雖然此方式保障個別需求點的速度較快，但配送任務完成最遲的需求點卻耗時太久，導致整個前線地區部隊的整體聯合效益降低。傳統無人機任務分配也有對總時間進行優化的模型，但卻沒有考慮載重量會影響無人機最大飛行速度。所以，本研究將基于載重量參數，使用兩種算法對照地去優化配送無人機的任務分配，以使得整個前線區域的最遲配送完成總時間最短。

目前國內小型配送無人機最典型的是多旋翼無人機，其中最常用的是四旋翼和六旋翼無人機。四旋翼無人機的巡航速度為36 m/h，飛行速度范圍在30 km/h～54 km/h，最大起飛重量16 kg，有效載荷10 kg，留空時間2 h，可在海拔4 000 m的高度上作業。六旋翼無人機的巡航速度為30 m/h，飛行速度范圍在30 km/h～43km/h，最大起飛重量24 kg，有效載荷24 kg，留空時間2 h，可在海拔6 000 m 的高度上作業［28］。根據文獻所述，小型無人機載重與最大飛行速度近似呈線性關系，故可將飛行范圍中的最大值作為空載時的最大飛行速度，將飛行范圍中的最小值作為滿載時的最大飛行速度［29］。為得到配送無人機飛行速度V 與其載重量Z 的關系，本研究綜合考慮多種無人機在常見環境下的飛行數據，最終采用空載時60 km/h 的飛行速度和滿載（10 kg）時40 km/h 的飛行速度這兩組數據，可得：

4 配送無人機應急任務分配建模

本研究針對部隊較為需求的物資——彈藥，進行配送無人機應急任務分配建模。從1 個供應點出發，出動N 架配送無人機對M個需求點實施彈藥配送，每架配送無人機在保障一個需求點后，可根據具體情況分析是否在已完成配送任務的需求點j 出發，繼續保障其他需求點。每個需求點的位置和彈藥需求情況已知，每個需求點最多受兩架無人機保障，每架無人機最多前往兩個需求點。雖然配送無人機前往兩個需求點的任務分配會導致某些需求點配送時間延長，但能縮短整個聯合區域的最遲保障總時間。下面就對總時間這個目標進行討論優化。

4.1 模型假設

（1）每架無人機從后勤供給點出發,沿著某一條飛行路線把所裝載的所有物資配送給前線需求點。由于每個飛行路徑只考慮一架配送無人機，故不考慮編隊設計。

（2）每架無人機的載重量是有限制的，所運載的物資補給總重量不能超過該范圍。為了簡化問題,假設所有配送無人機型號相同，擁有相同的載重能力。同時不考慮物資種類對飛行的影響。

（3）不考慮配送無人機在各個目標部隊位置處的轉向角約束，也不考慮航跡規劃。

（4）不考慮其他影響最大飛行速度的因素，且配送無人機都以最大飛行速度進行配送。

4.2 符號說明

（1） 集合。M為配送無人機集合，且M={1,2,…,i,…,n}；N為需求點集合，且N={1,2,…,k,…,n}；W為配送無人機出發點集合，包括后勤供應點和中轉需求點，且W={1,2,…,j,…,n}，當j=1 時為后勤供應點，當j>1 時為中轉需求點。

（2）參數。dijk為第i架配送無人機從第j個配送無人機出發點到第k個需求點的距離；tmax為配送無人機的最長飛行時間；aijk為第i架配送無人機從第j個配送無人機出發點到第k個需求點的載重量(zi)；amax為配送無人機的最大載重量；zk為第k個需求點的物資需求重量；為第i架配送無人機載重從第j個配送無人機出發點到第k個需求點的最大飛行速度。

（3）決策變量。xijk為0 至1 變量，當第i架配送無人機從第j個配送無人機出發點到第k個需求點時等于1，否則等于0。

4.3 數學模型

式（2）為問題的目標函數，求整個前線區域完成任務的總時間最短。式（3）為求每個路徑的飛行時間。約束（4）是保證每個需求點最多可通過兩種路徑保障物資需求。約束（5）是保證每個配送無人機最多到達兩個需求點即完成任務。約束（6）是保證每個配送無人機的續航能力能完成配送任務。約束（7）是保證每個需求點的物資需求量剛好被滿足。約束（8）是確保決策變量xijk為0 至1 變量。約束（9）是保證每架配送無人機的載重量不超過其載重上限。

4.4 模型求解算法

排序算法的基本思路是：配送任務完成最快的配送無人機保障最慢的需求點，次快的配送無人機保障次慢的需求點。依此類推，得到縮減的最遲配送任務完成時間。

貪婪算法的基本思路是：從問題的初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。根據貪婪算法的思路，先求需求點N的配送任務完成時間最多能縮減多少，即通過定下一個載重量變化值，不斷從保障需求點2 到N-1 中的配送無人機拿出一架進行載重量迭代。因為載重量有上限且每架無人機保障的需求點物資需求量不一樣，故每架無人機的迭代次數是不一樣的；每次迭代得到的結果不僅要考慮原先路徑的配送時間減少多少，還要考慮新增路徑的配送時間，若新增路徑的配送時間比沒迭代前的原先路徑配送時間還長，則此方案放棄。最終在遍歷所有載重量和所有無人機中轉保障需求點N后，得到需求點N完成配送任務的新時間。將需求點N所耗的新時間與需求點N-1 所耗的時間進行比較：若需求點N 所耗的新時間大于需求點N-1 所耗的時間，則此需求點N所耗的新時間即為整個前線區域新的最遲配送任務完成總時間；若小于需求點N-1 所耗的時間，將需求點N-1 重復需求點N的步驟，但在無人機的迭代中將不能再使用保障需求點N的無人機，即保障需求點N的無人機放入禁忌表。按上述步驟逐一循環，最終得到一個新的最遲配送任務完成總時間，其算法流程如圖2 所示。

圖2 貪婪搜索算法流程

5 算例分析

5.1 算例構建

下面以我方一個后勤供應點派出10 架配送無人機對10 個前線需求點進行物資配送任務為背景，先設計一組相同載重量變化值的實驗，以觀察比較兩種算法之間的不同之處；再設計5 組不同載重量變化值的迭代實驗，以觀察不同載重量變化值對完成任務的總時間和配送無人機配送路徑的影響。

采用MATLAB 2017 版本進行算例分析，將所有需求點的彈藥需求重量設置在5 kg～10 kg，并且所有需求點之間在x軸方向的取值范圍不超過10 km，在y 軸方向的取值范圍也不超過10 km，最終確定了所有需求點在橫坐標［30,40］和縱坐標［25,35］范圍內。供應點的位置根據最近距離優先的方式，選在（0，30）的位置上。實驗采取相同的配送無人機，其飛行速度和載重量的關系如前文模型假設。下面根據需求點數量為10 時得到一組初始解時間。為了與接下來算法的結果作對比，將這組初始解時間由快到慢排序，并將供應點編號為1，需求點根據配送任務完成的快慢程度編號為2 到11，具體數據見表1，其網絡拓撲圖如圖3 所示。

表1 算例的初始解

圖3 算例的初始配送網絡

為能更好地分析比較不同結果的好壞程度，我們使用時間縮減率來代替最遲配送任務完成時間進行比較。公式如下：

5.2 兩種算法之間的結果比較

為直觀比較兩種算法的優劣，實驗采取載重量變化值為0.1 時進行比較，兩種算法所得的結果如表2 所示。

表2 算例采用兩種算法得到的完成任務所需時間比較單位：h

采用排序算法得到的無人機任務分配將使整個前線區域的配送任務完成總時間減少至0.925 742 510 h，時間縮減率只達到1.6%；而采用貪婪搜索算法得到的無人機任務分配不僅使初始解中配送任務完成的最遲時間降至比第二遲時間還低，還將原先第二遲時間進一步縮減，使得整個前線區域的配送任務完成總時間減少至0.859 388 154 h，時間縮減率達到約8.7%，其網絡拓撲圖如圖4 所示。

圖4 算例基于貪婪搜索算法的配送網絡

5.3 載重變化量不同對貪婪算法結果的影響

實驗采取5 組載重量變化值，分別為0.1、0.3、0.4、0.5、0.7，基于貪婪搜索算法所得的結果見表3。載重量變化值為0.4 時，時間縮減率為8.7%。載重量變化值為0.5 時，無人機3 增加了載重量卻仍與載重量變化值為0.1 時的時間相同，故這種方式使得整個前線區域的配送任務完成總時間仍減少至0.859 388 154 h，時間縮減率仍為8.7%。載重量變化值為0.3 時，這種方式使得整個前線區域的配送任務完成總時間減少至0.863 088 966 h，時間縮減率為8.2%。載重量變化值為0.7 時，所有無人機任務分配中只有無人機3 需要多載2.1 kg 物資在保障需求點4 后前往需求點11，雖然導致原先配送任務完成的最遲時間降到了和載重量變化值為0.3時一樣的0.863 088 966 h，但由于原先第二遲時間0.873 048 308 h 大于調整后的最遲時間，并且其需求點沒有其他無人機進行二次保障，所以這種方式使得整個前線區域的配送任務完成總時間減少至0.873 048 308 h，時間縮減率為7.2%。

表3 算例基于貪婪搜索算法得到的不同載重下完成任務所需時間 單位：h

觀察發現，載重量變化值為0.3 和0.7 時，需求點11 完成配送任務的時間都縮減至0.863 088 966 h，可得到需求量變化值為2.1 的時候是保障需求點11的一個次優解；載重量變化值為0.1、0.4 和0.5 時，3 組數據得出的時間縮減率一樣，可得到這一次隨機分配的10 個需求點中，載重量變化值為2 的時候即可得到一個次優解；當載重量變化值再進一步往小于0.1 的方向減少時，可能會產生更優的結果。

6 結論

目前，無人機在物流領域的應用只停留在理論和小范圍試點階段，但已有研究表明無人機在物流領域有著豐富的應用場景和發展前景，而且針對物流領域較為關鍵的配送環節，應急物流配送存在的諸多瓶頸問題難以較好地改善，而無人機的精確保障、快速反應、不間斷作業和零傷亡率等特性有利于突破應急物流配送中所面臨的高精確性、高時效性、高安全性等瓶頸問題［30-31］。本研究以物資配送為基礎，提出依靠無人機進行應急物流配送，先設想了應用配送無人機引發的倉庫空間布局和運作模式的改革，然后建立了配送無人機的任務分配模型，在考慮載重量會影響最大飛行速度的基礎上，應用貪婪搜索算法推導出配送無人機進行雙目標應急配送的較優解，與原來供應點用配送無人機只保障一個需求點目標相比，總時間縮減率可達7%～8%，對未來實際應用配送無人機進行各種物資應急物流配送具有一定的參考價值；最后在進行結果分析時，將載重量變化值設置不同大小，發現并非設置越小越好，而是要根據空間內具體的配送網絡設置相應的載重量變化值。

隨著配送無人機的機體技術發展，其續航能力和載重量將可滿足多目標中轉需求，接下來可進一步研究基于載重量參數的配送無人機多目標中轉任務分配。隨著配送無人機信息技術的發展，其應用場景不僅僅局限于常規的應急物流，還可運用于某些特殊場景，例如海島場景，由于海島分散且需求量不大，用運輸船配送物資需要經過多次中轉和裝卸，導致配送成本較高而且費時較長，甚至導致出現“錯漏串”等問題，而使用無人機進行海島物資配送能有效降低物流成本和提高配送的齊套能力，且結合本研究探討的無人機任務分配模型還可以進一步提高配送效率。在偏遠地區場景中，由于終端用戶離物流中心距離較遠且基礎建設較差，物流配送成本高于收益，所以許多偏遠地區用戶的物品需要幾周的配送時間甚至沒有快遞服務，而無人機的點對點配送能有效解決應急物流在偏遠地區的瓶頸問題，將分配和派送等多個環節簡化為“一鍵”實施，實現跨越式精準保障。