孟姍姍 ,郭秀萍,2

(1.西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院,成都 610031；2.北京郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院,北京 100876)

近年來,無人機以成本低、速度快、飛行路徑接近直線等優(yōu)勢在物流領(lǐng)域得到迅速發(fā)展[1-2],亞馬遜、谷歌、京東等多家企業(yè)都在嘗試使用無人機提供更高效的服務(wù)。但因其續(xù)航里程和載荷能力有限,卡車-無人機聯(lián)合配送問題得到廣泛關(guān)注,Wang等[3-4]的研究也證明,卡車-無人機聯(lián)合配送在最壞情況下的效率仍優(yōu)于卡車單獨配送。

Murray等[5]和Agatz等[6]首先通過對經(jīng)典旅行商問題的擴(kuò)展,并假設(shè)無人機每次飛行只攜帶一個包裹,提出了飛行助手旅行商問題(Flying Sidekick Traveling Salesman Problem,FSTSP)、帶無人機的旅行商問題(Traveling Salesman Problem with Drone,TSP-D)。文獻(xiàn)[7-9]中對FSTSP 進(jìn)行了擴(kuò)展,考慮多卡車-無人機協(xié)同配送,設(shè)計了求解大規(guī)模問題的啟發(fā)式方法；Marinelli等[10]將TSPD 擴(kuò)展到在卡車路徑任意位置發(fā)射和回收無人機,并使用貪婪算法求解。但上述研究均假設(shè)無人機一次飛行只服務(wù)一個客戶點,而一次多點配送可以充分發(fā)揮無人機優(yōu)勢,針對此問題,Pedro等[11]提出了一種基于迭代的貪婪算法,優(yōu)化無人機多點配送路徑。文獻(xiàn)[12-13]中考慮每輛卡車配備多架無人機,無人機一次服務(wù)多個客戶,設(shè)計了靈活的啟發(fā)式方法。上述研究不考慮重量對無人機電池能耗和速度的影響,雖然文獻(xiàn)[14-15]中驗證了無人機電池能耗與重量的近似線性關(guān)系,并應(yīng)用于無人機單獨配送問題；Jeong等[16]考慮無人機能源消耗和限制飛行區(qū)域的FSTSP,提出兩階段構(gòu)造和搜索方法等,但均未考慮卡車-無人機聯(lián)合、同時取送貨的情況。因此,本文提出“最大重量判斷法”構(gòu)造初始可行解,以及基于節(jié)點特性的改進(jìn)模擬退火算法(SA)進(jìn)一步優(yōu)化總成本。

綜上所述,本文針對實際配送中客戶點同時取送貨的雙重需求,考慮不同載荷對電池能源消耗和路徑選擇的影響下,無人機一次可攜帶多個包裹時的卡車-無人機聯(lián)合路徑優(yōu)化問題,提出卡車-無人機聯(lián)合取送貨模式,并設(shè)計兩階段優(yōu)化方法。仿真結(jié)果表明,本文提出的模式和方法能有效降低總成本,且算法效率較高。

1 問題描述

卡車單獨取送貨模式如圖1 所示,卡車在載重約束下,攜帶一定量包裹從配送中心出發(fā),依次完成同時取送貨任務(wù)后返回配送中心。隨著物流量的不斷增大,卡車單獨取送貨面臨交通和成本壓力,難以高效完成任務(wù)。為此,本文提出一種卡車-無人機聯(lián)合取送貨模式,以縮短卡車行駛距離,降低總成本,如圖2所示,每輛卡車攜帶一架無人機和包裹從配送中心出發(fā),按照預(yù)定路線,在客戶點取送包裹,無人機可以攜帶一些小包裹,從卡車上起飛,同時完成一些取送任務(wù),無人機只能在配送中心或客戶點起飛或與卡車匯合,在返回卡車后進(jìn)行電池更換,并可以再次發(fā)射,在完成所有取送任務(wù)后,一起返回配送中心。其中,需求(取貨量或配送量)超出無人機載重的客戶點稱為“超重點”,必須由卡車服務(wù)；剩余客戶點稱為“無人機可服務(wù)點”。

同時,由于無人機輕量、速度快,質(zhì)量對電池能耗,即續(xù)航里程影響較大,如圖3所示,設(shè)無人機最大承載量為3 kg,無人機先服務(wù)客戶3時負(fù)荷減少(左圖),而先服務(wù)客戶2時負(fù)荷增加,消耗更多能量,甚至超出承載力(右圖)。由于考慮路徑方向性和無人機載重變化,增大了解空間和搜索難度。

Dorling等[15]驗證了無人機在懸停、水平飛行和改變高度時,平均功率消耗大致相等。因此,考慮無人機恒定功率下,電池能耗與無人機重量正相關(guān),本文擴(kuò)展了Liu等[17]的能耗模型,引入?yún)?shù)α表示單位距離單位重量能耗率,用ws表示無人機自身重量,wdi為無人機d離開點i時的載重,dij為i～j的距離,則無人機d經(jīng)過弧(i,j)的能量消耗表示為:Fdij=α(ws+wdi)dij；用P表示無人機功率,則無人機d從點i～j的飛行時間和速度分別為:

用Cdf表示無人機每瓦時能量消耗成本,則無人機d經(jīng)過弧(i,j)的能耗成本為

綜上所述,本文假設(shè):每輛卡車有相同的載重限制；無人機有電池能量和容量約束,電池能耗隨無人機重量線性變化；每個客戶由卡車或無人機一次服務(wù)完成,且取貨與送貨同時進(jìn)行；無人機只能在客戶點或配送中心與卡車同步匯合,考慮無人機能耗和安全性,卡車到達(dá)匯合點的時間不晚于無人機；一架無人機一次可取送多件包裹；無人機在卡車上更換電池后可繼續(xù)取送貨,且每次發(fā)射時電池滿電；卡車速度恒定,無人機速度隨載重變化；每段里程用歐式距離測量；不考慮客戶點時間窗限制。

2 模型構(gòu)建

模型中使用的符號:

N——所有節(jié)點集合,配送中心表示為o(出發(fā)點)和e(返回點),o∈N,e∈N

A——所有弧的集合,(i,j)∈A,i,j∈N,i≠j

C——客戶點集合,C=N{o,e}={1,2,…,n}

No,Ne——分別為路徑的起點和終點集合,

fdk——無人機d子路徑k的節(jié)點集合,fdk={dk0,dk1,…,dkp},k∈KD

K,D——分別為使用的卡車和無人機集合,K={t|t=1,2,…,m},D={d|d=1,2,…,m}

Cvt——卡車每公里的里程成本

Ct,Cd——分別為卡車、無人機的單位使用成本

Q——卡車最大承載量

W,F——分別為無人機最大承載量和電池最大能量值(單位:Wh)

wti——為卡車t在點i停留期間,各狀態(tài)(如發(fā)射前、回收后等)載重的最大值

ttij,tdij——分別為卡車t及其無人機在弧(i,j)∈A(i≠j)的旅行時長

tti,tdi——分別為卡車t及其無人機到達(dá)點i的時間

ts——單位客戶點的服務(wù)時間,即客戶點裝卸包裹時間

xtij——當(dāng)卡車t經(jīng)過弧(i,j)∈A(i≠j)時為1,否則為0

ydij——當(dāng)無人機d經(jīng)過弧(i,j)∈A(i≠j)時為1,否則為0

zti——當(dāng)卡車t服務(wù)客戶i時為1,否則為0

zdi——當(dāng)無人機d服務(wù)客戶i時為1,否則為0

bdij——當(dāng)無人機d從點i發(fā)射,在點j返回時為1,否則為0

sdi——當(dāng)無人機d從點i發(fā)射時為1,否則為0

ldi——當(dāng)無人機d在點i返回時為1,否則為0

htd——當(dāng)卡車t配備無人機d時為1,否則為0

uti,udi——分別表示點i在卡車t路徑、無人機d子路徑中的訪問順序,uti≥0,udi≥0

M——足夠大的正整數(shù)

建立如下數(shù)學(xué)模型:

目標(biāo)函數(shù)

式(3)表示最小化總成本,其中,m為卡車或無人機使用量,由優(yōu)化結(jié)果確定；式(4)表示每輛卡車從配送中心出發(fā)并返回配送中心；式(5)保證每對無人機發(fā)射點和回收點流量守恒；式(6)為卡車線路節(jié)點的進(jìn)出平衡約束；式(7)保證每個無人機服務(wù)點流量守恒；式(8)保證每個客戶被卡車或無人機服務(wù),且僅一次；式(9)表示每條無人機子路徑至少服務(wù)一個客戶；式(10)、(11)保證發(fā)射點和回收點為卡車經(jīng)過點,且在該點分別有無人機離開和返回；式(12)、(13)對式(10)、(11)進(jìn)行補充,以明確變量間約束關(guān)系；式(14)確保無人機的每次發(fā)射和返回在所屬同一卡車路徑上；式(15)、(16)表示每個節(jié)點至多發(fā)射或回收一次無人機；式(17)表示卡車經(jīng)過點i、j,無人機從點i發(fā)射后,沒有在點j返回,則不能在點j發(fā)射,以保證無人機子路徑間的不交叉性；式(18)、(19)確保無人機發(fā)射回收順序與卡車、無人機訪問順序一致；式(20)表示不允許卡車和無人機并行經(jīng)過同一段弧；式(21)保證每輛卡車在各節(jié)點滿足承載量約束；式(22)保證每條無人機子路徑各節(jié)點上的載重不超出無人機最大承載量；式(23)為每架無人機每次飛行的能耗限制；式(24)、(25)分別為卡車和無人機到達(dá)每個節(jié)點的時間約束；式(26)保證卡車到達(dá)匯合點的時間不晚于無人機。

3 方法設(shè)計

由于問題的NP-hard性質(zhì),本文提出一種兩階段求解方法,獲得近似最優(yōu)解。第1階段,運用“最大重量判斷法”構(gòu)造初始可行解,為卡車指派取送任務(wù)并確定卡車使用量；第2 階段,對模擬退火算法(SA)進(jìn)行改進(jìn),以優(yōu)化卡車-無人機路徑,實現(xiàn)成本最小化。

針對卡車-無人機同時取送貨問題特點,在優(yōu)化無人機路徑時,不僅要滿足無人機承載量、電池能耗以及路徑間不交叉等約束,還需考慮卡車在其各路徑節(jié)點的載重情況,求解空間較小。為此,本文提出“最大重量判斷法”構(gòu)造初始解,以擴(kuò)大第2階段解空間,提高求解速度和質(zhì)量。其次,在卡車、無人機、同時取送貨等多重實際約束下,求解易陷入局部最優(yōu),因此,在第2階段,使用模擬退火算法(SA),以一定概率接受次優(yōu)解。同時,為使SA 適合問題特性,結(jié)合節(jié)點類型,設(shè)計了3類11種鄰域搜索算子,生成候選解；為節(jié)約總成本,在搜索中允許在同一節(jié)點(包括倉庫)發(fā)射和回收無人機,并使用區(qū)域設(shè)定法和禁忌列表等加速策略,增加搜索可行性,減少搜索重復(fù)性,提高求解效率。

首先,針對每輛卡車t,定義如下概念:

(1)卡車點i?？ㄜ噒路徑中不參與無人機發(fā)射和回收的節(jié)點(i∈tp)。

(2)無人機點i?？ㄜ噒無人機服務(wù)的客戶節(jié)點(i∈dt)。

(3)組合點i?？ㄜ噒路徑中參與無人機發(fā)射或回收的節(jié)點,包括發(fā)射點(發(fā)射但不回收無人機,i∈spt)、回收點(回收但不發(fā)射無人機,i∈lpt)和混合點(同時發(fā)射和回收無人機,i∈slt=sst∪sdt,i∈sst表示卡車在i點發(fā)射無人機,并在原地收集；i∈sdt表示卡車在i點回收無人機后,原地再次發(fā)射)。(1)和(3)合稱為卡車路徑點。

3.1 編碼

采取自然數(shù)編碼,卡車路徑中,用0 表示卡車ID,總節(jié)點數(shù)(1+n)表示終點配送中心ID,顧客集為{1,2,…,n},如圖4所示,從左向右,第1個0后的數(shù)字為第1輛卡車依次訪問的客戶點ID；無人機路徑中,起始數(shù)字表示卡車序號(1,2,…,m),其后跟隨的數(shù)字為該卡車(卡車1)對應(yīng)的無人機路徑,包含組合點,如13-3-10-11為一個“無人機子路徑”,表示無人機從點13發(fā)射,服務(wù)客戶3、10后,在點11返回。虛豎線“┇”為無人機子路徑分隔符,以輔助說明。

3.2 第1階段:構(gòu)造初始解

由于需要考慮車輛載重及各節(jié)點載荷變化,簡單的貪婪算法或隨機生成初始解的方式[1,17]需要進(jìn)行多次載重可行性判斷,增加搜索時間,故提出“最大重量判斷法”(簡稱MW 法)進(jìn)行初始解構(gòu)造,其優(yōu)勢在于保證后續(xù)卡車路徑的可行性,擴(kuò)大第2階段解空間,提高后續(xù)搜索的收斂速度和質(zhì)量。

初始解的構(gòu)造包括卡車單獨取送貨路徑構(gòu)造和無人機路徑添加兩部分。首先,采用MW 法構(gòu)造由卡車完成全部取送貨任務(wù)的完整路徑,為卡車分配任務(wù),確定卡車使用量(步驟1～3)；然后,基于節(jié)點特征,將部分卡車服務(wù)客戶轉(zhuǎn)化為無人機服務(wù)客戶,形成初始解(步驟4)。

MW 法基本思路:使用最大重量對客戶分組,將組內(nèi)同時取送貨旅行商問題(TSP-SPD)轉(zhuǎn)化為一般旅行商問題(TSP)。對于每個客戶i,定義μi=pi-di表示客戶i的凈需求(其中,di和pi分別為客戶i的配送量和取貨量)；定義表示車輛經(jīng)過客戶i后的載重累積增量。假設(shè)卡車服務(wù)一組客戶V?C,從配送中心出發(fā)時的載重量為wv,則

是滿足卡車載重約束的充要條件[18]。cumi最大值即該組客戶中正μi之和,表示為:,則最大重量為wv+uv。MW 法構(gòu)造初始解的基本步驟如下:

步驟1計算所有客戶點的凈需求量μi,總配送量及正凈需求和uc,進(jìn)行最大重量判斷,如果wc+uc≤Q,則一輛卡車即可滿足全部需求,初始卡車路徑的構(gòu)建為傳統(tǒng)TSP,使用模擬退火算法(SA)優(yōu)化,優(yōu)化方式如圖5所示,然后轉(zhuǎn)步驟4；否則,轉(zhuǎn)步驟2。

步驟2初始化客戶總配送量w=0,正凈需求和u=0,卡車路徑列表rt=[0],從配送中心出發(fā),依次尋找最近的客戶點i,并更新w,如果μi＞0,更新u,如果w+u≤Q,則在rt列表中添加客戶點i；否則,在rt列表中添加0,初始化w、u和rt,啟動另一條卡車路徑。重復(fù)上述操作,至所有客戶被添加,形成初始卡車路徑。

步驟3使用模擬退火算法求解有最大重量約束的TSP(TSP-MW),優(yōu)化步驟2的初始解,每次搜索以最大重量wv+uv≤Q(設(shè)該卡車服務(wù)一組客戶V)為判斷條件,若超出,則返回上一步繼續(xù)搜索,搜索方式如圖6、7所示,為同卡車、不同卡車路徑節(jié)點2-opt交換。

步驟4針對每條卡車路線,通過將部分卡車路徑點調(diào)整為無人機點,生成無人機路徑,在滿足無人機載重和能耗約束下,采取如下操作:

操作1將卡車點轉(zhuǎn)為無人機點,如圖8中的點6,構(gòu)造無人機子路徑2→6→4,無人機從點2出發(fā),服務(wù)客戶6后返回點4,卡車直接從2→4,同時計算成本節(jié)約量,如果節(jié)約量為正,則執(zhí)行此操作,如下操作亦然。

操作2將發(fā)射點轉(zhuǎn)為無人機點,如圖9所示,如果點4的取送任務(wù)可由無人機完成,則將客戶4調(diào)整為無人機點,點4左側(cè)相鄰點5為新發(fā)射點,無人機子路徑為5→4→9→,卡車直接從5→2。

操作3將回收點轉(zhuǎn)為無人機點,如圖10 所示,如果無人機在完成客戶5的取送任務(wù)后可以繼續(xù)服務(wù)客戶2,則將客戶2調(diào)整為無人機點,點2右側(cè)相鄰點4為回收點,無人機子路徑為→5→2→4,卡車直接從7→4。

操作4將混合點轉(zhuǎn)為無人機點,如圖11 所示,將兩個子路徑合并,形成路徑→7→9→3→,卡車直接從6→2。

按照卡車訪問順序進(jìn)行循環(huán),每次循環(huán),針對卡車訪問點類型,進(jìn)行判斷和替換操作,直至不存在正成本節(jié)約,輸出初始解。其中,無人機子路徑載重判斷依據(jù)為

設(shè)該無人機一次飛行服務(wù)一組客戶d。

3.3 第2階段:優(yōu)化初始解

為提升解的搜索效率和質(zhì)量,對模擬退火算法(SA)進(jìn)行改進(jìn),針對每輛卡車優(yōu)化初始解。

(1)多種鄰域搜索操作。傳統(tǒng)模擬退火算法對解空間的搜索能力較弱,使得算法整體運行時間過長。為此,參考Liu等[17]的研究,設(shè)計了同路插入、異路插入和兩點交換3類方法對解鄰域進(jìn)行搜索,取最優(yōu)結(jié)果為候選解,每次搜索均需進(jìn)行無人機載重及能耗判斷,若超出則返回上一步繼續(xù)搜索。考慮問題的復(fù)雜性和無人機約束條件,針對節(jié)點類型采取不同策略,提高搜索效率。

同路插入。針對同一卡車,在不改變客戶服務(wù)方式下,從該線路服務(wù)的客戶中隨機選擇一個貪婪插入成本最小的可行位置。包括卡車點同路插入、無人機點同路插入和混合點同路插入3種。

圖12為將卡車點貪婪插入所在卡車路徑,此時被插入節(jié)點原來位置清空,后續(xù)節(jié)點位置前移；圖13為將無人機點插入同卡車的無人機路徑,可以插入該點所在無人機子路徑,也可以插入其他無人機子路徑,選擇插入成本最小的位置,插入方法同上；組合點(此處不考慮混合點的情況)插入所在卡車路徑,需要考慮路徑方向的一致性,如果卡車路徑中,發(fā)射點插入位置在原回收點之后,或回收點插入位置在原發(fā)射點之前,則對應(yīng)無人機子路徑倒向。如圖14所示,回收點9 的插入位置在原發(fā)射點3 之前,該無人機子路徑變?yōu)?→7→3。

異路插入。針對同一卡車,在改變客戶服務(wù)方式下,從該線路服務(wù)的客戶中隨機選擇一個貪婪插入成本最小的可行位置,同樣包含3種方式。如圖15所示,為將卡車點插入同卡車的無人機路徑中,成為無人機點,或為該卡車點建立新的無人機子路徑,貪婪插入原無人機路徑中,取成本較小的方式。將無人機點插入所屬卡車路徑的情況如圖16所示,若選擇點為該無人機子路徑唯一服務(wù)點,則刪除該無人機子路徑。圖17為將發(fā)射點轉(zhuǎn)化為無人機點,即將插入成本最小的卡車路徑點添加到原無人機子路徑端點(如點2),成為新發(fā)射點,卡車路徑中,原發(fā)射點位置清空,新發(fā)射點位置不變。針對回收點的操作同上；如果將混合點插入無人機路徑,則與3.2節(jié)圖11的操作相同,將在該混合點交匯的兩個無人機子路徑合并為一條子路徑,并在對應(yīng)卡車路徑中刪除該點。

兩點交換。針對同一卡車,從該路線服務(wù)的客戶中隨機選擇兩個進(jìn)行交換,采用5種方式,同時,在生成隨機數(shù)時排除無人機點與“超重點”間交換,減少解的不可行性。圖18為兩卡車點交換,圖19為卡車點與無人機點間交換,圖20為無人機點間交換的兩種情況,即同無人機子路徑內(nèi)、不同子路徑間無人機點交換。圖21、22所示為交換點中存在組合點的情況,此時,對應(yīng)無人機路徑中的組合點也需要交換,存在組合點與卡車路徑點間同路交換和與無人機點異路交換兩種。

(2)設(shè)計加速策略,提高優(yōu)化效率。為避免不必要的搜索,針對問題特征設(shè)計了加速策略:區(qū)域設(shè)定法,即在不失解最優(yōu)性前提下,提前排除部分不可行解,針對性縮小搜索空間,提高算法效率。包括3個方面:①在卡車點異路插入-創(chuàng)建新無人機子路徑、組合點異路插入中,新發(fā)射點的選取范圍,首先排除原發(fā)射點、混合點和被插入點(約束式(15)～(16)),新回收點的選取亦然,且兩者形成的組合應(yīng)滿足與卡車相同的訪問順序(約束式(18)～(19))；②由于無人機載重約束,在異路插入、涉及無人機點的交換中,被插入點/被交換點的選擇范圍應(yīng)限定在被優(yōu)化路線中無人機可服務(wù)點集合內(nèi)；③交換操作中,隨機選取被交換點時,首先排除無人機點與超重點的所有交換方式。此外,由于問題存在多重約束,為進(jìn)一步提高搜索效率,使用禁忌列表節(jié)約計算時間:在SA 內(nèi)循環(huán)中(每一溫度下)使用禁忌列表存儲已經(jīng)進(jìn)行的操作,以避免重復(fù)性鄰域搜索和判斷,并在每次內(nèi)循環(huán)結(jié)束后進(jìn)行禁忌列表初始化。

以創(chuàng)建新無人機子路徑的區(qū)域設(shè)定為例進(jìn)行理論分析。設(shè)卡車t的路徑節(jié)點數(shù)為c(含首尾倉庫),無人機子路徑數(shù)量為b(即原發(fā)射點與混合點之和),一次搜索中,如果不使用區(qū)域設(shè)定法,可形成(c-12)種發(fā)射-回收組合,否則至多可形成(c-b-1)2種組合(未考慮與卡車行駛方向的一致性),兩者之差為:y=-b2+2b(c-1)。因為0≤b≤c-1,所以y在該區(qū)間單調(diào)遞增,即當(dāng)c一定時,隨著無人機發(fā)射次數(shù)b和迭代次數(shù)的增加,計算量持續(xù)增加,在考慮方向性時,兩者差距更大,同時,無效搜索的增加,會降低解的質(zhì)量。

4 算例分析

以網(wǎng)站http://www.bernabe.dorronsoro.es/vrp/上CVRP 標(biāo)準(zhǔn)算例庫中的A-n32-k5、A-n44-k7、A-n55-k9、A-n69-k9 以及A-n80-k10 等5 個算例為基礎(chǔ),對數(shù)據(jù)集進(jìn)行改進(jìn),分別命名為:M-n32、M-n44、M-n55、M-n69 和M-n80。改進(jìn)方法為:設(shè)定“超重點”比例為10%(ξ=[n×10%]),將其配送或取貨量設(shè)定到(3,10),剩余客戶的配送量為原來的0.1,調(diào)整至(0,2.5),并為其中90%的客戶在(0,2.5)范圍內(nèi)隨機添加取貨量,單位均為kg。同時,將各節(jié)點坐標(biāo)乘以0.1,單位為km,以適應(yīng)無人機載重和續(xù)航要求。

相關(guān)參數(shù)設(shè)置:無人機自身質(zhì)量取2 kg,最大承載量取3 kg,最大載荷下的續(xù)航距離取10 km,電池單位能耗率α=3 Wh,則電池可提供的能量為150 Wh,電池功率取450 W；卡車最大承載量取90 kg,里程成本為每km 1.5元,設(shè)卡車與無人機單位里程成本比β=25[17],則無人機的單位能耗成本為4元/k Wh；卡車和無人機的單位固定費用分別取30元和3元；卡車行駛速度取40 km/h,單位客戶點服務(wù)時間為3 min。

本文兩階段算法均由Python 編程實現(xiàn)；運行環(huán)境為Windows 10操作系統(tǒng),處理器為Intel(R)Core(TM)i7-10750 H CPU @2.60 GHz。

4.1 優(yōu)化結(jié)果分析

首先以算例M-n44為例,對第1、2階段的優(yōu)化結(jié)果進(jìn)行比較。所需卡車量為1,初始解如圖23所示,卡車?yán)锍虨?7.11 km,總成本為105.93元；最優(yōu)解如圖24所示,卡車?yán)锍虨?3.99 km,總成本為87.16元,分別減少27.85%和17.72%,總運行時間為22.14 s,證明了方法的有效性。

進(jìn)一步,分別通過不同規(guī)模算例對設(shè)計的方法進(jìn)行檢測。第1 階段,初始溫度分別取100、100、100、110和110 ℃,終止溫度均為1 ℃,退火系數(shù)取0.98,迭代次數(shù)均為20；第2 階段,初始溫度均取100 ℃,終止溫度均為1 ℃,退火系數(shù)取0.95,迭代次數(shù)均為10。每個算例運算10 次,取最優(yōu),結(jié)果如表1所示。

表1中:Tr/Dr表示卡車(無人機)使用量；R1、R2分別為第1、2階段的卡車?yán)锍蹋籆1、C2為第1、2階段的總成本；Δ1、Δ2為兩個階段卡車?yán)锍毯涂偝杀靖倪M(jìn)率,T為平均運行時間,所有運算均在1 min內(nèi)完成。Tntl、Tnrs分別為不使用禁忌列表和區(qū)域設(shè)定法時的平均運算時間,本文方法的平均優(yōu)化結(jié)果分別為:88.67、94.73、131.16、137.59 和159.93,不使用禁忌列表時的優(yōu)化結(jié)果與其基本一致,而未使用區(qū)域設(shè)定法時,平均優(yōu)化結(jié)果分別為:89.23、96.76、133.58、143.07 和163.37。可以看出,兩種方法均可以提高運算速度,同時,區(qū)域設(shè)定法對總成本也有一定優(yōu)化,且加速效果更明顯。

表1 兩階段優(yōu)化結(jié)果對比

同時,與卡車單獨取送貨方式比較,圖25所示為總成本對比,經(jīng)兩階段優(yōu)化,總成本相比卡車單獨取送貨分別減少17.00%、26.70%、18.29%、25.37%和19.74%；圖26所示為總時間對比,優(yōu)化后的時間分別減少17.09%、16.01%、7.91%、20.04% 和11.99%。由于卡車承載力有限,多卡車-無人機同時取送貨下,隨著客戶規(guī)模的增大,卡車使用量階段性增加,故時間呈波動變化,即當(dāng)卡車使用量增加時,總時間因任務(wù)的多卡車分擔(dān)而減少。多卡車模式下,總時間由耗時最長的路線決定,故同一卡車使用量下,總時間先減少后增加。圖27所示為卡車?yán)锍虒Ρ?由于無人機的參與,聯(lián)合模式下卡車?yán)锍虦p少近40%,且隨著客戶點的增加而增幅較緩。

4.2 不同聯(lián)合取送貨模式比較

首先,與無人機具有單位容量(一次服務(wù)一個客戶)時卡車-無人機聯(lián)合取送貨模式(簡稱“無人機單位容量模式”)比較,以算例M-n69為例,圖28所示為無人機單位容量模式,總成本為140.97元,卡車?yán)锍虨?7.11 km,無人機服務(wù)的客戶量為31；圖29所示為本文模式,總成本為130.32元,卡車?yán)锍探抵?0.22 km,無人機服務(wù)客戶量達(dá)41。顯然,本文模式能夠有效發(fā)揮無人機運力,節(jié)省總成本。

進(jìn)一步,與無人機不參與取貨時,卡車-無人機聯(lián)合配送模式比較。以算例M-n32為例,將取貨量pick分別設(shè)定為10和20。遵循同時取送、每個客戶只訪問一次的原則,針對不同取貨量,分別運算10次取最優(yōu),最優(yōu)路徑如表2所示。

由表2可見:當(dāng)pick=10時,無人機不取貨模式的總成本為86.85元,總時間為134.71 min,卡車?yán)锍虨?5.05 km,無人機服務(wù)量為15；本文模式的總成本為83.41元,總時間為125.00 min,卡車?yán)锍虨?2.56 km,無人機服務(wù)量為16。當(dāng)pick=20時,無人機不取貨模式的總成本為102.57元,總時間為148.57 min,卡車?yán)锍虨?6.06 km,無人機配送量為6；本文模式的總成本為84.84元,總時間為131.61 min,卡車?yán)锍虨?3.27 km,無人機服務(wù)量為15,在成本、時間和卡車?yán)锍躺戏謩e減少17.29%、11.42%和27.77%?？梢?無人機不取貨模式對取貨量敏感,無人機參與取送程度不同,直接影響總成本,本文提出的同時取送貨模式,能夠更有效地利用無人機,實現(xiàn)成本和時間節(jié)約。

表2 兩種模式卡車-無人機最優(yōu)路徑

4.3 靈敏度分析

為識別關(guān)鍵參數(shù)的影響,參照文獻(xiàn)[7,17]和前面的算例分析,選取超重點比例(ξ)、無人機最大容量(W)、無人機電池最大能量(F)和卡車-無人機單位里程成本比(β)4 個參數(shù),每個參數(shù)設(shè)置6個級別,基于算例M-n32、M-n69,共生成48種場景進(jìn)行測算,每個場景運行10次的平均結(jié)果如圖30所示。由圖30可以看出,較大規(guī)模算例對參數(shù)更敏感。

圖30(a)所示為超重點比例對成本的影響。可出看出,隨著超重點比例的增加,無人機可取送包裹量減少,總成本增加,更接近卡車單獨取送貨模式。無人機最大容量變化對成本的影響如圖30(b)所示。隨著無人機載荷能力的提高,成本下降,特別是當(dāng)容量為緊約束時(W≤4 kg),成本下降幅度最大。無人機電池能量對成本的影響如圖30(c)所示。隨著電池能量的增加,成本呈先快后慢的下降趨勢。圖30(d)說明,無人機的飛行成本直接影響總成本,當(dāng)無人機能耗成本較高時,無人機使用率下降,成本增加,卡車-無人機聯(lián)合取送貨模式的成本優(yōu)勢基于無人機低成本特點。綜上可知,在超重點較少,無人機容量和電池能量較大,且里程成本較低時,性能最好,無人機優(yōu)勢更明顯,總成本較低。

4.4 “最大重量判斷法”對算法效率影響

以算例M-n80為例對本文提出的“最大重量判斷法”算法效率進(jìn)行測試。隨機初始解的平均優(yōu)化結(jié)果為179.88 元,平均運行時間60.65 s；而使用MW 法的平均優(yōu)化結(jié)果為159.93 元,平均運行時間40.64 s,結(jié)果更優(yōu)。

在圖31中,左圖為采用MW 法進(jìn)行卡車單獨取送貨初始解構(gòu)造,右圖為隨機初始解。由圖31可以看出,本文提出的MW 法在迭代開始階段便將卡車?yán)锍虄?yōu)化到一個近似最優(yōu)的位置,而隨機初始解雖收斂較快,但距離MW 法仍有差距。圖32所示為第2階段兩條路徑里程成本優(yōu)化結(jié)果,MW 法避免了第2階段卡車載重的多次判斷,增大了無人機路徑解空間,加快收斂速度,結(jié)果更優(yōu)。而隨機初始解,在第2階段的每次搜索中,均需考慮卡車承載力限制,解搜索空間較小,優(yōu)化效果不明顯。可見,本文提出的MW 法能有效提升解收斂效率和效果。

同時,不使用MW 法構(gòu)造初始解時,第2階段的每次搜索需要進(jìn)行卡車各節(jié)點載重判斷,基于動態(tài)規(guī)劃思想,構(gòu)造判斷函數(shù)。如圖33所示,針對每條卡車路線,建立狀態(tài)集合state1、state2,每個節(jié)點內(nèi)由于取送貨及發(fā)射或回收無人機,卡車載重存在多個中間狀態(tài),取最大載重存入state1(不考慮到達(dá)該點時的初始載重),最終載重存入state2,則卡車載重的判斷條件為:max(state1)≤Q。其中,state2用于節(jié)點間載重狀態(tài)轉(zhuǎn)移,前一點的最終載重為后一點的初始載重,用于計算state1。

設(shè)卡車路線t的總配送量為wt,總?cè)∝浟繛閜t,mj和vj分別為路線t無人機子路徑j(luò)的總配送和總?cè)∝浟?tj={j|j=1,2,…,p}為路線t所有無人機子路徑的集合；第i階段(節(jié)點)的最終載重狀態(tài)變量為xi,fi(xi)和f′i(xi)分別為第i階段的卡車最終載重和最大載重,t(i),i=1,2,…,e為路線t第i階段對應(yīng)的節(jié)點。如果t(i)為組合點,則mk、vk分別為t(i)所在無人機子路徑的總配送和總?cè)∝浟?；如果t(i)同時為兩個無人機子路徑的匯合點,mk和vk對應(yīng)于其中前一無人機子路徑的總配送和總?cè)∝浟?則初始最終載重狀態(tài)為

對應(yīng)的初始最大載重為:f′1(x1)=f1(x1),則最終載重狀態(tài)轉(zhuǎn)移方程為(1＜i≤e)

5 結(jié)語

本文基于無人機輕量、成本低、受地面交通狀況影響少的特點,針對正逆向物流優(yōu)化問題,考慮同時取送、無人機電池能耗隨載重變化、無人機一次飛行可取送多個包裹等因素,提出卡車-無人機聯(lián)合取送貨模式,構(gòu)建兩階段求解方法:提出“最大重量判斷法”構(gòu)造初始可行解,為卡車指派取送貨任務(wù)并確定卡車使用數(shù)量；采用基于節(jié)點特征的改進(jìn)模擬退火算法進(jìn)一步優(yōu)化卡車-無人機路徑,最小化總成本。仿真結(jié)果驗證了兩階段算法的有效性,提出的卡車-無人機聯(lián)合取送貨模式較其他模式可有效減少總成本,“最大重量判斷法”顯著提高了算法收斂速度和效果,對實際情況中卡車-無人機聯(lián)合取送貨問題的解決有指導(dǎo)和借鑒意義。未來的研究將考慮取送貨的時間窗因素,進(jìn)一步優(yōu)化總時間。