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

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

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

" 中圖分類號：F724.6" " 文獻標志碼：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

基金項目：交通行業重點實驗室開放課題“運輸車輛檢測、診斷與維修技術”（JTZL2205）；云基物聯網高速公路建養設備智能化實驗室開放課題（KF_2022_301002）

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

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

0" 引" 言

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

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

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

實際上，前置倉生鮮電商即時配送派單有其自身特點，需要基于此進行研究。

1" 配送派單特點分析

1.1" 騎手性質屬于專送

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

1.2" 配送時效要求高

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

1.3" 騎手通常只服務于某個前置倉

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

2" 配送派單模型建立

2.1" 問題描述

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

2.2" 條件假設和參數設定

2.2.1" 條件假設

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

2）前置倉為顧客準備商品的時間加在顧客服務時間里；

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

4）不考慮社區進不去、交通堵塞、車輛拋錨等極端情況；

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

2.2.2" 參數設定

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

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

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

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

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

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

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

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

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

2.3" 模型建立

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

在騎手派單配送過程中，因為時間窗和騎手為一位顧客平均服務時間不超過10分鐘，為了方便計算，將目標函數設置成完成所有配送任務所需的最小時間，將路程用騎手固定的配送速度量化成時間。因此具體目標函數如下。

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

1）出發點和返回點都是前置倉配送中心。

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

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

[i=0nxkij=yki] （3）

[j=0nxkij=ykj] （4）

3）配送時間要在時間窗的范圍內。

[ri≤ti≤Lti] （5）

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

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

[maxi=1nyki≤5] （7）

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

[ft=10] （8）

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

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

3.1" 遺傳算法流程圖

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

3.2" 遺傳算法求解設計

3.2.1" 初始種群

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

3.2.2" 適應度函數

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

3.2.3" 編碼和解碼

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

3.2.4" 選擇算子

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

3.2.5" 交叉算子

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

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

3.2.6" 變異算子

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

3.2.7" 終止條件

終止條件有多個，一個是進化到最大代數，一個是整個種群染色體產生新種群的變化不大，還有一個則是目標函數達到預先設定的要求。

因為本算法是要求完成所有配送任務最小總耗時，因此終止條件設置成最大迭代次數，如果求解得出的迭代收斂圖仍有進化的趨勢，就增大迭代次數直至進化到無法產生新種群。

4" 實例分析

4.1" 案例介紹

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

4.2" 案例求解

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

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

4.3" 與模擬優化后的搶單模式對比分析

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

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

通過對比兩種模式下的總耗時和路線規劃圖，可以看出派單模式更占優勢，具體體現在路線規劃和成本兩方面。

在路線規劃方面：派單模式下運力分配較為平均，從平臺角度出發，力求整體最優，即總耗時最少。而搶單模式下是從騎手的角度出發，哪怕進行了一定的優化，也會因為騎手搶單導致單數分配不合理，總體結果較差，由圖7可知，有的訂單之間的距離相差很遠卻歸一個騎手派送，而有的騎手訂單少而且距離近，容易陷入空閑時間，運力分配不平均就造成了資源的浪費。

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

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

5" 結" 論

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

參考文獻：

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

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

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

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

[5]" 徐倩. 外賣平臺騎手派單與路徑決策協同優化[D]. 大連：大連海事大學，2020.

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

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

[8]" 張源凱，黃敏芳，胡祥培. 網上超市訂單分配與物流配送聯合優化方法[J]. 系統工程學報，2015，30（2）：251-258.

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