基于遺傳算法的前置倉生鮮電商即時配送派單研究

摘" 要：前置倉生鮮電商即時配送派單尤為重要。文章首先分析了配送派單特點(diǎn)，即騎手性質(zhì)屬于專送和配送時效要求高、騎手通常只服務(wù)于某個前置倉等，然后在此基礎(chǔ)上建立了帶有單邊硬時間窗的派單模型，以完成所有配送任務(wù)總耗時最小為目標(biāo)函數(shù)，以時間窗、不同騎手分配訂單差距、騎手最大接單數(shù)為約束條件，采用遺傳算法進(jìn)行求解，并進(jìn)行了實(shí)例分析，與模擬優(yōu)化后的搶單模式進(jìn)行對比分析，結(jié)果表明派單模式下運(yùn)力分配更加平均、總耗時更少，此外，騎手的忠誠度更高。

" 關(guān)鍵詞：前置倉生鮮電商；即時配送派單；遺傳算法

" 中圖分類號：F724.6" " 文獻(xiàn)標(biāo)志碼：A" " DOI：10.13714/j.cnki.1002-3100.2024.24.009

Abstract： Forward warehouse fresh food e-commerce instant delivery dispatch is particularly important. This paper first analyzes the characteristics of distribution dispatching， namely， the nature of the delivery rider belongs to the special delivery， the distribution time requirement is high， and the delivery rider usually only serves a certain pre-position warehouse， and the like. Then， on this basis， the paper establishes the dispatching model with a one-sided hard time window， and with the objective function of minimizing the total time consumed to complete all the distribution tasks， and with the constraints of the time window， the gap of the orders allocated by different riders， and the maximum number of riders to receive the orders， and genetic algorithms are used for the solution of this problem. And an example analysis is conducted to compare and analyze with the simulated optimized order-grabbing model， and the results show that the dispatch model has a more even distribution of capacity and less total time consumed， and in addition， the loyalty of the delivery riders is higher.

Key words： forward warehouse fresh food e-commerce; instant delivery dispatch; genetic algorithms

收稿日期：2024-04-20

基金項(xiàng)目：交通行業(yè)重點(diǎn)實(shí)驗(yàn)室開放課題“運(yùn)輸車輛檢測、診斷與維修技術(shù)”（JTZL2205）；云基物聯(lián)網(wǎng)高速公路建養(yǎng)設(shè)備智能化實(shí)驗(yàn)室開放課題（KF_2022_301002）

作者簡介：金貴林（1981—），男，湖北孝感人，武漢科技大學(xué)汽車與交通工程學(xué)院，講師，碩士，主要從事運(yùn)輸與物流工程研究。

引文格式：金貴林，李康樂，李德鑫. 基于遺傳算法的前置倉生鮮電商即時配送派單研究[J]. 物流科技，2024，47（24）：39-43.

0" 引" 言

近年來，前置倉生鮮電商企業(yè)快速發(fā)展[1-2]，典型代表有樸樸超市、叮咚買菜、美團(tuán)買菜等，這類企業(yè)以生鮮為主打，兼顧全品類運(yùn)營，采用“純線上運(yùn)營+前置倉配送”模式，一般主打30分鐘即時送達(dá)，顯然，如何對騎手進(jìn)行配送派單是一個關(guān)鍵性問題。

不少學(xué)者對這個問題進(jìn)行了相關(guān)研究。有的從平臺出發(fā)考慮配送派單。鄧娜等[3]對現(xiàn)有外賣訂單分配任務(wù)模式進(jìn)行分析，指出搶單這種方式存在的問題，具體來說存在離站點(diǎn)近的搶不到、而有多單的仍繼續(xù)搶單的情況，一方面是騎手之間薪資差距拉開較大，另一方面是搶單會導(dǎo)致無單配送員閑置，平臺配送效率降低；訂單配送信息被分散化，缺乏訂單集中并單優(yōu)化的思想，存在根據(jù)配送員、取餐點(diǎn)和送餐點(diǎn)平臺在派單時給同一配送員指派多單或配送員在搶單時搶多單進(jìn)行一次配送多單的情況，對此提出了基于聚類分析和TSP路徑規(guī)劃的優(yōu)化訂單集指派模式。

從騎手角度出發(fā)考慮配送派單。張柳楊[4]針對騎手配送的異質(zhì)性，將騎手的配送效率分為了四個不同的客戶滿意度模型，以騎手啟動成本、顧客滿意度為優(yōu)化目標(biāo)，構(gòu)建任務(wù)指派整數(shù)線性規(guī)劃模型。鄧娜等[3]提出了一種基于聚類分析和TSP路徑規(guī)劃的訂單集指派模式。徐倩[5]從平臺現(xiàn)階段發(fā)展出關(guān)注平臺成本、騎手期望和顧客滿意度，建立以騎手績效成本和顧客滿意度成本為目標(biāo)的函數(shù)模型。卞喆[6]針對訂單分配不均、騎手離職率較高的情況提出了公平派單和提高用戶滿意度的訂單分配方法，先采用改進(jìn)的K-means聚類算法對訂單數(shù)據(jù)進(jìn)行分類，然后在配送員收入均衡準(zhǔn)則下兼顧配送成本和客戶滿意度，構(gòu)建了多目標(biāo)取送貨配送路徑優(yōu)化模型來提升騎手的積極性和忠誠度。

實(shí)際上，前置倉生鮮電商即時配送派單有其自身特點(diǎn)，需要基于此進(jìn)行研究。

1" 配送派單特點(diǎn)分析

1.1" 騎手性質(zhì)屬于專送

騎手性質(zhì)屬于專送，一般都有統(tǒng)一的服裝，甚至包括所騎車輛也統(tǒng)一規(guī)格統(tǒng)一配色，只服務(wù)于某家前置倉生鮮電商，這就導(dǎo)致企業(yè)配送人力成本較高，必然要求運(yùn)力資源充分利用，同時還需考慮騎手收入。這種情況下，騎手業(yè)務(wù)相對均衡是一個理想的選擇。

1.2" 配送時效要求高

前置倉生鮮電商較為注重品質(zhì)，同時生鮮類產(chǎn)品對配送質(zhì)量要求高，另外同類企業(yè)競爭激烈，導(dǎo)致配送時效要求高，一般為25～35分鐘左右。

1.3" 騎手通常只服務(wù)于某個前置倉

外賣平臺一般是沒有倉庫的，而前置倉生鮮電商通常要設(shè)置倉。前置倉成本較高，一般而言，同一個城市同一家生鮮電商的不同前置倉設(shè)置有一定距離，考慮到配送時效要求高，一個騎手通常只服務(wù)于某個前置倉，在配送非高峰期的時候，騎手通常處于某個前置倉附近等待訂單。

2" 配送派單模型建立

2.1" 問題描述

針對某家前置倉生鮮電商的某個前置倉，根據(jù)客戶的要求在時間窗的范圍內(nèi)，以最少的時間完成所有的訂單，主打即時快速配送。問題可以具體描述為：在某一個前置倉所負(fù)責(zé)的區(qū)域內(nèi)，某一時間段有若干位顧客下單，前置倉能夠調(diào)用若干名騎手，在已知顧客商品需求和位置信息的情況下，通過選擇目標(biāo)進(jìn)行派單，在滿足單邊硬時間窗的條件下，使得完成所有訂單花費(fèi)時間最少。

2.2" 條件假設(shè)和參數(shù)設(shè)定

2.2.1" 條件假設(shè)

1）一位顧客只會下一個訂單，不考慮多單和取消訂單的情況；

2）前置倉為顧客準(zhǔn)備商品的時間加在顧客服務(wù)時間里；

3）一個訂單只能由一名騎手負(fù)責(zé)，不允許中途添加任務(wù)或放棄任務(wù)；

4）不考慮社區(qū)進(jìn)不去、交通堵塞、車輛拋錨等極端情況；

5）所有騎手的速度固定，配送活動視作勻速運(yùn)動。

2.2.2" 參數(shù)設(shè)定

1）[P]，騎手集合[P=pp=0，1，2，3…p]；

2）[N]，前置倉與所有顧客點(diǎn)的集合[N=nn=0，1，2，3…n]，0表示前置倉；

3）[tij]，騎手從[i]位置到[j]位置所需時間；

4）[xkij]，決策變量，第[i]個騎手是否從[j]地移動到[k]地；

5）[ykj]，決策變量，路徑上是否包含[j]點(diǎn)；

6）[ti]，第[i]個訂單實(shí)際送到時間；

7）[ri]，第[i]個訂單送達(dá)不能早于這個時間；

8）[Lti]，第[i]個訂單送達(dá)不能超過這個時間；

9）[ft]，每個訂單的服務(wù)時間。

2.3" 模型建立

這里定義，騎手為每一位顧客（即每個訂單）平均服務(wù)時間不超過10分鐘，包括：聯(lián)系顧客時間，如打電話、走樓梯或乘坐電梯到達(dá)用戶門前叫門所需時間，等待取貨時間，前置倉為顧客準(zhǔn)備商品的時間也加在這里，根據(jù)實(shí)際調(diào)研也可改為其他分鐘數(shù)。

在騎手派單配送過程中，因?yàn)闀r間窗和騎手為一位顧客平均服務(wù)時間不超過10分鐘，為了方便計(jì)算，將目標(biāo)函數(shù)設(shè)置成完成所有配送任務(wù)所需的最小時間，將路程用騎手固定的配送速度量化成時間。因此具體目標(biāo)函數(shù)如下。

[mini=0pj=0nk=0ntijxkij] （1）

1）出發(fā)點(diǎn)和返回點(diǎn)都是前置倉配送中心。

[i=1nxkij=i=1nxkij≤1] （2）

2）每位顧客只會被一個騎手服務(wù)一次。

[i=0nxkij=yki] （3）

[j=0nxkij=ykj] （4）

3）配送時間要在時間窗的范圍內(nèi)。

[ri≤ti≤Lti] （5）

4）接單最多的騎手和接單最少的騎手單數(shù)差距不超過兩單，且單個騎手最多接單數(shù)不超過5單。

[maxi=1nyki-mini=1nyki≤2] （6）

[maxi=1nyki≤5] （7）

5）每個訂單的平均服務(wù)時間為10分鐘。

[ft=10] （8）

3" 基于遺傳算法的配送派單求解

關(guān)于這類配送派單模型求解，學(xué)者提出了很多方法[7-9]，本文考慮到全局尋與參數(shù)設(shè)置的通用性，這里采用遺傳算法求解。

3.1" 遺傳算法流程圖

遺傳算法具體的流程圖如圖1所示。

3.2" 遺傳算法求解設(shè)計(jì)

3.2.1" 初始種群

初始種群采取隨機(jī)生成的方法得到。

3.2.2" 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是與選擇算子相搭配，用來篩選出優(yōu)良個體的評估函數(shù)，本文只有一個目標(biāo)函數(shù)，就是完成任務(wù)所用的總時間，即求取最小值。這里，總時間越少，適應(yīng)度就越高。

3.2.3" 編碼和解碼

該算法編碼是客戶點(diǎn)的不同順序的組合（簡稱客戶點(diǎn)組合），再加上分割點(diǎn)組合。例如，設(shè)定條件中有10個訂單4個騎手，采用自然編碼的方式，分為1—10，這10個數(shù)字隨機(jī)排列，即騎手對所有客戶都進(jìn)行了配送服務(wù)；而解碼是用分割點(diǎn)將編碼分割，分割點(diǎn)數(shù)量為騎手?jǐn)?shù)量-1，數(shù)字隨機(jī)，這里是4位騎手，也就是3個分割點(diǎn)，即這10個客戶隨機(jī)排列，將10個訂單從3個位置分開。比如：編碼3、7、5、4、1、9、6、2、10、8，分割點(diǎn)2、5、7。意思就是從第2個數(shù)字位置開始分割第一份，第一份也就是3、7，第二份就是從第2個數(shù)字到第5個數(shù)字的部分，即5、4、1，第三份就是從第5個位置到第7個位置，即9、6，最后一份就是剩下的2、8、10，得到的四個部分即為4個騎手的配送派單路線。如圖2所示。

3.2.4" 選擇算子

選擇算子采用的是輪盤賭算法，這就相當(dāng)于把所有染色體放在一個餅狀圖中，適應(yīng)度越高的染色體在這個餅狀圖中所占的面積就越大，最后在這個圖中隨機(jī)選取染色體。在這種算法模式下，適應(yīng)度高的被選中的概率就高，優(yōu)良基因被保留下來的概率也越大，重復(fù)此操作產(chǎn)生的新種群優(yōu)良基因會越來越多，更容易產(chǎn)生最優(yōu)解。

3.2.5" 交叉算子

交叉算子首先選取兩條染色體，在染色體A的客戶點(diǎn)組合上隨機(jī)選取某一個位置，在這個位置進(jìn)行分割，將分割點(diǎn)后的部分放到染色體B的頭部，然后從前往后依次剔除重復(fù)點(diǎn)。分割點(diǎn)組合的交叉操作也是相同的，若形成新的分割點(diǎn)位數(shù)大于初始位數(shù)，則按大小順序保留前三位。交叉過后形成了新的染色體B1的隨機(jī)序列，如果要對染色體1進(jìn)行交叉操作也是使用相同的方法。

例如，染色體A：4、10、7、3、5、8、1、6、2、9，染色體B：8、10、2、7、3、1、9、5、4、6，隨機(jī)概率產(chǎn)生的交叉點(diǎn)為6，則在染色體A中取1、6、2、9，把這一段添加到染色體B前端，并刪去重復(fù)的基因，得到新染色體B1：1、6、2、9、8、10、7、3、5、4。如果對A使用交叉操作產(chǎn)生新染色體A1，則使用同種方法截取一段染色體B的基因加到A前面，刪去相同基因即可。見圖3。

3.2.6" 變異算子

變異算子使用常規(guī)的反轉(zhuǎn)變異，首先在一條染色體客戶點(diǎn)組合上隨機(jī)選取一段，然后進(jìn)行順序反轉(zhuǎn)，而分割點(diǎn)組合沒有很好的辦法，一般選擇隨機(jī)生成的方式。比如，染色體：4、8、3、10、6、1、7、2、5、9，在2、7位置截取，采用反轉(zhuǎn)變異，則原染色體中的基因3、10、6、1、7反轉(zhuǎn)為7、1、6、10、3，然后新染色體2：4、8、7、1、6、10、3、2、5、9。見圖4。

3.2.7" 終止條件

終止條件有多個，一個是進(jìn)化到最大代數(shù)，一個是整個種群染色體產(chǎn)生新種群的變化不大，還有一個則是目標(biāo)函數(shù)達(dá)到預(yù)先設(shè)定的要求。

因?yàn)楸舅惴ㄊ且笸瓿伤信渌腿蝿?wù)最小總耗時，因此終止條件設(shè)置成最大迭代次數(shù)，如果求解得出的迭代收斂圖仍有進(jìn)化的趨勢，就增大迭代次數(shù)直至進(jìn)化到無法產(chǎn)生新種群。

4" 實(shí)例分析

4.1" 案例介紹

以WH市某個PP超市前置倉為例，某一時刻開始，陸續(xù)有14個顧客下單，設(shè)置前置倉的坐標(biāo)為（3，3），需求點(diǎn)為0，顧客點(diǎn)編號為i=1，2，3.....14，騎手?jǐn)?shù)量為4名，每名騎手最多接5單，配送平均速度為5m/s，一名騎手為一個顧客服務(wù)的平均時間為10分鐘，時間窗設(shè)置為顧客下單時間后的20～35分鐘，訂單平均2分鐘產(chǎn)生一單。顧客點(diǎn)位置與訂單時間窗信息如表1所示。

4.2" 案例求解

遺傳算法參數(shù)設(shè)置為：迭代次數(shù)500，種群規(guī)模60，交叉概率0.8，變異概率0.3，求解結(jié)果如表2所示。

從表2可以看出，第5次求解結(jié)果為最佳，其騎手路線規(guī)劃與求解適應(yīng)度曲線見圖5、圖6。

4.3" 與模擬優(yōu)化后的搶單模式對比分析

在實(shí)際過程中，很難對搶單模式下騎手路線進(jìn)行規(guī)劃，因?yàn)槊總€訂單會被哪個騎手搶到不確定，因此采取的是模擬優(yōu)化后能進(jìn)行路線規(guī)劃的搶單模式。14個訂單4個騎手，每個騎手最多接5單，訂單隨機(jī)分配給4個騎手，不設(shè)置單數(shù)差距約束，多次試驗(yàn)取最優(yōu)值。設(shè)置好初始條件后使用遺傳算法初步求解，作為理想條件的搶單模式配送（不考慮搶單模式中訂單傳遞導(dǎo)致出錯和不同騎手派送重復(fù)走一條路的情況），模擬求解結(jié)果見圖7、圖8。

模擬搶單模式下求解的結(jié)果如上圖所示，總耗時為341.78分鐘。

通過對比兩種模式下的總耗時和路線規(guī)劃圖，可以看出派單模式更占優(yōu)勢，具體體現(xiàn)在路線規(guī)劃和成本兩方面。

在路線規(guī)劃方面：派單模式下運(yùn)力分配較為平均，從平臺角度出發(fā)，力求整體最優(yōu)，即總耗時最少。而搶單模式下是從騎手的角度出發(fā)，哪怕進(jìn)行了一定的優(yōu)化，也會因?yàn)轵T手搶單導(dǎo)致單數(shù)分配不合理，總體結(jié)果較差，由圖7可知，有的訂單之間的距離相差很遠(yuǎn)卻歸一個騎手派送，而有的騎手訂單少而且距離近，容易陷入空閑時間，運(yùn)力分配不平均就造成了資源的浪費(fèi)。

在成本方面：派單模式力求全局最優(yōu)，總耗時對比搶單模式要低不少，這就意味著更高的配送效率和服務(wù)質(zhì)量，顧客滿意度也會更高。此外，配送的速度是平均速度，更短的耗時也就意味著更少的成本，而且派單模式下，騎手單數(shù)之間的差值更小，這種模式避免了騎手過載問題和騎手挑單產(chǎn)生的訂單傳遞問題，管理成本更少。

在實(shí)際過程中，派單模式的優(yōu)勢更為明顯。搶單模式下騎手根據(jù)自身經(jīng)驗(yàn)進(jìn)行路線規(guī)劃，雖然可能規(guī)劃出最優(yōu)路線，但是訂單分配不合理也會導(dǎo)致總體上遠(yuǎn)不如派單模式，系統(tǒng)也沒有能力從平臺出發(fā)做到全局最優(yōu)，雖然搶單模式平臺維護(hù)成本較低，但是訂單管理成本和配送成本比派單模式要高不少。因此實(shí)際上兩種模式配送效率的差距比本設(shè)計(jì)中模擬的差距更大，此外，派單模式下騎手之間的派單數(shù)量差距不超過兩單，這種分配模式能在一定程度上保證騎手的忠誠度，而且派單模式下不會產(chǎn)生騎手路線重合的情況，減少資源浪費(fèi)，路程更短用時更少，平臺效益更高。

5" 結(jié)" 論

前置倉生鮮電商即時配送派單尤為重要。本文在派單模式下選擇目標(biāo)進(jìn)行配送，從平臺角度出發(fā)，基于遺傳算法在全局上力求完成所有配送任務(wù)總耗時最少，對案例進(jìn)行分析求解，并與模擬優(yōu)化后的搶單模式進(jìn)行對比分析，結(jié)果表明派單模式的配送優(yōu)化決策更好。

參考文獻(xiàn)：

[1]" 弓序．新零售背景下生鮮電商前置倉模式的研究——以樸樸超市為例[J]. 全國流通經(jīng)濟(jì)，2022（23）：39-41.

[2]" 徐一丹，周豐婕，付耀榕. 福建地區(qū)前置倉模式下生鮮平臺的對比分析[J]. 河北企業(yè)，2023（8）：99-101.

[3]" 鄧娜，張建軍．O2O外賣訂單配送任務(wù)分配模式研究[J]. 上海管理科學(xué)，2018，40（1）：63-66.

[4]" 張柳楊．派單模式下考慮騎手異質(zhì)性的外賣配送策略研究[D]. 重慶：重慶大學(xué)，2021.

[5]" 徐倩. 外賣平臺騎手派單與路徑?jīng)Q策協(xié)同優(yōu)化[D]. 大連：大連海事大學(xué)，2020.

[6]" 卞喆. 基于均衡準(zhǔn)則的眾包外賣訂單分配及配送優(yōu)化研究[D]. 西安：西安電子科技大學(xué)，2021.

[7]" 蔣林華. 線上限時配送的訂單分配策略[J]. 物流技術(shù)，2022，41（7）：92-95，119.

[8]" 張?jiān)磩P，黃敏芳，胡祥培. 網(wǎng)上超市訂單分配與物流配送聯(lián)合優(yōu)化方法[J]. 系統(tǒng)工程學(xué)報(bào)，2015，30（2）：251-258.

[9]" 李娜. 基于粒子群算法的生鮮產(chǎn)品即時配送路徑優(yōu)化[J]. 物流科技，2023（3）：22-27.