半自動化倉庫內訂單分批優化研究

項 溪，唐仕青，徐曉威，宮 琳，劉 欣 （北京理工大學 機械與車輛學院，北京 100081）

0 引 言

近年來，我國電商行業發展迅速，移動支付普及得越來越廣泛，網購交易規模增長甚猛。國家統計局數據顯示，2021年全國電子商務交易同比增長19.6%，對應全年1 083.0億件的快遞業務支持[1]。面對如此巨量的訂單，倉儲物流效率成為決定電子商務服務品質的重要環節[2]。公司為應對日漸加劇的市場競爭，努力保持訂單履行的高度及時性，以確保為消費者提供高質量的網上購物體驗。然而，這給倉庫的訂單處理帶來了越來越大的壓力，據統計，傳統配送中心內，揀選作業成本占總成本的60%、訂單處理時間占比達30%~40%，訂單揀選已成為制約電商發展的物流瓶頸[3]。訂單分批處理則是提高訂單揀選效率的一種常用方法，將若干個訂單分批成組，將每批訂單依次委派給揀貨員，每批訂單由單個揀選員通過巡回揀貨完成揀選任務。

經典的訂單分批問題（Oder Batching Problem, OBP）只考慮商品的種類和數量，通常結合倉庫的布局轉化成揀貨員的路徑優化問題，OBP已經被證明是NP-hard的。吳天行等對OBP提出了人工蜂群算法求解，并創新性地結合“反學習”理論提高算法的收斂[4]。王轉等面向“人到貨”系統提出啟發式揀貨策略，以批次里程節約量之和最大化為目標，提出D-eco分批算法求解，補充了物流中心實際操作問題的解決方案[5]。陳彥博等面向多區塊、多通道、多交叉點的倉庫系統，以揀選員的總行走距離最小化為目標，提出針對大規模問題的分支定價算法，并結合實際電商倉庫運作案例給出算法可行性證明[2]。黃敏芳等受JIT裝配流水線思想啟發，考慮訂單在并行分區的揀選和批次的排序兩流程之間受到的制約，提出兩階段啟發式優化方法，實現流程工序的均衡[6]。張國維等就AGV倉庫訂單分批問題，以搬運和揀選成本最小化為目標，提出交替選擇的貪婪算法求解，并與CPLEX比較了求解誤差[7]。

已有研究不斷豐富了OBP的應用場景和模型細節，并在求解上對算法進行了不斷的創新，但模型的復雜度往往過高，以致于難以快速處理較大規模的分批訂單。另一方面，現有研究往往只關注單一揀選員的揀選路徑規劃問題，而對考慮倉庫布局的多人并行揀選的訂單分批問題研究甚少。綜上，本文考慮一種“人到貨”半自動化倉庫的布局及運作方法，針對訂單分批處理，提出了一個混合整數規劃模型，并使用Gurobi作為MIP求解器對模型進行算例驗證。

1 問題建模

本節提出了一種半自動化倉庫的布局模式及運作方法，并構建了相應的數學模型。

1.1 問題描述

本文基于倉儲布局提出一種“人到貨”倉庫采取多人分區、并行揀選的運作策略。考慮如圖1所示的半自動化倉庫布局：矩形倉庫內設有垂直于墻面的平行過道。每條過道的兩側安裝有從墻面出發的貨架，貨架上有連續不斷、用來臨時存儲貨物的方形貨槽，并且每個槽內只允許盛放同種商品。在貨架盡頭及與之靠近的墻面之間設有傳送帶，傳送帶在經過過道時，會以一定的功率持續不斷地將揀貨員揀出的出庫貨物傳輸到緩沖區。緩沖區的分揀員則需注意及時取出商品并按訂單所需要的組合放在一起，最后將訂單打包出庫。此處將訂單定義為客戶所需商品的清單，包括商品的指定類別（本文以SKU ID表示）和各類別所需的數量。

圖1 半自動化倉庫的布局及運作模式

基于該半自動化倉庫的布局，本文考慮采用多人訂單揀選模式，如圖2所示。

圖2 多人揀選模式

首先分析單個訂單的揀選流程。揀貨員執行“獲取訂單→檢索商品位置→取貨→搬運”的操作步驟。開始之前，所有揀貨員都在各過道的傳送帶處等待，訂單抵達系統時，轉化為取貨清單，清單內包含各商品所在的過道及貨架等具體位置信息。揀貨員收到清單后，迅速開始移動，通過在過道內的一次往返，就揀出全部目標商品；對于沒有取貨要求的過道，揀選員則需在起點處保持等待，直至整個倉庫進入下一訂單的揀選。取貨時，揀貨員用手推車搬運揀出的商品，回到起點后卸貨至傳送帶上，通過傳送帶將揀選出的商品傳輸至緩沖區。當所有揀貨員都完成卸貨時，定義本訂單的揀選結束，接下來倉庫進入下一訂單的揀選。由于訂單結構的差異性，這種逐單件揀選的模式會造成巨大的人力浪費和大量訂單延誤。因此，實際電商倉儲選擇采取分批揀選方式。

訂單分批即揀貨員們在過道內一次往返時需要處理多個訂單，如圖3所示。當一個訂單涉及多個通道的揀選時，由多個對應通道的揀選員分別執行揀選。當若干個訂單被分到同一批次揀選時，由多名揀選員在各自的過道內分別對多個訂單內的多個商品進行揀選。揀選員揀出的商品經傳送帶抵達緩沖區時，分揀員將其逐個撿出，并根據訂單組成將商品打包。

圖3 訂單分批處理的流程示意圖

當系統面臨大批量訂單涌入時，對訂單進行逐一單件揀選將會造成揀選員的重復行走，增加移動時間；如果將大量訂單合并揀選，雖然會縮短揀貨員的行走時間，但也會大大增加分揀員的工作負荷。因此本文的研究目標旨在為實時變化的訂單需求，找到快速合理的訂單分批方法，使系統內訂單的總處理時間達到最小，提高電商倉庫的訂單處理效率。

1.2 模型構建

1.2.1 模型假設

每個訂單不允許被拆分到不同批次；每個過道有且僅有一名揀貨員；揀貨員在過道中進行往返時手推車的容量是固定且相同的；訂單是固定時間窗口內的全部累積訂單；不考慮臨時插入的新訂單。

1.2.2 符號說明

在研究模型的描述和建立之前，首先給出符號如表1。

表1 符號說明

1.2.3 目標函數

考慮訂單的實時性需求變化，往往需要根據實時需求進行動態分批，通常會設置固定時間窗，對時間窗內累積收到的訂單進行分批優化，通過時間窗的平移，實現對長期需求變化的動態分批。而對于電商倉庫而言，其首要目標往往是提高訂單處理效率而反映訂單處理效率最主要的指標就是處理時間，因此本文將系統固定時間窗內累計訂單的總處理時間最小化作為主要優化目標。

如果系統采用訂單分批方法，則目標等價于使全部批次的總處理時間最小化，即系統揀選時間與分揀執行時間之和最小。

1.2.3.1 系統揀選時間

相較于檢索和行走時間，揀選員拾取貨物的作業時間幾乎可以忽略不計，因此揀選時間等于對商品的檢索和在過道內行走所需時間。

假設各過道揀貨員的移動速度相同且保持不變，倉庫內貨架的長度一致，為在過道j中取走本批次所需全部商品所經過的距離，由于揀選員的移動方式是在過道內進行一次往返，因此其移動時間為。同時考慮過道j的揀選員拿到清單后對商品的檢索時間，則總揀選時間為：

將各過道揀貨員的最長用時定義為系統對批次的揀選時間，于是批次k的總揀選時間為

當要求Tkp最小時，式（2）等價于

1.2.3.2 分揀時間

分揀時間等于將商品還原為訂單要求的組合并對訂單進行打包這兩部分的時間之和。分批k包含的訂單總數為Σo∈Oyok，所包含的商品總數為Σo∈OCo·yok，因此，

綜上，目標函數應為

1.2.4 約束條件

對于訂單分批問題，本文考慮有如下約束條件。

其中：約束（6）和（7）用來生成商品、訂單和批次之間的子集關系；約束（8）用于保證每個訂單在同一批次內；約束（9）計算各道揀選員的行走距離，并選出其中的最大值；約束（10）表示在整個倉庫中，批次內商品總量不超過推車的總容量；約束（11）聲明決策變量為0~1變量。

2 算例分析

為了檢驗前文所述模型的可行性，本文基于新加坡NTUC FairPrice藥品倉庫Unity的真實訂單數據與文獻[8]的算例進行數值實驗。所有實驗均在Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz上完成，使用Gurobi 10.0.1作為MIP求解器，所有代碼均在Python 3.11上編寫并運行。

2.1 算例生成

首先基于新加坡NTUC FairPrice藥品倉庫Unity的真實訂單數據和文獻[8]的算例，對于實驗中所涉及的參數說明如表2所示。

表2 算例部分參數生成

2.2 實驗結果及分析

基于表2算例參數及真實訂單數據，分別進行了五組實驗，分別在商品種類數量為40、60、80、100、120時進行不同訂單規模的數值實驗。同時考慮到混合整數規劃求解的難度，將Gurobi求解器的TimeLimit參數設置為120 s，求解結果如下表所示。

表3 不同商品種類及訂單規模下的Gurobi 求解結果

本文又進一步分析了不同訂單規模下解的質量，即Obj和Gap的影響。繪制出折線圖如圖4所示。

圖4 不同規模下求出的Obj 和Gap

從圖4可以看出隨著訂單規模的擴大，訂單總處理時間增多，但求出最優可行解的Gap仍穩定在一定的數值范圍內；同時，商品種類的增加也會延長訂單的總處理時間。總的來說，隨著商品種類和訂單規模的增加，模型的復雜度提升，但解的質量仍舊保持相對穩定狀態，說明本文所建立模型對中小規模訂單處理的性能較好。

3 總結與展望

為滿足復雜環境下實時性變化的需求，本文提出了一種動態訂單分批的思路，并建立了一個針對中小規模下訂單分批問題的混合整數規劃模型。本文的研究結果可以集成到倉儲管理系統（Warehouse Management System, WMS）中，從而有效應對訂單激增等變化，對提高倉庫的訂單處理效率具有重要作用。考慮到實際業務流程，本文的研究還存在一些不足，例如還需考慮訂單的截止日期、緊急訂單的插入等問題，此外本文的訂單分批問題還可與儲位分配等問題進行聯合優化。