徐翔斌，馬中強

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

0 引言

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

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

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

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

1 問題描述及模型構建

1.1 問題描述

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

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

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

表1 基本參數(shù)

表2 決策變量

1.3 指派策略設計

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

1.4 模型構建

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

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

(9)

(10)

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

2 算法設計

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

2.1 解的編碼

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

2.2 初始解生成

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

為使DPLR初始解滿足式(8)描述的倉庫布局的連續(xù)變化關系，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，否則結束。

2.3 鄰域搜索

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

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

SA-STE算法領域搜索及不合理解修復步驟如下：

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

3 數(shù)值實驗

倉庫布局及實驗參數(shù)參考文獻[1]和文獻[14]設定如下：①平均訂單規(guī)模為10，揀貨總周期為8小時；②貨架總數(shù)為倉庫儲位總數(shù)的80%，即L=I×80%，并且SKU總數(shù)等于L；③需求關系服從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)，運行環(huán)境Win10、64bit操作系統(tǒng)、8 GB內(nèi)存。

表3 算法參數(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問題進行求解，結果如表4所示。

表4 SA-STE算法收斂過程

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

3.2 算法性能分析

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

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

續(xù)表5

如圖7所示為SA-STE算法的性能分析結果，分別從收益和計算時間兩個方面與CPLEX進行比較。由圖7a可知，在任意倉庫規(guī)模下，訂單量越大，SA-STE的求解結果越接近CPLEX最優(yōu)解；并且在訂單量相同的情況下，隨著倉庫規(guī)模增大，SA-STE的求解結果相比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)化效果分析

隨機指派(Random Storage, RS)和固定位置指派(Dedicated Storage，DS)策略被廣泛用于貨位指派優(yōu)化，在WS為(600,480)的情況下，分別對DPLR與RS、DS的貨位指派效果進行對比，結果如表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%左右的貨架搬運距離，能有效地提高RMFS的揀選效率；在倉庫規(guī)模一定的情況下，訂單量越大，DPLR的優(yōu)化效果越顯著，即存儲暢銷SKU的貨架被更大概率的指派到靠近揀貨站臺的區(qū)域(即圖9中右側(cè)紅色區(qū)域)存儲，這說明了本文提出的模型和算法可以實現(xiàn)倉庫存儲結構與SKU需求模式相匹配的優(yōu)化效果，適合訂單量和需求波動性巨大的電商、超市以及工廠等企業(yè)的RMFS動態(tài)貨架儲位再指派優(yōu)化。

4 結束語

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

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