張玉州,葉 亮,鄭軍帥
(安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 安慶 246133)
外賣O2O(online to offline)[1]已成為現(xiàn)代客戶依賴的主流消費(fèi)方式,外賣配送實(shí)質(zhì)是車輛路徑問題(vehicle routing problem,VRP)的實(shí)際應(yīng)用案例。VRP最早由Dantzig和Ramser[2]于1959年提出,國(guó)內(nèi)外學(xué)者對(duì)VRP問題進(jìn)行了大量的研究,許多與時(shí)間相關(guān)的車輛調(diào)度問題都可歸納為VRP的一類重要拓展,稱為帶時(shí)間窗限制車輛路線問題(vehicle routing problems with time windows,VRPTW)[3],如郵件投遞、應(yīng)急物資配送等。啟發(fā)式算法是求解此類拓展問題的主要方法,例如節(jié)約法[4]、捕食搜索算法[5]、最近鄰域算法(nearest neighbor algorithm,NN)[6]、遺傳算法[7-8]、禁忌搜索算法[9]等。啟發(fā)式算法的優(yōu)點(diǎn)為具有全局搜索能力,求解效率高,如Kwon等[10]運(yùn)用禁忌搜索算法求解VRP問題,求解數(shù)在50~100。
近年來(lái),人工智能方法[11-12]在解決組合優(yōu)化問題上得到了充分應(yīng)用,張建強(qiáng)等[13]利用遺傳算法求解物流配送路徑優(yōu)化問題,戴韜等[14]利用VRP理論考慮了船舶航線規(guī)劃問題,郭月[15]、楊博文[16]等對(duì)外賣市場(chǎng)配送發(fā)展進(jìn)行了分析。滾動(dòng)時(shí)域控制(receding horizon control,RHC)作為一種動(dòng)態(tài)下在線優(yōu)化控制策略,國(guó)內(nèi)外學(xué)者也設(shè)計(jì)了基于RHC的算法對(duì)動(dòng)態(tài)優(yōu)化問題進(jìn)行求解[17-20],驗(yàn)證了基于RHC策略的合理性和有效性。
綜上所述,隨時(shí)間窗推移而發(fā)生的動(dòng)態(tài)干擾外賣配送問題研究仍然較少。以降低外賣配送總延誤時(shí)間為主要目標(biāo),文中設(shè)計(jì)了一種基于RHC的NN算法(RHC-NN)對(duì)問題模型進(jìn)行求解。實(shí)驗(yàn)結(jié)果證明了訂單在五種不同動(dòng)態(tài)干擾下用新算法解決問題的有效性,可為平臺(tái)商戶節(jié)約成本和提升客戶滿意度提供決策支持。
針對(duì)動(dòng)態(tài)干擾變化下的某平臺(tái)商戶的午餐外賣配送車輛路徑問題,利用滾動(dòng)時(shí)域策略降低動(dòng)態(tài)干擾,目標(biāo)是送餐員沿途配送每一位客戶的訂單,并在滿足訂單量需求、配送車輛的承載限制和客戶的預(yù)期時(shí)間等約束條件下,縮短配送服務(wù)延誤時(shí)間,最后在完成所有配送服務(wù)后,返回中心。
1.2.1 模型參數(shù)
涉及的主要參數(shù)如下:
Q:一輛車的車載量;
Mi:每位顧客訂單的需求量;
Tn:車輛配送的最大行駛時(shí)間;
En:客戶訂單的最早到達(dá)時(shí)間;
Fn:客戶訂單最晚到達(dá)時(shí)間;
N:配送點(diǎn)個(gè)數(shù),其訂單需求記為Mi(i=1,2,…,N);
cij:表示從點(diǎn)i到點(diǎn)j的運(yùn)輸成本;
xij:表示車輛從i到j(luò)的配送過(guò)程發(fā)生,xij=1;
任務(wù)i最早開始服務(wù)時(shí)間為ETi,任務(wù)最晚時(shí)間為L(zhǎng)Ti。
1.2.2 約束條件
結(jié)合外賣配送的問題特點(diǎn),可對(duì)變量描述如下:
(1)只考慮單站點(diǎn)單人單摩托車的配送,單次行駛距離最大為L(zhǎng),配送速度為V;
(2)配送路徑優(yōu)化的目標(biāo)是行使成本最低,即總延誤時(shí)間最小,距離較短;
(3)每輛車的服務(wù)總需求量在該車的承載能力Q以內(nèi),車輛保持勻速行駛。
1.2.3 建立模型
根據(jù)上述問題描述,動(dòng)態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標(biāo)函數(shù)如下:
(1)
(2)
(3)
(4)
(5)
ETi≤ti≤LTi,i=1,2,…,N
(6)
xij,yij∈(0,1),i,j=0,1,…,N
(7)
式1為目標(biāo)函數(shù)配送的車輛的運(yùn)輸費(fèi)用最小;式2為車輛容量約束,車輛載重貨物總量不得超出承載能力;式3保證整個(gè)路徑中不存在局部多余的路徑;式4、式5確保每個(gè)顧客都會(huì)被配送;式6為需求時(shí)間約束;式7為決策變量。
FCFS(first come first service)是一種按照訂單產(chǎn)生順序,分配預(yù)期配送時(shí)間的策略,忽略了配送路線的交叉、往返等問題,配送效率不高,尤其訂單出現(xiàn)隨機(jī)變化時(shí),如服務(wù)時(shí)間的更改,缺陷更加凸顯。鑒于此,引入滾動(dòng)時(shí)域控制策略,將整個(gè)配送時(shí)域分成若干等長(zhǎng)的時(shí)間窗口,根據(jù)最新訂單的時(shí)間順序截取客戶進(jìn)入當(dāng)前窗口,采用某一優(yōu)化策略進(jìn)行路徑規(guī)劃、配送,持續(xù)該過(guò)程直到所有客戶服務(wù)完畢。考慮到進(jìn)入窗口內(nèi)的決策客戶數(shù)一般較少,所以文中選取一種性能較好的啟發(fā)式算法—NN對(duì)訂單進(jìn)行排序,RHC與NN進(jìn)行結(jié)合構(gòu)成RHC-NN算法,對(duì)整個(gè)時(shí)域中的訂單進(jìn)行排序,以實(shí)現(xiàn)運(yùn)輸費(fèi)用的最小化。
RHC策略將配送時(shí)間域H劃分為NW優(yōu)化配送時(shí)間窗口,窗口大小為H/NW。將服務(wù)時(shí)間落在窗口內(nèi)的訂單組成決策對(duì)象集合,對(duì)集合內(nèi)需要服務(wù)的決策對(duì)象進(jìn)行優(yōu)化、排序。若決策后對(duì)象的服務(wù)時(shí)間落在當(dāng)前時(shí)域中,則安排配送,否則留至下一時(shí)域窗口等待決策、服務(wù)。當(dāng)前窗口的訂單處理結(jié)束后,則繼續(xù)進(jìn)行新時(shí)域窗口的在線優(yōu)化,此過(guò)程持續(xù)至所有訂單均被服務(wù)。實(shí)時(shí)更新排序如圖1所示。
圖1 基于RHC的外賣配送全過(guò)程
NN是一種求解速度快的啟發(fā)式算法,以路線距離鄰域最小為最優(yōu)的配送算法能夠拓展當(dāng)前解的搜索空間。首先是任取一出發(fā)點(diǎn),依次取最近的點(diǎn)加入當(dāng)前路線,直至形成回解,其具體步驟如下:
第一步:從待決策對(duì)象集合S={c1,c2,…,cp}中任選一對(duì)象ci,以其為起點(diǎn),其中p為當(dāng)前決策對(duì)象數(shù)。令r←ci,且S=S
第三步:若S≠?,則轉(zhuǎn)第二步繼續(xù)執(zhí)行,否則結(jié)束當(dāng)前搜索。
該策略無(wú)法對(duì)動(dòng)態(tài)擾動(dòng)的訂單做出應(yīng)急處理,抗動(dòng)態(tài)干擾能力較弱,如訂單被要求提前或延遲配送,單一的NN算法無(wú)法處理動(dòng)態(tài)干擾。
以最近鄰域算法作為時(shí)域上路徑排序的在線優(yōu)化算法,從而基于RHC-NN的具體步驟如下:
第一步:假設(shè)已知NW外賣訂單到達(dá)時(shí)間,設(shè)置時(shí)間間隔長(zhǎng)度T與時(shí)域上時(shí)間間隔總數(shù)NW,初始化時(shí)域序號(hào)q=1。
第二步:根據(jù)當(dāng)前外賣訂單信息,由所有計(jì)劃到達(dá)時(shí)間位于[t(q),t(q)+NT]的外賣,構(gòu)成當(dāng)前時(shí)域上的待排序外賣訂單集合S(q)。
第三步:使用最近鄰域算法NN對(duì)S(q)中的外賣優(yōu)化排序,篩選出存在動(dòng)態(tài)擾動(dòng)的訂單,重新排序。
第四步:根據(jù)優(yōu)化后的排序,給S(q)中的外賣配送服務(wù)時(shí)間,將當(dāng)前時(shí)域窗口中的訂單進(jìn)行配送,其余動(dòng)態(tài)干擾的訂單分配到后續(xù)窗口中進(jìn)行配送。
第五步:若所有外賣訂單已送達(dá),則結(jié)束算法。
第六步:更新外賣訂單的相關(guān)信息,q=q+1,轉(zhuǎn)第二步繼續(xù)執(zhí)行。
為驗(yàn)證模型與設(shè)計(jì)算法的真實(shí)有效性,對(duì)初始訂單分靜態(tài)和動(dòng)態(tài)進(jìn)行實(shí)驗(yàn),靜態(tài)包括正常配送、擁擠配送、非擁擠配送三種狀態(tài);動(dòng)態(tài)包括高頻率擾動(dòng)和低頻率擾動(dòng)兩種狀態(tài),并在每種狀態(tài)下使用FCFS、NN和RHC-NN算法分別對(duì)算例進(jìn)行仿真。
其中ON表示初始訂單號(hào)、ET表示預(yù)期配送時(shí)間、AT表示實(shí)際配送時(shí)間、TW表示時(shí)間間隔,三種算法在三種狀態(tài)下的仿真結(jié)果如表1~表3所示。
表1 Normal狀態(tài)下各算法配送結(jié)果
注:FCFS、NN、RHC-NN的總延誤分別為1 573.88 min、1 264.49 min、219.55 min,總距離分別為64 193.04 m、26 080.09 m、47 880.42 m。
表2 Crowd狀態(tài)下各算法配送結(jié)果
注:FCFS、NN、RHC-NN的總延誤分別為1 405.59 min、712.14 min、192.7 min,總距離分別為64 193.04 m、26 080.09 m、35 161.05 m。
表3 Slow狀態(tài)下各算法配送結(jié)果
續(xù)表3
注:FCFS、NN、RHC-NN的總延誤分別為2 840.84 min、1 599.72 min、166.07 min,總距離分別為64 193.04 m、26 080.09 m、56 264.03 m。
對(duì)比三種狀態(tài)下總配送距離發(fā)現(xiàn):FCFS的總距離保持不變,為64.2公里;NN總距離為26.1公里;新優(yōu)化算法RHC-NN的總距離分別是47.9公里、35.2公里、56.3公里。其中TD,TD-r表示總延誤時(shí)間和總延誤時(shí)間降低率,單位是min。以FCFS算法為計(jì)算基礎(chǔ),經(jīng)對(duì)比發(fā)現(xiàn),NN總延誤時(shí)間降低率分別為19.7%,49.3%,43.7%;RHC-NN分別為86.1%,86.3%,94.2%,降低率尤為顯著,具體如表4所示。
表4 三種狀態(tài)的下的仿真實(shí)驗(yàn)結(jié)果對(duì)比
條件相同,算例在兩種頻率下的仿真結(jié)果如表5、表6所示。在P=40%和P=10%的動(dòng)態(tài)擾動(dòng)下,F(xiàn)CFS和NN算法均無(wú)法對(duì)干擾下的訂單進(jìn)行實(shí)時(shí)的路徑優(yōu)化和排序,算法的總配送距離仍然不變;新優(yōu)化算法RHC-NN的總配送距離為50.5公里和42.1公里。
表5 High頻率下各算法配送結(jié)果
注:FCFS、NN、RHC-NN的總延誤分別為1 839.56 min、1 060.21 min、138.08 min,總距離分別為64 193.04 m、26 080.09 m、50 531.75 m。
表6 Low頻率下各算法配送結(jié)果
注:FCFS、NN、RHC-NN的總延誤分別為2 442.55 min、1 453.74 min、141.76 min,總距離分別為64 193.04 m、26 080.09 m、42 138.68 m。
對(duì)比發(fā)現(xiàn),NN、RHC-NN算法對(duì)訂單總延誤時(shí)間的影響如表7所示。NN的總延誤時(shí)間降低率分別為42.4%、40.5%;RHC-NN的總延誤時(shí)間降低率分別達(dá)到了92.5%、94.2%。
表7 兩種頻率的下的仿真實(shí)驗(yàn)結(jié)果對(duì)比
針對(duì)外賣配送中配送路徑規(guī)劃排序問題進(jìn)行建模和算法設(shè)計(jì),將配送服務(wù)時(shí)間分解為多個(gè)時(shí)間域窗口,并能從中篩選出存在著動(dòng)態(tài)擾動(dòng)的訂單,利用求解算法RHC-NN進(jìn)行重新優(yōu)化排序。仿真實(shí)驗(yàn)結(jié)果證明了模型中RHC-NN優(yōu)化的有效性和穩(wěn)定性,更適宜得到應(yīng)用和決策。該研究為動(dòng)態(tài)擾動(dòng)的外賣問題求解提供了一種新思路和可行的策略,但仍需進(jìn)一步在大規(guī)模問題上研究,也為今后求解實(shí)時(shí)動(dòng)態(tài)大規(guī)模、復(fù)雜VRPTW問題提供借鑒。