徐翔斌，馬中強(qiáng)

(華東交通大學(xué) 交通運(yùn)輸與物流學(xué)院，江西 南昌 330013)

0 引言

基于移動機(jī)器人的揀貨系統(tǒng)(Robotic Mobile Fulfillment System, RMFS)是一種全新的貨到人訂單揀選系統(tǒng)，相比于人工和AS/RS(automated storage and retrieval system)揀貨系統(tǒng)(統(tǒng)稱傳統(tǒng)揀貨系統(tǒng))，在揀貨效率和準(zhǔn)確性以及倉庫空間利用率等方面存在諸多優(yōu)勢，特別適合需求波動性大、時效性強(qiáng)的電商、超市以及工廠等企業(yè)的訂單揀選，已在亞馬遜、京東以及菜鳥等公司得到成功應(yīng)用[1]。

貨位指派作為RMFS的一個重要優(yōu)化方向，指的是將庫存存貨單元(Stock Keeping Unit, SKU)或貨架分配到倉庫中的合適貨位/儲位，使訂單揀選的時間/距離最短，科學(xué)的貨位指派方法可縮短行走距離、降低搜尋時間以提高倉庫揀貨效率[2]。Hausman等[3]最早對傳統(tǒng)揀貨系統(tǒng)的貨位指派策略進(jìn)行研究，隨后的文獻(xiàn)分別從需求相關(guān)性[4-5]、出貨量[6]、存儲空間指數(shù)(Cube-per-Order Index, COI)[7]、周轉(zhuǎn)率[8]以及需求和結(jié)構(gòu)相關(guān)性[9]等方面進(jìn)行了更加深入的研究。

與傳統(tǒng)揀貨系統(tǒng)不同，RMFS的貨位指派問題可分為貨架儲位指派(貨架儲位的一次性指派和再指派問題)和SKU上架指派(考慮SKU關(guān)聯(lián)性的上架指派問題)兩種。Xiang等[10]對RMFS的SKU上架指派和訂單分批問題進(jìn)行了協(xié)同優(yōu)化，在考慮SKU關(guān)聯(lián)性的前提下以貨架每層只存儲一種SKU的方式進(jìn)行上架指派;Yuan等[11]分別考慮了隨機(jī)、基于類和基于周轉(zhuǎn)率的指派策略，進(jìn)一步對貨架儲位指派進(jìn)行了研究，研究表明基于類的指派策略效果更好，并且發(fā)現(xiàn)將SKU分為3類時的優(yōu)化效果最為顯著;隨后Roy等[12]和Weidinger等[13]分別從隨機(jī)指派和分散指派兩方面對RMFS的貨架儲位指派和SKU上架指派進(jìn)行了研究;在此基礎(chǔ)上，Weidinger等[14]進(jìn)一步將貨架儲位再指派(Pod Location Reassignment， PLR)問題看作特殊區(qū)間調(diào)度問題進(jìn)行研究，設(shè)計了自適應(yīng)算法，結(jié)果表明其提出的PLR適應(yīng)性指派規(guī)則比傳統(tǒng)的指派策略要好，但未考慮動態(tài)情況下的貨位再指派問題。在實際情況中，客戶對訂單的配送時限和成本要求越來越高，由于受促銷、季節(jié)以及產(chǎn)品周轉(zhuǎn)率和生命周期等因素的影響，需要對RMFS的倉庫布局不斷優(yōu)化調(diào)整來適應(yīng)這種變化，從而達(dá)到滿足客戶需求的目的。因此，在RMFS中，考慮動態(tài)情況的PLR問題要比傳統(tǒng)的一次性貨位指派更具現(xiàn)實意義[15]。

鑒于此，本文以具有較大需求波動性和較強(qiáng)需求時效性的電商、超市和工廠的RMFS倉庫為研究背景，對動態(tài)貨架儲位再指派(Dynamic Pod Location Reassignment, DPLR)問題進(jìn)行研究，將其看作多階段的動態(tài)決策問題，考慮倉庫布局的動態(tài)連續(xù)變化關(guān)系。首先，構(gòu)建了反映倉庫布局實時變化的混合整數(shù)規(guī)劃模型；然后，設(shè)計了考慮動態(tài)關(guān)系的啟發(fā)式算法用于求解大規(guī)模的DPLR問題；最后，通過數(shù)值分析驗證了模型和算法的有效性，并通過與傳統(tǒng)指派策略對比說明了本文提出的模型和算法可以實現(xiàn)倉庫布局的最佳優(yōu)化。

1 問題描述及模型構(gòu)建

1.1 問題描述

DPLR是指移動貨架在工作站臺完成揀貨任務(wù)后，在被機(jī)器人重新送回存儲區(qū)時，為其重新指派合適儲位的過程。DPLR本質(zhì)上是為貨架重新指派合適的儲位，使其在倉庫內(nèi)的存儲位置與SKU的需求模式相匹配，即暢銷SKU所在的貨架存儲在靠近揀貨站臺的區(qū)域(如圖1A區(qū))，滯銷SKU所在的貨架存儲在遠(yuǎn)離揀貨站臺的區(qū)域(如圖1C區(qū))。本文考慮基于開放儲位倉庫布局的DPLR問題，開放儲位是指倉庫儲位除存儲移動式貨架外，還預(yù)留小部分空閑儲位的情況，適當(dāng)?shù)拈_放儲位有助于倉庫布局的調(diào)整，可縮短揀貨的時間/距離[1]。DPLR的具體過程如圖1所示，首先將倉庫存儲區(qū)域按距揀貨站臺的距離分為A、B、C三個區(qū)域，分別用于存儲暢銷、一般和滯銷SKU。圖1中的暢銷SKU所在貨架l(黑底網(wǎng)格線標(biāo)識)當(dāng)前位于滯銷SKU存儲區(qū)C，在揀貨周期t，貨架l被機(jī)器人搬出至揀貨站臺，揀貨人員完成SKU揀取后，再由機(jī)器人送回存儲區(qū)存儲。由于該貨架中SKU的需求模式與其存儲區(qū)域不匹配，DPLR需對該貨架進(jìn)行重新指派，因此該貨架在被送回存儲區(qū)域時，將被指派到黃金儲位區(qū)A的開放儲位1中；同樣，滯銷SKU所在貨架l′也將被重新指派到存儲區(qū)C的開放儲位2中。上述過程隨著揀貨過程實時動態(tài)進(jìn)行，最終使得整個倉庫的存儲結(jié)構(gòu)與SKU的需求模式相匹配。

1.2 參數(shù)及變量定義

DPLR模型參數(shù)及變量分別定義如表1和表2所示。

表1 基本參數(shù)

表2 決策變量

1.3 指派策略設(shè)計

DPLR的目的是使貨架在倉庫中的存儲位置與其需求模式(存儲的SKU)動態(tài)匹配，貨架的需求模式可用貨架周轉(zhuǎn)率fl描述，貨架周轉(zhuǎn)率計算存在兩種情況：當(dāng)貨架只存儲一種SKU時，fl為該SKU的需求頻率；當(dāng)貨架存儲多種SKU時，fl為其存儲所有SKU需求頻率的均值；貨架的存儲位置可用其所在儲位i距揀貨站臺的距離di來衡量。在此基礎(chǔ)上，本文提出基于貨架與儲位匹配度的動態(tài)儲位指派策略，設(shè)計貨架需求頻率與儲位距離關(guān)聯(lián)性指標(biāo)Cli來指導(dǎo)DPLR進(jìn)行動態(tài)儲位優(yōu)化，Cli為貨架周轉(zhuǎn)率與儲位至揀貨站臺距離之比，Cli=fl/di。Cli是將需求頻率高/低的貨架分別指派到距揀貨站臺較近/遠(yuǎn)的儲位，從而實現(xiàn)SKU的存儲位置與需求模式匹配。

1.4 模型構(gòu)建

模型假設(shè)：①每個貨架存儲一種SKU，并且每種SKU只存儲于一個貨架；②不考慮缺貨和補(bǔ)貨情況；③訂單信息已知；④不考慮機(jī)器人充電、道路擁堵等情況。在此基礎(chǔ)上，構(gòu)建DPLR的混合整數(shù)規(guī)劃模型如下:

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

?i∈I′,l∈L′,t∈T′;

(8)

(9)

(10)

目標(biāo)函數(shù)(1)表示貨架與儲位匹配程度最大。式(2)～式(10)為約束條件，其中：式(2)表示任意貨架在任意時刻必須存儲到一個儲位；式(3)表示任意儲位在任意時刻有貨架存儲或為開放儲位；式(4)表示在任意時刻被搬運(yùn)的貨架必須被指派，且只能指派到一個儲位；式(5)表示在任意時刻開放儲位i是否被指派貨架；式(6)表示t時刻待搬運(yùn)的貨架必須從t-1時刻的存儲位置搬出；式(7)為被搬運(yùn)貨架與指派儲位貨架關(guān)系約束，表示任意時刻被指派的貨架總數(shù)等于被搬運(yùn)的貨架總數(shù)；式(8)～式(9)表示倉庫布局動態(tài)連續(xù)變化關(guān)系，t時刻儲位i的狀態(tài)等于t-1時刻儲位i的狀態(tài)減去t時刻該儲位被搬出貨架的情況，并加上t時刻該儲位被搬入貨架情況之和；式(10)為變量取值約束。

2 算法設(shè)計

DPLR是典型的NP-hard問題，對于大規(guī)模DPLR問題，精確方法難以求解，需設(shè)計啟發(fā)式算法。模擬退火(Simulated Annealing, SA)算法因其具有受初始解影響小、全局尋優(yōu)能力強(qiáng)等特點，被廣泛用于求解組合優(yōu)化問題[16-18]。本文將設(shè)計反映倉庫動態(tài)變化關(guān)系的SA-STE(simulated annealing single-t exchange)算法來求解DPLR問題，算法流程如圖2所示。

2.1 解的編碼

解的編碼方式如圖3所示，橫坐標(biāo)表示整個揀貨周期，縱坐標(biāo)表示倉庫儲位，倉庫中的儲位狀態(tài)用0或正整數(shù)表示，0表示儲位為開放儲位，正整數(shù)為存儲在該儲位的貨架編號。揀貨周期t的倉庫布局通過該時刻末的倉庫布局狀態(tài)表示，例如在揀貨周期t=1，儲位1存儲2號貨架，儲位2為開放儲位，最后一個儲位I存儲17號貨架。當(dāng)揀貨總周期為T，倉庫總儲位為I時，解為一個T×I的二維數(shù)組，反映了整個揀貨周期內(nèi)倉庫布局狀態(tài)的連續(xù)變化關(guān)系。

2.2 初始解生成

由式(8)可知，周期t時刻的倉庫布局與t-1時刻的倉庫布局存在關(guān)聯(lián)性(如圖4)，當(dāng)揀貨周期t=5，9和17號貨架若在該時刻未被搬運(yùn)，其所在的儲位狀態(tài)應(yīng)與t=4時刻末的儲位狀態(tài)相同，其儲位仍為3和I；同樣，t=6時，若貨架1、9、56和7未被搬運(yùn)，則其所在儲位1、3、I-2和I-1的狀態(tài)與t=5時刻末的儲位狀態(tài)一致，其他時刻的倉庫布局關(guān)聯(lián)關(guān)系以此類推。

為使DPLR初始解滿足式(8)描述的倉庫布局的連續(xù)變化關(guān)系，SA-STE算法初始解生成步驟如下：

步驟2生成一個在[1,L]區(qū)間內(nèi)的1×I的數(shù)組，并使其滿足約束(2)～約束(5)。

步驟4l=l+1，若l?Ωt且l≤L，則轉(zhuǎn)步驟3;若l∈Ωt，則重新執(zhí)行步驟4,若l>L,則轉(zhuǎn)步驟5。

步驟5令l=1，t=t+1，若t≤T，則轉(zhuǎn)步驟 2，否則結(jié)束。

2.3 鄰域搜索

本文提出單時刻交換(Single-t Exchange, STE)規(guī)則用于候選解的生成，STE規(guī)則生成新的候選解分為以下3步：①在揀貨周期[1,T]內(nèi)隨機(jī)產(chǎn)生一個揀貨時刻t；②在該時刻隨機(jī)選擇兩個儲位；③交換這兩個儲位中的存儲內(nèi)容(貨架)。根據(jù)儲位中存儲內(nèi)容的不同，存在貨架—貨架、貨架—空位以及空位—空位3種類型的交換方式，如圖4所示，根據(jù)STE規(guī)則先隨機(jī)產(chǎn)生一個揀貨時刻t=3，并在該時刻隨機(jī)選擇兩個交換儲位，若為(10,14)，則是貨架—貨架的交換方式；若為(15,18)，則是貨架—空位的交換方式；若為(19,25)，則為空位—空位的交換方式。

由于倉庫布局存在時序關(guān)聯(lián)性，交換產(chǎn)生的新解可能會打破這一關(guān)系，產(chǎn)生不合理的解。為此需要進(jìn)行解的修復(fù)，具體可分為向前修復(fù)(Forward Repair, FR)和向后修復(fù)(Backward Repair, BR)，其中FR為向時間遞減方向修復(fù)，BR為向時間遞增方向修復(fù)。不合理解的修復(fù)過程如圖5所示，當(dāng)揀貨周期t=5，隨機(jī)產(chǎn)生兩個交換儲位14和20，對其中存儲的1號貨架和21號貨架進(jìn)行儲位交換，若1號或21號貨架在該時刻或下一時刻都未被搬運(yùn)，則在t=4(FR)或t=6(BR)時刻，14和20號這兩個儲位也應(yīng)交換存儲內(nèi)容(雙箭頭弧形曲線所示)，直至交換儲位的所有貨架與其上一時刻/下一時刻不存在位置繼承(被搬運(yùn))或t=0/t=T為止。

SA-STE算法領(lǐng)域搜索及不合理解修復(fù)步驟如下：

步驟3若在a時刻存在貨架—貨架或貨架—空位的交換，并且存在交換貨架不屬于Ωa，則令m=a-1，轉(zhuǎn)步驟4；若在a時刻存在貨架—貨架或貨架—空位的交換，并且存在交換貨架不屬于Ωa+1，則令n=a+1則轉(zhuǎn)步驟5。

3 數(shù)值實驗

倉庫布局及實驗參數(shù)參考文獻(xiàn)[1]和文獻(xiàn)[14]設(shè)定如下：①平均訂單規(guī)模為10，揀貨總周期為8小時；②貨架總數(shù)為倉庫儲位總數(shù)的80%，即L=I×80%，并且SKU總數(shù)等于L；③需求關(guān)系服從20/80規(guī)則，即20%的SKU產(chǎn)生80%的訂單銷量；④倉庫儲位總數(shù)I分別取60,600,800,1 000,1 200；⑤總訂單量(Order Quantity, OQ)分別取60,300,600,1 200,2 400,3 600。算法參數(shù)如表3所示，利用MATLAB R2014a編程實現(xiàn)，運(yùn)行環(huán)境Win10、64bit操作系統(tǒng)、8 GB內(nèi)存。

表3 算法參數(shù)設(shè)定

DPLR問題的求解規(guī)模取決于倉庫規(guī)模(Warehouse Size，WS)和總訂單量OQ，其中倉庫規(guī)模WS又由儲位規(guī)模(I)和貨架規(guī)模(L)決定，因此，DPLR的問題規(guī)?？杀硎緸?I,L,OQ)。

3.1 算法收斂性驗證

在初始倉庫布局、SKU需求頻率以及客戶訂單數(shù)據(jù)相同的情況下，分別利用CPLEX和SA-STE對規(guī)模為(60,48,1200)和(600,480,1200)的DPLR問題進(jìn)行求解，結(jié)果如表4所示。

表4 SA-STE算法收斂過程

由表4可知，當(dāng)問題規(guī)模為(60,48,1 200)時，SA-STE和CPLEX分別耗時267.83 s和254.32 s,貨架與儲位匹配度值(簡稱“匹配度”)分別為129.59和138.18；當(dāng)問題規(guī)模為(600,480,1 200)時，SA-STE和CPLEX分別耗時1 671.32 s和1 983.41 s，貨架與儲位匹配度值分別為201.33和211.36。SA-STE算法求解兩種問題規(guī)模的收斂過程和CPLEX的求解結(jié)果對比如圖6所示，這表明不同規(guī)模的DPLR問題，SA-STE都能在較短時間內(nèi)實現(xiàn)平穩(wěn)收斂，并能找到與CPLEX求解結(jié)果相近的解，從而表明SA-STE算法在求解質(zhì)量和計算時間方面都能滿足實際要求。

3.2 算法性能分析

分別對4種倉庫規(guī)模WS和6種訂單量OQ進(jìn)行組合實驗，總共24(4×6)種場景?？紤]到隨機(jī)因素，對每種實驗場景運(yùn)行10次取平均，結(jié)果如表5所示，其中求解差距為SA-STE的解與CPLEX最優(yōu)解的比值。

表5 不同問題規(guī)模下的實驗結(jié)果

續(xù)表5

如圖7所示為SA-STE算法的性能分析結(jié)果，分別從收益和計算時間兩個方面與CPLEX進(jìn)行比較。由圖7a可知，在任意倉庫規(guī)模下，訂單量越大，SA-STE的求解結(jié)果越接近CPLEX最優(yōu)解；并且在訂單量相同的情況下，隨著倉庫規(guī)模增大，SA-STE的求解結(jié)果相比CPLEX最優(yōu)解差距均未超過10%(以訂單量2 400和 3600為例)，這說明針對大規(guī)模的DPLR問題，SA-STE的求解質(zhì)量可靠。

由圖7b可知，在訂單量較大(2 400和3 600)的情況下，隨著倉庫規(guī)模的增大，CPLEX的計算時間出現(xiàn)了指數(shù)爆炸增長，在倉庫規(guī)模為(1 200,960)的情況下，CPLEX無法在可以接受的時間內(nèi)求得最優(yōu)解；但SA-STE的求解時間隨著倉庫規(guī)模的增大變化不大，可以在合理的時間內(nèi)尋找到接近最優(yōu)解的可行方案。

由此可知，SA-STE能夠求解倉庫規(guī)模和訂單量都較大的DPLR問題，可以在保證解的質(zhì)量的同時大幅度縮短求解時間。

3.3 DPLR優(yōu)化效果分析

隨機(jī)指派(Random Storage, RS)和固定位置指派(Dedicated Storage，DS)策略被廣泛用于貨位指派優(yōu)化，在WS為(600,480)的情況下，分別對DPLR與RS、DS的貨位指派效果進(jìn)行對比，結(jié)果如表6所示。

表6 DPLR優(yōu)化效果

初始倉庫儲位狀態(tài)熱力圖如圖8所示，右邊的色度條表示貨架頻率，范圍為[0,1]，貨架頻率越接近1，表明存儲的SKU越暢銷。

在不同OQ下，經(jīng)DPLR優(yōu)化后的倉庫儲位狀態(tài)熱力圖如圖9所示。

由表6、圖8和圖9可知：相比RS和DS，DPLR可縮短30%左右的貨架搬運(yùn)距離，能有效地提高RMFS的揀選效率；在倉庫規(guī)模一定的情況下，訂單量越大，DPLR的優(yōu)化效果越顯著，即存儲暢銷SKU的貨架被更大概率的指派到靠近揀貨站臺的區(qū)域(即圖9中右側(cè)紅色區(qū)域)存儲，這說明了本文提出的模型和算法可以實現(xiàn)倉庫存儲結(jié)構(gòu)與SKU需求模式相匹配的優(yōu)化效果，適合訂單量和需求波動性巨大的電商、超市以及工廠等企業(yè)的RMFS動態(tài)貨架儲位再指派優(yōu)化。

4 結(jié)束語

本文研究了RMFS的DPLR問題，在考慮倉庫布局動態(tài)連續(xù)變化的情況下構(gòu)建了以貨架與儲位匹配度為優(yōu)化目標(biāo)的混合整數(shù)規(guī)劃模型，并設(shè)計了SA-STE算法對大規(guī)模DPLR問題進(jìn)行求解。結(jié)果表明，SA-STE算法能在較短時間內(nèi)求得接近CPLEX的解，通過與傳統(tǒng)指派策略比較發(fā)現(xiàn)，本文提出的模型和算法可以實現(xiàn)倉庫存儲結(jié)構(gòu)與SKU需求模式相匹配的優(yōu)化效果，有效地降低了機(jī)器人搬運(yùn)距離，提高了揀貨效率。

當(dāng)暢銷SKU貨架被指派到靠近揀貨站臺的區(qū)域存儲時，可能會出現(xiàn)搬運(yùn)機(jī)器人在該區(qū)域的交通擁堵。因此，考慮機(jī)器人行走路徑和擁堵情況的DPLR問題有待進(jìn)一步研究。