李珍萍,韓倩倩，儀明超

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 問(wèn)題描述與分析

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

為了簡(jiǎn)化問(wèn)題，本文作如下假設(shè)：

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

(2)系統(tǒng)使用標(biāo)準(zhǔn)化貨箱，貨箱的大小一樣。貨箱緩存區(qū)最多可以同時(shí)容納H個(gè)貨箱。

(3)假設(shè)倉(cāng)庫(kù)中每種商品的總庫(kù)存量可以滿足所有訂單對(duì)該商品的總訂購(gòu)量，不考慮缺貨的情況。

(4)每個(gè)貨箱每次出入庫(kù)時(shí)間相同，揀選員從貨箱中揀取每件商品的時(shí)間相同，揀選員從貨箱中揀取商品時(shí)的移動(dòng)距離(時(shí)間)忽略不計(jì)。

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

2.2 模型建立

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

i為訂單序號(hào),i=1,2,…,N；

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

m為貨箱序號(hào),m=1,2,…,M；

t為商品類別序號(hào),t=1,2,…,T；

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

Q為每個(gè)貨箱最大存儲(chǔ)量；

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

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

決策變量定義如下：

smkt為揀選批次k時(shí)需要從貨箱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)

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

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

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

假設(shè)某段時(shí)間內(nèi)收到12個(gè)訂單, 每個(gè)訂單中訂購(gòu)的各種商品及數(shù)量如下，其中括號(hào)中的數(shù)字表示商品的訂購(gòu)數(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)}。

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

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

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

3 啟發(fā)式算法

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

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

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

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

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

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

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

ami=

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

更新貨箱m*中剩余的商品存儲(chǔ)量和批次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 計(jì)算結(jié)束，輸出揀選每個(gè)批次需要使用的貨箱集合(對(duì)應(yīng)決策變量y0)，計(jì)算揀選所有批次需要使用的貨箱總數(shù)量z0。

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

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

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

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

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

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

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

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

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

若zrepair

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

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

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

算法具體步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟5若k+1

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

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

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

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

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

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

啟發(fā)式算法的參數(shù)設(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編程實(shí)現(xiàn)三階段算法，并在Inter Core i5-8 265U筆記本電腦運(yùn)行。

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

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

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

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

4.3 靈敏度分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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