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

閆 軍，常 樂，封麗華

1.蘭州交通大學(xué) 甘肅省物流與信息技術(shù)研究院，蘭州730070

2.蘭州交通大學(xué) 機電技術(shù)研究所，蘭州730070

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

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

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

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

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

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

1 問題描述和數(shù)學(xué)建模

1.1 問題描述與符號說明

在OOBP中，運輸存貨單位（stock keeping unit，SKU）被用于區(qū)分倉庫內(nèi)的N種產(chǎn)品類型，在某一時刻下庫存量為X={x1,x2,…,xN}，其中i=(1,2,…,N)表示第i個SKU。每個i都具有變量wi給出的標(biāo)準(zhǔn)重量/體積，并且揀選一次的容量（揀選小車容量）由G≥max{wi,i=1,2,…,n} 進行限制。一個工作周期內(nèi)的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} 表示，其中下標(biāo)m是總批次數(shù)，而Bk表示第k批次?k={1,2,…,m}，每個Bk是由Bk={q1,q2,…,qN}表示的PO的子集，而qi是一個或多個訂單的某個SKU 的需求數(shù)量。在本文的訂單分批揀選系統(tǒng)中需要考慮：（1）應(yīng)將哪些客戶訂單分配給同一批次；（2）每個批次開始揀選的時間；（3）每批訂單應(yīng)由哪個揀選員進行揀選。根據(jù)以上訂單分批過程和系統(tǒng)要求，得出防止訂單揀選過早或延誤的揀選次序規(guī)劃，并最大程度地減少揀選路徑。

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

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

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

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

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

1.2 模型構(gòu)建

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

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

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

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

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

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

2 基于規(guī)則的兩階段啟發(fā)式算法

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

2.1 整體算法思路

在訂單揀選系統(tǒng)中區(qū)分三種類型的決策點：

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

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

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

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

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

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

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

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

2.2 分批算法

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

訂單分批的目標(biāo)是減少同一批次所包含的商品種類數(shù)，加快揀選過程，因此設(shè)計兩種類中心：一種是按照商品種類劃分，定義某批次待揀商品種類為該批次的類中心。例如批次覆蓋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) 則被用來表示此批次的貨架類中心。這兩種類中心通過權(quán)重進行合并，綜合考慮揀貨員的揀貨種類和揀貨行走距離。

2.3 揀貨路徑規(guī)劃算法

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

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

表1 遺傳算法染色體結(jié)構(gòu)Table 1 Chromosome structure of genetic algorithm

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

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

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

3 算例實驗與結(jié)果分析

3.1 實驗參數(shù)設(shè)置

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

表2 實驗參數(shù)Table 2 Experimental parameters

3.2 結(jié)果分析

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

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

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

圖5 不同揀貨員數(shù)量實驗結(jié)果Fig.5 Experimental results of different numbers of pickers

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

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

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

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

4 結(jié)束語

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

未來的研究目標(biāo)應(yīng)該是擴展本文提出的模型，以考慮除揀貨工作以外的其他目標(biāo)函數(shù)，并提出適當(dāng)?shù)乃惴▉斫鉀Q多目標(biāo)問題。未來研究的第二個方向?qū)⑹钦嫌唵闻幚砗蛙囕v路徑問題，并共同優(yōu)化它們。