余海燕，茍夢(mèng)圓，吳騰宇

1.重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074

2.重慶口岸物流與航運(yùn)發(fā)展研究中心，重慶 400074

3.智能物流網(wǎng)絡(luò)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400074

4.重慶郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院，重慶 400065

疫情的高傳播性使部分地區(qū)加強(qiáng)了道路管控措施，物資配送嚴(yán)重受阻，對(duì)于醫(yī)藥等應(yīng)急物資如何高效、準(zhǔn)確、安全地配送已是當(dāng)務(wù)之急。其間無(wú)人機(jī)在“最后一公里”藥物配送中獲得亮眼表現(xiàn)，可見(jiàn)無(wú)人機(jī)在應(yīng)急物資配送中的適用性。但是，無(wú)人機(jī)存在飛行半徑有限等短板，將其與車輛進(jìn)行組合配送更適應(yīng)現(xiàn)實(shí)場(chǎng)景。除此之外，在現(xiàn)實(shí)應(yīng)急配送場(chǎng)景中，決策者往往必須在對(duì)未來(lái)一無(wú)所知或部分信息未知的情形下進(jìn)行對(duì)全局有影響的決策。因此，需求產(chǎn)生的突發(fā)性、高度不可預(yù)見(jiàn)性及不確定性是應(yīng)急物資配送難以組織實(shí)施的重要原因之一。然而，當(dāng)前無(wú)人機(jī)與車輛并行配送領(lǐng)域中對(duì)需求不確定性研究較少，將此類動(dòng)態(tài)因素引入車輛無(wú)人機(jī)并行配送問(wèn)題，是該問(wèn)題可行且有價(jià)值的發(fā)展方向。

考慮需求實(shí)時(shí)不確定性產(chǎn)生情形下的車輛無(wú)人機(jī)并行配送問(wèn)題可以用車輛無(wú)人機(jī)并行在線配送問(wèn)題描述。與一般車輛無(wú)人機(jī)并行配送問(wèn)題相比，應(yīng)急配送需求序貫出現(xiàn)，服務(wù)器只能實(shí)時(shí)獲知其相關(guān)信息，因此具有在線性。與一般車輛在線配送問(wèn)題相比，無(wú)人機(jī)配送范圍有限、一單一送，且需考慮無(wú)人機(jī)與車輛之間協(xié)調(diào)問(wèn)題。因此，提出車輛無(wú)人機(jī)并行在線配送問(wèn)題。

對(duì)于車輛無(wú)人機(jī)并行配送問(wèn)題，Chung 等[1]將目前該問(wèn)題所涉及算法進(jìn)行了歸納，發(fā)現(xiàn)多以車輛為主無(wú)人機(jī)為輔構(gòu)建配送網(wǎng)絡(luò)，并設(shè)計(jì)相應(yīng)的離線算法。Murry和Chu[2]將車輛無(wú)人機(jī)并行配送問(wèn)題定義為PDSTSP（parallel drone scheduling traveling salesman problem）問(wèn)題，并設(shè)計(jì)了車輛優(yōu)先配送需求的啟發(fā)式算法。Dell’Amico 等[3]以總時(shí)間最小化為目標(biāo)，提出了以分支定界算法為主的迭代啟發(fā)式算法。Nguyen 等[4]研究了以最小化總運(yùn)營(yíng)成本為目標(biāo)的車輛無(wú)人機(jī)并行配送路徑優(yōu)化問(wèn)題。Saleu等[5]采用迭代兩步啟發(fā)式算法求解，通過(guò)雙準(zhǔn)則最短路徑問(wèn)題解碼及動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)。總體而言，此問(wèn)題相關(guān)研究大多建立在所有信息已知的情形下，與現(xiàn)實(shí)場(chǎng)景中應(yīng)急需求信息未知不符。除此之外，研究大多構(gòu)建以車輛為主的配送網(wǎng)絡(luò)，現(xiàn)實(shí)場(chǎng)景中應(yīng)急需求未知且緊迫，優(yōu)先考慮無(wú)人機(jī)配送能明顯減少單個(gè)需求點(diǎn)的等待配送時(shí)間，因此考慮動(dòng)態(tài)因素并設(shè)計(jì)無(wú)人機(jī)優(yōu)先的在線算法具有現(xiàn)實(shí)意義。

對(duì)于車輛無(wú)人機(jī)并行配送問(wèn)題涉及未知需求方面，任璇等[6]進(jìn)行了文獻(xiàn)歸納總結(jié)。Ulmer 和Thomas[7]研究了需求在一天中任意時(shí)間釋放的“當(dāng)日達(dá)”問(wèn)題，采用了動(dòng)態(tài)規(guī)劃進(jìn)行解決。王新玉和趙志明[8]指出即時(shí)重優(yōu)化也是常見(jiàn)的求解策略，通過(guò)基于最壞情形考慮的競(jìng)爭(zhēng)分析法能有效、可靠度量動(dòng)態(tài)問(wèn)題的求解策略性能，且動(dòng)態(tài)問(wèn)題的解決方案不應(yīng)該是靜態(tài)輸出，而是根據(jù)新到達(dá)的服務(wù)需求與系統(tǒng)當(dāng)前狀態(tài)決定執(zhí)行哪些調(diào)度操作。在線算法正是基于此思想進(jìn)行策略設(shè)計(jì)，在線分析法則是圍繞所設(shè)計(jì)在線策略進(jìn)行系統(tǒng)評(píng)估的方法。設(shè)計(jì)相應(yīng)的在線算法并通過(guò)在線分析法進(jìn)行算法優(yōu)劣性衡量能夠有效解決需求信息未知的現(xiàn)實(shí)問(wèn)題。

在Sleator和Tarjian[9]正式提出在線問(wèn)題及在線分析法后，在線配送問(wèn)題開(kāi)始受到關(guān)注。車輛與無(wú)人機(jī)并行在線算法的研究重點(diǎn)在于需求分配及路徑規(guī)劃，這一方面可通過(guò)在線理論進(jìn)行分析處理。Ausiello等[10]最早使用在線理論分析TSP（traveling salesman problem）問(wèn)題，證明得出一般網(wǎng)絡(luò)上Eventually Replan算法競(jìng)爭(zhēng)比為2。馬衛(wèi)民和王刊良[11]證明局內(nèi)封閉式車輛調(diào)度問(wèn)題車輛數(shù)為1 時(shí)重新計(jì)劃策略的競(jìng)爭(zhēng)比為3.5。戴敏等[12]證明局內(nèi)開(kāi)放式多車輛調(diào)度問(wèn)題重新計(jì)劃策略的競(jìng)爭(zhēng)比為3.5。Jaillet 和Lu[13]研究具有實(shí)時(shí)服務(wù)可選擇性的在線旅行商問(wèn)題，并證明所提出策略在正半軸競(jìng)爭(zhēng)比為2.5。馬軍平等[14]提出具有服務(wù)時(shí)長(zhǎng)和服務(wù)可選擇性的車輛調(diào)度問(wèn)題，并設(shè)計(jì)了相應(yīng)的在線算法。吳騰宇等[15]運(yùn)用在線分析法衡量了非對(duì)稱網(wǎng)絡(luò)下JPⅠ-rd（judge the path increment with release date）等算法的性能。與現(xiàn)有的車輛在線調(diào)度問(wèn)題研究不同，車輛無(wú)人機(jī)并行在線配送問(wèn)題還需考慮無(wú)人機(jī)不同于車輛的特性，如裝載量、速度、服務(wù)范圍等。

綜上所述，將車輛與無(wú)人機(jī)并行配送應(yīng)用于應(yīng)急配送領(lǐng)域是有效且可行的。通過(guò)與現(xiàn)有研究比較可知（見(jiàn)表1），車輛與無(wú)人機(jī)并行配送領(lǐng)域的算法研究有一定基礎(chǔ)，但針對(duì)需求不確定性考慮較少，與現(xiàn)實(shí)場(chǎng)景結(jié)合不夠緊密，設(shè)計(jì)相應(yīng)的在線算法具有現(xiàn)實(shí)意義，且如何設(shè)計(jì)相應(yīng)的在線算法，衡量算法的性能及適用性，目前尚未有相關(guān)的研究。

表1 車輛無(wú)人機(jī)并行配送問(wèn)題研究對(duì)比Table 1 Research comparison of truck-drone parallel delivery problem

基于此，本文研究在需求實(shí)時(shí)產(chǎn)生的情況下，如何分配需求并規(guī)劃路徑使得最長(zhǎng)配送時(shí)間盡可能少的車輛無(wú)人機(jī)并行在線配送問(wèn)題。該問(wèn)題可通過(guò)在線分析法有效解決。首先給出問(wèn)題描述和基本定義，然后通過(guò)競(jìng)爭(zhēng)分析得出所研究的在線問(wèn)題下界及所設(shè)計(jì)在線均衡策略競(jìng)爭(zhēng)比，從而衡量在線均衡策略的性能；通過(guò)建立離線問(wèn)題模型，設(shè)計(jì)離線算法，運(yùn)用MATLAB 將CPLEX 最優(yōu)解與離線算法結(jié)果進(jìn)行比較，為在線均衡算法內(nèi)容作支撐；通過(guò)對(duì)在線均衡算法的仿真分析，驗(yàn)證在線均衡算法的有效性。

1 符號(hào)說(shuō)明及問(wèn)題描述

1.1 符號(hào)說(shuō)明

V：網(wǎng)絡(luò)頂點(diǎn)集合，V={x0,x1,…,xk} ；

E：網(wǎng)絡(luò)邊集合，E={e0,e1,…,ek} ；

d(u,v)：頂點(diǎn)u,v間邊的權(quán)，其中u,v∈V；

G：配送網(wǎng)絡(luò)，G=(V,E)，以配送站作為原點(diǎn)，原點(diǎn)唯一令其為頂點(diǎn)o∈V，網(wǎng)絡(luò)滿足u,v,w∈V,d(u,v)+d(v,w)≥d(w,u)；

ri：兩元數(shù)組，ri=(ti,xi)，代表在ti時(shí)刻于xi處產(chǎn)生需求，其中ti表示服務(wù)請(qǐng)求的發(fā)布時(shí)間，xi表示服務(wù)請(qǐng)求的發(fā)布位置；

R：需求組成的序列集合，R={r1,r2,…,rm} ，其中需求按釋放時(shí)間先后排列；

I：需求序號(hào)集合，I={1 ,2,…,n} ；

J：配送網(wǎng)絡(luò)頂點(diǎn)序號(hào)集合，J={0 ,1,…,n} ，其中0為配送站；

S：無(wú)人機(jī)的最遠(yuǎn)飛行半徑；

k：無(wú)人機(jī)飛行速度，其中k>1；

δ：一個(gè)任意小的正數(shù)；

L*(t,o,R)：在時(shí)刻t由原點(diǎn)o開(kāi)始完成R中的所有服務(wù)需求并回到原點(diǎn)o所花費(fèi)的最短時(shí)間；

Rd：按最優(yōu)調(diào)度L*(t,X,R)分配給無(wú)人機(jī)的需求序列集合；

Rv：按最優(yōu)調(diào)度L*(t,X,R)分配給車輛的需求序列集合；

Rsv：車輛需求序列中待服務(wù)需求集合，Rsv?Rv；

tid：無(wú)人機(jī)配送需求ri所花費(fèi)時(shí)間；

tij：車輛從需求ri位置到需求rj位置所花費(fèi)時(shí)間；

Pv(t)：在t時(shí)刻車輛的位置；

Td：無(wú)人機(jī)配送總時(shí)間；

Tv：車輛配送總時(shí)間；

T：總服務(wù)時(shí)間，其中T=max{Td,Tv} ；

xij：車輛從需求ri到需求rj則等于1，否則等于0；

yi：無(wú)人機(jī)配送第i個(gè)需求則等于1，否則等于0。

1.2 問(wèn)題描述

假設(shè)所有需求ri隨機(jī)分布在網(wǎng)絡(luò)圖G上，且均為同一類型物資，需求量均為1，實(shí)時(shí)產(chǎn)生、序貫而出、不能拒絕。配送站使用無(wú)人機(jī)及車輛并行配送，其中無(wú)人機(jī)與車輛數(shù)目均為1，初始時(shí)刻無(wú)人機(jī)與車輛均處于配送站，服務(wù)過(guò)程中經(jīng)過(guò)需求點(diǎn)即該需求點(diǎn)配送完成，配送完成后需返回配送站。無(wú)人機(jī)運(yùn)載量為1，最遠(yuǎn)飛行半徑為S，以k(k>1) 個(gè)單位速度移動(dòng)；車輛運(yùn)載量為∞，最遠(yuǎn)里程為∞，以為1的單位速度移動(dòng)。由于運(yùn)載量限制，無(wú)人機(jī)需于配送站取貨，而車輛無(wú)需。

對(duì)于d(o,xm)≤S的需求點(diǎn)，可使用無(wú)人機(jī)或車輛進(jìn)行配送；對(duì)于d(o,xm)>S的需求點(diǎn)，只能由車輛進(jìn)行配送。令Td為無(wú)人機(jī)配送總時(shí)間，Tv為車輛配送總時(shí)間?？偡?wù)時(shí)間由無(wú)人機(jī)或車輛最晚返回配送站的時(shí)間決定，求如何安排配送方式及規(guī)劃路線使總服務(wù)時(shí)間最小化。

如圖1所示，在t時(shí)刻同時(shí)新增兩個(gè)需求點(diǎn)，此時(shí)原本由無(wú)人機(jī)配送的需求改為由車輛進(jìn)行配送，由此車輛及無(wú)人機(jī)的路徑改變。

圖1 問(wèn)題描述示意圖Fig.1 Schematic diagram of problem description

對(duì)于該研究問(wèn)題，可用競(jìng)爭(zhēng)分析法衡量所設(shè)計(jì)在線算法的優(yōu)劣性。競(jìng)爭(zhēng)分析是衡量動(dòng)態(tài)問(wèn)題求解策略性能的方法之一，是在線對(duì)手與離線對(duì)手之間的博弈過(guò)程。在這個(gè)博弈過(guò)程中，離線對(duì)手釋放需求序列，其釋放的需求會(huì)盡可能利于離線對(duì)手而不利于在線對(duì)手。從而，離線對(duì)手從0 時(shí)刻便知曉全部需求信息，而在線對(duì)手未知。對(duì)于同樣的輸入序列θ，令在線對(duì)手采用策略β服務(wù)輸入序列θ所得解為Conline(θ)，離線對(duì)手采用最優(yōu)策略服務(wù)輸入序列θ所得解為COPT(θ)。對(duì)于任意的θ，都存在常數(shù)ρ與γ使得Conline(θ)≤ρ×COPT(θ)+γ成立，則策略β的競(jìng)爭(zhēng)比為ρ。若不存在小于競(jìng)爭(zhēng)比ρ的在線策略，稱ρ為該問(wèn)題下界。當(dāng)ρ越趨近于1 時(shí)，策略性能越好。

2 車輛無(wú)人機(jī)并行配送在線問(wèn)題下界

定理1對(duì)于車輛無(wú)人機(jī)并行配送在線問(wèn)題，其下界為1.5。

證明以直線為例，不失一般性。在直線的正半軸上，需求ri的位置xi，即該點(diǎn)到原點(diǎn)的距離；在直線的負(fù)半軸上，需求ri的位置xi取絕對(duì)值，即該點(diǎn)到原點(diǎn)的距離。假設(shè)無(wú)人機(jī)、車輛的服務(wù)序列中存在最遠(yuǎn)需求點(diǎn)(ti,|s|)、(ti,|y|)，車輛最遠(yuǎn)配送需求點(diǎn)與配送站距離大于無(wú)人機(jī)最遠(yuǎn)配送需求點(diǎn)。于-δ時(shí)刻釋放需求r1=(-δ,s)。需求r1在無(wú)人機(jī)與車輛配送范圍內(nèi)，在線對(duì)手可采用無(wú)人機(jī)或車輛進(jìn)行配送。在線對(duì)手于t時(shí)刻開(kāi)始服務(wù)需求r1，下面對(duì)t的取值分情況討論。

情形1當(dāng)ts/k。同理，若y時(shí)刻在線車位于?處，則需求r2=(y,-y)。在線對(duì)手在獲知需求r2后，由于 |y|>|s|，超出無(wú)人機(jī)配送范圍，只能由車輛進(jìn)行配送。對(duì)于離線對(duì)手，若需求r2=(y,y)，無(wú)人機(jī)不參與配送，從0時(shí)刻開(kāi)始車輛沿正半軸運(yùn)動(dòng)。若需求r2=(y,-y)，則0時(shí)刻開(kāi)始車輛沿負(fù)半軸運(yùn)動(dòng)，無(wú)人機(jī)沿正半軸運(yùn)動(dòng)。Conline≥max{3y+?,( 3s)/k-δ} =3y+?;COPT=2y,ρ=Conline/COPT ≥( 3 y+? )/( 2y )≥( 3y )/( 2y)。對(duì)于情形1，ρ≥1.5。

情形2當(dāng)t≥s/k時(shí)，則離線對(duì)手不再釋放新需求。離線對(duì)手從0 時(shí)刻開(kāi)始無(wú)人機(jī)服務(wù)需求r1。此時(shí)COPT=2s/k，Conline≥3s/k-δ；ρ=Conline/COPT≥(3s/k-δ)(2s/k)。

對(duì)于情形2，取δ→0，ρ≥1.5。

因此，直線上策略的競(jìng)爭(zhēng)比下界為1.5。證畢。

定理1表明對(duì)于車輛無(wú)人機(jī)并行配送調(diào)度問(wèn)題，考慮最壞情形下任意的在線策略目標(biāo)值與離線策略最優(yōu)目標(biāo)值的比值下界為1.5。

3 車輛無(wú)人機(jī)并行配送在線策略

3.1 在線均衡策略設(shè)計(jì)

假設(shè)現(xiàn)有一個(gè)明確的離線算法，可根據(jù)當(dāng)前任意輸入得到對(duì)應(yīng)的較優(yōu)解。

在線均衡策略：當(dāng)新需求釋放時(shí)，進(jìn)行即時(shí)重優(yōu)化，按離線算法將此時(shí)已獲知的全部需求重新分配給車輛與無(wú)人機(jī)服務(wù)，形成各自新的服務(wù)序列，其中已服務(wù)需求不再服務(wù)，車輛按當(dāng)前位置規(guī)劃最優(yōu)路徑，并依次服務(wù)待服務(wù)需求。

3.2 在線均衡策略性能分析

根據(jù)1.1 節(jié)中的符號(hào)定義，顯然Rd∪Rv=R,Rd∩Rv=??，F(xiàn)假設(shè)最后一個(gè)服務(wù)請(qǐng)求為rm(tm,xm)。通過(guò)競(jìng)爭(zhēng)分析，考慮需求產(chǎn)生的最壞情形，可證明在相同情形下在線均衡策略所得結(jié)果與離線對(duì)手最優(yōu)結(jié)果之比的上界。

引理1對(duì)于d(o,xm)≤S，即新需求可由車輛或無(wú)人機(jī)進(jìn)行服務(wù)，該不等式成立COPT≥max{L*( 0 ,o,R),tm+d(o,xm)/k}；對(duì)于d(o,xm)>S，即新需求只能由車輛服務(wù)，此時(shí)COPT≥max{L*( 0 ,o,R),tm+d(o,xm)}。

證明 情形1當(dāng)d(o,xm)≤S，即新服務(wù)需求加入無(wú)人機(jī)或車輛需求序列中。

由于在需求尚未釋放前不能對(duì)其進(jìn)行服務(wù)，因此對(duì)于最后一個(gè)服務(wù)請(qǐng)求為rm(tm,xm)，可有COPT(R)≥tm+T(o,xm)，其中T(o,xm)表示返程時(shí)間。當(dāng)由無(wú)人機(jī)進(jìn)行服務(wù)時(shí)，由于無(wú)人機(jī)飛行速度為k，則有T(o,xm)=d(o,xm)/k。當(dāng)由車輛進(jìn)行服務(wù)時(shí)，由于車輛行駛速度為1，那么T(o,xm)=d(o,xm)/1=d(o,xm)。由于存在所有需求僅由無(wú)人機(jī)配送的可能性，因此COPT≥max{L*( 0 ,o,R)，tm+d(o,xm)k} 。

情形2當(dāng)d(o,xm)>S，即新服務(wù)需求加入車輛需求序列中。同理，由于車輛行駛速度為1，存在T(o,xm)=d(o,xm)/1=d(o,xm)。因此，COPT≥max{L*( 0 ,o,R),tm+d(o,xm)}。

綜上，引理1得證。證畢。

引理2當(dāng)新需求rm(tm,xm)釋放時(shí)，可有L*( 0 ,o,R)≥L*(tm,o,Rsv)，0

證明當(dāng)配送需求序列相同且出發(fā)點(diǎn)相同時(shí)，出發(fā)時(shí)間越晚，所獲得的已知信息將會(huì)越多，從而所得到的規(guī)劃路線越優(yōu)。因此，當(dāng)0

由于新需求rm(tm,xm)釋放時(shí)，采用離線算法重新規(guī)劃，tm時(shí)刻車輛新服務(wù)序列Rv與離線算法所得車輛服務(wù)序列相等，Rsv表示車輛需求序列中待服務(wù)需求集，易知Rsv?Rv?R。需求點(diǎn)相同的情況下，所服務(wù)需求數(shù)量越少所花費(fèi)時(shí)間越短，因此L*(tm,o,R)≥L*(tm,o,Rv)≥L*(tm,o,Rvs)。引理2得證。證畢。

引理3在無(wú)新需求釋放情況下，該不等式成立

證明假設(shè)車輛存在待服務(wù)需求，車輛新服務(wù)序列為Rv={rv1,rv2,…,rvn}，其中需求點(diǎn)rvi=(tvi，xiv),tvi

定理2在線均衡策略競(jìng)爭(zhēng)比為2.5。

證明對(duì)于產(chǎn)生的任何一個(gè)新需求，只有由無(wú)人機(jī)配送或車輛配送兩種策略選擇，因此考慮以下兩種情形：

情形1由離線算法，新需求由無(wú)人機(jī)配送。令U={u1,u2,…,un} 為tm時(shí)刻無(wú)人機(jī)n個(gè)待服務(wù)需求各自的配送時(shí)長(zhǎng)，n≥0，有該不等式成立：d(o,xm)/k。

情形1.1假設(shè)車輛不存在待服務(wù)需求，則有Tv≤tm+d(Pv(tm),o) ，即可得該不等式成立：Conline(R)≤易知tm+根據(jù)引理1，可得COPT≥tm+d(o,xm)/k。此時(shí)假設(shè)W={w1,w2,…,wn} 為離線對(duì)手無(wú)人機(jī)服務(wù)序列各需求配送時(shí)長(zhǎng)。由于采用離線算法，對(duì)于相同的輸入序列與算法，離線對(duì)手與在線對(duì)手此時(shí)結(jié)果相同，因此集合U?W。COPT=

情形1.2假設(shè)車輛存在待服務(wù)需求，在tm時(shí)刻，車輛從當(dāng)前位置出發(fā)服務(wù)新服務(wù)序列中待服務(wù)需求集，則Tv≤tm+L*(tm,Pv(tm),Rvs)≤tm+L*(tm+Pv(tm),o,Rsv)+Pv(tm)。 由 引 理3，L*(tm+Pv(tm),o,Rvs)+Pv(tm)≤由引理因此，Tv≤tm+COPT(R)+( 1/2)COPT(R)≤( 5/2)COPT(R)。又

情形2由離線算法，新需求由車輛配送，即車輛存在待服務(wù)需求。由情形1.2 知，Tv≤tm+L*(tm+同理，令U={u1,u2,…,un}為tm時(shí)刻無(wú)人機(jī)新服務(wù)序列中n個(gè)待服務(wù)需求配送時(shí)長(zhǎng)，n≥0，有2COPT(R)。Conline(R)=max{Td,Tv} ≤( 5/2)COPT(R)。

綜上所述，該策略競(jìng)爭(zhēng)比為2.5。證畢。

針對(duì)3.1 節(jié)中在線均衡算法所調(diào)用的離線算法，可通過(guò)研究其對(duì)應(yīng)的離線問(wèn)題得到，由此產(chǎn)生第4 章內(nèi)容。

4 車輛無(wú)人機(jī)并行配送離線策略分析

4.1 離線模型建立

相對(duì)于車輛無(wú)人機(jī)并行在線配送問(wèn)題，對(duì)應(yīng)的離線問(wèn)題與其區(qū)別僅在于離線問(wèn)題從初始時(shí)刻便已知所有需求點(diǎn)的所有信息，其余問(wèn)題描述一致?；谠搯?wèn)題，可建立如下模型：

目標(biāo)函數(shù)（1）表示總服務(wù)時(shí)間由無(wú)人機(jī)或車輛最晚返回配送站的時(shí)間決定；約束（2）表示無(wú)人機(jī)所耗費(fèi)時(shí)間為無(wú)人機(jī)服務(wù)序列中各需求所耗費(fèi)時(shí)間之和；約束（3）表示車輛所耗費(fèi)時(shí)間為車輛服務(wù)序列中各段路程所耗費(fèi)時(shí)間之和；約束（4）表示無(wú)人機(jī)與車輛所服務(wù)需求點(diǎn)之和與總服務(wù)需求數(shù)相等，即Rd∪Rv=R；約束（5）、（6）表示各需求只能由無(wú)人機(jī)或車輛進(jìn)行服務(wù)，即Rd∩Rv=?，且為節(jié)點(diǎn)平衡約束，表示各需求只服務(wù)一次；約束（7）表示如果車輛從0 點(diǎn)出發(fā)則必然會(huì)回到0點(diǎn)；約束（8）避免車輛路徑形成子環(huán)；約束（9）表示模型中決策變量的取值范圍。

4.2 離線算法提出

對(duì)于該問(wèn)題是否能求出最優(yōu)解，需考慮其時(shí)間、空間復(fù)雜度。該規(guī)劃模型屬于匹配模型與TSP 模型結(jié)合。由于TSP 問(wèn)題屬于NP 難問(wèn)題，其又包含于車貨匹配問(wèn)題中，因此該問(wèn)題也屬于NP難問(wèn)題，無(wú)法在有效時(shí)間內(nèi)求出最優(yōu)解，可采用啟發(fā)式算法進(jìn)行求解。

針對(duì)該問(wèn)題，結(jié)合均衡算法、插入法思想提出無(wú)人機(jī)優(yōu)先均衡算法。令Rex為d(o,xm)>S的需求集合，=Td-Tv,Tmseitnus為差值集合且初始為空集，其余參數(shù)見(jiàn)1.1節(jié)。以下為無(wú)人機(jī)優(yōu)先均衡算法偽代碼。

其中1～8行求出初始解，9～22行通過(guò)迭代選擇得出最終解。

4.3 離線算法性能分析

無(wú)人機(jī)優(yōu)先均衡算法的時(shí)間復(fù)雜度為O(n3)。假設(shè)n是需求點(diǎn)數(shù)量，該算法的時(shí)間復(fù)雜度主要由初始解生成與迭代選擇兩部分決定。在初始解生成中，所涉及以配送時(shí)長(zhǎng)最短為目標(biāo)的遺傳算法時(shí)間復(fù)雜度為O(n3)，j∈I循環(huán)的時(shí)間復(fù)雜度為O(n)，其余代碼時(shí)間復(fù)雜度為常量，因此整個(gè)初始解生成部分時(shí)間復(fù)雜度為O(n)+O(n3)。在迭代選擇過(guò)程中，主要對(duì)rj∈Rd進(jìn)行循環(huán)，其時(shí)間復(fù)雜度為O(m?n3)，其中m為Rd集合中需求點(diǎn)數(shù)，m≤n，因此迭代選擇部分時(shí)間復(fù)雜度為O(m?n3)。綜上所述，無(wú)人機(jī)優(yōu)先均衡算法的時(shí)間復(fù)雜度為O(n3)+O(m?n3)=O(n3)。

除此之外，對(duì)于同樣的輸入，通過(guò)比較無(wú)人機(jī)優(yōu)先均衡算法所求解與CPLEX最優(yōu)解可有效驗(yàn)證離線算法的性能。針對(duì)離線模型，通過(guò)MATLAB 2018a 調(diào)用CPLEX 及YALMⅠP 工具箱進(jìn)行求解。引入變量T3，由目標(biāo)函數(shù)minT=max{Td,Tv} ，令Td≤T3、Tv≤T3，將4.1節(jié)中的模型轉(zhuǎn)化為線性規(guī)劃模型。

仿真初始設(shè)置為：車輛行駛速度為1，無(wú)人機(jī)飛行速度為2，無(wú)人機(jī)飛行半徑為8，由于問(wèn)題重點(diǎn)在于無(wú)人機(jī)飛行范圍內(nèi)的需求分配，為達(dá)到更好的展示效果，令需求一半在無(wú)人機(jī)飛行半徑內(nèi)隨機(jī)產(chǎn)生，一半無(wú)限制。

所設(shè)計(jì)離線算法與CPLEX運(yùn)行結(jié)果對(duì)比見(jiàn)表2，其中最優(yōu)值保留三位小數(shù)。由表2可知，所設(shè)計(jì)離線算法結(jié)果與CPLEX最優(yōu)值相比，隨著需求點(diǎn)數(shù)量的增加，計(jì)算時(shí)間明顯小于CPLEX 的計(jì)算時(shí)間，且結(jié)果偏差在合理范圍內(nèi)。由此說(shuō)明了離線算法的有效性。

表2 離線算法與CPLEX對(duì)比結(jié)果Table 2 Comparison results of offline algorithm and CPLEX

5 在線算法仿真分析

對(duì)于隨機(jī)生成的需求點(diǎn)坐標(biāo)及釋放時(shí)間，通過(guò)計(jì)算在線算法所得結(jié)果與離線最優(yōu)下界值之比，進(jìn)行在線算法關(guān)于輸入?yún)?shù)的仿真分析。與4.3節(jié)中需求于0時(shí)刻一同釋放不同，此時(shí)離線解同樣受需求釋放的限制，計(jì)算較為復(fù)雜，與其下界值相比不影響在線算法性能判斷。離線最優(yōu)下界取值方法見(jiàn)3.2節(jié)中引理1。

初始設(shè)置為需求點(diǎn)個(gè)數(shù)為10，無(wú)人機(jī)與車輛速度之比為1.5，需求點(diǎn)坐標(biāo)最大值與無(wú)人機(jī)飛行半徑之比為2，釋放時(shí)間上限為50 min，每次獨(dú)立測(cè)試50 次所得結(jié)果分別取平均值，得以下結(jié)果，如表3 所示。由于理論分析是基于最壞情形分析之下所得，而實(shí)際場(chǎng)景下不一定是最壞情形，因此結(jié)果中所得實(shí)際比值明顯小于理論分析所得競(jìng)爭(zhēng)比。

表3 仿真分析結(jié)果Table 3 Simulation analysis results

將需求點(diǎn)個(gè)數(shù)設(shè)為20，其余參數(shù)與本節(jié)初始設(shè)置相同，得在線結(jié)果示意圖（如圖2）、離線結(jié)果示意圖（如圖3）、結(jié)果比較表（見(jiàn)表4）。其中需求1代表配送站，各需求點(diǎn)序號(hào)按釋放先后排列，離線結(jié)果示意圖建立在所有需求信息在0時(shí)刻已知情形下。

圖2 在線結(jié)果示意圖Fig.2 Schematic diagram of online results

圖3 離線結(jié)果示意圖Fig.3 Schematic diagram of offline results

表4 結(jié)果比較表Table 4 Results comparison table

分析運(yùn)行結(jié)果可知：

（1）隨著需求點(diǎn)數(shù)量增加，在線均衡策略仍舊適用，但在線均衡策略結(jié)果與離線結(jié)果差距增加。需求個(gè)數(shù)不變情形下，釋放時(shí)間上限提高，需求釋放時(shí)間間隔增加，在線均衡策略結(jié)果與離線結(jié)果差距減小。因此，所提出的在線均衡策略更適用于需求點(diǎn)數(shù)量較少、釋放時(shí)間間隔較長(zhǎng)的情形。

（2）在現(xiàn)實(shí)場(chǎng)景中，對(duì)于車輛與無(wú)人機(jī)并行在線配送問(wèn)題，無(wú)人機(jī)方面有以下建議。在無(wú)人機(jī)選用方面，選用服務(wù)范圍更廣、相對(duì)車輛速度更快的無(wú)人機(jī)能減小在線結(jié)果與離線下界比值，即使得在線均衡策略表現(xiàn)更優(yōu)。在無(wú)人機(jī)配送方面，當(dāng)出現(xiàn)接近無(wú)人機(jī)飛行限制范圍的需求時(shí)，使用車輛進(jìn)行服務(wù)，從而使無(wú)人機(jī)能更好地服務(wù)近距離需求，在更短時(shí)間內(nèi)滿足更多應(yīng)急需要。

6 結(jié)語(yǔ)

本文研究了在應(yīng)急配送背景下，基于需求實(shí)時(shí)產(chǎn)生的無(wú)人機(jī)與車輛并行配送在線優(yōu)化問(wèn)題。綜合考慮了現(xiàn)實(shí)場(chǎng)景中需求實(shí)時(shí)產(chǎn)生，無(wú)人機(jī)服務(wù)半徑有限、載重量有限、速度快等問(wèn)題特征以及并行配送的服務(wù)模式，通過(guò)競(jìng)爭(zhēng)分析法證明了該問(wèn)題下界為1.5，并基于重規(guī)劃思想設(shè)計(jì)了在線均衡算法，通過(guò)最壞情形分析法證明了在線算法的競(jìng)爭(zhēng)比為2.5。由于所設(shè)計(jì)的在線算法調(diào)用了離線算法，因此對(duì)離線問(wèn)題進(jìn)行了描述、建模并設(shè)計(jì)了相應(yīng)算法，通過(guò)與CPLEX 結(jié)果比較得出所設(shè)計(jì)的離線算法速度快，偏差低。最后，通過(guò)調(diào)整不同的輸入?yún)?shù)，得出不同參數(shù)改變下在線算法依舊有效。通過(guò)所設(shè)計(jì)的在線均衡算法，可對(duì)車輛與無(wú)人機(jī)平行應(yīng)急物資配送實(shí)時(shí)優(yōu)化領(lǐng)域作理論補(bǔ)充。未來(lái)的研究方向可從混合在線配送進(jìn)行考慮，混合在線配送指在部分信息未知情形下采用兩種以上配送模式進(jìn)行配送服務(wù)。