張玉州，葉 亮，鄭軍帥

(安慶師范大學 計算機與信息學院，安徽 安慶 246133)

0 引 言

外賣O2O(online to offline)[1]已成為現(xiàn)代客戶依賴的主流消費方式，外賣配送實質(zhì)是車輛路徑問題(vehicle routing problem，VRP)的實際應用案例。VRP最早由Dantzig和Ramser[2]于1959年提出，國內(nèi)外學者對VRP問題進行了大量的研究，許多與時間相關(guān)的車輛調(diào)度問題都可歸納為VRP的一類重要拓展，稱為帶時間窗限制車輛路線問題(vehicle routing problems with time windows，VRPTW)[3]，如郵件投遞、應急物資配送等。啟發(fā)式算法是求解此類拓展問題的主要方法，例如節(jié)約法[4]、捕食搜索算法[5]、最近鄰域算法(nearest neighbor algorithm，NN)[6]、遺傳算法[7-8]、禁忌搜索算法[9]等。啟發(fā)式算法的優(yōu)點為具有全局搜索能力，求解效率高，如Kwon等[10]運用禁忌搜索算法求解VRP問題，求解數(shù)在50～100。

近年來，人工智能方法[11-12]在解決組合優(yōu)化問題上得到了充分應用，張建強等[13]利用遺傳算法求解物流配送路徑優(yōu)化問題，戴韜等[14]利用VRP理論考慮了船舶航線規(guī)劃問題，郭月[15]、楊博文[16]等對外賣市場配送發(fā)展進行了分析。滾動時域控制(receding horizon control，RHC)作為一種動態(tài)下在線優(yōu)化控制策略，國內(nèi)外學者也設(shè)計了基于RHC的算法對動態(tài)優(yōu)化問題進行求解[17-20]，驗證了基于RHC策略的合理性和有效性。

綜上所述，隨時間窗推移而發(fā)生的動態(tài)干擾外賣配送問題研究仍然較少。以降低外賣配送總延誤時間為主要目標，文中設(shè)計了一種基于RHC的NN算法(RHC-NN)對問題模型進行求解。實驗結(jié)果證明了訂單在五種不同動態(tài)干擾下用新算法解決問題的有效性，可為平臺商戶節(jié)約成本和提升客戶滿意度提供決策支持。

1 外賣問題建模

1.1 問題描述

針對動態(tài)干擾變化下的某平臺商戶的午餐外賣配送車輛路徑問題，利用滾動時域策略降低動態(tài)干擾，目標是送餐員沿途配送每一位客戶的訂單，并在滿足訂單量需求、配送車輛的承載限制和客戶的預期時間等約束條件下，縮短配送服務(wù)延誤時間，最后在完成所有配送服務(wù)后，返回中心。

1.2 模型建立

1.2.1 模型參數(shù)

涉及的主要參數(shù)如下：

Q：一輛車的車載量；

Mi：每位顧客訂單的需求量；

Tn：車輛配送的最大行駛時間；

En：客戶訂單的最早到達時間；

Fn：客戶訂單最晚到達時間；

N：配送點個數(shù)，其訂單需求記為Mi(i=1,2,…,N)；

cij：表示從點i到點j的運輸成本；

xij：表示車輛從i到j(luò)的配送過程發(fā)生，xij=1；

任務(wù)i最早開始服務(wù)時間為ETi，任務(wù)最晚時間為LTi。

1.2.2 約束條件

結(jié)合外賣配送的問題特點，可對變量描述如下：

(1)只考慮單站點單人單摩托車的配送，單次行駛距離最大為L，配送速度為V；

(2)配送路徑優(yōu)化的目標是行使成本最低，即總延誤時間最小，距離較短；

(3)每輛車的服務(wù)總需求量在該車的承載能力Q以內(nèi)，車輛保持勻速行駛。

1.2.3 建立模型

根據(jù)上述問題描述，動態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標函數(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為目標函數(shù)配送的車輛的運輸費用最??；式2為車輛容量約束，車輛載重貨物總量不得超出承載能力；式3保證整個路徑中不存在局部多余的路徑；式4、式5確保每個顧客都會被配送；式6為需求時間約束；式7為決策變量。

2 基于RHC的最近鄰域算法

2.1 基本思路

FCFS(first come first service)是一種按照訂單產(chǎn)生順序，分配預期配送時間的策略,忽略了配送路線的交叉、往返等問題，配送效率不高，尤其訂單出現(xiàn)隨機變化時，如服務(wù)時間的更改，缺陷更加凸顯。鑒于此，引入滾動時域控制策略，將整個配送時域分成若干等長的時間窗口，根據(jù)最新訂單的時間順序截取客戶進入當前窗口，采用某一優(yōu)化策略進行路徑規(guī)劃、配送，持續(xù)該過程直到所有客戶服務(wù)完畢。考慮到進入窗口內(nèi)的決策客戶數(shù)一般較少，所以文中選取一種性能較好的啟發(fā)式算法—NN對訂單進行排序，RHC與NN進行結(jié)合構(gòu)成RHC-NN算法，對整個時域中的訂單進行排序，以實現(xiàn)運輸費用的最小化。

2.2 RHC

RHC策略將配送時間域H劃分為NW優(yōu)化配送時間窗口，窗口大小為H/NW。將服務(wù)時間落在窗口內(nèi)的訂單組成決策對象集合，對集合內(nèi)需要服務(wù)的決策對象進行優(yōu)化、排序。若決策后對象的服務(wù)時間落在當前時域中，則安排配送，否則留至下一時域窗口等待決策、服務(wù)。當前窗口的訂單處理結(jié)束后，則繼續(xù)進行新時域窗口的在線優(yōu)化，此過程持續(xù)至所有訂單均被服務(wù)。實時更新排序如圖1所示。

圖1 基于RHC的外賣配送全過程

2.3 NN

NN是一種求解速度快的啟發(fā)式算法，以路線距離鄰域最小為最優(yōu)的配送算法能夠拓展當前解的搜索空間。首先是任取一出發(fā)點，依次取最近的點加入當前路線，直至形成回解，其具體步驟如下：

第一步：從待決策對象集合S={c1,c2,…,cp}中任選一對象ci，以其為起點，其中p為當前決策對象數(shù)。令r←ci，且S=S(〗ci}。

第三步：若S≠?，則轉(zhuǎn)第二步繼續(xù)執(zhí)行，否則結(jié)束當前搜索。

該策略無法對動態(tài)擾動的訂單做出應急處理，抗動態(tài)干擾能力較弱，如訂單被要求提前或延遲配送，單一的NN算法無法處理動態(tài)干擾。

2.4 RHC-NN

以最近鄰域算法作為時域上路徑排序的在線優(yōu)化算法，從而基于RHC-NN的具體步驟如下：

第一步：假設(shè)已知NW外賣訂單到達時間，設(shè)置時間間隔長度T與時域上時間間隔總數(shù)NW，初始化時域序號q=1。

第二步：根據(jù)當前外賣訂單信息，由所有計劃到達時間位于[t(q),t(q)+NT]的外賣，構(gòu)成當前時域上的待排序外賣訂單集合S(q)。

第三步：使用最近鄰域算法NN對S(q)中的外賣優(yōu)化排序，篩選出存在動態(tài)擾動的訂單，重新排序。

第四步：根據(jù)優(yōu)化后的排序，給S(q)中的外賣配送服務(wù)時間，將當前時域窗口中的訂單進行配送，其余動態(tài)干擾的訂單分配到后續(xù)窗口中進行配送。

第五步：若所有外賣訂單已送達，則結(jié)束算法。

第六步：更新外賣訂單的相關(guān)信息，q=q+1，轉(zhuǎn)第二步繼續(xù)執(zhí)行。

3 仿真與結(jié)果分析

為驗證模型與設(shè)計算法的真實有效性，對初始訂單分靜態(tài)和動態(tài)進行實驗，靜態(tài)包括正常配送、擁擠配送、非擁擠配送三種狀態(tài)；動態(tài)包括高頻率擾動和低頻率擾動兩種狀態(tài)，并在每種狀態(tài)下使用FCFS、NN和RHC-NN算法分別對算例進行仿真。

3.1 三種狀態(tài)的仿真實驗

其中ON表示初始訂單號、ET表示預期配送時間、AT表示實際配送時間、TW表示時間間隔，三種算法在三種狀態(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。

對比三種狀態(tài)下總配送距離發(fā)現(xiàn)：FCFS的總距離保持不變，為64.2公里；NN總距離為26.1公里；新優(yōu)化算法RHC-NN的總距離分別是47.9公里、35.2公里、56.3公里。其中TD，TD-r表示總延誤時間和總延誤時間降低率，單位是min。以FCFS算法為計算基礎(chǔ)，經(jīng)對比發(fā)現(xiàn)，NN總延誤時間降低率分別為19.7%，49.3%，43.7%；RHC-NN分別為86.1%，86.3%，94.2%，降低率尤為顯著，具體如表4所示。

表4 三種狀態(tài)的下的仿真實驗結(jié)果對比

3.2 兩種頻率的實驗

條件相同，算例在兩種頻率下的仿真結(jié)果如表5、表6所示。在P=40%和P=10%的動態(tài)擾動下，F(xiàn)CFS和NN算法均無法對干擾下的訂單進行實時的路徑優(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。

對比發(fā)現(xiàn)，NN、RHC-NN算法對訂單總延誤時間的影響如表7所示。NN的總延誤時間降低率分別為42.4%、40.5%；RHC-NN的總延誤時間降低率分別達到了92.5%、94.2%。

表7 兩種頻率的下的仿真實驗結(jié)果對比

4 結(jié)束語

針對外賣配送中配送路徑規(guī)劃排序問題進行建模和算法設(shè)計，將配送服務(wù)時間分解為多個時間域窗口，并能從中篩選出存在著動態(tài)擾動的訂單，利用求解算法RHC-NN進行重新優(yōu)化排序。仿真實驗結(jié)果證明了模型中RHC-NN優(yōu)化的有效性和穩(wěn)定性，更適宜得到應用和決策。該研究為動態(tài)擾動的外賣問題求解提供了一種新思路和可行的策略，但仍需進一步在大規(guī)模問題上研究，也為今后求解實時動態(tài)大規(guī)模、復雜VRPTW問題提供借鑒。