無人機與物流柜協同配送最短路徑問題啟發式算法

朱外明，梁培培，劉根節，趙亞娟

(安慶師范大學 經濟與管理學院，安徽 安慶 246133)

0 引言

隨著5G通信等相關技術的快速發展，無人機被越來越多地應用到物流領域[1]。使用無人機配送包裹具有快速、安全、24 h可用、環境友好、不占用道路交通資源和解放人力等優勢。目前，谷歌、UPS、DHL、亞馬遜、京東、順豐和中國郵政等國內外一些物流企業在物流無人機領域持續多年投入研究，并積累了大量的無人機配送實踐經驗。在該領域，一種使用無人機與物流柜協同配送包裹的方式具有較高的實用價值和廣闊的應用前景。目前，已有若干企業成功地將該模式應用到城市的快餐、血漿和核酸樣本等運輸場景中，取得了一定的成效。

在該模式中，物流柜的柜頂部設有自動化裝卸包裹的裝置，并作為無人機的起降平臺，無人機在物流柜頂部自動完成包裹的裝載，飛行到指定的物流柜頂部后自動完成包裹的卸載。由于該過程需要較少的人力干預，因此自動化程度較高，適用于“非接觸”式的配送場景。由于一個物流柜的頂部一次只能供一架無人機停靠，即無人機對物流柜具有獨占性，因此固定數量的物流柜成為多架無人機“競爭的稀缺資源”，這也導致在該模式下，無人機的任務規劃問題具有一定的難度。

無人機攜帶貨物從發出地飛往接收地，其有序訪問的多個物流柜之間的路線連起來構成路徑[2-3]，可行的規劃方案包含每架無人機的飛行路徑。無人機需要在物流柜上裝卸貨物和更換電池，且無人機對物流柜具有獨占性[4-5]，即一個物流柜一次只能服務一架無人機，可行的規劃方案包含無人機在物流柜上的停靠方案。由于無人機飛行需要消耗電能，如何制定出綜合的路徑與停靠方案，讓無人機完成全部任務的配送，使得飛行的總路徑最短？這就是本文研究的無人機與物流柜協同配送最短路徑規劃問題(Drone and Locker Cooperative Delivery Problem with Total Distance Minimization，DLDP-TDM)。

由于DLDP-TDM是一個路徑規劃與機器調度深度耦合的問題，其建模與求解具有一定的難度。與該問題相關的經典運籌問題包括車輛路徑[6-7]、機器調度[4-5]、無人機任務規劃[8-9]和岸橋調度[10]等，而這些都只與DLDP-TDM的部分特征相似。生產運輸規劃問題[11-12]與DLDP-TDM的相關程度較高，但是二者也存在本質的區別，即生產運輸規劃是機器調度與路徑規劃的集成問題，而DLDP-TDM是二者的耦合問題。此外，近年來，基于車機協同[13-14]的規劃問題也成為熱點，主要包括帶無人機的旅行商問題(Traveling Salesman Problem with Drone，TSP-D)[15-19]和帶無人機的車輛路徑問題(Vehicle Routing Problem with Drones，VRP-D)[20-21]，例如，經典的“Horsefly Routing”[14]“Flying Sidekick”[15]等。在這些問題中，無人機與載機平臺(例如卡車)[22]是一一對應的，無人機不在載機平臺間切換飛行，因此與DLDP-TDM問題并不相同。目前，未發現國內外有關于DLDP-TDM問題的研究工作。

本文深入分析了DLDP-TDM問題的特征，找到了最優解的一個下界，定義了任務子集可執行的條件，介紹了任務環在執行前后系統狀態保存不變的性質，設計了求解規劃問題高效的啟發式算法。選取了中國9座城市，從中選取著名的商業中心等地，使用真實企業的無人機數據，進行了仿真驗證。模擬3種不同的無人機配送場景，生成了3組共81個仿真算例，計算結果表明，提出的啟發式算法具有優效性。

1 問題描述與數學模型

設指定區域內有物流柜與無人機協同配送系統，系統的硬件由分布在m個指定站點的物流柜和停靠在物流柜上的無人機組成，第i個站點處設有bi個物流柜，bi也可記作b(i)，每個物流柜k∈K頂部最多只能停靠一架無人機，無人機的總數不超過物流柜的總數|K|，使用D表示無人機的集合。無人機d∈D可以在物流柜上自動裝載包裹，飛行至另一物流柜的頂部，并完成包裹的自動卸載。無人機每次最多只能攜帶一個包裹。無人機每次飛行完成后，需要在物流柜的頂部更換電池，假設這一過程也是自動化的。

對于給定的協同配送系統，配送任務(以下簡稱任務)集J由多個待配送的包裹組成，配送任務j∈J對應一個源站點rj和目的站點kj，站點rj到kj的距離記為dj，每個包裹均需要由無人機進行配送。包裹在源站點的物流柜是固定的，可以運輸到目的站點的任一物流柜。無人機的飛行需要消耗電能，且所消耗的電能與無人機飛行的距離是相關的，本文假設無人機飛行時載貨與否不影響能量的消耗，且無人機的能量消耗與飛行距離成正比例關系。因此希望無人機能夠使用最短的飛行距離完成全部的配送任務。

雖然時間也是任務規劃的經典優化目標之一，但是卻不在本文的考慮范圍之內。一方面，因為在本文考慮的配送場景中，能量消耗所形成的成本遠遠高于因時間延誤所形成的成本；另一方面，因為無人機飛行速度較快，且均沿直線飛行，大部分配送包裹均能在指定的時間內運輸到目的地。

1.1 優化目標

無人機完成全部配送任務的總距離是規劃問題的優化目標，該目標函數由哪幾部分組成呢？因為無人機一次最多只能攜帶一個包裹，所以無人機的飛行主要包含2種類型：空載飛行和載物飛行。由于所有的包裹均需配送，因此每個包裹從源站點到目的站點之間的飛行距離必須全部計入目標函數。因此，可以輕松得到規劃問題最優解的下界，即性質1。

另一方面，由于無人機必須停靠在物流柜上，給定數量的物流柜成為無人機競爭的資源，因此必須添加一定數量的空載飛行才能確保規劃方案的可行性。定義無人機的空載飛行為輔助任務。任意2個站點之間均可能形成輔助任務，設e=i→i′為從站點i到i′的飛行航線，E={e|?i≠i′,i≤m,i′≤m}為任意2個站點間飛行航線的集合，de為航線e的距離，xe∈Z+∪{0}為需要添加的飛行航線e的次數，則優化目標為：

(1)

(2)

將每架無人機飛行經過的物流柜連起來，能夠構成一條連貫的路徑，因此總體規劃包含路徑規劃子問題。在路徑規劃問題中，經典的數學模型是基于路徑的集合分區模型。使用u表示無人機的一條路徑，無人機d的所有可行的路徑集合記為Ud，全部無人機路徑的集合為U={Ud|d∈D}。給定路徑u，其包含的輔助任務是固定的，使用參數pe,u∈Z+∪{0}表示在路徑u的輔助任務中航線e的飛行次數。使用0～1決策變量xu表示是否選擇路徑u，式(2)可寫為：

(3)

1.2 約束條件

從無人機的視角來看，由于每個無人機只能從各自的路徑集合中選擇一條路徑作為執行方案，因此建立式(4)：

(4)

給定路徑u，其是否執行了任務j是已知的，使用參數gj,u∈{0,1}表示任務j是否在路徑u中得到執行。由于每個任務只需要執行一次，因此建立式(5)：

(5)

從物流柜的視角來看，每個物流柜一次僅供一架無人機停靠，類比于機器上一次只加工一個工件，無人機在物流柜上的停靠行為類比于待加工的工件，因此總體規劃包含機器調度子問題。給定路徑u，其飛行經過的物流柜是已知的，使用fk,u∈Z+∪{0}表示路徑u在物流柜k上的停靠次數，則物流柜k上的停靠行為總數可用決策變量表示為：

vk=∑u∈Uxu·fk,u。

(6)

(7)

(8)

(9)

(10)

(11)

式(7)表示從虛擬的停靠行為0開始，式(8)表示到最終的停靠行為vk+1結束，式(9)表示每個實際的停靠僅有一個緊前和緊后停靠行為，式(10)表示每個實際的停靠行為必須被選中一次，式(11)表示物流柜上一次只能服務一個停靠行為。

式(3)～式(5)和式(7)～式(11)為DLDP-TDM的數學模型。由于vk是依賴于決策變量xu的，因此，式(7)～式(11)也依賴于決策變量xu。上述模型是一個兩階段優化模型，求取問題的精確解具有一定的難度。本文深入分析規劃方案內部的結構特征，提出了一種構造啟發式算法，能夠求得問題高質量的可行解。

2 啟發式算法

定義協同配送系統狀態為各站點上無人機的停靠數量，記為s，它會隨著無人機位置的變化而變化，即每次無人機完成一次飛行后，系統狀態可能會發生改變。使用f(i,s)表示在狀態s下站點i上停靠的無人機數量。在給定系統狀態下，有些任務可以直接執行而不需要添加輔助任務。對于任務j，如果當前系統狀態滿足：

f(rj,s)>0，

(12)

f(kj,s)

(13)

則j為在當前系統狀態下可執行任務，使用T(s)表示在狀態s下所有可執行任務的集合。

需要特別說明的是，在判斷j是否可直接執行時，只需檢查其源站點是否有無人機停靠即可，而無需檢查存放包裹的物流柜上是否停靠有無人機。這是因為即使存放包裹的物流柜上沒有停靠無人機，但同站點其他物流柜上有無人機時，也可以使用其他物流柜上的無人機執行運輸任務。無人機在同站點的物流柜之間切換飛行時消耗的能量可以忽略不計。

由若干任務首尾相連可以形成任務環，如果任務環中有至少一個站點停靠有無人機，則整個任務環可以直接執行而不需要添加輔助任務。可以從2個特例說明：① 如果任務環中只有一個站點停靠有唯一的無人機，則可以由該無人機依次運輸包裹，直至完成全部任務，并返回初始站點；② 如果任務環中每個站點的每個物流柜上均停靠有無人機，則每個站點可以同時起飛一架無人機運輸包裹，即實時運輸。使用C表示任務環，I(C)為環C中的站點集合，則基于上述2個特例可以分析得到，如果任務環C滿足：

(14)

則環C為系統狀態s下的可執行環。

而且當環中的任務被執行完以后，環中每個站點停靠無人機的數量與執行之前是相等的。因為在執行任務后，環中每個站點飛入無人機的次數與飛出無人機的次數相等。因此，執行任務環的前后除了任務數減少以外，系統狀態不發生改變，即性質2。這為設計啟發式算法提供了思路。

性質2：設C(s)為系統狀態s下的可執行環，s′為執行C(s)全部任務后的系統狀態，則有：s′=s。

優化目標為最小化無人機飛行的總距離，因此，應當盡可能少地使用輔助任務。由于執行任務環前后系統狀態不變，而使得待執行任務減少，因此，應當盡可能多地先執行環。而當系統中找不到可執行環時，應當盡可能地安排可執行任務。而一旦某個任務被執行后，系統狀態又發生改變，此時可以再次嘗試搜索可執行環。重復上述操作，直到找不到可執行任務時停止。

當存在未安排的任務且基于當前系統狀態無法搜索到可執行任務時，需要通過添加輔助任務調動無人機以改變系統狀態，使得某個任務得以執行。而一旦該操作執行以后，系統的狀態又會發生改變，因此又可以搜索可執行環或可執行任務。按照該思路設計啟發式算法，能夠使得全部任務得以規劃，具體算法如下。

算 法:啟發式算法輸 入:系統狀態s,待配送任務集J,空規劃方案Q輸 出:更新的規劃方案Q步驟1:如果J≠?,轉步驟2,否則轉步驟8;步驟2:如果存在環C滿足式(14),轉步驟3,否則轉步驟4;步驟3:執行環C,令Q=Q∪C ,令J=JC,轉步驟1;步驟4:如果存在T(S)?J使得?j∈T(S)為可執行任務,轉步驟5,否則轉步驟6;步驟5:選擇j∈T(S)執行,令Q=Q,j ,令J=Jj,更新系統狀態s,轉步驟1;步驟6:如果存在l∈J,使得添加輔助任務集合O后l可執行,轉步驟7,否則轉步驟1;步驟7:添加輔助任務集合O,執行O和l,令Q=Q∪O,j ,令J=Jj,轉步驟1;步驟8:J=?,算法執行結束,輸出Q。

算法中，判斷系統中是否存在任務環可使用樹搜索的方法。具體而言，從系統的某個站點開始，沿著以該站點作為源站點的任務搜索到下一個站點，不斷重復上述搜索，如果某一站點在此過程中被遍歷2次，則一定存在任務環。使用該方法不僅可以判斷任務環的存在，還能夠找出對應的任務環。需要說明的是，每次僅需要搜索到一個任務環即可，而無需一次性地搜索出全部的任務環。這是因為搜索出的任務環如果是可行的且被執行后會從任務集合中刪除，因此可以使得后續的搜索規模不斷地減小。

添加輔助任務總體可以分為3種情況：① 源站點沒有無人機，目的站點有空閑的物流柜，需要從其他站點調來無人機執行任務；② 源站點有無人機，目的站點沒有空閑的物流柜，需要調走目的站點的無人機以創造空閑的物流柜；③ 源站點沒有無人機，目的站點也沒有空閑物流柜，既需要調來無人機執行任務又需要創造出空閑的物流柜。為使總目標盡可能地小，應當盡量地使所添加的輔助任務的距離盡可能的短。因此，為每個需要添加輔助任務的實際任務尋找最短的輔助任務，然后從全部待添加的實際任務中選擇一個輔助任務距離最短的進行執行。

3 仿真實驗

為驗證啟發式算法的優效性，進行了仿真計算實驗。選取我國9座城市，并從9座城市中選擇了著名的小區、醫院和餐館/商業中心等，基于第三方地圖軟件開放平臺獲取經緯度和直線距離數據。每個站點物流柜的數量在[1,4]之間隨機生成。設置數量分別為20，50，80共3種不同的任務規模，每個城市、每個任務規模下隨機生成任務數據，共生成27個算例(S01～S27)。使用某一線企業真實投入使用的無人機數據，航速和最大續航里程分別為60 km/h和25 km。使用Java編程實現算法程序，基于CPU為i5-8265、內存為8 GB、操作系統為Windows10 Home Basic的計算機完成仿真計算。求解的統計結果如表1所示。

從表1中可以看到，在每個算例中，站點個數比較均勻地分布在25～40之間，而無人機的數量少于等于對應的站點數量。無人機飛行的總距離即為目標函數值，它是配送任務總距離與輔助任務總距離之和。其中，輔助任務距離占比等于輔助任務總距離與配送任務總距離的比值。根據性質1可知，后者為最優目標函數值的下界，定義輔助任務距離占比為：

(15)

從表1中可以看出，最小值為6%，最大值為24%。從最后一列可以看出，啟發式算法求解全部算例的計算機運行時間均在1 s以內，說明了所設計的啟發式算法高效。

表1 基于均勻分布隨機生成仿真算例計算求解統計結果Tab.1 Statistical results for solving the simulated instances generated following a uniform distribution

上述算例集(記為SET-1)中，配送任務是均勻隨機生成的。在某些應用場景中，配送任務的數據具有一些新的特征，因此在上述選取站點數據的基礎上，模擬了另外2種場景，生成了另外2組新的配送任務數據集。第2個數據集(SET-2)模擬餐館送餐場景，配送任務由少量的餐館運送至數量較多的小區；第3個數據集模擬血清或核酸樣本送檢場景，配送任務由數量較多的小區運輸至數量較少的醫院。求解后，記錄算法求解每個算例的計算運行時間，結果顯示，所有算例均能在1 s以內求得可行解。另外，記錄每個算例解的輔助任務距離占比，并按照任務數量分組，繪制出統計圖，如圖1所示。

(a) 任務數20時各城市對應3種場景的輔助任務距離占比

(b) 任務數50時各城市對應3種場景的輔助任務距離占比

(c) 任務數80時各城市對應3種場景的輔助任務距離占比圖1 不同任務規模對應3種配送場景求解結果的輔助任務距離占比曲線Fig.1 The plot of the distance ratios between auxiliary and delivery tasks for three distribution scenarios with different task scales

從圖1可以看到，所有算例的輔助任務距離占比均介于[0,1]，說明所添加的輔助任務的總距離均小于配送任務的總距離。在3種任務規模下，數據集SET-1對應的曲線明顯低于SET-2和SET-3，這說明對于第2和第3個數據集模擬的配送場景，需要添加更多(更長)的輔助任務。這一點不難分析，因為后2個場景中，配送任務的運輸方向不是“平衡”的，需要更多的調動無人機改變系統狀態，以使得后續的配送任務得以執行。SET-2和SET-3對應的曲線高度比較接近，這說明，這2種配送場景雖然不同卻具有某些相似的特征。另外，隨著任務數的增加，SET-1對應的曲線與SET-2，SET-3的曲線之間的距離呈現增大的趨勢，這是因為SET-1的配送任務始終較為“平衡”，而SET-2和SET-3的配送任務的不“平衡”特征隨著任務數的增加而益發明顯。

4 結束語

本文研究了使用無人機與物流柜協同執行物流配送任務的最短路徑問題，即制定無人機的飛行計劃，使得無人機以最短的總飛行距離完成全部的配送任務。該問題是一個路徑規劃與機器調度深度耦合的復雜優化問題。本文深入地分析了問題特征，找到了評估解質量的下界；發現了任務環這一特殊的任務結構，以及機柜系統執行任務環的前后系統狀態不變的性質。基于這些發現，設計了高效的啟發式求解算法。基于真實的城市地理位置、距離數據和無人機數據，進行了仿真實驗。模擬了實時配送、快餐配送和樣本送檢3種不同的配送場景，生成了對應的數據集。求解結果表明，所設計的算法均能在短時間內求得問題高質量的解。

DLDP-TDM的優化目標為最小化無人機飛行的總距離，該問題沒有考慮時間效率的影響。今后將研究DLDP-TDM的擴展問題。例如，在部分場景中，任務具有嚴格的時間窗口限制，即必須在指定的時間內執行任務，帶時間窗約束的規劃問題更難求解。此外，在飛行總距離相同的情況下，不同的任務執行順序對應不同的完成時間，如何制定規劃使得無人機在盡可能短的時間內完成全部配送任務，對于提高協同配送系統的利用率具有一定的意義。