在線訂單分批及揀選路徑規劃模型及算法

閆 軍，常 樂，封麗華

1.蘭州交通大學 甘肅省物流與信息技術研究院，蘭州730070

2.蘭州交通大學 機電技術研究所，蘭州730070

訂單揀選是從倉庫中的存儲位置取回物品以滿足客戶需求的過程。在人到貨訂單揀選系統中，客戶指定的訂單在運送給客戶之前，需要經過倉庫中的幾個物理過程，包括接收訂單、下架、揀選、檢查和包裝。倉配企業的進貨方式一般是從生產廠商方大批量接收貨物并進行存儲，而具有配送需求的客戶通常是訂購小批量產品，因此出現了揀貨這一生產活動。過長的處理和交付時間以及高昂的人工和交付成本，將導致不滿意的客戶服務，可能會降低倉庫的競爭力[1]。

訂單分揀系統可以分為兩類：貨到人訂單分揀系統和人到貨訂單分揀系統。在第一種類型的訂單揀選系統中，自動存儲和穿梭車將所需物品運送到固定揀選機，而在第二種類型的訂單揀選系統中，揀選員步行或乘車穿越倉庫并收集訂單所涉及的物品[2]。因為人工成本高的因素，訂單分批系統的好壞會對人到貨訂單揀選系統產生巨大影響，所以本文主要研究第二種類型的訂單揀選系統，考慮減少此類企業的生產成本。人到貨訂單分揀系統在運營過程中會出現三個不同的計劃問題：將物料分配到存儲地點（倉庫貨位優化），將客戶訂單分配到不同的分揀批次（訂單分批）和拾取貨物時穿梭倉庫的行走路徑（揀選路徑規劃）。本文主要關注第二個問題。在這個問題中，通過優化不同的客戶訂單之間的揀配訂單組合，可以大大提高倉庫運營效率。

針對來自客戶訂單中的可用信息，可以區分兩種不同類型的訂單批處理問題：離線（靜態）訂單分批處理問題，該活動在計劃期開始時就知道所有客戶訂單；在線（動態）訂單分批處理問題（online order batching problem，OOBP），提前不知道客戶訂單，并且隨著時間的推移會產生新的訂單[3]。本文考慮了具有多個揀選員的在線訂單批處理問題，其中需要解決三個主要決策問題：（1）哪些客戶訂單應分組在同一批中；（2）應如何將已構造的批次分配給空閑的揀選人員；（3）何時開始每批的揀選過程。目的是最小化所有批次的最大完成時間。由于離線訂單批處理問題是NP 難題，本文提出了一種基于規則的啟發式方法來解決上述決策問題。該算法將在線訂單批處理問題分解為與定義的決策點類型有關的一些離線問題，并基于由分批處理規則、分批處理選擇規則和揀選員分配規則組成的決策規則來解決每個離線訂單批處理問題。

對于處理離線訂單分批處理問題的算法，精確算法方面，Gademann和Velde[4]提出了一種分支定價算法，以在合理的計算時間內解決離線訂單批處理問題的小實例。Bozer和Kile[5]提出了一種混合整數規劃方法，以獲得離線訂單分批處理問題的最佳解決方案，但該方法僅適用于訂單數量少（最多25個）的實例。而啟發式算法方面，國內外文獻中主要有四種類型：基于優先級規則的算法、種子算法、保存算法和元啟發式算法。第一類算法是按照訂單的到達順序或重要程度等優先級規則進行分批處理；第二類種子算法一般依據某種規則選擇種子訂單，然后依據訂單一致性原則進行分批處理；第三類保存算法是尋找訂單間的相似性，以獲得揀選路徑最大節省值為目標進行訂單的合并；最后一類元啟發式算法是構建訂單分批的初始解結構，通過在可行域內的隨機搜索得到相對最優的結果。如Hsu等[6]提出了一種遺傳算法來解決離線訂單分批問題，但是他們的方法僅限于S形路由策略。Tsai等[7]提出了一種具有提前和拖延懲罰的多重遺傳算法，以解決集成的訂單分批和分揀機路由問題，并獲得最佳的分揀計劃。Henn[8]也提出了一種算法，該算法是迭代局部搜索和蟻群算法的組合。Henn 和Schmid[9]展示了如何使用元啟發式算法來最大程度地減少給定預定日期的給定客戶訂單集的總拖延時間。

有些文獻將對OOBP 的部分研究抽象為經典生產運輸聯合調度的變體，王旭坪等[10]以訂單的總服務時間最小為目標，設計三階段啟發式算法處理在線訂單分批問題；曾慶成等[11]考慮提前下單和實時下單共同參與的實際情況，設計基于插入算法和2-opt 鄰域搜索的混合啟發式算法進行求解。除此之外，馬氏華等采用等待機制設計延時動態時間窗分批策略；陳方宇等[12]對實時訂單進行仿真實驗，通過重復使用算法優化結果得出訂單分批和揀選路徑規劃方案。近年來OOBP 在建模時經常考慮時間窗口對分批處理的影響，Chew 和Tang[13]考慮S型揀貨路徑策略，將可變時間窗口應用于OOBP模型。作者運用理論分析，將訂單揀選系統建模為具有兩個隊列的排隊網絡：第一個隊列進行分批處理過程，在該過程中，根據優先級規則對客戶訂單進行排序，并當隊列中積累一定量的訂單時對客戶訂單進行分批合并。第二個隊列進行揀選過程，將已分批處理的訂單移至第二隊列進行揀選。Le-Duc和de Koster[14]提出了一種排隊模型，該模型考慮了固定時間窗和可變時間窗批次，計算雙區型倉庫中客戶訂單的平均周轉時間。綜上所述，文獻中對訂單分批的研究為OOBP的數學建模和解決算法提供了豐富的可借鑒方法，但OOBP的研究大多是進行先到先分批的策略或累計到一定數量的訂單進行離線訂單分批處理，有關在線訂單分批和揀選路徑優化進行聯合調度的研究較少。

本文構建限制訂單過早或延遲處理的在線訂單揀選分批優化模型，并考慮存在多個揀貨員的情況，求解出所有批次平均最小服務時間；根據訂單的時間窗規則構建在線訂單分批求解模型，即按照客戶的需求情況來決定處理訂單的實際時間；求解算法方面，訂單的分批采用改進的k-means聚類算法進行，揀貨路徑的規劃由遺傳算法求解給出。最后通過數據實驗，從服務時間、完成訂單數量、有效訂單數量、延遲時間等多方面，將本研究算法與傳統算法分批結果進行對比分析，以證明模型和算法的有效性，為倉儲管理部門提高訂單處理服務質量提供決策支持。

1 問題描述和數學建模

1.1 問題描述與符號說明

在OOBP中，運輸存貨單位（stock keeping unit，SKU）被用于區分倉庫內的N種產品類型，在某一時刻下庫存量為X={x1,x2,…,xN}，其中i=(1,2,…,N)表示第i個SKU。每個i都具有變量wi給出的標準重量/體積，并且揀選一次的容量（揀選小車容量）由G≥max{wi,i=1,2,…,n} 進行限制。一個工作周期內的PO是由PO={O1,O2,…,On} 表示的n個訂單集合，Oj表示第j個訂單。PO中對xi的總需求由Qi表示，PO中單個訂單Oj對xi的具體需求由qij表示，其中Oj={q1j,q2j,…,qNj} 。不同客戶在同一時間段下達訂單的情況很常見，PO中可能具有處于不同訂單的相同SKU，并且各訂單的需求不相同。因此必須將PO分為多個揀選批次，這些批次將具有一種或多種SKU，最終由揀選員按照一定順序進行揀選。故PO又可以由集合PO={B1,B2,…,Bm} 表示，其中下標m是總批次數，而Bk表示第k批次?k={1,2,…,m}，每個Bk是由Bk={q1,q2,…,qN}表示的PO的子集，而qi是一個或多個訂單的某個SKU 的需求數量。在本文的訂單分批揀選系統中需要考慮：（1）應將哪些客戶訂單分配給同一批次；（2）每個批次開始揀選的時間；（3）每批訂單應由哪個揀選員進行揀選。根據以上訂單分批過程和系統要求，得出防止訂單揀選過早或延誤的揀選次序規劃，并最大程度地減少揀選路徑。

倉庫為雙區型矩形布局倉庫，每一區域都包含10個高層貨架（五層），兩個區域的貨架可以細分為1 600個倉儲模塊。這些模塊由集合M={m1,m2,…,m1600} 表示，其中下標表示倉儲模塊。倉庫設有一個進出口m0，揀貨員從此口出發揀貨并回到這個地點，因此批次Bk的揀貨路徑可以表達為RBk={m0,m1,…,mu,…,ms,m0} 。倉庫存儲策略為ABC 分類法，根據貨物的出庫頻率劃分儲位，圖1 顯示了倉庫的布局，其中不同的顏色表示ABC類中的SKU位置。貨架巷道從進出口由近到遠依次為巷道1 至巷道10，每個雙排倉儲模塊為D1×D1的矩形模塊，單排倉儲模塊為，貨架間巷道寬度為D2，雙區之間主通道寬度為D3。貨位的儲位使用[x,y,z]表示，其中y表示貨物所處巷道的儲位編號，雙區貨架從西到東依次由1到b表示，x表示貨物所處的巷道數，z∈(0,1) 用于定義貨架的前后排，后排貨架(z=0)面向倉庫進出口，前排貨架(z=1)與后排貨架面對面放置。倉庫布局如圖1所示。

圖1 倉庫布局圖Fig.1 Warehouse layout

根據以上倉庫參數，兩貨位mu、mh之間的最短距離由式（1）表示：

倉庫進出口m0與任意儲位mu的距離由式（2）表示：

Bk批次的揀選行走距離由式（3）給出，m個批次訂單總的揀選行走路徑由式（4）表示：

1.2 模型構建

本節描述在線訂單分批揀選優化問題的數學模型：分批處理在線訂單和生成批次內的揀貨順序，即如何將多個SKU分組為n個批次，在滿足揀選載具容量和訂單時間窗要求的情況下，減少揀貨員在倉庫內的揀選行程。

揀貨員的行進速度為v，揀選第k批貨物時行走時間可以由式（5）表示：

訂單在倉庫內的揀選時間以及訂單揀選完成后的整理打包所花費的時間，由式（6）表示：

其中，Pti表示選取倉庫內貨物單元i所花費的時間，Sti是整理和包裝每個獨立訂單所花費的時間。

基于以上內容，訂單分批問題可以表述成如下模型：

目標函數表示最小化揀選時間，式（8）確保倉庫可以滿足訂單的需求，式（9）表示每個批次的容量小于揀選設備的裝載量。

2 基于規則的兩階段啟發式算法

本文考慮解決具有多個揀貨員的在線訂單分批問題，其中沒有有關即將到來的訂單到達時間的信息。訂單分批問題的離線模式屬于NP-hard，而且其在線模式需要在合理的時間點內解決某些訂單，因此本文提出了一種基于規則的啟發式算法，以形成分批處理并形成揀貨路徑安排，將其分配給適當的揀貨員進行揀貨活動，目的是使所有批次的完成時間最小化。

2.1 整體算法思路

在訂單揀選系統中區分三種類型的決策點：

A：至少一個揀貨員無工作任務而且有一組訂單未被處理的時間點。

B：訂單到達的時間點，至少有一個揀貨員無工作任務，處于空閑狀態。

C：最后一個客戶訂單到達的時間點。

在每個決策點，都需要獲取離線版本問題的解決方案，如圖2。在時間t（每個決策點類型為A、B或C），將未處理的訂單輸入到批次生成系統中。如果存在未分配給任何批次的未處理訂單，則使用批次啟發式規則來生成一組批次，被輸入到分批處理操作系統中通過分配規則（HA1、HA2和HA3）選擇揀貨員進行揀貨。

圖2 基于在線規則的算法流程圖Fig.2 Algorithm flow chart based on online rules

HA1：使用選擇規則為每個空閑的揀貨員選擇一個批次，揀貨員立即啟動所選批次的揀配任務。

HA2：將所有未處理的批次分配給空閑的揀貨員，開始所有批次的揀配工作。

HA3：根據等式WTj=2ri+stj-sti，計算每個未處理批次定義等待閾值時間。在此等式中，j表示批次的索引，而i表示該批次中最長服務訂單的索引。ri代表客戶訂單i的到達時間。stj和sti分別代表批次j和訂單i的服務時間。根據批次的等待閾值，選擇具有最大等待閾值的批次和空閑揀貨員以等待可能的即將到來的訂單。然后將剩余的批次分配給其他閑置的揀貨員。如果只有一個批次和一個空閑揀貨員，則根據此規則，空閑揀貨員和批次將等待可能的即將到來的訂單。當空閑揀貨員和批次正在等待時，如果在出現新的決策點之前經過了等待閾值時間，則空閑揀貨員立即開始選擇批次進行揀貨任務。

2.2 分批算法

分批處理算法將采用k-means聚類算法，其在處理樣本量較大的分類問題時可以快速得到近似最優解[15]。由于訂單分批問題的樣本屬于分類型數據，采用歐式距離定義其特性不能很好地劃分數據之間的相似性。本文根據倉庫的具體環境，以及訂單分批的數據類型和數學模型結構，重新定義類中心和訂單到類中心的距離。

訂單分批的目標是減少同一批次所包含的商品種類數，加快揀選過程，因此設計兩種類中心：一種是按照商品種類劃分，定義某批次待揀商品種類為該批次的類中心。例如批次覆蓋3個訂單，訂單1商品集合為{C,D}，訂單2商品集合為{A,C,D}，訂單3商品集合為{D,E}，(1,0,1,1,1) 則被用來表示此批次的商品類中心。另一種是按照貨架位置劃分，定義某批次待揀商品所處貨架位置為該批次的類中心。例如批次覆蓋3 個訂單，訂單1商品涉及貨架{2,4,5}，訂單2商品涉及貨架{1,2,5}，訂單3 商品涉及貨架{4 ,5},(1,1,0,1,1) 則被用來表示此批次的貨架類中心。這兩種類中心通過權重進行合并，綜合考慮揀貨員的揀貨種類和揀貨行走距離。

2.3 揀貨路徑規劃算法

遺傳算法在訂單分批問題的研究中應用廣泛，充分證明了它在解決訂單分批問題上的可行性，且遺傳算法有很強的全局搜索能力和較強的魯棒性。本文設計了遺傳算法來分配批次訂單給相應的揀貨員，并對批次內的訂單進行排序，獲得較優的揀貨路徑。

在路徑規劃遺傳算法中，染色體通過SKU 對應的儲位單元進行編碼。因此，據表1中的示例，揀貨序列由每個批次中的具體商品對應的集合M={m1,m2,…,m1600}組成，并將m0輸入到序列的初始位置和最終位置。

表1 遺傳算法染色體結構Table 1 Chromosome structure of genetic algorithm

本文選擇機制借鑒輪盤賭模式，在初始解集中挑選出進行交叉變異的父代。染色體隨機兩點交叉形成新的子代，變換方式如圖3所示。生成的子代依據公式計算出的概率進行突變，突變方式如圖4所示進行基因位的交換。完成上述操作后，對父代和子代分別進行適應度值排序，選取父代x%的優秀個體和子代(100-x)%的優秀個體組成新的種群，既防止算法過早地進入收斂，也可保證最優解不會丟失。算法進行多次迭代，達到停止標準后輸出揀貨序列。

圖3 染色體交叉變換方式Fig.3 Chromosome crossover transformation method

圖4 染色體變異方式Fig.4 Chromosome variation method

3 算例實驗與結果分析

3.1 實驗參數設置

本文采用文獻[10]設計的數據進行實驗，將揀選區域擴展為雙區型倉庫，包含10個揀選巷道和1 600種商品。車輛配送時間17：00—18：00，訂單是14：00—18：00時間段內按照λ=14 的泊松分布隨機產生。倉庫揀選具體參數如表2所示。

表2 實驗參數Table 2 Experimental parameters

3.2 結果分析

文獻[10]基于巷道相似度進行訂單的分批處理，并考慮訂單的完成期限，設計實驗將文獻方法與本文提出的解決方案進行對比分析。在多揀貨員的揀貨系統中，揀貨員數量對結果有顯著影響，設立不同揀貨員數量進行多組實驗。

為明確訂單規模對結果的影響和驗證本文算法的有效性，設計實驗分別處理500、2 000、5 000 規模的在線訂單，在本文的在線訂單系統中分別使用本文算法、遺傳算法、蟻群算法、模擬退火算法進行三組實驗。

由圖5可知，當揀貨員為2人時，根據本文算法求解出的有效訂單數量較文獻算法少，但揀貨員數量多于2時，有效訂單數、配送率（有效訂單/總訂單）、平均有效訂單服務時間、訂單延遲時間、剩余時間這5個指標，本文算法優于文獻[10]算法。仿真結果表明，訂單分批與揀貨路徑的聯合調度方式可以有效減少訂單的延遲或過早處理的情況。

圖5 不同揀貨員數量實驗結果Fig.5 Experimental results of different numbers of pickers

圖6～圖8 分別為500、2 000、5 000 訂單規模下揀貨員行走里程的實驗計算結果。收斂圖表明k-means 算法與遺傳算法的結合可以快速得到較優結果，并且其結果優于其他單一算法所得結果，尤其是在5 000 規模訂單時可以得到遠優于其他算法的結果，可以證明本文算法在一定程度上提升了倉庫內的揀選效率。通過各算法之間的對比發現，k-means算法會首先將相關性較差的訂單合并方式去除，隨后采用遺傳算法對結果進一步優化得出近似最優解。

圖6 訂購500規模下不同算法收斂過程Fig.6 Convergence process of different algorithms under order of 500 scale

圖7 訂購2 000規模下不同算法收斂過程Fig.7 Convergence process of different algorithms under order of 2 000 scale

圖8 訂購5 000規模下不同算法收斂過程Fig.8 Convergence process of different algorithms under order of 5 000 scale

4 結束語

本文考慮了人工訂單揀選倉庫中具有多個揀貨員的在線訂單批處理和調度問題。難點在于從動態到達的訂單中形成批次，將其分配給揀貨員，并以最小化所有批次的最大完成時間為目標的揀配過程。為了使模型具有實際意義，將所有批次的最大完成時間作為目標函數，一方面它可以減少揀貨員的正常工作時間和加班時間，另一方面它可以減少交貨時間，從而提高服務水平。采用k-means 算法和遺傳算法構建基于規則的啟發式算法，用以解決在線訂單分批問題，并通過與相關文獻方法的對比實驗，驗證所提出算法的有效性。

未來的研究目標應該是擴展本文提出的模型，以考慮除揀貨工作以外的其他目標函數，并提出適當的算法來解決多目標問題。未來研究的第二個方向將是整合訂單批處理和車輛路徑問題，并共同優化它們。