基于雙節(jié)點時間窗的外賣配送路徑優(yōu)化研究

王海燕 戴 雪

(福州大學(xué)經(jīng)濟與管理學(xué)院， 福建福州 350108)

一、引言

隨著通信基礎(chǔ)設(shè)施的完善和移動互聯(lián)網(wǎng)的迅猛發(fā)展，截至2020年6月，手機上網(wǎng)人數(shù)達9.32億，占網(wǎng)民比99.2%。[1]移動支付和移動導(dǎo)航為外賣行業(yè)的發(fā)展奠定了技術(shù)和設(shè)施根基，外賣服務(wù)己深入大眾生活。外賣也由原來的高補貼搶占用戶和商家戰(zhàn)略轉(zhuǎn)移到提高服務(wù)質(zhì)量上來。配送人員由經(jīng)驗自行規(guī)劃配送路徑會導(dǎo)致顧客不滿意，并且配送人員會因此受到懲罰，外賣平臺流失客源風(fēng)險增加、商家訂單量也可能隨之減少。因此，為外賣規(guī)劃最優(yōu)的配送路徑具有現(xiàn)實意義。

在外賣行業(yè)相關(guān)問題研究方面，學(xué)者從外賣行業(yè)發(fā)展現(xiàn)狀、平臺商業(yè)模式、消費者行為、食品安全等問題展開探索。敬小玲等通過SWOT分析法，總結(jié)了外賣行業(yè)的優(yōu)勢、劣勢以及目前所存在的問題。[2]趙雪冉和孫永波對外賣平臺商業(yè)模式的內(nèi)涵及特征進行了論述，并分析了目前平臺發(fā)展存在的問題以及外賣閉環(huán)關(guān)鍵因素，為外賣平臺的進一步發(fā)展提出了相關(guān)建議。[3]Yeo et.al,Hu & Chen從消費者滿意度水平方面進行了分析。[4][5]取送貨問題最早由Desaulniers等在2002年正式給出定義和數(shù)學(xué)模型，并用啟發(fā)式算法進行求解。[6]Soumia I等在車輛路徑問題中首次引入時間窗概念。[7]Landrieu等研究了禁忌搜索算法求解單一車輛的帶時間窗的取送貨問題。[8]余建軍等在生鮮外賣配送路徑研究中，引入災(zāi)變操作的遺傳算法與節(jié)約里程算法進行對比，結(jié)果表明改進的遺傳算法可以得到更優(yōu)的組合。[9]

在考慮滿足顧客時間窗的外賣配送路徑優(yōu)化研究中，劉旺盛等、李萍等、李桃迎等均在目標函數(shù)中考慮顧客節(jié)點超時而產(chǎn)生的成本。[10][11][12]而實際情況中，有些銷量多，名氣大的商家有權(quán)要求配送員在規(guī)定時間內(nèi)到達商家點取餐，以保證外賣送達到顧客手中的口感。因此，本文考慮商家和顧客雙節(jié)點時間窗的外賣配送車輛路徑研究，建立車輛運輸成本和雙節(jié)點時間懲罰成本為目標的模型，針對外賣先取餐后送餐、時間窗約束、載重約束、商家和客戶節(jié)點配對的關(guān)系，設(shè)計符合外賣配送情景的遺傳算法對外賣配送路徑進行優(yōu)化。

二、問題描述和模型構(gòu)建

(一)問題描述

在外賣配送的過程中，配送員從配送中心出發(fā)，去往商家節(jié)點取餐，途經(jīng)所有訂單的取送餐節(jié)點，且同一訂單先取餐后送餐，訂單重量不能超過最大載重量，最后從顧客節(jié)點還回配送中心。如果配送員超時到達商家節(jié)點或顧客節(jié)點，均要承擔(dān)一定的懲罰成本。因此，平臺應(yīng)優(yōu)化配送路徑，盡可能讓配送員在時間窗內(nèi)到達取送餐節(jié)點，使成本之和達到最小。

在實際情況中,外賣配送中存在一對多的情形,包括多名顧客向一家商家下單和一名顧客同時向多家商家下單，這大大增加了模型的復(fù)雜性。因此設(shè)立虛擬點對顧客和商家點需求進行拆分，使得商家節(jié)點和顧客節(jié)點一一對應(yīng)。如圖1左邊，原先顧客1、2向商家1下單，顧客3向商家2、3下訂單，出現(xiàn)顧客和商家一對多、多對一情形。引入虛擬點，讓每筆訂單都只有一對一的商家和顧客。商家1的虛擬點為商家4，顧客3的虛擬點為顧客4，如圖1右邊所示，使同一訂單中商家和顧客達到一一對應(yīng)，簡化模型。

圖1 虛擬點示意

(二)問題假設(shè)

1. 所有配送車輛一樣，即各類參數(shù)(電壓、載重量、功率、最大行駛里程等)相同。

2. 配送車輛勻速行駛，不考慮天氣、交通等特殊情況影響。

3. 配送車輛無最大行駛里程約束。

4. 每份外賣重量已知。

5. 配送中心、顧客、商家的位置已知及其之間為歐式距離。

6. 不考慮特殊訂單，比如單個訂單的重量超過配送車輛的最大載重量。

7. 為確認騎手能準點出發(fā)，準時上班，騎手應(yīng)先去配送中心集合再開始前往商家點取餐進行配送。

(三)符號定義

A={2,4,6,8,…,2n}：表示所有商家節(jié)點(包括虛擬商家節(jié)點)集合。

B={3,5,7,…,2n+1}：表示顧客節(jié)點(包括虛擬顧客節(jié)點)集合。訂單數(shù)為n，訂單取送餐節(jié)點配對點為{(2,3),(4,5),(6,7),…,(2n,2n+1)}。

N=A∪B:商家節(jié)點和顧客節(jié)點集合。

C={1}∪A∪B：表示所有點集合，1表示配送中心。

K={1,2,3,…,m}:表示配送車輛集合，k∈K。

ETik：平臺規(guī)定配送車輛k到達節(jié)點i的預(yù)計時間，i∈N。

tik:配送車輛k到達節(jié)點i的實際時間，i∈N。

Tik:表示配送車輛k在節(jié)點i處的服務(wù)時間;i∈N。

dij:表示節(jié)點i與節(jié)點j之間的距離;i∈C,j∈C。

vk:表示配送車輛k平均配送速度;k∈K。

tijk:表示配送車輛k從節(jié)點i到節(jié)點j的行駛時間，tijk=dij/vk，i∈C,j∈C,k∈K。

bi：顧客點i的送餐量，i∈B。

di：商家點j的取餐量，j∈A。

wijk：配送車輛從離開節(jié)點i之后到達節(jié)點j之前的載重量，i∈N,j∈N,k∈K。

Q:表示配送車輛的最大裝載量。

e:表示配送車輛單位距離的運輸成本。

c1:在取餐節(jié)點超時的單位時間懲罰成本。

c2：在送餐節(jié)點超時t分鐘內(nèi)的單位時間懲罰成本。

c3：在送餐節(jié)點超時t分鐘外的單位時間懲罰成本，c3>c2。

決策變量：

(四)模型構(gòu)建

從外賣平臺的角度考慮，建立車輛運輸成本和時間懲罰成本為目標的模型。

(1)車輛運輸成本：

(1)

(2)時間懲罰成本：對于取餐節(jié)點超時，超時越長，懲罰成本越大；而送餐節(jié)點超時存在兩種情況，超時在t分鐘內(nèi)(一般超時)，處于顧客可容忍的時間范圍，此時單位時間懲罰成本為c2，而超時超過t分鐘外(嚴重超時)，顧客不滿意度加強，此時單位時間懲罰成本為c3(c3>c2)。因此所有訂單在取餐節(jié)點以及送餐節(jié)點超出規(guī)定達到時間而產(chǎn)生的成本之和表達式為：

(2)

目標函數(shù)：

(3)

約束條件：

式(4)表示每筆訂單僅被一輛配送車輛服務(wù)一次；式(5)表示一筆訂單的取送餐只能由一輛車輛k完成；式(6)表示先取餐后送餐；式(7)表示車輛動態(tài)載重平衡；式(8)表示最大載重約束；式(9)表示配送車輛k的取送餐總量相等；式(10)表示配送車輛在每個節(jié)點時間計算式；式(11)表示配送車輛k從配送中心出發(fā)到達的下一個節(jié)點必須是去商家節(jié)點取餐，最終必須從顧客節(jié)點回到配送中心。

三、求解模型的遺傳算法設(shè)計

Step1 編碼生產(chǎn)：采用自然數(shù)編碼，把商家和顧客點按照不重復(fù)的自然數(shù)隨機排列。商家和顧客經(jīng)過虛擬化處理后，設(shè)訂單數(shù)為n，則商家和顧客點都為n，設(shè)商家點集合為偶數(shù)A={2,4,6,…,2n}，顧客點集合為寄數(shù)B={3,5,…,2n+1}，并設(shè)配送中心為1。訂單配對點{(2,3),(4,5),(6,7),…,(2n,2n+1)}。

Step2 初始化種群：外面配送路徑優(yōu)化與傳統(tǒng)的路徑優(yōu)化區(qū)別之一在于配送員要嚴格遵循“先取餐,后送餐”的順序原則。因此在同一訂單中，保證商家在前、顧客在后的順序隨機放入基因中。例如以三筆訂單(2,3),(4,5),(6,7)為例，隨機生成一條基因4-6-5-2-7-3，保證基因次序的合理性。

Step3 確定適應(yīng)度：適應(yīng)值為目標函數(shù)的倒數(shù)。

Step4 選擇：采用輪盤賭選擇。

Step5 交叉：隨機選擇兩條染色體采用部分匹配交叉法(PMX)的交叉方法，保證每條染色體的基因只出現(xiàn)一次，并淘汰交叉后不符合配對點順序的染色體，符合外賣配送要求。交叉過程如圖2所示。

圖2 交叉過程示意

最后，淘汰不符合配對點順序的染色體。例如交叉結(jié)果中2-5-6-3-8-7-4-9，商家節(jié)點4和顧客節(jié)點5是訂單配對點，應(yīng)先到點4取餐再去點5送餐，所以不符合要求，將其淘汰。交叉結(jié)果的另一條染色體2-8-4-5-6-7-3-9符合要求。

Step6 變異：商家點和顧客點存在一一對應(yīng)關(guān)系，因此需要對同一訂單的配對點同時進行交換變異。例如染色體8-4-9-5-2-6-3-7，選取訂單1、2，對應(yīng)配對點{2,3}、{4,5}，為保證每筆訂單次序合理性，2和4交換位置，3和5交換位置，形成變異后的子代染色體8-2-9-3-4-6-5-7。

Step7 終止條件：迭代到設(shè)定的最大迭代次數(shù)，則終止循環(huán)。

四、算例研究

為驗證算法和模型的有效性，本文選取福州大學(xué)旗山校區(qū)周圍的10個商家節(jié)點和10個客戶節(jié)點來模擬一位配送員的配送情況。通過百度地圖坐標拾取器獲得經(jīng)緯度，將經(jīng)緯度換算成實際距離。[13]外賣訂單相關(guān)信息如表1所示。配送中心坐標為(3317,5328)。由數(shù)據(jù)可以看出，商家點坐標有兩個是一樣的，這是因為兩位顧客同時向一位商家點下單。

表1 外賣訂單信息及取送餐規(guī)定時間

根據(jù)實際情況，設(shè)置模型所需要的具體參數(shù)如表2。

表2 模型及算法參數(shù)

由于算法設(shè)計，軌跡圖中，1為配送中心，偶數(shù)為商家，奇數(shù)為顧客，10和12為同一商家，就用10表示；14和16為同一商家，用14表示，得到了一條最優(yōu)的外賣配送路徑：1-2-4-3-10/12-14/16-18-20-5-8-11-6-17-9-19-7-21-13-15-1，配送距離為19.9166km，超時懲罰成本為1.0889，總配送成本為11.0472元，配送路徑如圖3所示。

圖3 算例優(yōu)化配送路線

為驗證模型及算法的有效性，對比取餐后立即對其進行送餐的單批配送和先全部取餐后送餐的聚集配送兩種方案[14],結(jié)果如表3所示。對于聚集配送，因為配送車輛最大載重為12kg,所以進行了兩次聚集配送。配送距離比本文優(yōu)化模式下少行駛2.5km，但超時成本卻遠大于優(yōu)化模式下的超時成本。對于一取一送下的單批配送，訂單較多情況下會出現(xiàn)嚴重超時現(xiàn)象，配送距離與超時成本都劣于優(yōu)化模式。綜上對比，本文構(gòu)建的模型和算法對外賣配送路徑優(yōu)化研究是有效的。

表3 三種送餐方法下的配送路徑

五、結(jié)論

本文建立了商家節(jié)點和客戶節(jié)點雙節(jié)點時間窗約束以及嚴格的先取餐后送餐的配對點配送順序的外賣配送路徑優(yōu)化問題研究的數(shù)學(xué)模型，并使用遺傳算法完成求解，通過實例驗證其可行性。最后，與單批配送和聚集配送進行相比，進一步證明了本文配送模型的有效性。

本文建立外賣配送模型并進行了簡化，現(xiàn)實外賣配送中存在各種情況，如隨時出現(xiàn)新訂單，需要對新出現(xiàn)的訂單和未完成的訂單進行重新規(guī)劃路徑，以達到最優(yōu)。接下來將研究隨時出現(xiàn)新訂單的動態(tài)外賣路徑。

注釋：

[1] 中國互聯(lián)網(wǎng)絡(luò)信息中心發(fā)布第46次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告》，《國家圖書館學(xué)刊》2020年第6期。

[2] 敬小玲：《“互聯(lián)網(wǎng)+”背景下外賣行業(yè)發(fā)展分析》，《市場研究》2018年第1期。

[3] 趙雪冉、孫永波：《外賣O2O平臺商業(yè)模式分析及發(fā)展對策》，《商業(yè)經(jīng)濟研究》2017年第3期。

[4] Yeo V.C.S., Goh S.K., Rezaei S., “Consumer experiences; attitude and behavioral intention toward online food delivery (OFD) services”,JournalofRetailingandConsumerServices, vol. 35, no. 5(2017), pp. 150-162.

[5] Hu J.X., Chen X.Y.,“Study on the satisfaction of consumers with online ordering services and its influencing factors in O2O mode: a microcosmic perspective on the provision of takeout services”，InternationalJournalofResearchinSocialSciences, vol. 63, no.8(2018), pp. 230-253.

[6] Desaulniers G.J., Desrosiers A., Erdmann M.M., Solomon F.,“The VRP with pickup and delivery”,EuropeanJournalofOperationalResearch, vol. 33, no. 4(2002), pp. 225-242.

[7] Soumia I., Gendreau M., Potvin J.Y.,“Diversion Issues in Real-Time Vehicle Dispatching”,TransportationScience, vol. 34, no. 4(2000), pp. 378-399.

[8] Landrieu A., Mati Y., Binder Z.,“A tabu search heuristic for the single vehicle pickup and delivery problem with time windows”,JournalofIntelligentManufacturing, vol. 12, no. 5-6 (2001), pp. 479-508.

[9] 余建軍、程文琪、吳永忠：《考慮顧客滿意度的生鮮外賣路徑規(guī)劃》，《工業(yè)工程與管理》2021年第4期。

[10] 劉旺盛、吳球軍、嚴浩洲、敬添俊：《帶硬時間窗的外賣配送車輛路徑問題》，《集美大學(xué)學(xué)報》(自然科學(xué)版)2020年第6期。

[11] 陳 萍、李 航：《基于時間滿意度的O2O外賣配送路徑優(yōu)化問題研究》，《中國管理科學(xué)》2016年第S1期。

[12] 李桃迎、呂曉寧、李 峰、陳 燕：《考慮動態(tài)需求的外賣配送路徑優(yōu)化模型及算法》，《控制與決策》2019年第2期。

[13] 曾富全、龐 詠：《坐標系轉(zhuǎn)換及相關(guān)問題的探討》，《云南地質(zhì)》2017年第2期。

[14] 丁艷慧：《美團外賣配送模式選擇研究》，碩士學(xué)位論文,南京大學(xué),2018年。