朱外明，梁培培，劉根節(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)勢(shì)。目前，谷歌、UPS、DHL、亞馬遜、京東、順豐和中國(guó)郵政等國(guó)內(nèi)外一些物流企業(yè)在物流無人機(jī)領(lǐng)域持續(xù)多年投入研究，并積累了大量的無人機(jī)配送實(shí)踐經(jīng)驗(yàn)。在該領(lǐng)域，一種使用無人機(jī)與物流柜協(xié)同配送包裹的方式具有較高的實(shí)用價(jià)值和廣闊的應(yīng)用前景。目前，已有若干企業(yè)成功地將該模式應(yīng)用到城市的快餐、血漿和核酸樣本等運(yùn)輸場(chǎng)景中，取得了一定的成效。

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

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

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

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

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

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

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

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

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

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

另一方面，由于無人機(jī)必須?？吭谖锪鞴裆?，給定數(shù)量的物流柜成為無人機(jī)競(jìng)爭(zhēng)的資源，因此必須添加一定數(shù)量的空載飛行才能確保規(guī)劃方案的可行性。定義無人機(jī)的空載飛行為輔助任務(wù)。任意2個(gè)站點(diǎn)之間均可能形成輔助任務(wù)，設(shè)e=i→i′為從站點(diǎn)i到i′的飛行航線，E={e|?i≠i′,i≤m,i′≤m}為任意2個(gè)站點(diǎn)間飛行航線的集合，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ī)的視角來看，由于每個(gè)無人機(jī)只能從各自的路徑集合中選擇一條路徑作為執(zhí)行方案，因此建立式(4)：

(4)

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

(5)

從物流柜的視角來看，每個(gè)物流柜一次僅供一架無人機(jī)?？?，類比于機(jī)器上一次只加工一個(gè)工件，無人機(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)表示每個(gè)實(shí)際的?？?jī)H有一個(gè)緊前和緊后停靠行為，式(10)表示每個(gè)實(shí)際的停靠行為必須被選中一次，式(11)表示物流柜上一次只能服務(wù)一個(gè)?？啃袨椤?/p>

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

2 啟發(fā)式算法

定義協(xié)同配送系統(tǒng)狀態(tài)為各站點(diǎn)上無人機(jī)的?？繑?shù)量，記為s，它會(huì)隨著無人機(jī)位置的變化而變化，即每次無人機(jī)完成一次飛行后，系統(tǒng)狀態(tài)可能會(huì)發(fā)生改變。使用f(i,s)表示在狀態(tài)s下站點(diǎn)i上?？康臒o人機(jī)數(shù)量。在給定系統(tǒng)狀態(tài)下，有些任務(wù)可以直接執(zhí)行而不需要添加輔助任務(wù)。對(duì)于任務(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í)行時(shí)，只需檢查其源站點(diǎn)是否有無人機(jī)?？考纯桑鵁o需檢查存放包裹的物流柜上是否?？坑袩o人機(jī)。這是因?yàn)榧词勾娣虐奈锪鞴裆蠜]有?？繜o人機(jī)，但同站點(diǎn)其他物流柜上有無人機(jī)時(shí)，也可以使用其他物流柜上的無人機(jī)執(zhí)行運(yùn)輸任務(wù)。無人機(jī)在同站點(diǎn)的物流柜之間切換飛行時(shí)消耗的能量可以忽略不計(jì)。

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

(14)

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

而且當(dāng)環(huán)中的任務(wù)被執(zhí)行完以后，環(huán)中每個(gè)站點(diǎn)停靠無人機(jī)的數(shù)量與執(zhí)行之前是相等的。因?yàn)樵趫?zhí)行任務(wù)后，環(huán)中每個(gè)站點(diǎn)飛入無人機(jī)的次數(shù)與飛出無人機(jī)的次數(shù)相等。因此，執(zhí)行任務(wù)環(huán)的前后除了任務(wù)數(shù)減少以外，系統(tǒng)狀態(tài)不發(fā)生改變，即性質(zhì)2。這為設(shè)計(jì)啟發(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)時(shí)，應(yīng)當(dāng)盡可能地安排可執(zhí)行任務(wù)。而一旦某個(gè)任務(wù)被執(zhí)行后，系統(tǒng)狀態(tài)又發(fā)生改變，此時(shí)可以再次嘗試搜索可執(zhí)行環(huán)。重復(fù)上述操作，直到找不到可執(zhí)行任務(wù)時(shí)停止。

當(dāng)存在未安排的任務(wù)且基于當(dāng)前系統(tǒng)狀態(tài)無法搜索到可執(zhí)行任務(wù)時(shí)，需要通過添加輔助任務(wù)調(diào)動(dòng)無人機(jī)以改變系統(tǒng)狀態(tài)，使得某個(gè)任務(wù)得以執(zhí)行。而一旦該操作執(zhí)行以后，系統(tǒng)的狀態(tài)又會(huì)發(fā)生改變，因此又可以搜索可執(zhí)行環(huán)或可執(zhí)行任務(wù)。按照該思路設(shè)計(jì)啟發(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)的某個(gè)站點(diǎn)開始，沿著以該站點(diǎn)作為源站點(diǎn)的任務(wù)搜索到下一個(gè)站點(diǎn)，不斷重復(fù)上述搜索，如果某一站點(diǎn)在此過程中被遍歷2次，則一定存在任務(wù)環(huán)。使用該方法不僅可以判斷任務(wù)環(huán)的存在，還能夠找出對(duì)應(yīng)的任務(wù)環(huán)。需要說明的是，每次僅需要搜索到一個(gè)任務(wù)環(huán)即可，而無需一次性地搜索出全部的任務(wù)環(huán)。這是因?yàn)樗阉鞒龅娜蝿?wù)環(huán)如果是可行的且被執(zhí)行后會(huì)從任務(wù)集合中刪除，因此可以使得后續(xù)的搜索規(guī)模不斷地減小。

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

3 仿真實(shí)驗(yàn)

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

從表1中可以看到，在每個(gè)算例中，站點(diǎn)個(gè)數(shù)比較均勻地分布在25～40之間，而無人機(jī)的數(shù)量少于等于對(duì)應(yīng)的站點(diǎn)數(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ì)算機(jī)運(yùn)行時(shí)間均在1 s以內(nèi)，說明了所設(shè)計(jì)的啟發(fā)式算法高效。

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

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

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

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

(c) 任務(wù)數(shù)80時(shí)各城市對(duì)應(yīng)3種場(chǎng)景的輔助任務(wù)距離占比圖1 不同任務(wù)規(guī)模對(duì)應(yīng)3種配送場(chǎng)景求解結(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對(duì)應(yīng)的曲線明顯低于SET-2和SET-3，這說明對(duì)于第2和第3個(gè)數(shù)據(jù)集模擬的配送場(chǎng)景，需要添加更多(更長(zhǎng))的輔助任務(wù)。這一點(diǎn)不難分析，因?yàn)楹?個(gè)場(chǎng)景中，配送任務(wù)的運(yùn)輸方向不是“平衡”的，需要更多的調(diào)動(dòng)無人機(jī)改變系統(tǒng)狀態(tài)，以使得后續(xù)的配送任務(wù)得以執(zhí)行。SET-2和SET-3對(duì)應(yīng)的曲線高度比較接近，這說明，這2種配送場(chǎng)景雖然不同卻具有某些相似的特征。另外，隨著任務(wù)數(shù)的增加，SET-1對(duì)應(yīng)的曲線與SET-2，SET-3的曲線之間的距離呈現(xiàn)增大的趨勢(shì)，這是因?yàn)镾ET-1的配送任務(wù)始終較為“平衡”，而SET-2和SET-3的配送任務(wù)的不“平衡”特征隨著任務(wù)數(shù)的增加而益發(fā)明顯。

4 結(jié)束語

本文研究了使用無人機(jī)與物流柜協(xié)同執(zhí)行物流配送任務(wù)的最短路徑問題，即制定無人機(jī)的飛行計(jì)劃，使得無人機(jī)以最短的總飛行距離完成全部的配送任務(wù)。該問題是一個(gè)路徑規(guī)劃與機(jī)器調(diào)度深度耦合的復(fù)雜優(yōu)化問題。本文深入地分析了問題特征，找到了評(píng)估解質(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è)計(jì)了高效的啟發(fā)式求解算法?；谡鎸?shí)的城市地理位置、距離數(shù)據(jù)和無人機(jī)數(shù)據(jù)，進(jìn)行了仿真實(shí)驗(yàn)。模擬了實(shí)時(shí)配送、快餐配送和樣本送檢3種不同的配送場(chǎng)景，生成了對(duì)應(yīng)的數(shù)據(jù)集。求解結(jié)果表明，所設(shè)計(jì)的算法均能在短時(shí)間內(nèi)求得問題高質(zhì)量的解。

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