帶硬時間窗的O2O 生鮮外賣即時配送路徑優(yōu)化

余海燕 ,唐婉倩 ,吳騰宇

(1.重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院,重慶 400074；2.智能物流網(wǎng)絡(luò)重慶市重點實驗室,重慶 400074；3.重慶郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院,重慶 400065)

受新型冠狀病毒肺炎的影響以及生活水平的不斷提高,人們更傾向足不出戶的購買生鮮,并對生鮮的品質(zhì)和配送效率越來越關(guān)注,這對生鮮企業(yè)在如何平衡生鮮品質(zhì)和配送效率方面提出了更高的配送管理要求。但目前生鮮企業(yè)仍然存在配送效率不高,配送距離過長等問題,嚴(yán)重影響生鮮的品質(zhì),因此,如何保證在既定時間內(nèi)送達(dá)的同時降低即時配送的成本是值得研究的現(xiàn)實問題。

線上線下(Online To Offline,O2O)生鮮外賣即時配送的一般過程可以描述為：客戶在盒馬鮮生、京東生鮮等外賣平臺下單,平臺接收訂單后,系統(tǒng)將會根據(jù)客戶的時間窗、配送員位置及送貨地點,分配訂單給相應(yīng)的配送員,配送員有車容量限制并且需要在每個客戶的最晚送達(dá)時間內(nèi)送達(dá),在配送員服務(wù)完他所需服務(wù)的客戶后返回配送中心。在上述過程中,需求訂單實時產(chǎn)生,每個訂單有相應(yīng)的硬時間窗,平臺只有在該需求訂單出現(xiàn)時才獲知該訂單的信息,而平臺需要根據(jù)實時的訂單信息進(jìn)行車輛調(diào)度和路徑規(guī)劃,保證在最晚送達(dá)時間內(nèi)送達(dá)?？紤]到需求訂單實時產(chǎn)生、配送員位置分散、客戶具有不同時間窗且必須在最晚時間內(nèi)送達(dá)等特點,研究以配送距離最短為目標(biāo)的O2O 生鮮外賣即時配送路徑優(yōu)化問題。

與帶硬時間窗的O2O 生鮮外賣即時配送路徑優(yōu)化問題相關(guān)的文獻(xiàn)包括帶取送貨的動態(tài)車輛路徑問題(Dynamic Vehicle Routing Problem with Pickup and Delivery,DVRPPD)和帶時間窗的車輛路徑問題(Vehicle Routing Problem with Time Window,VRPTW)。

帶取送貨的車輛路徑問題(Vehicle Routing Problem with Pickup and Delivery,VRPPD)是在車輛路徑問題(VRP)中加入取送貨作業(yè),屬于一類特殊的VRP,由Min[1]提出。根據(jù)需求信息是提前已知或是實時出現(xiàn)的,VRPPD 又可分為帶取送貨的動態(tài)車輛路徑問題和帶取送貨的靜態(tài)車輛路徑問題。在已有的VRPPD 研究中,大多數(shù)學(xué)者的研究都是靜態(tài)的。生鮮外賣即時配送路徑優(yōu)化問題由于訂單需求實時特性和配送員的動態(tài)性,更類似于動態(tài)VRPPD。動態(tài)VRPPD 由Psaraftis[2]提出并與靜態(tài)VRP 對比進(jìn)行前景分析與展望。動態(tài)VRPPD 著重考慮對于實時信息的處理,由于需求的動態(tài)性,難以用精確方法求解,很難找到其最優(yōu)解,故學(xué)者們往往采用智能算法求解,如遺傳算法[3-4]、粒子群算法[5-6]以及蟻群算法[7-8]等。對上述關(guān)于DVRPPD 的研究鮮少針對帶硬時間窗的生鮮配送問題進(jìn)行研究。

隨著VRP 的發(fā)展,許多學(xué)者開始把時間約束加入到VRP中,提出了VRPTW,VRPTW 是VRP的一個重要分支。根據(jù)時間窗的特點,VRPTW 可分為帶硬時間窗的車輛路徑問題和帶軟時間窗的車輛路徑問題。其中,對于帶硬時間窗的車輛路徑問題,大多選用現(xiàn)代啟發(fā)式算法[9-10]求解。對于帶軟時間窗的車輛路徑問題的研究有：葛顯龍等[11]考慮碳排放,建立帶軟時間窗的多車車輛路徑模型,設(shè)計混合遺傳算法從而降低成本；吳瑤等[12]針對易腐產(chǎn)品,考慮交付產(chǎn)品時的價值損耗,建立時變網(wǎng)絡(luò)下的交付時間窗模型,并設(shè)計混合遺傳算法求解；張建同等[13]考慮不同時段的車速,建立時變的帶時間窗的車輛路徑模型,設(shè)計變鄰域模擬退火算法求解該模型；Gyorgyi等[14]提出帶時間窗的動態(tài)隨機(jī)取送貨問題,考慮時間窗的不確定性,解決了單個決策點的最小成本流問題；Zulvia等[15]建立帶時間窗的易腐產(chǎn)品綠色VRP 模型,考慮對運(yùn)營成本、劣化成本、碳排放和顧客滿意度的優(yōu)化,并設(shè)計多目標(biāo)梯度進(jìn)化算法求解該模型。上述VRPTW 的相關(guān)研究為本文的時間窗的處理與路徑優(yōu)化算法的設(shè)計提供了重要參考,但是其中未考慮到訂單的即時調(diào)度特性。

已有研究對帶時間窗的車輛路徑問題和帶取送貨的動態(tài)車輛路徑問題進(jìn)行了充分研究,但對基于數(shù)據(jù)的動態(tài)實時出現(xiàn)的帶時間窗的生鮮配送訂單分配和路徑優(yōu)化研究還不足。并且,以往研究模型不適宜本文研究的問題,因此建立原創(chuàng)性的模型加以研究。本文針對生鮮農(nóng)產(chǎn)品新鮮度要求高、時效性強(qiáng)等特點,考慮訂單的動態(tài)性、硬時間窗等因素,以配送路徑最短為優(yōu)化目標(biāo),建立帶硬時間窗的即時配送模型,并設(shè)計滾動時域延遲配送算法求解該模型。最后,通過大量數(shù)值仿真研究驗證該算法的有效性,并對滾動時域時長、時間窗時間間隔、配送員數(shù)量及車容量等參數(shù)進(jìn)行敏感性分析,為生鮮企業(yè)的配送策略選擇提供參考。下文將從問題描述、建模、提出滾動時域延遲配送算法、仿真結(jié)果分析及結(jié)論等方面來論述。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

假設(shè)在一個O2O 生鮮外賣平臺上,如盒馬鮮生等商家自有平臺,客戶可以在平臺上實時下單,每個客戶需求訂單都要求在一定的時間范圍內(nèi)送貨上門,即每個訂單具有一個固定的時間窗且每個訂單的需求量為1,同時眾包配送員為生鮮外賣訂單提供即時配送服務(wù)。需求訂單實時出現(xiàn)后,平臺系統(tǒng)根據(jù)一定的規(guī)則分配訂單給配送員。初始狀態(tài)下配送員隨機(jī)分布在某一區(qū)域內(nèi),配送員接受訂單后,需要在配送中心取貨,取貨點始終在配送中心,且只有一個配送中心。一個配送員可以服務(wù)多個客戶(一對多),最大載重量為配送員的最大容量C,每個客戶只能被服務(wù)一次,配送車輛相同,配送員均以速度v行進(jìn),配送員需要在服務(wù)完他所需要服務(wù)的訂單后返回配送中心,并且需要保證在最晚配送時間范圍內(nèi),送至某一區(qū)域的不同客戶手中。問題是,如何進(jìn)行實時的訂單分配和路徑規(guī)劃使得所有配送員的配送距離最短。

該問題中訂單的實時動態(tài)性為理論模型的建立增加了難度,為了更清晰地描述訂單的實時出現(xiàn)和動態(tài)分配過程,本文將連續(xù)時間進(jìn)行離散化處理。如圖1所示,時刻1產(chǎn)生訂單O1、O2,生鮮外賣平臺獲知包括其時間窗、送貨點位置在內(nèi)的所有訂單信息,而對未來即將出現(xiàn)的訂單信息未知,此時生鮮外賣平臺需要決策是否進(jìn)行訂單分配與路徑規(guī)劃。若平臺決定暫時不進(jìn)行訂單分配,等到下一時刻再進(jìn)行決策。在時刻2產(chǎn)生新的訂單O3、O4和O5,并獲知相應(yīng)的訂單信息,此時生鮮外賣平臺又需要進(jìn)行決策。例如其可以將之前產(chǎn)生的所有訂單分配給配送員1并進(jìn)行如圖1所示的配送路線規(guī)劃。根據(jù)圖1表現(xiàn)出的對動態(tài)信息的處理及硬時間窗的要求,可以構(gòu)建如下模型。

圖1 配送路線圖

1.2 符號說明

G=(V,E)——網(wǎng)絡(luò)圖,訂單需求點均位于網(wǎng)絡(luò)圖G上,其中,頂點集合V={v1,v2,…,vn1},邊集合E={e1,e2,…,en2}

l(vi,vj)——網(wǎng)絡(luò)圖中vi與vj之間的距離

u0——為取貨點(配送中心)

σ={O1,O2,…,On}——訂單序列,共有n個訂單

Oi=(ri,di,LTi)——訂單,其中：ri為需求訂單的釋放時間；di∈V表示訂單位置；LTi為訂單Oi允許的最晚送達(dá)時間,i∈I={1,2,…,n}

t∈T——當(dāng)前時間t,將其視為離散數(shù)據(jù),T為當(dāng)前時間的集合

k∈K——配送員k,K為所有配送員的集合

C——配送員的容量

v——配送員的行駛速度

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

決策變量

xikt——訂單Oi在時刻t是否正在由配送員k服務(wù),1為是,0為否。正在服務(wù)的含義已經(jīng)將訂單Oi分配給配送員k,但還未完成服務(wù)

1.3 即時調(diào)度模型

在上述模型中,式(1)表示總行駛距離最小的目標(biāo)函數(shù),式(2)～(4)為訂單約束,其中：式(2)保證每個訂單由且僅由一個配送員服務(wù)；式(3)保證每個訂單最多由一個配送員服務(wù)；式(4)保證當(dāng)訂單Oi分配給配送員k且路徑被選中時,xikt的值在訂單Oi的服務(wù)時間段內(nèi)都取1；式(5)為時間窗約束,訂單Oi的實際送達(dá)時間不早于訂單Oi的釋放時間,不晚于訂單Oi允許的服務(wù)最晚送達(dá)時間。式(6)～(8)為配送員約束,其中：式(6)保證每個配送員每個時刻正在服務(wù)的訂單數(shù)不超過其最大容量；式(7)保證每個配送員僅選取一條配送路徑；式(8)保證只有當(dāng)訂單Oi分配給配送員k時,訂單Oi才會出現(xiàn)在配送員k的路徑上。式(9)～(13)為路徑約束,其中：式(9)保證只有當(dāng)訂單Oi在配送員k的第j條路徑上時,訂單Oi在路徑中的送達(dá)時間才不為0；式(10)保證每個訂單的取貨時間早于其送貨時間；式(11)保證每個訂單的取貨時間晚于其釋放時間；式(12)、(13)表示在路徑中訂單的取貨與送貨時間不早于配送員按速度v行駛能到達(dá)其取貨點和送貨點的最早時間,配送員在行駛途中可以等待,故其到達(dá)時間可能晚于其最早可能的到達(dá)時間。式(14)～(17)為變量約束,其中：式(14)表示在路徑中訂單Oi的實際送達(dá)時間,若訂單Oi不在路徑則為0；式(15)表示訂單Oi的實際取貨時間；式(16)保證當(dāng)訂單取貨后且服務(wù)完成之前決策變量xikt才能取1；式(17)為決策變量的約束。

上述建立的帶硬時間窗的O2O 生鮮外賣即時配送路徑優(yōu)化模型中,由于訂單的釋放時間ri是無法提前獲知的,即該問題是一個實時調(diào)度問題,無法采用最優(yōu)算法對該問題進(jìn)行求解,故設(shè)計基于滾動時域的延遲配送算法用于解決該實時調(diào)度問題,與滾動時域非延遲配送算法對比,并用數(shù)值仿真方法進(jìn)行研究。

2 求解算法

下面將給出滾動時域延遲配送算法和滾動時域非延遲配送算法,通過分析各種參數(shù)的變化對目標(biāo)函數(shù)值的影響,對比兩種算法的有效性和適用性。

2.1 滾動時域延遲配送算法

滾動時域延遲配送算法的思路：每間隔一段時間重新進(jìn)行訂單分配與路徑規(guī)劃,每次重新規(guī)劃時,在每個訂單的時間窗約束下盡量推遲訂單的分配,以保證有更多的訂單可以進(jìn)行合并配送。算法步驟如下：

(1)初始化信息,等待滾動時域時長分鐘,更新待服務(wù)訂單集合后轉(zhuǎn)步驟(2)。

(2)判斷下一個時域訂單是否超過最晚送達(dá)時間,若是,則轉(zhuǎn)步驟(3)；若否,則轉(zhuǎn)步驟(4)。

(3)計算下一個時域即將超過最晚送達(dá)時間的訂單數(shù)量,若此訂單數(shù)量小于等于一輛車的車容量,則分配給距離配送中心最近的配送員,再調(diào)用TSP模型,進(jìn)行路徑優(yōu)化；若此訂單數(shù)量大于每輛車車容量,則分配給距離配送中心最近的(訂單數(shù)/車容量)個配送員,再調(diào)用VRP模型進(jìn)行訂單分配和路徑優(yōu)化。

(4)進(jìn)入下一個時域,更新所有訂單及配送員信息,輸出在當(dāng)前時間的訂單信息、配送員信息、最優(yōu)路徑和目標(biāo)函數(shù)值。

(5)最后判斷是否有未服務(wù)的訂單,若是,則轉(zhuǎn)步驟(2)；若否,則結(jié)束。

2.2 滾動時域非延遲配送算法

滾動時域非延遲配送算法的思路：每間隔一段時間重新進(jìn)行訂單分配與路徑規(guī)劃,每次重新規(guī)劃時,在每個訂單的時間窗約束下分配,保證訂單在時間窗范圍內(nèi)送達(dá)。算法步驟如下：

天脊集團(tuán)是社會的一分子，是社會哺育了天脊，發(fā)展的天脊更要反哺社會。30多年的發(fā)展，天脊集團(tuán)培養(yǎng)了大批技術(shù)人才、管理人才貢獻(xiàn)中國煤化工事業(yè)。從天脊集團(tuán)走進(jìn)科研院所、走向全國大型煤化工企業(yè)高管團(tuán)隊的優(yōu)秀人才達(dá)300人以上。

(1)初始化信息,等待滾動時域時長分鐘,更新待服務(wù)訂單集合后轉(zhuǎn)步驟(2)。

(2)判斷當(dāng)前時間,訂單是否在時間窗內(nèi),若是,則轉(zhuǎn)步驟(3)；若否,則轉(zhuǎn)步驟(4)。

(3)計算在時間窗內(nèi)的訂單數(shù)量,若此訂單數(shù)量小于等于一輛車的車容量,則分配給距離配送中心最近的配送員,再調(diào)用TSP模型,進(jìn)行路徑優(yōu)化；若此訂單數(shù)量大于每輛車車容量,則分配給距離配送中心最近的盡量少個配送員,再調(diào)用VRP 模型進(jìn)行訂單分配和路徑優(yōu)化。

(4)進(jìn)入下一個時域,更新所有訂單及配送員信息,輸出在當(dāng)前時間的訂單信息、配送員信息、最優(yōu)路徑和目標(biāo)函數(shù)值。

(5)最后判斷是否有未服務(wù)的訂單,若是,則轉(zhuǎn)步驟(2)；若否,則結(jié)束。

利用專業(yè)的數(shù)學(xué)仿真軟件對兩種算法進(jìn)行仿真研究,仿真流程如圖2所示。

圖2 滾動時域延遲配送算法和滾動時域非延遲配送算法仿真流程圖

滾動時域延遲配送算法著重考慮：①對動態(tài)信息的處理。訂單出現(xiàn)后判斷此訂單在下一個時域是否超過最晚送達(dá)時間,若超過則需立即配送,沒有超過則等待下一次更新,并且以是否有未服務(wù)的訂單為整個程序結(jié)束的條件。②訂單分配和路徑優(yōu)化。根據(jù)訂單數(shù)量、車容量和配送員距離配送中心的距離進(jìn)行訂單分配,并且調(diào)用TSP或VRP模型進(jìn)行路徑優(yōu)化。而滾動時域非延遲配送算法考慮在時間窗范圍內(nèi)送達(dá),不必盡量推遲訂單的分配。根據(jù)上述兩種算法仿真流程圖進(jìn)行仿真,因此有如下仿真研究。

3 仿真研究

采用滾動時域延遲配送算法和非延遲配送算法,選取實際網(wǎng)絡(luò)和一般網(wǎng)絡(luò)進(jìn)行對比,說明其有效性。通過變化滾動時域時長、時間窗時間間隔、車容量及訂單數(shù)量等參數(shù),觀察平均每單配送距離的變化,進(jìn)行適用性分析并得出結(jié)論。

3.1 有效性分析

為了研究兩種算法在不同網(wǎng)絡(luò)下的有效性,選取兩種具有代表性的網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行對比分析：

(1)以重慶市南岸區(qū)盒馬鮮生(南湖路店)為配送中心,向周圍輻射3 km,選取真實住宅小區(qū)的地理位置,如圖3所示。

圖3 真實住宅小區(qū)的地理位置圖

考慮到客戶下單的可能性,選取離配送中心1 km內(nèi)的小區(qū)25個,離配送中心1～2 km 內(nèi)的小區(qū)15個,離配送中心2～3 km 內(nèi)的小區(qū)10個作為需求點。通過專業(yè)的數(shù)學(xué)仿真軟件對滾動時域延遲配送算法和非延遲配送算法進(jìn)行編程,其中,仿真時間為120 min,配送員數(shù)量為50,車容量為10,時間窗時間間隔為30,滾動時域時長取15～35 min,間隔5 min觀察其變化,每輪數(shù)據(jù)仿真50次,取平均值,得到目標(biāo)函數(shù)值。由表1和圖4可以看出,配送員數(shù)量為50,車容量為10,滾動時域時長為25 min,當(dāng)時間窗時間間隔為30時,滾動時域延遲配送算法平均每單配送距離為1.378 8 km。滾動時域非延遲配送算法平均每單配送距離逐漸減少。

(2)隨機(jī)生成一個仿真網(wǎng)絡(luò),以一配送中心為原點,半徑為3 km 的圓內(nèi)均勻生成50個客戶點及客戶的時間窗。通過專業(yè)的數(shù)學(xué)仿真軟件對滾動時域延遲配送算法和非延遲配送算法進(jìn)行編程,仿真時間為120 min,其中,配送員數(shù)量為50,車容量為10,時間窗時間間隔為30,滾動時域時長取15～35 min,間隔5 min觀察其變化,每輪數(shù)據(jù)仿真50次,取平均值,得到目標(biāo)函數(shù)值。由表1和圖4可以看出,配送員數(shù)量為50,車容量為10,滾動時域時長為25 min,當(dāng)時間窗時間間隔為30時,滾動時域延遲配送算法平均每單配送距離為1.050 9 km。滾動時域非延遲配送算法平均每單配送距離逐漸減少。

表1 不同網(wǎng)絡(luò)下平均每單配送距離變化表

圖4 不同網(wǎng)絡(luò)下訂單平均每單配送距離變化圖

結(jié)論1隨著滾動時域時長的增加,滾動時域延遲配送算法的平均每單配送距離先增大后減小,中間出現(xiàn)平均每單配送距離的最大值。滾動時域非延遲配送算法的平均每單配送距離逐漸減小。

由表1和圖4可知,兩種網(wǎng)絡(luò)的仿真結(jié)果所得的平均每單的配送距離與實際相符,從而驗證了本仿真系統(tǒng)和算法的有效性。對于滾動時域延遲配送算法,隨著滾動時域時長的增加,平均每單配送距離都是先增大后減小,當(dāng)滾動時域時長為15 min時,平均每單配送距離達(dá)到最大值,并且兩種網(wǎng)絡(luò)的最大值相差不大,在誤差范圍內(nèi)。出現(xiàn)這種結(jié)果是因為滾動時域時長如果越短,訂單將會一直等待,直到累積到一定數(shù)量的訂單再進(jìn)行配送,避免一單一送,一個配送員配送更多的貨物,平均每單配送距離會越小。滾動時域時長如果越長,累積更多的訂單,一個配送員也會配送更多的貨物,平均每單配送距離會越小。對于滾動時域非延遲配送算法,隨著滾動時域時長的增加,平均每單配送距離逐漸減少,這是因為不考慮盡量推遲訂單的分配,累積的訂單沒有滾動時域延遲配送算法的訂單多,滾動時域時長越長,集合訂單一起配送,每單配送距離越短。但滾動時域時長越長,會影響生鮮的品質(zhì)。因此,從生鮮品質(zhì)和平均每單距離綜合考慮,滾動時域延遲配送算法優(yōu)于非延遲配送算法。下面選取一般網(wǎng)絡(luò)“配送員數(shù)量為50,車容量為10,滾動時域時長為25,時間窗時間間隔為30”作為標(biāo)準(zhǔn)案例進(jìn)行適用性分析。

3.2 適用性分析

適用性分析的目的是找出影響目標(biāo)函數(shù)的因素,分析變動的原因,確定其影響的程度。此適用性分析將上述一般網(wǎng)絡(luò)“配送員數(shù)量為50,車容量為10,滾動時域時長為25,時間窗時間間隔為30”作為標(biāo)準(zhǔn)案例,基于標(biāo)準(zhǔn)案例,調(diào)整算法中的某些參數(shù),包括時間窗時間間隔、車容量及訂單數(shù)量,觀察對平均每單配送距離的影響。

結(jié)論2隨著時間窗時間間隔的增加,滾動時域延遲配送算法的平均每單配送距離趨于穩(wěn)定,最大值與最小值相差6.3%。滾動時域非延遲配送算法的平均每單配送距離逐漸減少。

出現(xiàn)這種結(jié)果是因為滾動時域延遲配送算法只考慮了在最晚送達(dá)時間內(nèi)送達(dá),是單邊時間窗,時間窗間隔的變化對平均每單配送距離影響較小。而滾動時域非延遲配送算法的平均每單配送距離逐漸減少,因為滾動時域時長越長,集合訂單一起配送,每單配送距離越短,但此算法在時間窗內(nèi)都可以配送,累積的訂單比滾動時域延遲配送算法的訂單少,需要比滾動時域延遲配送算法派出的配送員多,所以整體比滾動時域延遲配送算法的平均每單配送距離大。

結(jié)論3在兩種算法下,車容量越大,平均每單配送距離越小。

由表2和圖5可以看出,兩種算法的平均每單配送距離減速較為穩(wěn)定,由此可知,車容量越大,配送員一次帶的量越大,可能有時只需一個配送員就可以配送完成,所以平均每單配送距離越短。整體來看,滾動時域非延遲配送算法比延遲配送算法的平均每單配送距離大。

表2 各參數(shù)影響訂單平均每單配送距離表 km

圖5 各參數(shù)影響訂單平均每單配送距離圖

結(jié)論4隨著單位時間內(nèi)訂單數(shù)量的增加,滾動時域延遲配送算法的平均每單配送距離逐漸穩(wěn)定。滾動時域非延遲配送算法的平均每單配送距離逐漸減少。

由表2和圖5可以看出,滾動時域延遲配送算法在訂單數(shù)很少時,積累的訂單數(shù)不夠多,會出現(xiàn)一單一送的情況,所以此時平均每單配送距離很大,隨著訂單數(shù)量的增加,積累的訂單數(shù)足夠多,合單配送,平均每單配送距離逐漸穩(wěn)定。滾動時域非延遲配送算法的平均每單配送距離逐漸減少,這是因為訂單數(shù)量越多,合單配送,平均每單的配送距離越小。整體來看,滾動時域非延遲配送算法比延遲配送算法的平均每單配送距離大。

上述結(jié)論可為生鮮外賣平臺的配送策略提供參考,可保證在最晚送達(dá)時間內(nèi)送達(dá)的同時,選擇最優(yōu)路徑。并且,可得出生鮮外賣平臺的管理啟示：

(1)平臺的調(diào)度算法應(yīng)該選取合適的滾動時域時長,不宜選取中間數(shù)值。

(2)在實際允許的情況下,盡可能增加每輛車的車容量。

(3)在生鮮外賣點單高峰期,即單位時間內(nèi)訂單數(shù)量較多時,采用滾動時域延遲配送算法比較合適。

(4)基于對生鮮品質(zhì)和每單配送距離的綜合考慮,選擇滾動時域延遲配送算法比較合適。

4 結(jié)語

針對生鮮農(nóng)產(chǎn)品新鮮度要求高和時效性強(qiáng)的特點,對帶硬時間窗的O2O 生鮮外賣即時配送路徑優(yōu)化問題進(jìn)行了研究,考慮動態(tài)的訂單需求、訂單的滾動時域時長以及客戶時間窗等因素,以配送總距離最小為優(yōu)化目標(biāo),建立帶硬時間窗的即時配送模型,并設(shè)計更適應(yīng)該問題的滾動時域延遲配送算法求解該模型。通過大量數(shù)值仿真研究驗證兩種算法的有效性,并且發(fā)現(xiàn)：在滾動時域延遲配送算法下,隨著滾動時域時長的增加,平均每單配送距離先增大后減小,中間出現(xiàn)平均每單配送距離的最大值。隨著時間窗時間間隔的增加,平均每單配送距離趨于穩(wěn)定。車容量越大,平均每單配送距離越小。隨著單位時間內(nèi)訂單數(shù)量的增加,平均每單配送距離逐漸穩(wěn)定。滾動時域時長、車容量及訂單數(shù)量等變量均對目標(biāo)函數(shù)值有較大影響。該模型可以有效的用于優(yōu)化路徑,保證在最晚送達(dá)時間內(nèi)送達(dá)的同時,使配送員盡可能多拿訂單,針對該模型的滾動時域延遲配送算法取得了良好的結(jié)果,整體平均每單配送距離比滾動時域非延遲配送算法小,可為生鮮企業(yè)的配送提供參考。

在實際應(yīng)用中,生鮮外賣平臺采用的算法應(yīng)選擇合適的滾動時域時長,要滿足客戶更短的送達(dá)時間要求,需要付出的配送成本將會增加,要降低配送成本可適當(dāng)延長承諾的最短送達(dá)時間,為了降低配送距離及其成本可以增大每個配送員的車容量。進(jìn)一步,還可以考慮每個客戶時間窗時間間隔不同和每個客戶需求量不同的情形下,生鮮外賣即時配送路徑優(yōu)化問題。