無人機(jī)與物流柜協(xié)同配送最短路徑問題啟發(fā)式算法

朱外明，梁培培，劉根節(jié)，趙亞娟

(安慶師范大學(xué) 經(jīng)濟(jì)與管理學(xué)院，安徽 安慶 246133)

0 引言

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

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

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

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

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

1 問題描述與數(shù)學(xué)模型

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

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

雖然時間也是任務(wù)規(guī)劃的經(jīng)典優(yōu)化目標(biāo)之一，但是卻不在本文的考慮范圍之內(nèi)。一方面，因為在本文考慮的配送場景中，能量消耗所形成的成本遠(yuǎn)遠(yuǎn)高于因時間延誤所形成的成本；另一方面，因為無人機(jī)飛行速度較快，且均沿直線飛行，大部分配送包裹均能在指定的時間內(nèi)運輸?shù)侥康牡亍?/p>

1.1 優(yōu)化目標(biāo)

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

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

(1)

(2)

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

(3)

1.2 約束條件

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

(4)

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

(5)

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

vk=∑u∈Uxu·fk,u。

(6)

(7)

(8)

(9)

(10)

(11)

式(7)表示從虛擬的?？啃袨?開始，式(8)表示到最終的?？啃袨関k+1結(jié)束，式(9)表示每個實際的?？績H有一個緊前和緊后?？啃袨椋?10)表示每個實際的?？啃袨楸仨毐贿x中一次，式(11)表示物流柜上一次只能服務(wù)一個?？啃袨椤?/p>

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

2 啟發(fā)式算法

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

f(rj,s)>0，

(12)

f(kj,s)

(13)

則j為在當(dāng)前系統(tǒng)狀態(tài)下可執(zhí)行任務(wù)，使用T(s)表示在狀態(tài)s下所有可執(zhí)行任務(wù)的集合。

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

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

(14)

則環(huán)C為系統(tǒng)狀態(tài)s下的可執(zhí)行環(huán)。

而且當(dāng)環(huán)中的任務(wù)被執(zhí)行完以后，環(huán)中每個站點?？繜o人機(jī)的數(shù)量與執(zhí)行之前是相等的。因為在執(zhí)行任務(wù)后，環(huán)中每個站點飛入無人機(jī)的次數(shù)與飛出無人機(jī)的次數(shù)相等。因此，執(zhí)行任務(wù)環(huán)的前后除了任務(wù)數(shù)減少以外，系統(tǒng)狀態(tài)不發(fā)生改變，即性質(zhì)2。這為設(shè)計啟發(fā)式算法提供了思路。

性質(zhì)2：設(shè)C(s)為系統(tǒng)狀態(tài)s下的可執(zhí)行環(huán)，s′為執(zhí)行C(s)全部任務(wù)后的系統(tǒng)狀態(tài)，則有：s′=s。

優(yōu)化目標(biāo)為最小化無人機(jī)飛行的總距離，因此，應(yīng)當(dāng)盡可能少地使用輔助任務(wù)。由于執(zhí)行任務(wù)環(huán)前后系統(tǒng)狀態(tài)不變，而使得待執(zhí)行任務(wù)減少，因此，應(yīng)當(dāng)盡可能多地先執(zhí)行環(huán)。而當(dāng)系統(tǒng)中找不到可執(zhí)行環(huán)時，應(yīng)當(dāng)盡可能地安排可執(zhí)行任務(wù)。而一旦某個任務(wù)被執(zhí)行后，系統(tǒng)狀態(tài)又發(fā)生改變，此時可以再次嘗試搜索可執(zhí)行環(huán)。重復(fù)上述操作，直到找不到可執(zhí)行任務(wù)時停止。

當(dāng)存在未安排的任務(wù)且基于當(dāng)前系統(tǒng)狀態(tài)無法搜索到可執(zhí)行任務(wù)時，需要通過添加輔助任務(wù)調(diào)動無人機(jī)以改變系統(tǒng)狀態(tài)，使得某個任務(wù)得以執(zhí)行。而一旦該操作執(zhí)行以后，系統(tǒng)的狀態(tài)又會發(fā)生改變，因此又可以搜索可執(zhí)行環(huán)或可執(zhí)行任務(wù)。按照該思路設(shè)計啟發(fā)式算法，能夠使得全部任務(wù)得以規(guī)劃，具體算法如下。

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

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

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

3 仿真實驗

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

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

(15)

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

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

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

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

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

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

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

4 結(jié)束語

本文研究了使用無人機(jī)與物流柜協(xié)同執(zhí)行物流配送任務(wù)的最短路徑問題，即制定無人機(jī)的飛行計劃，使得無人機(jī)以最短的總飛行距離完成全部的配送任務(wù)。該問題是一個路徑規(guī)劃與機(jī)器調(diào)度深度耦合的復(fù)雜優(yōu)化問題。本文深入地分析了問題特征，找到了評估解質(zhì)量的下界；發(fā)現(xiàn)了任務(wù)環(huán)這一特殊的任務(wù)結(jié)構(gòu)，以及機(jī)柜系統(tǒng)執(zhí)行任務(wù)環(huán)的前后系統(tǒng)狀態(tài)不變的性質(zhì)?；谶@些發(fā)現(xiàn)，設(shè)計了高效的啟發(fā)式求解算法?；谡鎸嵉某鞘械乩砦恢?、距離數(shù)據(jù)和無人機(jī)數(shù)據(jù)，進(jìn)行了仿真實驗。模擬了實時配送、快餐配送和樣本送檢3種不同的配送場景，生成了對應(yīng)的數(shù)據(jù)集。求解結(jié)果表明，所設(shè)計的算法均能在短時間內(nèi)求得問題高質(zhì)量的解。

DLDP-TDM的優(yōu)化目標(biāo)為最小化無人機(jī)飛行的總距離，該問題沒有考慮時間效率的影響。今后將研究DLDP-TDM的擴(kuò)展問題。例如，在部分場景中，任務(wù)具有嚴(yán)格的時間窗口限制，即必須在指定的時間內(nèi)執(zhí)行任務(wù)，帶時間窗約束的規(guī)劃問題更難求解。此外，在飛行總距離相同的情況下，不同的任務(wù)執(zhí)行順序?qū)?yīng)不同的完成時間，如何制定規(guī)劃使得無人機(jī)在盡可能短的時間內(nèi)完成全部配送任務(wù)，對于提高協(xié)同配送系統(tǒng)的利用率具有一定的意義。