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

0 引 言

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

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

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

1 問題建模

本節(jié)提出了一種半自動化倉庫的布局模式及運作方法，并構(gòu)建了相應的數(shù)學模型。

1.1 問題描述

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

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

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

圖2 多人揀選模式

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

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

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

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

1.2 模型構(gòu)建

1.2.1 模型假設

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

1.2.2 符號說明

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

表1 符號說明

1.2.3 目標函數(shù)

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

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

1.2.3.1 系統(tǒng)揀選時間

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

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

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

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

1.2.3.2 分揀時間

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

綜上，目標函數(shù)應為

1.2.4 約束條件

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

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

2 算例分析

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

2.1 算例生成

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

表2 算例部分參數(shù)生成

2.2 實驗結(jié)果及分析

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

表3 不同商品種類及訂單規(guī)模下的Gurobi 求解結(jié)果

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

圖4 不同規(guī)模下求出的Obj 和Gap

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

3 總結(jié)與展望

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