“貨到人”揀選系統中電商訂單分批優化研究

李昆鵬, 劉騰博

(華中科技大學 管理學院,湖北 武漢 430074)

0 引言

近年來，隨著電子商務的發展以及移動支付的普及，網絡購物已經成為人們生活中不可或缺的一部分。數據顯示，2019年“雙十一”購物節天貓平臺24小時成交額達2684億元，訂單量也從2009年的26萬件增長到了12.92億件，十年來增長4970倍，巨大的訂單增長量對電商企業物流系統提出了更高的要求。據統計，在傳統配送中心內部，揀選作業成本占總成本的60%，訂單處理時間占比高達30%～40%。由此可見，訂單揀選已成為制約電商發展的物流瓶頸。亞馬遜在2012年斥資7.75億美元收購Kiva Systems公司，其研發的Kiva系統可通過機器人搬運貨架實現自動化揀選作業，該系統為其節省運營費用20%以上，且準確率高達99.99%，這也激發了我國大型電商企業開始積極研發倉儲機器人(AGV)系統，并將其應用于訂單揀選作業，實現“由人取貨物”到“貨物送到人”的轉變。近兩年，我國AGV技術發展迅速，面對不斷趨于“多品種、小批量、高時效”的電商訂單揀選挑戰，如何對訂單合理分批，更好地發揮AGV在揀選效率、作業準確率等方面的優勢，已成為電商企業應用“貨到人”系統進一步提升揀選效率的新途徑。

在采用AGV的“貨到人”揀選系統中，主要流程如圖1中(a)所示。對于一定時間內的訂單，首先根據商品需求和庫存確定需要搬運的貨架，并將搬運任務分配至AGV；然后AGV將貨架運送至揀選站臺，由揀選人員從貨架上揀取商品并放入訂單對應的周轉箱；最后AGV再將貨架運回原位，該模式可極大提高揀選效率。隨著消費者需求不斷趨于多樣化，每個訂單通常由多臺AGV搬運多個貨架才能滿足，不僅浪費倉庫資源，而且AGV數量的增加還導致發生碰撞的可能性增大。如果能建立訂單與貨架之間的聯系，如圖1中(b)所示，將調用貨架相似度較高的訂單合并為一個批次揀選，則AGV搬運貨架一次可供應多個訂單需求。訂單合理分批不僅能夠提高AGV工作效率，而且貨架搬運次數的減少可有效縮短作業完成時間?；诖?，本文以最小化AGV搬運貨架次數為目標，深入研究“貨到人”揀選系統的訂單分批問題。該問題不僅要考慮訂單的貨架選取方法，還要設計批次劃分標準，是一個十分復雜的NP-Hard問題，也是目前學術界和企業界關注較少但十分有必要優化的環節。

圖1 “貨到人”揀選系統流程

訂單分批的概念早在1997年就由AcKerman[1]首次提出，目前在傳統“人到貨”揀選模式下關于訂單分批問題的研究較多。在行走距離方面，郜振華等[2]、王轉等[3]、Koch[4]等以揀選距離最短為目標，分別采用螢火蟲分批算法、基于里程節約的方法、遺傳算法求解。在揀選時間方面，Henn等[5]以最小化總延遲時間為目標提出變鄰域搜索算法；王旭坪等[6]考慮訂單平均服務時間最短構建模型；Lenoble等[7]和于嵐等[8]以最小化訂單完成時間為目標建立模型。在訂單相似度上，李詩珍等[9]提出了基于儲位、巷道及面積的相似系數計算方法；羅曉萌等[10]將通道重合數作為訂單相似系數。Gademann等[11]通過復雜度分析證明了訂單分批問題屬于NP-Hard問題。

近年來，隨著AGV技術的不斷成熟，國內外學者對“貨到人”揀選系統的訂單分批問題開展了初步研究。范繼東[12]以貨架搬運次數最少為目標設計基于k-means聚類算法的訂單分批算法；李珍萍等[13]以人工揀貨成本和AGV搬運成本之和最小為目標建立模型。部分學者將訂單分批問題與其他問題相結合進行探索。Xiang等[14]和李曉杰[15]結合儲位分配問題，前者以最大化訂單關聯度和最小化貨架訪問次數為目標構建模型；后者以減少AGV往返運送貨架次數為目標設計揀選策略。Boysen等[16]和吳穎穎等[17]考慮揀選順序，前者優化目標為最小化AGV搬運貨架次數；后者為最大化單揀選站臺訂單耦合因子之和。Ardjmand[18]研究了訂單分配、訂單批處理及揀選路徑問題。

綜上所述，國內外學者主要研究了傳統“人到貨”揀選模式下的訂單分批問題，而采用AGV的“貨到人”揀選系統與其具有本質區別，很多研究成果和算法不能直接應用。目前關于“貨到人”揀選系統訂單分批問題的研究較少，已有文獻多在訂單與貨架對應關系已知的情況下構建數學模型并設計啟發式算法求解，且多假設每種商品只能存儲在一個貨架上。而在實際中，電商訂單信息通常包括所需商品及數量，且商品庫存在多個貨架上均有分布，應首先根據訂單需求選取供應貨架。鑒于此，本文在構造模型時考慮訂單需求與商品庫存之間的聯系，在設計算法時定義貨架相似度作為訂單選取貨架的評價指標，最終形成一套能夠最大化減少AGV搬運貨架次數的訂單分批方案。

基于以上分析，本文考慮在訂單需求多樣化、商品庫存多貨架分布、訂單與貨架供需關系未知等更符合實際的背景下研究訂單分批問題。首先，構建以最小化AGV搬運貨架次數為目標的整數規劃模型；然后，設計兩階段訂單分批啟發式算法，并提出兩種方法創建新批次；最后通過實驗驗證本文模型和算法的有效性，分析兩種批次創建方法的適用性，采用靈敏度分析探討周轉箱的合理配置數量。實驗證明本文提出的兩階段算法能夠在短時間內得到較優分批方案，在實際應用中具有一定的可行性。研究成果不僅可以擴展訂單分批問題的現有理論，而且能夠為企業采用AGV進一步提升揀選效率提供新的思路。

1 考慮貨架搬運次數訂單分批模型

1.1 問題描述及假設

本文研究“貨到人”揀選系統的訂單分批問題，描述如下：在采用AGV的智能倉庫中有t個揀選站臺、r個貨架，共存儲h種商品。每個貨架有多個儲位，每個儲位存放一種商品，每種商品存放在多個貨架上。每個揀選站臺配備d個周轉箱，每個周轉箱對應一個訂單。某段時間內共接收到n個需求已知的訂單揀選任務，如何對這些訂單進行分批以實現批次揀選作業。在“貨到人”揀選系統中，作業完成時間主要取決于AGV搬運貨架的行走時間，若能調用較少貨架滿足所有訂單的商品需求，則可最大程度減少作業完成時間?；诖?，本文以最小化AGV搬運貨架次數為目標，決策多訂單的批次分配及批次與貨架的服務關系，并計算批次的商品需求量及貨架的供應量。為方便建模，考慮以下假設：

①AGV電量充足，且數量足夠多；②商品庫存量充足能夠滿足訂單集合需求；③在給定的時間段內每個貨架只能被AGV搬運一次；④同一訂單不能被分配至多個批次；⑤每個揀選站臺完成一個批次的揀選作業，即批次數等于揀選站臺數t，批次的最大訂單數等于周轉箱數d。

1.2 模型建立

根據問題描述，符號及變量定義如表1所示，數學模型構建如下:

表1 模型符號變量定義

(14)

目標函數(1)表示最小化AGV搬運貨架次數；式(2)保證每個訂單均被分配至批次；式(3)保證每個批次均會被貨架服務；式(4)表示每個批次至少包含一個訂單；式(5)為批次的最大訂單數限制；式(6)表示每個貨架最多服務一個批次；式(7)表示批次需求等于其所包含訂單的商品需求量之和；式(8)表示批次需求可被多個貨架供應；式(9)表示貨架的供應量不能超過其存儲量；式(10)保證批次的商品需求都能被滿足；式(11)表示貨架是否被搬運取決于其是否供應批次商品需求；式(12)表示0-1變量；式(13)、(14)表示整數變量。

2 基于貨架相似度的兩階段訂單分批算法

訂單分批是將訂單集合劃分為包含一個或多個訂單的批次進行揀選，本文提出了基于貨架相似度的兩階段訂單分批算法SSTOBA(Shelf Similarity based Two-phase Order Batching Algorithm)，如圖2所示。第一階段，包括新批次創建和訂單加入批次兩個步驟：(1)采用兩種方法創建新批次。法一：計算兩兩訂單的貨架相似度并將相似度最大的合并作為新批次，若最大相似度為0，則將訂單各自作為揀選批次；法二：計算每個訂單的所需貨架數并將數值最大的作為新批次。(2)訂單加入批次。計算訂單與當前批次的貨架相似度并將相似度最大的訂單加入，直至訂單數達到周轉箱數，在此過程中若最大相似度為0，則將當前批次作為揀選批次。通過以上兩個步驟將所有訂單分配至批次。然后，遍歷每個訂單作為第一個初始批次得到各自分批方案，將較優方案作為初始解。第二階段，設計局部搜索算法改進初始解，通過兩種移除算子和修復算子不斷更新當前解，得到最優解或近似最優解。

圖2 求解框架

為建立訂單與貨架之間的供需匹配關系，在算法中考慮兩種規則為訂單選取貨架，然后定義貨架相似度函數作為評價指標。本節先對貨架選取規則和相似度函數進行說明，在此基礎上介紹算法兩個階段的具體步驟。

2.1 兩種訂單選取貨架規則

電商訂單所需商品通常來自多個貨架，同種商品在多個貨架存儲，因此每個訂單對應多種貨架組合。在實際中訂單與貨架的匹配關系未知，需首先對貨架量化作為選取依據。本文結合訂單需求量和商品庫存量的關系提出兩種貨架量化標準。其中，Om表示訂單需求商品m的數量，Skm表示貨架存儲商品m的數量，具體描述如下。兩種標準為貨架存k儲或可滿足訂單需求商品的類型數，分別表示為Mk和Nk。當訂單對商品m有需求，若貨架k存儲商品m，即Om>0,Skm>0，則Mk值加一；若貨架存儲商品且庫存量滿足需求量，即Om>0,Skm>Dm，則Nk值加一，檢測所有商品需求得到貨架k的Mk值和Nk值。

為得到較優組合，在對貨架量化基礎上，提出兩種貨架選取規則，區別在于Mk和Nk的計算次序不同，如圖3所示。對于貨架集合S={1,…,r}。首先，根據訂單需求Om，計算每個貨架的Mk值(Nk值)并選擇最大值貨架。若存在h個貨架具有最大值，則比較貨架的Nk值(Mk值)并選擇最大值貨架。若仍存在t個貨架兩數值均最大，則從中隨機選擇貨架。然后，使該貨架盡可能滿足訂單需求，更新Om和Skm。最后，按照兩種規則不斷選擇供應貨架，直至訂單的所有商品需求均被滿足，由此得到訂單的兩種供應貨架組合。

圖3 兩種貨架選取規則

2.2 貨架相似度函數

(15)

(16)

(17)

2.3 兩階段算法步驟

2.3.1 第一階段生成初始解

本文算法基于訂單選取貨架規則和貨架相似度函數，在第一階段，根據批次中是否已有訂單進行新批次創建及訂單加入批次，提出兩種方法創建新批次，①兩訂單貨架相似度最大；②單訂單所需貨架數最多，分別表述為法一和法二。為擴大搜索空間，遍歷訂單集合，各訂單依次作為第一個批次，得到基于每個訂單的分批方案。由于訂單在兩種規則下選取貨架對應兩種貨架組合，最終得到2n種分批方案。鑒于每個方案均建立在第一個批次已有訂單的基礎上，為更清楚展現算法邏輯，描述順序為訂單加入批次和新批次創建，主要流程如圖4所示，具體步驟如下。

(1)訂單加入批次

Step2若批次中訂單數小于周轉箱數，返回Step1，繼續加入訂單；若已達到周轉箱數，則當前批次為揀選批次，刪除其供應貨架，執行Step3。

Step3若集合中訂單數大于1，則生成新的空批次，執行Step4采用兩種方法創建新批次；若訂單數為1，則該訂單為揀選批次，終止算法。

(2)新批次創建

Step4(法二) 當批次為空，按所需貨架數對集合中訂單排序，將所需貨架數最多的訂單作為新批次，并將其從集合中刪除，返回Step1。

同理得到O={1,…,n}中每個訂單的兩種貨架組合分別作為第一個批次的分批方案，共得到2n種訂單分批方案，計算每個方案中AGV完成所有訂單揀選任務的搬運貨架次數，將搬運次數最少的作為第一階段初始解s0。

2.3.2 第二階段局部搜索算法改進初始解

基于第一階段所得初始解，為提高算法尋優能力以獲得高質量的解，在第二階段加入局部搜索算法，包括破環與修復兩個步驟，通過兩種移除算子和修復算子改進當前解，主要步驟如下。

兩種移除算子：①移除批次訂單。在當前解中，隨機選擇20%的批次，從每個批次中隨機移除一個訂單，得到破壞解sd。將移除的訂單存入未分批集合R，對應貨架存入可用貨架集合S；②移除訂單貨架。在當前解中，隨機選擇30%的貨架移除，存入可用貨架集合S，同時將對應訂單刪除，存入未分批集合R，得到破環解sd。

修復算子：基于貨架集合S，對訂單集合R，計算各訂單與破壞解sd中所有未飽和批次的貨架相似度(訂單數未達到周轉箱數)，將相似度最大的訂單插入，并將其從集合R中刪除，同時將其所需貨架從集合S中刪除。繼續執行插入，直到集合R中的訂單均分配至批次，得到修復解se。

Step1參數初始化。輸入第一階段初始解s0，初始目標函數值為AGV搬運貨架次數r0；初始化當前解rc和當前目標函數值sc，使sc=s0，rc=r0；設置l=0，L=0，當前解最大未改善次數lmax，算法最大迭代次數Lmax。

Step2若L

Step3若l

Step4通過移除算子得到破環解sd，然后采用修復算子得到修復解se。計算修復解se的貨架搬運次數，作為其目標函數值re，如果re

Step5輸出近似最優解s*=sc，近似最優目標函數值r*=rc。

3 仿真實驗及數據測試

本文所有測試在Intel Core i5 2.2GHz CPU with 4GB RAM的計算機上運行，采用CPLEX作為模型求解器，啟發式算法采用C++編碼，實驗部分設置最大迭代次數為100。

3.1 小規模仿真實驗

為驗證本文數學模型和算法中兩種批次創建方法的有效性，采用小規模算例對比分析CPLEX與算法求解結果。為使算法所得批次數等于揀選站臺數，以不影響貨架搬運次數為前提改進算法所得方案，在符合周轉箱數范圍內將包含訂單數較少的批次合并。本文考慮訂單需求多樣化、商品庫存多貨架分布的特點隨機生成數據，對5組不同規模的算例測試。其中，總商品類型數為8，揀選站臺數為5，周轉箱數為4。

結果如表2所示，以AGV搬運貨架次數(Out)為衡量指標。M1、M2分別表示第一階段新批次創建的法一和法二；CS1、CS2分別表示最優解與法一、法二求解所得百分差，等于“(SSTOBA-CPLEX)/SSTOBA*100%”；time1、time2、time3分別表示CPLEX、法一、法二的求解時間。

表2 小規模實驗結果

圖5 三種方式下貨架搬運次數對比圖

結果表明，(1)對于貨架搬運次數，如圖5所示，在不同算例規模下，CPLEX求解模型可最大程度減少搬運次數。在兩階段算法中，采用不同方法創建新批次對求解結果有所影響，法一比法二能夠獲得更少的搬運次數。此外，對于表現較好的法一，搬運次數與最優解僅相差1～2次，平均相差7.4%，且在有些情況下能夠獲得最優解，說明算法具有合理性和有效性。(2)在求解時間上，如圖6所示，當訂單數由14、貨架數由40不斷增加時，模型求解時間呈指數型增長，由于電商配送中心對時間要求極高，CPLEX在求解大規模問題時耗時較長，因此很有必要探索高效的啟發式算法，而本文算法能夠在短時間內獲得AGV搬運貨架次數較少的訂單分批方案，具有很好的實用性。由此可見，本文建立的數學模型是正確且有效的，兩階段算法中的法一能在短時間內獲得最優解或近似最優解。

3.2 大規模仿真實驗

為分析本文在第一階段提出的兩種批次創建方法的適用性，以及局部搜索算法對初始解的改進效果，本節采用兩階段算法對更大規模算例測試。在衡量分批效果上，選取AGV搬運貨架次數(Out)和分批后的批次數(Batch)兩個指標評價。實驗結果如表3所示，其中，P1、P2分別表示第一階段和第二階段；P1O、P2O分別表示在第一階段和第二階段法一與法二在搬運次數上的差異，計算分別為“(P1 M1-P1 M2)/P1 M2*100%”和“(P2 M1-P2 M2)/P2 M2*100%”，負號表示相對減少；M1O、M2O表示法一和法二在兩個階段結果的百分差，計算分別為“(P1 M1-P2 M1)/P2 M1*100%”和“(P1 M2-P2 M2)/P2 M2*100%”；BGap表示法一與法二在批次數上的差異，等于“(M1-M2)/M2*100%”。

表3 大規模實驗結果

由結果可知，(1)對于貨架搬運次數，如圖7所示，由P1O、P2O可知，法一與法二的搬運次數相差較大，在第一階段法一比法二平均減少40.3%，在第二階段平均減少38.5%；由M1O、M2O可知，采用局部搜索算法能在一定程度上改善初始解，與第一階段相比，法一與法二分別平均節約搬運次數23.4%和32.4%。法二改進后的解仍比法一初始解的搬運次數多，主要原因是，在第一階段，法一將貨架相似度最大的兩個訂單合并作為新批次，更能節約搬運次數，初始解與近似最優解差距較小。(2)對于批次數，如圖8所示，法一得到的批次數較多，由BGap可知法一比法二平均增加42.9%，最大差距為66.7%。主要原因是，法一考慮當不存在兩訂單所需貨架相同時將訂單各自作為揀選批次，故出現批次中僅包含一個訂單的情況較多導致批次數增加。綜上，采用法一的兩階段算法能夠獲得更少的搬運次數，從而有效縮短AGV搬運貨架行走時間。

圖7 兩種方法不同階段貨架搬運次數差異圖

圖8 兩種方法批次數差異圖

3.3 周轉箱數量靈敏度分析

在采用“貨到人”揀選模式的倉庫中，每個揀選站臺配備一定數量周轉箱，分別對應一個訂單。周轉箱作為物流容器，數量過多將會占用空間且增加采購成本，因此，本節基于兩階段算法探討周轉箱的合理配置數量。隨機生成一組中等規模算例：總商品類型數為20、訂單數為30、貨架數為60。結果如表4所示，其中，time1、time2分別表示法一和法二的求解時間；P2O、BGap分別表示法一與法二在貨架搬運次數、批次數上的差異，負號表示相對減少。計算分別為“(P2 M1-P2 M2)/P2 M2*100%”和“(M1- M2)/M2*100%”。

表4 周轉箱數量靈敏度分析

由結果可知，隨著周轉箱數的增加，兩種方法在貨架搬運次數和批次數上基本呈現由下降到平穩波動的變化趨勢，如圖9和圖10所示。主要原因是，訂單加入批次的停止條件包括兩個，訂單與批次不存在所需貨架相同以及批次訂單數達到周轉箱數。(1)當周轉箱數較少時，即使存在訂單與批次的所需貨架相同，由于最大訂單數限制可能無法繼續加入批次。(2)當周轉箱數由4增加至10時，批次可包含訂單增多，將相似度最大的訂單加入批次能有效減少搬運次數，同時，批次中訂單數的增多導致總批次數減少。(3)當由10逐步增加時，批次最大訂單數的限制作用不明顯，訂單停止加入批次主要是由于不存在所需貨架相同，此時周轉箱數的增加對搬運次數和批次數的影響很小。由此可知，在中等規模下合適的周轉箱數為9～10個，此時貨架搬運次數較少且周轉箱利用率較高。綜上，通過對周轉箱數量進行靈敏度分析，可為不同倉庫規模的周轉箱數量配置提供參考，達到合理利用倉庫資源、提高企業經濟效益的目的。

圖9 不同周轉箱規模下貨架搬運次數變化圖

圖10 不同周轉箱規模下批次數變化圖

4 結論

本文研究了“貨到人”揀選系統的電商訂單分批問題，考慮訂單需求多樣化、商品庫存多貨架存儲以及訂單與貨架匹配關系未知等實際因素，以最小化AGV搬運貨架次數為目標構建數學模型，并設計基于貨架相似度的訂單分批算法求解。最后通過實驗驗證了本文模型和算法的有效性和實用性，實驗結果表明，(1)采用法一基于兩訂單貨架相似度最大的兩階段算法能獲得更少的搬運次數，在有些情況下能夠獲得最優解。(2)本文算法能夠在具有110個貨架、28種商品的倉庫中對55個訂單分批處理，在第二階段，法一和法二比初始解分別平均減少搬運次數23.4%和32.4%。(3)在中等倉庫規模下周轉箱合理配置數量為9～10個。綜上，本研究不僅擴展了“貨到人”揀選系統中訂單分批問題的相關理論，而且可為企業通過訂單分批進一步提高AGV揀選效率提供參考。此外，考慮多種實際因素對智能倉庫建設具有重要理論價值和現實意義。未來的研究中，可以考慮將AGV路徑規劃與訂單分批相結合進行深入探討，此外，還會考慮在線訂單分批問題。