帶硬時間窗的O2O 生鮮外賣即時配送路徑優化

余海燕 ,唐婉倩 ,吳騰宇

(1.重慶交通大學 經濟與管理學院,重慶 400074；2.智能物流網絡重慶市重點實驗室,重慶 400074；3.重慶郵電大學 經濟管理學院,重慶 400065)

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

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

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

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

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

1 問題描述及數學模型

1.1 問題描述

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

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

圖1 配送路線圖

1.2 符號說明

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

l(vi,vj)——網絡圖中vi與vj之間的距離

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

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

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

t∈T——當前時間t,將其視為離散數據,T為當前時間的集合

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

C——配送員的容量

v——配送員的行駛速度

M——足夠大的正數

決策變量

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

1.3 即時調度模型

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

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

2 求解算法

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

2.1 滾動時域延遲配送算法

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

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

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

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

(4)進入下一個時域,更新所有訂單及配送員信息,輸出在當前時間的訂單信息、配送員信息、最優路徑和目標函數值。

(5)最后判斷是否有未服務的訂單,若是,則轉步驟(2)；若否,則結束。

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

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

天脊集團是社會的一分子，是社會哺育了天脊，發展的天脊更要反哺社會。30多年的發展，天脊集團培養了大批技術人才、管理人才貢獻中國煤化工事業。從天脊集團走進科研院所、走向全國大型煤化工企業高管團隊的優秀人才達300人以上。

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

(2)判斷當前時間,訂單是否在時間窗內,若是,則轉步驟(3)；若否,則轉步驟(4)。

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

(4)進入下一個時域,更新所有訂單及配送員信息,輸出在當前時間的訂單信息、配送員信息、最優路徑和目標函數值。

(5)最后判斷是否有未服務的訂單,若是,則轉步驟(2)；若否,則結束。

利用專業的數學仿真軟件對兩種算法進行仿真研究,仿真流程如圖2所示。

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

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

3 仿真研究

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

3.1 有效性分析

為了研究兩種算法在不同網絡下的有效性,選取兩種具有代表性的網絡數據進行對比分析：

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

圖3 真實住宅小區的地理位置圖

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

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

表1 不同網絡下平均每單配送距離變化表

圖4 不同網絡下訂單平均每單配送距離變化圖

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

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

3.2 適用性分析

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

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

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

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

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

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

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

結論4隨著單位時間內訂單數量的增加,滾動時域延遲配送算法的平均每單配送距離逐漸穩定。滾動時域非延遲配送算法的平均每單配送距離逐漸減少。

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

上述結論可為生鮮外賣平臺的配送策略提供參考,可保證在最晚送達時間內送達的同時,選擇最優路徑。并且,可得出生鮮外賣平臺的管理啟示：

(1)平臺的調度算法應該選取合適的滾動時域時長,不宜選取中間數值。

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

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

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

4 結語

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

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