劉艷秋，段聰

(1.沈陽(yáng)工業(yè)大學(xué) 管理學(xué)院，遼寧 沈陽(yáng)，110870；2.沈陽(yáng)工業(yè)大學(xué) 理學(xué)院，遼寧 沈陽(yáng)，110870)

隨著科學(xué)技術(shù)的不斷發(fā)展，無(wú)人機(jī)在各個(gè)領(lǐng)域的廣泛應(yīng)用為它在物流領(lǐng)域的發(fā)展提供了新的突破口。對(duì)比于傳統(tǒng)卡車(chē)運(yùn)輸，無(wú)人機(jī)不受地面交通的影響，可以有效提升配送效率。且無(wú)人機(jī)配送存在小批量、高頻次等特點(diǎn)，也更適合物流末端的配送[1]。但由于無(wú)人機(jī)飛行受到載重以及飛行耐力的約束[2-3]，因此,可將裝載無(wú)人機(jī)的卡車(chē)(下文均以卡車(chē)代替)作為無(wú)人機(jī)的發(fā)射與回收節(jié)點(diǎn)，二者聯(lián)合進(jìn)行配送可以有效規(guī)避卡車(chē)配送路徑受限以及無(wú)人機(jī)飛行受載重以及飛行耐力的約束，使之能夠進(jìn)行高效的配送。

國(guó)內(nèi)外學(xué)者對(duì)卡車(chē)與無(wú)人機(jī)聯(lián)合配送下的車(chē)輛路徑問(wèn)題(vehicle routing problem with drone，VRP-D)展開(kāi)了廣泛研究。MURRAY等[4]最先提出了一輛卡車(chē)搭載一架無(wú)人機(jī)合作分發(fā)包裹的問(wèn)題(FSTSP)，并設(shè)計(jì)了混合整數(shù)線性規(guī)劃公式，設(shè)計(jì)了兩種啟發(fā)式算法對(duì)小規(guī)模實(shí)例進(jìn)行求解。AGATZ等[5]在此基礎(chǔ)上構(gòu)建了帶有無(wú)人機(jī)的旅行售貨員問(wèn)題(travelling salesman problem，TSP-D)的整數(shù)線性規(guī)劃模型，并將所提出的啟發(fā)式算法應(yīng)用于不同規(guī)模大小的實(shí)例中。HA等[6]提出了關(guān)于TSP-D的一個(gè)新的問(wèn)題——最小成本TSP-D，設(shè)計(jì)了兩種啟發(fā)式算法并進(jìn)行了對(duì)比實(shí)驗(yàn)。LI等[7]研究了帶有時(shí)間窗和移動(dòng)衛(wèi)星的兩級(jí)車(chē)輛路徑問(wèn)題，以綜合成本最小化為目標(biāo)，研究了多車(chē)輛與無(wú)人機(jī)的問(wèn)題，運(yùn)用自適應(yīng)大規(guī)模鄰域搜索算法分別對(duì)小規(guī)模和大規(guī)模算例進(jìn)行求解。

綜上可知：相關(guān)路徑文獻(xiàn)為了簡(jiǎn)化問(wèn)題，在構(gòu)建模型方面考慮的要素比較單一，導(dǎo)致忽略了一些現(xiàn)實(shí)的因素。將無(wú)人機(jī)與卡車(chē)聯(lián)合配送模式應(yīng)用于取送貨問(wèn)題的文獻(xiàn)暫沒(méi)有，而在真實(shí)的物流網(wǎng)絡(luò)中，考慮在送貨過(guò)程中完成取貨任務(wù)，比傳統(tǒng)不考慮取貨過(guò)程的問(wèn)題更具有實(shí)用性。且在車(chē)輛路徑優(yōu)化問(wèn)題中，考慮正向物流和逆向物流的整合成為企業(yè)提升效率和降低成本的重要途徑[8]。鑒于這種情況，在基于運(yùn)籌學(xué)和智能優(yōu)化算法的基礎(chǔ)上，建立了考慮客戶(hù)的取送貨需求混合整數(shù)規(guī)劃模型，并設(shè)計(jì)嵌入遺傳算法的鄰域搜索算法對(duì)模型進(jìn)行求解。在規(guī)劃如何將客戶(hù)的取貨需求與送貨需求有效地分配給無(wú)人機(jī)與卡車(chē)的同時(shí)，進(jìn)行車(chē)輛路徑優(yōu)化。最后，將模型與算法應(yīng)用于算例進(jìn)行分析驗(yàn)證，為相關(guān)企業(yè)提供理論依據(jù)及解決思路。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述與模型分析

某地區(qū)有已知取送貨需求的n個(gè)客戶(hù)點(diǎn)，采用卡車(chē)攜帶小型無(wú)人機(jī)聯(lián)合配送的方式從配送中心O(也作O')出發(fā)為客戶(hù)進(jìn)行配送，配送模式見(jiàn)圖1，在完成所有客戶(hù)服務(wù)后返回倉(cāng)庫(kù)O'，使得總配送時(shí)間最短。由于某些客戶(hù)需求無(wú)法由無(wú)人機(jī)完成(例如超過(guò)無(wú)人機(jī)有效載重的包裹，客戶(hù)位置超過(guò)無(wú)人機(jī)飛行最大距離的包裹等)。因此，這樣的客戶(hù)僅能由卡車(chē)進(jìn)行服務(wù)，其余客戶(hù)均能由無(wú)人機(jī)安排配送。

圖1所示為該配送模式的路徑示意圖，以往研究中，卡車(chē)與無(wú)人機(jī)均需承擔(dān)配送任務(wù)，卡車(chē)在某一客戶(hù)點(diǎn)處發(fā)射無(wú)人機(jī)后停止其配送服務(wù)，在該處等待無(wú)人機(jī)并進(jìn)行回收。但在實(shí)際生活中，存在卡車(chē)無(wú)法長(zhǎng)時(shí)間停車(chē)和交通堵塞情況，必須盡快前往下一個(gè)客戶(hù)點(diǎn)，不能在發(fā)射地點(diǎn)等待無(wú)人機(jī)返回。因此，建立模型時(shí)考慮在無(wú)人機(jī)的服務(wù)過(guò)程中，使卡車(chē)?yán)^續(xù)進(jìn)行配送任務(wù)，并在其后續(xù)節(jié)點(diǎn)將無(wú)人機(jī)進(jìn)行回收。

圖1 配送模式Fig.1 The distribution mode

為便于該問(wèn)題中模型的建立及不失問(wèn)題的一般性，對(duì)模型做出如下假設(shè)：1)無(wú)人機(jī)單次發(fā)射只服務(wù)一個(gè)客戶(hù)；2)客戶(hù)節(jié)點(diǎn)需求不可分割；3)無(wú)人機(jī)僅能從客戶(hù)點(diǎn)所在位置處或配送中心位置處發(fā)射，且必須在沿途的后續(xù)客戶(hù)點(diǎn)或配送中心處匯合；4)當(dāng)無(wú)人機(jī)和卡車(chē)在某一客戶(hù)點(diǎn)匯合時(shí)，較早到達(dá)的一個(gè)等待另一個(gè)[9]；5)不考慮其他影響最大飛行速度的因素，且無(wú)人機(jī)都以最大飛行速度進(jìn)行配送。

1.2 參數(shù)定義

定義決策變量如下：xijv表示卡車(chē)v從節(jié)點(diǎn)i行駛到j(luò)的二元變量;yijku表示無(wú)人機(jī)u從節(jié)點(diǎn)i處發(fā)射，在結(jié)束節(jié)點(diǎn)j處服務(wù)后返回到節(jié)點(diǎn)k的二元變量;zuv表示無(wú)人機(jī)u在卡車(chē)v所配送路徑上的二元變量。

1.3 模型構(gòu)建

卡車(chē)與無(wú)人機(jī)聯(lián)合配送的車(chē)輛路徑優(yōu)化模型是使總配送時(shí)間最短為目標(biāo)函數(shù)以及多個(gè)約束條件組成。在確定目標(biāo)時(shí)考慮無(wú)人機(jī)與卡車(chē)的速度及其各自的服務(wù)時(shí)間，各個(gè)節(jié)點(diǎn)處車(chē)輛與無(wú)人機(jī)的載重等因素，實(shí)現(xiàn)真正可行的目標(biāo)解。其目標(biāo)函數(shù)公式如下所示:

mintO'

約束條件為

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

ti+η≤li，?i∈Ctruck

(17)

(18)

(19)

(20)

xijv∈{0,1},?i∈Nleave,j∈Narrive,u∈U

(21)

yijkv∈{0,1},?i∈Nleave,j∈CUAV,k∈Narrive,v∈V

(22)

zuv∈{0,1}，?u∈U,v∈V

(23)

目標(biāo)函數(shù)表示在滿(mǎn)足卡車(chē)與無(wú)人機(jī)需求和容量限制的同時(shí)，通過(guò)使用最少數(shù)量的車(chē)輛來(lái)求解最短完成時(shí)間。約束(1)～(6)表示卡車(chē)與無(wú)人機(jī)聯(lián)合配送的基本約束?？蛻?hù)攬貨和送貨的情況如約束(7)和(8)所示，約束中考慮在卡車(chē)路徑上存在無(wú)人機(jī)服務(wù)點(diǎn)的情況。約束(9)～(11)表示卡車(chē)與無(wú)人機(jī)的最大載重約束。約束(12)表示無(wú)人機(jī)的最大飛行距離約束。約束(13)～(20)表示在配送過(guò)程中卡車(chē)與無(wú)人機(jī)的時(shí)間連續(xù)性約束。約束(21)～(23)表示決策變量的取值范圍。

2 模型求解

卡車(chē)-無(wú)人機(jī)聯(lián)合配送問(wèn)題屬于一類(lèi)NP-hard的VRP變體問(wèn)題，因此，提出嵌入遺傳算法的鄰域搜索算法來(lái)求解該問(wèn)題。

2.1 客戶(hù)分類(lèi)

由于卡車(chē)與無(wú)人機(jī)容量限制有所不同，且無(wú)人機(jī)的飛行距離更是限制了無(wú)人機(jī)所能服務(wù)的客戶(hù)集合。因此，將客戶(hù)分成兩類(lèi)：1)選取所有客戶(hù)中需求量滿(mǎn)足無(wú)人機(jī)最大載重的客戶(hù)，再以最短路徑法計(jì)算其與卡車(chē)客戶(hù)之間所產(chǎn)生的最短飛行距離以及次最短距離，若二者距離之和不大于無(wú)人機(jī)的最大飛行距離，使該客戶(hù)加入到無(wú)人機(jī)客戶(hù)集；2)其余客戶(hù)加入到卡車(chē)客戶(hù)集。

2.2 路徑規(guī)劃

為解決卡車(chē)與無(wú)人機(jī)聯(lián)合配送的路徑規(guī)劃問(wèn)題，提出一種結(jié)合遺傳算法的鄰域搜索算法。在形成初始路徑的情況下，采用無(wú)人機(jī)回收端鄰域搜索的操作進(jìn)行路徑優(yōu)化。

首先，針對(duì)所有卡車(chē)客戶(hù)，形成一個(gè)帶有取送貨的車(chē)輛路徑問(wèn)題[10]，采用遺傳算法生成初始路徑[11]。在卡車(chē)初始路徑形成后，將無(wú)人機(jī)客戶(hù)插入到卡車(chē)路徑中形成一個(gè)完整的初始解。以搜索卡車(chē)路徑上距離無(wú)人機(jī)客戶(hù)最近的節(jié)點(diǎn)作為無(wú)人機(jī)的發(fā)射節(jié)點(diǎn)，該條卡車(chē)子路徑上的下一個(gè)節(jié)點(diǎn)作為無(wú)人機(jī)回收節(jié)點(diǎn)。

其次，進(jìn)行無(wú)人機(jī)的回收鄰域搜索。根據(jù)所建立模型特點(diǎn)，無(wú)人機(jī)既可由同一卡車(chē)進(jìn)行回收，也可由不同路徑上的卡車(chē)進(jìn)行回收。因此，針對(duì)無(wú)人機(jī)的回收客戶(hù)點(diǎn)，從該次無(wú)人機(jī)的起飛節(jié)點(diǎn)到其所在卡車(chē)路徑上的最后一個(gè)客戶(hù)點(diǎn)中隨機(jī)選取一客戶(hù)點(diǎn)作為該次無(wú)人機(jī)任務(wù)的回收節(jié)點(diǎn)進(jìn)行鄰域搜索。上述鄰域搜索無(wú)法保證新解均為可行解，所以給出以下非可行解的調(diào)整策略：1)如果當(dāng)前卡車(chē)路徑的所有位置均不可行，則將回收節(jié)點(diǎn)隨機(jī)插入其他卡車(chē)路徑中；2)如果針對(duì)該無(wú)人機(jī)所有卡車(chē)路徑均無(wú)法回收該無(wú)人機(jī)，則放棄本次局部搜索操作。

3 算例分析

由于缺乏對(duì)于該問(wèn)題的適用算例，故本節(jié)采用Solomon數(shù)據(jù)集中的RC101數(shù)據(jù)，生成25個(gè)客戶(hù)點(diǎn)的算例1和50個(gè)客戶(hù)點(diǎn)的算例2，將算例中原有的需求列數(shù)據(jù)作為各節(jié)點(diǎn)取貨量需求，采用隨機(jī)生成的方式添加送貨量需求的列數(shù)據(jù)。設(shè)置卡車(chē)和無(wú)人機(jī)速度分別為58和80 km/h，卡車(chē)與無(wú)人機(jī)最大載重分別為200和10 kg，無(wú)人機(jī)最遠(yuǎn)工作航程為20 km。由于無(wú)人機(jī)服務(wù)時(shí)相較于卡車(chē)更加便捷，所以將二者的服務(wù)時(shí)間設(shè)置為5和10 min兩部分。通常來(lái)說(shuō)，由于卡車(chē)配送會(huì)受到地面交通道路的管束，為簡(jiǎn)化模型，選取歐式距離的1.2倍來(lái)表示卡車(chē)在兩節(jié)點(diǎn)間的行駛距離，見(jiàn)式(24)。而無(wú)人機(jī)飛行距離并不受地面道路影響，所以采取歐式距離，見(jiàn)式(25)，表示單次無(wú)人機(jī)進(jìn)行服務(wù)全程的距離，包括無(wú)人機(jī)發(fā)射節(jié)點(diǎn)與該次所服務(wù)的無(wú)人機(jī)客戶(hù)節(jié)點(diǎn)的距離以及無(wú)人機(jī)客戶(hù)節(jié)點(diǎn)與無(wú)人機(jī)回收節(jié)點(diǎn)之間的距離。

(24)

(25)

算例使用Matlab R2018b進(jìn)行編程，運(yùn)行環(huán)境為Windows 10操作系統(tǒng)，處理器為Intel(R) Core(TM) i5-7200U CPU @ 2.50 GHz，2.71 GHz。

3.1 僅卡車(chē)配送的配送模式

該模式僅以卡車(chē)作為配送工具，在滿(mǎn)足各個(gè)節(jié)點(diǎn)處卡車(chē)的裝載量不大于最大載量的情況下，從配送中心出發(fā)為客戶(hù)進(jìn)行配送與攬收服務(wù)并最終返回配送中心。使綜合時(shí)間最短為目標(biāo)合理規(guī)劃運(yùn)輸路線，利用遺傳算法求解該問(wèn)題[12]，將算例中各節(jié)點(diǎn)的待攬收量、待配送量以及各客戶(hù)的位置信息代入程序[13]。

實(shí)驗(yàn)結(jié)果見(jiàn)表1，兩個(gè)實(shí)例僅由卡車(chē)配送時(shí)完成所有客戶(hù)服務(wù)總配送時(shí)間為11.490 6和21.206 4 h。最優(yōu)配送方案路線見(jiàn)圖2。

表1 傳統(tǒng)配送模式下最優(yōu)配送方案Table 1 The optimal distribution scheme at traditional distribution mode

圖2 傳統(tǒng)配送模式下最優(yōu)方案路徑圖Fig.2 Path diagrams of the optimal scheme in traditional distribution mode

3.2 卡車(chē)和無(wú)人機(jī)聯(lián)合配送的配送模式

該模式由卡車(chē)攜帶無(wú)人機(jī)從配送中心出發(fā)為客戶(hù)進(jìn)行配送與攬貨服務(wù)并最終返回配送中心。以綜合時(shí)間最短為目標(biāo)合理規(guī)劃運(yùn)輸路線。利用嵌入遺傳算法的鄰域搜索算法求解該問(wèn)題，將算例中需求量以及各客戶(hù)的位置信息代入程序。

運(yùn)用嵌入遺傳算法的鄰域搜索算法對(duì)2個(gè)算例進(jìn)行實(shí)驗(yàn)，最優(yōu)方案見(jiàn)表2，具體數(shù)據(jù)見(jiàn)表3和表4，最優(yōu)配送方案路線見(jiàn)圖3。2個(gè)實(shí)例由卡車(chē)與無(wú)人機(jī)聯(lián)合配送時(shí)完成所有客戶(hù)服務(wù)總配送時(shí)間分別為10.606 4和19.818 8 h，較初始解減少了6.53%和13.91%。

圖3 基于卡車(chē)和無(wú)人機(jī)聯(lián)合配送的最優(yōu)路徑圖Fig.3 The optimal route map based on truck and UAV joint distribution

表2 優(yōu)化前后數(shù)據(jù)對(duì)比Table 2 Comparison of data before and after optimization

綜上所述，卡車(chē)與無(wú)人機(jī)聯(lián)合配送比傳統(tǒng)卡車(chē)配送在算例1中節(jié)省了0.884 2 h，在算例2中節(jié)省了1.387 6 h。由表3可知：算例1中3條路徑最終解的目標(biāo)值與初始解的目標(biāo)函數(shù)值相比均減少0.246 8 h，至少減少了6%；算例2中5條路徑分別減少了0.645 5，0.547 9，0.786 1，0.645 6和0.577 0 h。由表4可知：最終解的目標(biāo)值與初始解的目標(biāo)函數(shù)值相比，均至少減少了10%。

表3 算例1的最優(yōu)方案表Table 3 The optimal scheme table for Examples 1

表4 算例2的最優(yōu)方案表Table 4 The optimal scheme table for Examples 2

實(shí)驗(yàn)結(jié)果表明：1)通過(guò)對(duì)算例的求解，驗(yàn)證了卡車(chē)與無(wú)人機(jī)聯(lián)合配送在配送時(shí)間上優(yōu)于傳統(tǒng)卡車(chē)配送；2)無(wú)人機(jī)回收鄰域搜索可以有效地對(duì)所建立地初始解進(jìn)行改進(jìn)。

4 結(jié)論

卡車(chē)與無(wú)人機(jī)聯(lián)合配送的方法和路徑直接影響到配送的速度、成本以及企業(yè)的收益，為滿(mǎn)足日益增長(zhǎng)的市場(chǎng)需求，提出了嵌入遺傳算法的鄰域搜索算法，并得出如下結(jié)論：

1)考慮卡車(chē)搭載裝有包裹的無(wú)人機(jī)進(jìn)行取送貨的現(xiàn)實(shí)特征，設(shè)計(jì)添加取送貨條件的無(wú)人機(jī)車(chē)輛路徑問(wèn)題，將無(wú)人機(jī)物流運(yùn)用到正向物流與逆向物流的整合問(wèn)題中，使無(wú)人機(jī)在物流問(wèn)題中的應(yīng)用得到進(jìn)一步完善。

2)嵌入遺傳算法的鄰域搜索算法可有效優(yōu)化物流中無(wú)人機(jī)的配送路徑，能夠?qū)⑽镔Y有效分配給卡車(chē)與無(wú)人機(jī)，并求得最優(yōu)解。車(chē)輛路徑優(yōu)化增添了新的解決方式。

除考慮以配送時(shí)間最短為目標(biāo)外，還有許多現(xiàn)實(shí)因素可作為模型來(lái)考慮優(yōu)化目標(biāo)，如客戶(hù)滿(mǎn)意度的優(yōu)化、減少運(yùn)輸工具的能源消耗等。