李珍萍,韓倩倩，儀明超

(北京物資學院 信息學院,北京 101149)

0 引言

隨著電商企業(yè)的發(fā)展，越來越多的電商企業(yè)推出了當日達或次日達的配送服務。同時，伴隨電商主播的帶貨熱潮，電商企業(yè)每天要處理的訂單數(shù)量激增，如何對這些多品種、小批量的訂單進行快速揀選，提高揀選作業(yè)效率、降低揀選成本，是電商企業(yè)關(guān)注的主要問題之一。

傳統(tǒng)倉庫中采取“人到貨”揀選模式，揀選人員行走距離長，造成訂單揀選時間較長、人力勞動成本較大的問題。為減少訂單揀選時間，企業(yè)通常會采用以下兩種方式來提高揀選作業(yè)效率[1]：①改變揀選策略，如采取分批揀選[2]或分區(qū)揀選策略[3]；②配置“貨到人”揀選系統(tǒng)[4]，如自動小車存儲及取貨系統(tǒng)(Autonomous Vehicle Storage and Retrieval System，AVS/RS)、基于自動引導小車(Automated Guided Vehicle，AGV)的“貨到人”系統(tǒng)、基于垂直升降機模塊的自動化立體倉庫等。

訂單分批策略是指將系統(tǒng)中到達的待揀選訂單(訂單池中的訂單)按照某種規(guī)則劃分成若干個批次，將同一批次訂單中的相同品項匯總后進行一批揀選[5]。傳統(tǒng)的“人到貨”系統(tǒng)訂單分批揀選問題的研究成果已經(jīng)十分豐富[6-9]，針對近年來發(fā)展起來的“貨到人”系統(tǒng)的研究尚在起步階段[10-16]，大部分研究成果集中在儲位優(yōu)化[17-19]與系統(tǒng)設計[20-21]方面，很少涉及訂單分批問題。

李珍萍等[11]針對基于AGV的“貨到人”系統(tǒng)中訂單分批問題，建立了以訂單分批揀選總成本最小化為目標的整數(shù)規(guī)劃模型，并設計了K-max聚類算法進行求解；XIANG等[12]針對Kiva公司研發(fā)的貨到人系統(tǒng)中的訂單分批揀選問題進行研究，以搬運貨架的總次數(shù)最小為目標構(gòu)建了整數(shù)規(guī)劃模型，利用訂單關(guān)聯(lián)度設計啟發(fā)式算法求解；BOYSEN等[13]針對基于AGV的“貨到人”系統(tǒng)中的特定批次的訂單排序問題，以搬運貨架總次數(shù)最小為目標構(gòu)建了混合整數(shù)規(guī)劃模型，利用啟發(fā)式算法與動態(tài)規(guī)劃算法進行求解；ELSAYED等[14]研究了自動存儲及取貨系統(tǒng)的訂單分批問題，以最小化訂單總完成時間為目標設計了多種啟發(fā)式算法;Fü?LER等[15]研究了自動存儲及取貨系統(tǒng)訂單分批后的批次內(nèi)部訂單排序問題，以最小化揀選員揀選次數(shù)為目標建立了混合整數(shù)規(guī)劃模型，并設計了兩階段啟發(fā)式算法進行求解；NICOLAS等[16]考慮了配置升降模塊的自動存儲及取貨系統(tǒng)中的訂單分批揀選問題，以訂單揀選結(jié)束時間最早為目標建立了整數(shù)規(guī)劃模型，并利用商業(yè)求解器CPLEX進行求解。

以上研究均以提高揀選工作效率或降低揀選成本為目標建立混合整數(shù)規(guī)劃模型，由于訂單分批揀選問題往往包含聚類問題、集合覆蓋問題等多個NP-hard子問題，因此訂單分批揀選問題屬于NP-hard問題，現(xiàn)有文獻均對問題進行了必要的簡化并通過設計啟發(fā)式算法進行求解。以上文獻都沒考慮訂單中的商品訂購數(shù)量和每個貨箱中存放的商品數(shù)量，假設一個貨箱中任意一種商品的存儲量均可滿足一個(或一批)訂單對該商品的需求量，且大多文獻中都假設一個貨箱只存儲一種商品，一種商品只存儲在一個貨箱中。在實際倉庫中，為減少貨箱出庫次數(shù)，企業(yè)會將經(jīng)常出現(xiàn)在同一個訂單中的多種商品存儲在同一個貨箱中，為了同時滿足多個揀選臺對同一種商品的需求，一種商品可能被存儲在多個貨箱(儲位)中。當一個貨箱(儲位)中存儲的某種商品數(shù)量小于一批訂單對該商品的總需求量時，需要從多個貨箱中揀取商品才能滿足該批次訂單的總需求，李珍萍等[22]針對該場景下的訂單分批揀選問題進行了初步研究，假設每個貨箱每次出庫只能用于一個批次的訂單揀選，且服務完該批次訂單立刻回庫。在這一假設下，以貨箱總出庫次數(shù)最少為目標建立數(shù)學模型，并設計了求解模型的算法。因為每個貨箱中包含的商品數(shù)量和商品種類有限，揀選每批次的所有訂單需要使用的貨箱較多，所以可能出現(xiàn)揀選不同批次的訂單需要出庫同一個貨箱的情況。因此，在實際訂單揀選中，AVS/RS系統(tǒng)中通常會設置容量有限的貨箱緩存區(qū)，用于暫時存放那些需要在多個批次訂單揀選中重復使用的貨箱。如果將使用頻率較高的貨箱暫存在貨箱緩存區(qū)，用于多個不同批次訂單的揀選，則可以減少貨箱出庫次數(shù)，縮短訂單揀選時間。

目前，對設置貨箱緩存區(qū)的“貨到人”系統(tǒng)訂單分批問題研究較少。JIANG等[23]研究了“人到貨”系統(tǒng)中帶有緩存區(qū)的訂單分批及批次排序問題，以最小化總揀選時間為目標建立訂單分批揀選模型；吳穎穎等[24]研究設置貨箱緩存區(qū)的“貨到人”系統(tǒng)中的訂單排序問題，將訂單耦合因子作為參數(shù)，建立訂單排序優(yōu)化模型；田彬等[25]研究了設置貨箱緩存區(qū)的“四向車”揀選系統(tǒng)中的批量訂單排序問題，建立了基于改進耦合度的訂單排序模型；夏德龍等[26]針對設置貨架緩存區(qū)的“貨到人”系統(tǒng)訂單排序問題，提出了以最大化減少貨架搬運次數(shù)為目標的訂單排序模型。由于“人到貨”系統(tǒng)與“貨到人”系統(tǒng)存在本質(zhì)的差別，“人到貨”系統(tǒng)中的訂單分批及排序方法不能直接應用到“貨到人”系統(tǒng)中。而且，現(xiàn)有的考慮貨箱緩存區(qū)的訂單排序問題中，未考慮商品訂購數(shù)量與貨箱中的商品存儲數(shù)量。因此現(xiàn)有文獻研究的問題與本文研究的場景不同，其結(jié)果不能直接解決本文的問題。

本文將在考慮訂單中商品訂購數(shù)量的前提下，研究設置貨箱緩存區(qū)的AVS/RS系統(tǒng)訂單分批揀選問題?？紤]到同一批次的訂單包含多種不同商品，且不同批次的訂單中可能包含相同的商品，一方面在揀選每個批次訂單時，需要出庫多個貨箱來滿足該批次的商品需求，另一方面，揀選不同批次訂單可能需要出庫同一個貨箱。通過在揀選臺附近設置貨箱緩存區(qū)，將使用頻率較高的貨箱暫存在貨箱緩存區(qū)，減少其出入庫次數(shù)?？紤]到緩存區(qū)的容量有限，為了提高有限緩存區(qū)的利用率，應盡可能減少或避免長時間不用的貨箱占用緩存區(qū)的情況發(fā)生。由于各個批次訂單的揀選順序直接影響貨箱出庫結(jié)果和緩存區(qū)的占用情況，在研究訂單分批問題時，應同時考慮批次的揀選順序、貨箱出庫方案以及出庫貨箱在緩存區(qū)的存放策略等，使得有限的緩存區(qū)得以高效利用，達到減少貨箱出入庫總次數(shù)、提高揀選效率的目的。

本文將建立該問題的聯(lián)合優(yōu)化模型，設計求解模型的三階段啟發(fā)式算法，并通過模擬計算驗證模型和算法的有效性，進一步分析揀選臺容量和緩存區(qū)容量變化對貨箱出庫總次數(shù)的影響，以及設置貨箱緩存區(qū)的優(yōu)越性。

1 自動小車存儲及取貨系統(tǒng)的工序流程

本文研究的自動小車存儲與取貨系統(tǒng)(AVS/RS)布局如圖1所示，該系統(tǒng)主要包括存儲區(qū)、輸送區(qū)和揀選區(qū)。存儲區(qū)由料箱式自動化立體倉庫、多層穿梭小車、出入庫緩存區(qū)和提升機組成，每個巷道旁的兩排貨架為一組，一組貨架共用一套輸送設備完成貨箱的出入庫操作，每層的穿梭小車負責貨箱在儲位與出入庫緩存區(qū)之間的水平輸送，提升機可以實現(xiàn)貨箱在出入庫緩存區(qū)與傳送帶之間的垂直輸送；輸送區(qū)主要包括出入庫傳送帶與循環(huán)輸送線，通過輸送區(qū)把不同巷道的貨箱輸出至指定揀選臺，或?qū)⒁淹瓿蓲x任務的貨箱輸送回庫；揀選區(qū)主要有揀選臺、貨箱緩存區(qū)與倉儲信息設備等，每個揀選臺可以同時揀選多個訂單(即一批訂單)，揀選員通過系統(tǒng)倉儲管理顯示屏、燈光指引技術(shù)、電子標簽技術(shù)等信息化輔助手段，根據(jù)訂單中訂購的商品從出庫貨箱或緩存區(qū)貨箱中揀取相應的商品。

在設置貨箱緩存區(qū)的AVS/RS系統(tǒng)中，當只有一個揀選臺時，訂單分批揀選過程如圖2所示。首先按照某種分批規(guī)則對訂單池內(nèi)的訂單進行分批，然后根據(jù)每個批次訂單中包含的商品信息計算揀選該批次訂單需要出庫的貨箱，通過穿梭小車、提升機與傳送帶等共同協(xié)作，將貨箱輸送到揀選臺供揀選員揀取商品。當揀選第k批次時，系統(tǒng)將該批次需要使用的每個貨箱m依次輸送至揀選臺，揀選完成后，根據(jù)揀選后續(xù)批次訂單是否需要使用貨箱m以及緩存區(qū)是否還有空余位置等信息，作出貨箱是否需要回庫的決策，將不需要回庫的貨箱m存放到貨箱緩存區(qū)，將需要回庫的貨箱回庫。若貨箱m被存放在緩存區(qū)，且揀選第k+1批次時需要該貨箱，則直接從緩存區(qū)調(diào)用貨箱m，完成揀選后再次判斷貨箱m是否需要回庫。

2 設置貨箱緩存區(qū)的訂單分批揀選問題數(shù)學模型

2.1 問題描述與分析

本文研究的設置貨箱緩存區(qū)的AVS/RS包含一個揀選臺，貨箱緩存區(qū)最多可以同時存放H個貨箱。已知倉庫中M個貨箱共存儲了T種商品，一個貨箱可存儲一種或多種商品，已知每個貨箱中存儲的各種商品數(shù)量，且每個貨箱中存儲的各種商品總量不超過Q。 在一段時間內(nèi)，配送中心共接到N個訂單O={O1,O2,…,ON}，已知每個訂單Oi(i=1,2,…,N)中各種商品的數(shù)量Di=(di1,di2,…diT)(dit指訂單i中商品t的需求數(shù)量)。由于揀選臺空間限制，每個批次的訂單數(shù)量不能超過C。 問題是如何將訂單進行分批并確定批次揀選順序，以及揀選每個批次的貨箱出入庫策略，才能使出庫貨箱總次數(shù)最小。

為了簡化問題，本文作如下假設：

(1)每個訂單箱只能容納一個訂單中的所有商品，揀選臺可以同時容納C個訂單箱。

(2)系統(tǒng)使用標準化貨箱，貨箱的大小一樣。貨箱緩存區(qū)最多可以同時容納H個貨箱。

(3)假設倉庫中每種商品的總庫存量可以滿足所有訂單對該商品的總訂購量，不考慮缺貨的情況。

(4)每個貨箱每次出入庫時間相同，揀選員從貨箱中揀取每件商品的時間相同，揀選員從貨箱中揀取商品時的移動距離(時間)忽略不計。

基于以上假設，揀選所有訂單的總時間可以表示為揀選訂單中的商品次數(shù)和貨箱出入庫次數(shù)的函數(shù)。揀選訂單中的商品次數(shù)與訂單中商品總數(shù)量成比例，對于給定的待揀選訂單，其中包含的所有商品總量為確定的常數(shù)，因此揀選訂單中商品總時間為常數(shù)；在假設4下，貨箱出庫總次數(shù)越少，系統(tǒng)的揀選效率越高。因此，對于給定的待揀選訂單，影響訂單揀選效率的主要因素為貨箱的出入庫次數(shù)，本文的優(yōu)化目標為最小化貨箱出庫總次數(shù)。

2.2 模型建立

本文模型符號和參數(shù)定義如下：

i為訂單序號,i=1,2,…,N；

k為批次順序,k=1,2,…,K；

m為貨箱序號,m=1,2,…,M；

t為商品類別序號,t=1,2,…,T；

C為每個批次訂單數(shù)量上限；

Q為每個貨箱最大存儲量；

H為貨箱緩存區(qū)的容量；

dit為訂單i對商品t的需求數(shù)量；

決策變量定義如下：

smkt為揀選批次k時需要從貨箱m中揀選的商品t數(shù)量。

建立混合整數(shù)規(guī)劃模型(模型一)：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

rmk≤ymk,?k=1,2,…,K-1,?m;

(8)

(9)

ym1=um1,?m;

(10)

ymk=umk+rm,k-1,?k=2,3,…,K,?m;

(11)

(12)

xik,ymk,umk∈{0,1},?i,m,k;

(13)

rmk∈{0,1},?m,k=1,2,…,K-1;

(14)

smkt∈Z+,?m,k,t。

(15)

其中：目標函數(shù)(1)表示使貨箱的出庫總次數(shù)極小化。約束條件(2)表示任意一個訂單恰好被分配到一個批次中；約束條件(3)表示每個批次包含的訂單數(shù)量不超過揀選臺容量；約束條件(4)表示每個批次中包含的每種商品總需求量與從出庫貨箱中揀選的該商品總量相等；約束條件(5)表示如果揀選批次k時，從貨箱m中揀取了某種商品，則決策變量ymk=1；約束條件(6)表示如果揀選批次k時沒有從貨箱m中揀取任何商品，則決策變量ymk=0；約束條件(7)表示從任意貨箱m中揀取同一種商品t的總數(shù)量限制；約束條件(8)表示只有揀選批次k時使用了貨箱m，貨箱m才有可能在揀選完批次k之后被存入緩存區(qū)；約束條件(9)表示揀選批次k之后被存入緩存區(qū)的貨箱m一定會在后續(xù)批次揀選中被使用；換言之，對于后續(xù)批次中均不需要使用的貨箱，不必存入緩存區(qū)；約束條件(10)表示揀選第1批次需要使用的貨箱只能是出庫貨箱；約束條件(11)表示揀選第2到K批次需要使用的貨箱一定是緩存區(qū)存放的貨箱或出庫貨箱；約束條件(12)表示揀選完任意批次k之后存入緩存區(qū)的貨箱總數(shù)不能超過緩存區(qū)總?cè)萘?；約束條件(13)～(15)為決策變量取值約束。

訂單分批揀選聯(lián)合優(yōu)化問題的混合整數(shù)規(guī)劃模型中同時包含了訂單分批決策、批次排序決策、揀選每個批次需要出庫的貨箱和從每個貨箱中揀取的商品數(shù)量，以及需要存入緩存區(qū)的貨箱等決策。通過求解該模型可以得到使出庫貨箱總次數(shù)達到最小的訂單分批揀選方案。

例1已知8種商品存儲在10個貨箱中，具體存儲信息如圖3所示，英文字母表示商品種類，數(shù)字表示存儲量。

假設某段時間內(nèi)收到12個訂單, 每個訂單中訂購的各種商品及數(shù)量如下，其中括號中的數(shù)字表示商品的訂購數(shù)量：

O1={A(1),C(2)}，O2={A(1),F(2)}，O3={A(1),B(1),C(1)}，O4={C(1),H(1)}，O5={B(1),D(1)}，O6={D(1),E(1)}，O7={F(1),G(2)}，O8={F(2)}，O9={B(1),D(1),E(1)}，O10={D(3)}，O11={B(2),F(1)}，O12={G(1),H(1)}。

已知揀選臺容量C=3，貨箱緩存區(qū)容量H=2，利用GUROBI軟件求解混合整數(shù)規(guī)劃模型，得到最優(yōu)分批揀選策略如表1所示。12個訂單被分為4個批次，表1中第1列給出了每個批次的揀選順序，第2列表示每個批次中包含的訂單集合，第3列表示揀選每個批次訂單需要使用的貨箱集合，第4列表示揀選每個批次訂單需要出庫的貨箱集合，第5列表示揀選完每個批次之后需要存入緩存區(qū)的貨箱集合。按照表1所示的最優(yōu)揀選策略，第一批次包含訂單O1,O2,O8，揀選該批次訂單需要使用貨箱5、7，出庫貨箱為5、7；第一批次揀選完成之后，貨箱5被存入緩存區(qū)，供揀選后續(xù)批次訂單使用。第二批次包含訂單O6,O9,O10，揀選該批次需要使用貨箱4、5、10，由于貨箱5已經(jīng)在緩存區(qū)，所以只需再出庫貨箱4、10；第二批次揀選完畢后，將貨箱10存入緩存區(qū)，此時緩存區(qū)存放的貨箱為5、10；第三批次包含訂單O3,O4,O12，揀選該批次訂單需要使用貨箱2、5、10，其中貨箱5、10直接從緩存區(qū)調(diào)用，因此只需要出庫貨箱2即可；揀選完第三批訂單之后，貨箱2、5被存入緩存區(qū)；揀選第四批訂單O5,O7,O11需要使用貨箱2、5，由于貨箱2、5均在緩存區(qū)，所以直接調(diào)用，不需要再出庫其他貨箱；第四批次訂單揀選完畢后所有貨箱回庫。按照以上方案分批揀選，總共需要出庫貨箱5次。

表1 示例對應的最優(yōu)訂單分批揀選方案

如果不設置貨箱緩存區(qū)，仍然按照表1中的訂單分批結(jié)果進行揀選，則揀選4個批次訂單需要出庫貨箱的總次數(shù)為10次(實際上，在不設置貨箱緩存區(qū)的情況下，最優(yōu)分批結(jié)果與表1中的分批結(jié)果可能不同，本文將在4.4節(jié)中進行討論)；由以上分析可以發(fā)現(xiàn)，通過設置貨箱緩存區(qū)，有效避免了同一貨箱在不同批次揀選時重復出入庫的操作，使貨箱出庫總次數(shù)減少了50%，大大提高了揀選效率，降低了揀選成本。

3 啟發(fā)式算法

訂單分批揀選問題可以分解為訂單分批、批次排序、確定揀選每個批次的貨箱出入庫方案等3個相互關(guān)聯(lián)的子問題。其中訂單分批問題本質(zhì)上是對訂單進行聚類，將關(guān)聯(lián)度較大的訂單劃分到一個批次中[27]；確定服務每個批次需要使用的貨箱集合可以歸結(jié)為集合覆蓋問題；確定分批后的批次揀選順序問題可以歸結(jié)為排序問題或帶約束的旅行商問題，以上子問題均屬于NP-hard問題。因為實際中，訂單分批揀選問題屬于運作層面的決策問題，需要在短時間內(nèi)給出方案，所以需要設計快速有效的求解算法。本章將結(jié)合問題數(shù)學模型的結(jié)構(gòu)特征，設計三階段啟發(fā)式算法。

3.1 計算訂單之間的加權(quán)相似度

利用訂單之間的加權(quán)相似度進行分批的基本思想為：通過訂單中包含的商品種類與商品在貨箱中的存儲位置信息，分別計算任意兩個訂單之間的品項相似系數(shù)與儲位相似系數(shù)，再根據(jù)給定的權(quán)重，計算訂單之間的加權(quán)相似度；根據(jù)訂單之間的加權(quán)相似度，利用貪婪規(guī)則對訂單進行聚類，盡可能地將加權(quán)相似度大的訂單分在一個批次中，從而減少貨箱的總出入庫次數(shù)。

首先借鑒文獻[6]提出的巷道相似系數(shù)，將任意兩個訂單中訂購的相同商品種類數(shù)占兩個訂單中的總商品種類數(shù)的比例，定義為兩個訂單之間的品項相似系數(shù)，即訂單Oi和訂單Oj的品項相似系數(shù)

式中Fi為訂單Oi中的商品種類集合。

然后，定義訂單之間的儲位相似系數(shù)。在AVS/RS系統(tǒng)中，由于一個貨箱可能存儲多種商品，出庫一個貨箱可以同時揀選多種商品，滿足一個或多個訂單中的商品需求。給定任意兩個訂單，根據(jù)兩個訂單中商品占用相同貨箱的比例，定義訂單之間的儲位相似系數(shù)[28]。

令VAi=(a1i,a2i,…aMi)表示訂單Oi的商品占用貨箱信息，其中

ami=

計算訂單之間的加權(quán)相似度。對于給定的加權(quán)系數(shù)ω(0≤ω≤1)，加權(quán)相似度

利用上式分別計算任意兩個訂單之間的加權(quán)相似度，則加權(quán)相似矩陣可以表示為：

其中g(shù)ij表示訂單Oi和訂單Oj的加權(quán)相似度。為了方便計算，當i=j時，令gij=0。

從加權(quán)相似度的定義可以看出，加權(quán)系數(shù)ω的取值直接影響加權(quán)相似度的計算結(jié)果。本文直接根據(jù)從貨箱中揀取一件商品的成本和出庫一個貨箱的成本之比，確定加權(quán)系數(shù)ω的取值[29]。

3.2 三階段啟發(fā)式算法

本節(jié)將基于訂單分批揀選聯(lián)合優(yōu)化問題包含的3個子問題，設計三階段啟發(fā)式算法。第一階段利用貪婪算法求出訂單分批結(jié)果，分別計算揀選每個批次需要使用的貨箱集合；第二階段求解各個批次的揀選順序；第三階段確定揀選每個批次時需要出庫的貨箱和揀選之后需要放入緩存區(qū)的貨箱。

3.2.1 第一階段：設計貪婪算法求出訂單分批結(jié)果及揀選每個批次需要使用的最少貨箱集合

利用加權(quán)相似度矩陣，設計貪婪算法求解訂單分批結(jié)果，并確定揀選每個批次需要使用的最少貨箱集合，本階段算法分為以下3步：

步驟1生成初始訂單分批結(jié)果。

步驟1.1 設置參數(shù)ω，得到加權(quán)相似度矩陣G。

步驟1.2 從矩陣G中尋找最大相似度系數(shù)gij及相應的訂單i與訂單j。 若gij<0，則轉(zhuǎn)步驟1.6；否則，轉(zhuǎn)步驟1.3。

步驟1.3 根據(jù)以下4種可能出現(xiàn)的情景，為訂單i與訂單j指派批次：

(1)兩個訂單均被指派批次，則轉(zhuǎn)步驟1.4。

(2)恰有一個訂單被指派批次，則將另一個訂單指派到相同的批次中，轉(zhuǎn)步驟1.4。

(3)兩個訂單均未被指派批次，且現(xiàn)有的非空批次數(shù)量小于K，則開啟一個新批次，并將兩個訂單同時指派到新批次中，轉(zhuǎn)步驟1.4。

(4)訂單i與訂單j均未被指派批次，且現(xiàn)有的非空批次數(shù)量等于K。 此時，如果能夠找到一個批次，其中包含的訂單數(shù)量小于C-2，則將兩個訂單同時指派到該批次中；否則將兩個訂單指派到任意兩個包含C-1個訂單的批次中，轉(zhuǎn)步驟1.4。

步驟1.4 將已指派批次的兩個訂單之間的相似度gij修改成-1。

步驟1.5 檢查每個批次中的訂單個數(shù)q是否達到上限C。

若q=C，則該批次中的訂單個數(shù)已達到上限，將該批次中各個訂單對應的加權(quán)相似度系數(shù)均修改為-1，轉(zhuǎn)步驟1.2；如果q

步驟1.6 結(jié)束，輸出初始訂單分批結(jié)果x0。

步驟2計算揀選每個批次訂單需要使用的最少數(shù)量貨箱集合。

步驟2.1 用Pk=(pk1,pk2,…,pkT)表示批次k中所有訂單訂購的各種商品總數(shù)量，其中元素pkt代表批次k中訂購商品t的總數(shù)量。令k=1，轉(zhuǎn)步驟2.2。

步驟2.2 按下列公式選擇包含批次k中尚未揀選商品數(shù)量最多的貨箱m*：

更新貨箱m*中剩余的商品存儲量和批次k中尚未滿足的商品需求量：

cm*t=cm*t-min{cm*t,pkt},?t;

pkt=pkt-min{cm*t,pkt}，?t。

步驟2.4 令k=k+1，若k≤K，轉(zhuǎn)步驟2.2；否則，轉(zhuǎn)步驟2.5；

步驟2.5 計算結(jié)束，輸出揀選每個批次需要使用的貨箱集合(對應決策變量y0)，計算揀選所有批次需要使用的貨箱總數(shù)量z0。

步驟3利用鄰域搜索方法改進訂單分批揀選初始方案x0和y0，以減少揀選過程中使用貨箱總次數(shù)z0。

輸入：貪婪算法求得的訂單分批揀選初始方案x0和y0，揀選所有批次需要使用的貨箱總次數(shù)z0；設置最大迭代次數(shù)Lmax，移除操作D，插入操作R。

輸出：近似最優(yōu)分批揀選方案x*=xc，y*=yc，目標函數(shù)值z*=zc。

初始化：當前解與當前目標函數(shù)值分別設置為：xc=x0,yc=y0,zc=z0，迭代次數(shù)l=0。

當l≤Lmax時，循環(huán)執(zhí)行步驟3.1～步驟3.3

步驟3.1 在初始分批結(jié)果中隨機選取20%的批次，在每個批次中任意移除一個訂單，生成破壞解xdestroy。 將已經(jīng)移除的訂單放到集合U中，等待重新分配批次。

步驟3.2 按照貪婪插入規(guī)則為被移除的訂單i∈U重新指派批次，生成鄰域解xrepair。

具體方法為：對于每一個訂單i∈U，計算其與破壞解xdestroy中每個未飽和批次中各個訂單的平均相似度，將訂單i重新指派到平均相似度最大的批次中。

步驟3.3 計算鄰域解xrepair對應訂單分批結(jié)果，揀選每個批次需要使用的貨箱信息yrepair，以及揀選所有批次需要使用的貨箱總數(shù)量zrepair。

若zrepair

令l=l+1，轉(zhuǎn)步驟3.1。

3.2.2 第二階段:利用鄰域搜索方法生成批次揀選順序，使相鄰兩個批次使用的相同貨箱數(shù)量之和達到最大

首先，利用貪婪算法生成各個批次的初始揀選順序π：任意選擇一個批次作為揀選序列中的第一個批次，按照貪婪規(guī)則，從未排序的批次中依次選擇與揀選序列中最后批次共用貨箱數(shù)量最多的批次加入揀選序列中，直到所有批次均加入序列中，生成初始可行解π。 然后，采用兩種局部搜索方法生成鄰域解，利用模擬退火機制逐步改進當前解，得到近似最優(yōu)解。本節(jié)采用的兩種生成鄰域解的操作分別是插入操作(改變π中的某一批次在序列中的位置)與交換操作(將π中的兩個批次在序列中位置進行交換)。

算法具體步驟如下：

輸入：初始可行解π、初始溫度τ、降溫速率λ、最大迭代次數(shù)Tmax、插入概率p；

輸出：近似最優(yōu)解πb。

步驟1利用貪婪算法生成各個批次的初始揀選順序π，計算按照該順序揀選時，相鄰兩個批次之間共用貨箱的總次數(shù)f(π)。

步驟2初始化當前解與及對應的目標函數(shù)值，令πc=π,f(πc)=f(π)。 初始化最優(yōu)解與最優(yōu)目標函數(shù)值，令πb=π,f(πb)=f(π)。

步驟3當t≤Tmax時，循環(huán)執(zhí)行以下(1)～(4)的操作：

(1)以概率p執(zhí)行插入操作，否則執(zhí)行交換操作，得到鄰域解π′，并計算其對應的目標函數(shù)值f(π′)；

(2)若f(π′)>f(πc)，則更新當前解與當前值；否則以一定的模擬退火概率接受鄰域解；

(3)若f(πc)>f(πb)，則更新最優(yōu)解與最優(yōu)值，令πb=πc，f(πb)=f(πc)否則不更新。

(4)更新當前溫度與當前迭代次數(shù)，令τ=τ·λ，t=t+1。

3.2.3 第三階段：確定按近似最優(yōu)解順序揀選每個批次時，實際出庫的貨箱、放入緩存區(qū)的貨箱及貨箱出庫總次數(shù)(整數(shù)規(guī)劃的目標函數(shù)值)

輸入：揀選各個批次k需要使用的貨箱集合Yk={m|ymk=1，m∈M},k∈K;

步驟1令R0=?，即貨箱緩存區(qū)初始狀態(tài)為空；令k=1，對任意的m∈M，令um1=ym1，U1=Y1， 表示揀選第1批次訂單需要使用的貨箱均為出庫貨箱。

步驟3對Uk∪Rk-1中的貨箱，按照em值由小到大排序，依次選擇em值較小的前min{H,|Uk∪Rk-1|}個貨箱存入緩存區(qū)，對于每個被選中的貨箱m，令rmk=1；計算揀選批次k之后存入緩存區(qū)的貨箱集合Rk={m|rmk=1}。

步驟4計算揀選第k+1批次需要出庫的貨箱集合Uk+1={m|m∈Yk+1且ym,k+1-rmk=1}。 對?m∈Uk+1，令um,k+1=1。

步驟5若k+1

4 模擬計算與結(jié)果分析

為驗證本文模型與算法的有效性，本章設計多個算例進行模擬計算。對于規(guī)模較小的算例，利用GUROBI求解器求解混合整數(shù)規(guī)劃模型得到的精確最優(yōu)解與啟發(fā)式算法求得的近似最優(yōu)解進行對比，分析啟發(fā)式算法的求解效果。當算例規(guī)模增大時，GUROBI求解器無法在可接受的時間內(nèi)求出精確最優(yōu)解，為此本文設置固定的運行時間，并比較GUROBI求解器在給定的運行時間內(nèi)得到的最好解與啟發(fā)式算法求得的近似最優(yōu)解的差異。對于每個算例，分別記錄兩種算法的運行時間，并進行對比分析。最后，針對揀選臺容量和貨箱緩存區(qū)容量變化對最優(yōu)解的影響進行了靈敏度分析，并將設置貨箱緩存區(qū)的訂單分批揀選模型與不設置貨箱緩存區(qū)的訂單分批揀選模型進行比較，分析設置貨箱緩存區(qū)的優(yōu)越性，并提出確定緩存區(qū)容量的思路。

4.1 參數(shù)設置與算例生成

設置商品種類數(shù)T、貨箱個數(shù)M、訂單數(shù)量N等3個參數(shù)的不同取值生成28組算例。設揀選臺容量C=3，貨箱緩存區(qū)容量H=2。 每個貨箱容量Q=20，每個貨箱中最多存儲4種商品；每個訂單中訂購的商品種類為1～4種，每種商品的訂購量為{1,2,3,4,5}的任意取值。

4.2 小算例計算結(jié)果與分析

本節(jié)將通過小算例分析啟發(fā)式算法的求解精度與計算時間。對于每一個算例，先利用GUROBI求解混合整數(shù)規(guī)劃模型得到精確最優(yōu)解，再利用啟發(fā)式算法運算10次，得到近似最優(yōu)解，取啟發(fā)式算法10次運算的平均值與精確最優(yōu)解進行對比。

啟發(fā)式算法的參數(shù)設置如下：相似度加權(quán)系數(shù)ω=0.5，第一階段迭代次數(shù)Lmax=100，模擬退火的初溫τ=200，降溫速率λ=0.9，第二階段最大迭代次數(shù)Tmax=200，生成鄰域解的插入概率p=0.2。 本文使用GUROBI 9.0.2求解混合整數(shù)規(guī)劃模型；利用MATLAB編程實現(xiàn)三階段算法，并在Inter Core i5-8 265U筆記本電腦運行。

首先，將啟發(fā)式算法10次運算求得的平均結(jié)果與利用GUROBI求解器得到的精確解進行對比，分析啟發(fā)式算法的近似比。表2列出了兩種方法的詳細求解結(jié)果。在每個算例中，精確解均優(yōu)于啟發(fā)式算法的平均值，啟發(fā)式算法平均值的近似比不超過1.4。啟發(fā)式算法的平均求解時間均在3 s以內(nèi)，而GUROBI的求解時間隨問題規(guī)模的增大呈指數(shù)增長，對于很小的算例可以在1 s以內(nèi)求得最優(yōu)解，隨著問題規(guī)模的增大，GUROBI的求解時間遠遠大于啟發(fā)式算法的平均求解時間。

表2 小規(guī)模算例的求解結(jié)果分析

隨著算例規(guī)模的增大，GUROBI的求解時間越來越長，對于中等規(guī)模的問題，求解器無法在2 000 s內(nèi)得到精確最優(yōu)解。由于訂單分批揀選問題屬于運作管理問題，需要在短時間內(nèi)作出決策，假設實際中可接受的最長決策時間為2 000 s。設定GUROBI求解器的運算時間為2 000 s，將求解器在2 000 s內(nèi)得到的最好解與啟發(fā)式算法求出的近似最優(yōu)解進行對比，分析啟發(fā)式算法的求解效果，詳細結(jié)果如表3所示。從表3可以看出，對于所有的算例，啟發(fā)式算法的最長平均求解時間不超過90 s。其中，只有對訂單數(shù)量為50或商品數(shù)量為20且訂單數(shù)量為100的4個小算例，求解器在2 000 s之內(nèi)得到了比啟發(fā)式算法更好的解，對于其余的16組算例，特別是訂單數(shù)量超過100的所有算例，啟發(fā)式算法得到的近似最優(yōu)解均明顯優(yōu)于GUROBI求解器在2 000 s內(nèi)得到的最好解。當固定商品數(shù)量和貨架數(shù)量時，隨著待揀選訂單數(shù)量的增加，啟發(fā)式算法的優(yōu)越性越來越明顯。

表3 中等規(guī)模算例的計算結(jié)果分析

4.3 靈敏度分析

對于給定的待揀選訂單，一些參數(shù)的變化會對訂單分批揀選結(jié)果產(chǎn)生直接的影響。揀選臺容量決定了一個批次中可以同時揀選的訂單數(shù)量，貨箱緩存區(qū)容量決定了批次之間共用貨箱中不需要回庫的貨箱最大數(shù)量，本節(jié)分別對揀選臺容量和貨箱緩存區(qū)容量變化對貨箱出庫總次數(shù)的影響進行靈敏度分析。

(1)揀選臺容量C的變化分析

為了分析揀選臺容量C的變化對貨箱出庫總次數(shù)的影響，固定貨箱緩存區(qū)容量H=2，選取參數(shù)為T=30,M=30,N=100和T=50,M=50,N=50的兩個算例。對于每一個算例，讓揀選臺容量C依次取2～6之間的整數(shù)，分別計算不同揀選臺容量下的最優(yōu)分批揀選方案對應的貨箱出入庫總次數(shù),結(jié)果如圖4所示。

由圖4可以看出，隨著參數(shù)C的增大，貨箱出入庫次數(shù)逐漸減小。這是因為參數(shù)C越大，每個批次包含的訂單數(shù)量越多，一個貨箱出庫平均可滿足的訂單數(shù)量越多；另一方面，參數(shù)C越大，批次數(shù)越少，同一貨箱的平均出庫次數(shù)減少，因此貨箱的總出庫次數(shù)也會減少。

(2)貨箱緩存區(qū)容量H的變化分析

為了分析貨箱緩存區(qū)容量H對貨箱出庫次數(shù)的影響，仍然以T=30,M=30,N=100和T=50,M=50,N=50的例子進行計算，固定揀選臺容量C=3，讓貨箱緩存區(qū)的容量H從1變化到10，分別求解訂單分批揀選問題，記錄貨量出庫總次數(shù)，具體結(jié)果如圖5所示。由圖5可以看出，當H從1增大到4時，算例1的貨箱出庫次數(shù)減少得較明顯，當H>4時，出庫次數(shù)減少的幅度下降。這是由于算例1中不同批次共用的貨箱數(shù)較少，當H大于任意兩個批次之間共用的貨箱最大數(shù)量時，繼續(xù)增大貨箱緩存區(qū)容量已經(jīng)毫無意義。在算例2中，隨著H的增大，貨箱出庫總次數(shù)單調(diào)減少，且減少趨勢與算例1類似。當H≤5時，貨箱出庫次數(shù)下降較快，當H>5時，貨箱出庫次數(shù)下降緩慢。實際中，由于增大貨箱緩存區(qū)容量需要一定的空間與成本，當緩存區(qū)容量達到一定規(guī)模以后，必然出現(xiàn)效益遞減的情況，因此，不應該盲目增大緩存區(qū)容量。

4.4 與不設置貨箱緩存區(qū)的訂單分批模型對比分析

從靈敏度分析結(jié)果可以看出，隨著貨箱緩存區(qū)容量的增大，揀選所有訂單需要出庫貨箱的總次數(shù)單調(diào)遞減。當貨箱緩存區(qū)容量等于0時，設置貨箱緩存區(qū)的訂單分批揀選問題轉(zhuǎn)化為不設置貨箱緩存區(qū)的訂單分批揀選問題。本節(jié)將對比分析兩情況下的求解結(jié)果。

對于不設置貨箱緩存區(qū)的訂單分批揀選問題，揀選任意一個批次k需要使用的貨箱與需要出庫貨箱完全相同，因此不設置貨箱緩存區(qū)的訂單分批揀選問題的優(yōu)化目標等于揀選每個批次需要使用的貨箱數(shù)量之和。為方便對比分析，仍然使用2.2節(jié)中定義的符號和變量，不設置貨箱緩存區(qū)的訂單分批揀選問題可以表示為如下混合整數(shù)規(guī)劃模型(模型二)：

(16)

s.t.

(17)

(18)

(19)

(20)

(21)

xik,ymk∈{0,1},?i,m,k;

(22)

smkt∈Z+,?m,k,t;

(23)

2.2節(jié)中的模型(模型一)與本節(jié)不設置貨箱緩存區(qū)的訂單分批模型(模型二)的目標函數(shù)均為最小化貨箱出庫總次數(shù)，但由于模型二中不設置貨箱緩存區(qū)，揀選每個批次需要使用的貨箱即為要出庫的貨箱。模型一的約束(2)～約束(5)、約束(7)與模型二的約束(17)～約束(21)含義相同。但兩個模型存在以下區(qū)別：首先，模型二不需要考慮批次順序，符號k在模型二中既可以理解為批次索引，也可以理解為批次順序索引，在模型一中則表示批次順序索引；模型一要考慮揀選每個批次時，需要出庫的貨箱、和需要放入緩存區(qū)的貨箱，因此模型一引入了兩個決策變量umk與rmk，其中umk表示揀選第k個批次時是否讓貨箱m出庫，rmk表示揀選完第k個批次后是否把貨箱m放入貨箱緩存區(qū)，通過約束條件(8)～約束(12)，表示能夠存入貨箱緩存區(qū)的貨箱需要滿足的約束以及揀選批次訂單需要使用的貨箱與緩存區(qū)內(nèi)貨箱之間的關(guān)系，而模型二中不需要考慮這5個約束及相關(guān)的變量；同時，模型一為了有效利用緩存區(qū)的容量，避免不需要的貨箱提前出庫占用緩存區(qū)，引入了約束條件(6)限制揀選批次k時需要出庫的貨箱必須是批次k中需要使用的貨箱。通過以上分析可以看出，設置貨箱緩存區(qū)的訂單分批模型中決策變量和需要考慮的約束條件更多，不設置貨箱緩存區(qū)的訂單分批模型可以看成設置貨箱緩存區(qū)的訂單分批模型的特殊情況(即H=0的情況)。下面通過一個具體例子，分析兩種模型的求解結(jié)果。

例2已知商品存儲信息、每個訂單中訂購的商品信息和揀選臺容量等與2.2節(jié)示例相同，假設系統(tǒng)不設置貨箱緩存區(qū)。利用GUROBI求解混合整數(shù)規(guī)劃模型(模型二)，得到如下分批結(jié)果：第一批包含訂單O1,O2,O8，第二批包含訂單O4,O7,O12，第三批包含訂單O6,O9,O11，第四批包含訂單O3,O5,O10。 與2.2節(jié)例1中設置貨箱緩存區(qū)的訂單分批模型求解結(jié)果相比，訂單分批結(jié)果與貨箱出庫情況均發(fā)生了變化(其中2.2節(jié)例1有多個最優(yōu)解，本節(jié)只對比其中一個最優(yōu)解)。不設置貨箱緩存區(qū)的訂單分批揀選方案與設置貨箱緩存區(qū)的訂單分批揀選方案如表4所示。由表4可以看出，不設置貨箱緩存區(qū)時一共需要出庫貨箱7次，設置貨箱緩存區(qū)時只需要出庫貨箱5次。

表4 兩種模型求解結(jié)果對比

分析表4的結(jié)果可知，在不設置貨箱緩存區(qū)的中，每個批次之間無共用的貨箱，且每個批次需要使用的貨箱與出庫貨箱相同，揀選4個批次需要使用的貨箱總數(shù)為7個。相比之下，設置貨箱緩存區(qū)的系統(tǒng)中，揀選每個批次需要使用的貨箱數(shù)明顯增多，揀選所有批次需要使用的貨箱總數(shù)為10個，但揀選相鄰批次可以共用的貨箱數(shù)量較多，通過將相鄰批次共用的貨箱存入緩存區(qū)，可以有效減少實際出庫的貨箱數(shù)量，本例中實際出庫貨箱數(shù)量為5，比不設置貨箱緩存區(qū)的情況減少了28.6%。以上研究結(jié)果表明，對于給定的待揀選訂單集合，與不設置貨箱緩存區(qū)的系統(tǒng)相比來說，設置貨箱緩存區(qū)的揀選系統(tǒng)可以使貨箱的總出庫次數(shù)明顯較少，從而達到降低貨箱出庫成本、縮短揀選作業(yè)時間的效果。

考慮到設置貨箱緩存區(qū)需要支付一定的固定成本，結(jié)合對貨箱緩存區(qū)容量的靈敏度分析，可以進一步確定最優(yōu)緩存區(qū)容量，使整個系統(tǒng)的總運行成本達到最小。

5 結(jié)束語

本文針對設置貨箱緩存區(qū)的AVS/RS系統(tǒng)中的訂單分批揀選問題，考慮訂單中商品訂購數(shù)量與貨箱中商品存儲數(shù)量，選取貨箱出入庫次數(shù)作為刻畫系統(tǒng)揀選效率的主要指標，以出庫貨箱總次數(shù)最小化為目標建立了訂單分批揀選聯(lián)合優(yōu)化問題的整數(shù)規(guī)劃模型，并設計了求解模型的三階段啟發(fā)式算法。通過設計不同規(guī)模的算例，驗證了本文模型與算法的正確性與有效性。進一步分析了揀選臺容量與貨箱緩存區(qū)容量變化對貨箱出庫次數(shù)的影響。

通過對比分析設置貨箱緩存區(qū)與不設置貨箱緩存區(qū)的訂單分批揀選問題數(shù)學模型結(jié)構(gòu)，證明了設置貨箱緩存區(qū)的問題是不設置貨箱緩存區(qū)情況的一般化推廣。通過具體實例分析，證明了設置貨箱緩存區(qū)的系統(tǒng)可以減少貨箱出庫總次數(shù)，提高訂單揀選效率。

本文研究設置貨箱緩存區(qū)的AVS/RS訂單分批問題時，只考慮了單揀選臺的情況，實際中可能存在多個揀選臺。當多個揀選臺之間的距離較遠時，貨箱緩存區(qū)不能共用，此時的問題可以分解為多個單揀選臺的子問題。當多揀選臺之間距離較近，且相鄰的揀選臺可以共用貨箱緩存區(qū)中存放的貨箱時，問題將變得更加復雜，此時需要綜合考慮訂單分批問題、多個揀選臺之間的任務分配問題、各個揀選臺的任務排序問題等，并協(xié)調(diào)多個揀選臺的出庫貨箱與緩存區(qū)內(nèi)貨箱的存取及調(diào)度等問題，未來可以結(jié)合這些場景，對問題進行深入探究，建立更加符合實際的模型。下一步，可以針對本文建立的訂單分批揀選模型結(jié)構(gòu)特征，設計求解模型的精確算法并進行理論分析，為設計更多的快速有效近似算法提供理論基礎(chǔ)。