可移動(dòng)貨架下的儲(chǔ)位選擇與揀貨路徑聯(lián)合優(yōu)化

賴品諺，張大力，趙思翔

(上海交通大學(xué) 1.深圳研究院，廣東 深圳 518057；2.中美物流研究院，上海 200030)

近年來，隨著B2C電商零售的快速發(fā)展以及網(wǎng)絡(luò)直播帶貨的流行，客戶在線訂單逐漸呈現(xiàn)小批量、多品種、異質(zhì)化的趨勢(shì)，這對(duì)倉庫內(nèi)作業(yè)的時(shí)效性提出了更高的要求，如何實(shí)現(xiàn)快速揀貨已成為現(xiàn)階段物流倉儲(chǔ)公司面臨的最重要挑戰(zhàn)之一。為了提高訂單分揀效率，文獻(xiàn)[1]中提出重要倉儲(chǔ)決策問題包括倉庫布局設(shè)計(jì)、存儲(chǔ)位置分配、訂單批處理以及揀選路線規(guī)劃，而更合理的存儲(chǔ)庫存單元(stock keeping unit,SKU) 是提高訂單揀選效率的有效方法[2]。傳統(tǒng)倉庫儲(chǔ)位采用SKU一對(duì)一存儲(chǔ)，而當(dāng)需要在短時(shí)間內(nèi)挑選大量不同種類的商品時(shí)，Weidinger[3]提出一種針對(duì)在線零售商需求的分散存儲(chǔ)策略，將同一種SKU分散存儲(chǔ)到倉庫各個(gè)位置的儲(chǔ)位中，增加揀選路徑柔性，能夠有效縮短到任意SKU的平均距離，這種策略帶來的問題是如何在多個(gè)儲(chǔ)位中選擇最優(yōu)的揀選儲(chǔ)位。在此基礎(chǔ)上，可移動(dòng)貨架倉儲(chǔ)系統(tǒng)的出現(xiàn)給揀貨效率的提高帶來新的希望[4]。王征等[5]闡述了可移動(dòng)倉儲(chǔ)系統(tǒng)的使用原理，其貨架體型較小可被移動(dòng)到倉庫任何位置。移動(dòng)式貨架的出現(xiàn)使得倉庫布局可以實(shí)時(shí)調(diào)整，增加了儲(chǔ)位管理的靈活性，同時(shí)也將儲(chǔ)位優(yōu)化問題提到了一個(gè)新的高度。如何對(duì)貨架進(jìn)行移動(dòng)且何時(shí)對(duì)貨架進(jìn)行移動(dòng)都是亟需研究的問題，每次的貨架移動(dòng)都會(huì)直接影響存放的SKU之間的距離，不僅需要考慮移動(dòng)后新的貨架布局給訂單揀貨帶來的移動(dòng)距離的減少，還需要考慮移動(dòng)貨架時(shí)產(chǎn)生的移動(dòng)成本。

針對(duì)分散存儲(chǔ)中儲(chǔ)位選擇與揀貨路徑的問題研究，Yang等[2]提出一個(gè)訂單批量優(yōu)化算法包，具體解決儲(chǔ)位選擇、路徑規(guī)劃和訂單分批3個(gè)問題，對(duì)于儲(chǔ)位選擇和訂單分批提出多種啟發(fā)式算法。此后Weidinger[3]研究矩形分散倉庫的揀貨路徑問題，提出聯(lián)合混合整數(shù)優(yōu)化模型，并證明了其NP-hard性質(zhì)，通過3個(gè)啟發(fā)式的優(yōu)先規(guī)則來完成對(duì)儲(chǔ)位的選擇問題。而基于一些儲(chǔ)位選擇的標(biāo)準(zhǔn)，Dmytrów[6]使用廣義距離度量創(chuàng)建一個(gè)混合變量，對(duì)所有儲(chǔ)位進(jìn)行排序，并對(duì)排名高的儲(chǔ)位進(jìn)行選擇。目前對(duì)于揀貨儲(chǔ)位的選擇多是基于規(guī)則的選擇方法，很少有將其與揀貨路徑聯(lián)合起來進(jìn)行建模求解。針對(duì)可移動(dòng)貨架的研究，王征[5]等基于顧客訂單建立了貨架熱度和關(guān)聯(lián)度生成模型，建立考慮機(jī)器人重載和空載行駛距離最小化的雙目標(biāo)整數(shù)規(guī)劃模型，并設(shè)計(jì)了禁忌搜索啟發(fā)式求解算法。Li等[7]解決了貨到人揀選模式的最佳移動(dòng)貨位選擇問題，目標(biāo)是最小化完成所有訂單中移動(dòng)貨架的總行程距離，建立整數(shù)規(guī)劃模型，提出一種具有多項(xiàng)式復(fù)雜度的三階段混合啟發(fā)式算法。Xiang等[8]研究可移動(dòng)系統(tǒng)中的儲(chǔ)位分配和訂單批處理問題，通過儲(chǔ)位分配以最大化同一貨架中產(chǎn)品的相似度，對(duì)于訂單批處理問題，提出一種啟發(fā)式方法來生成初始解決方案以及可變鄰域搜索啟發(fā)式方法對(duì)解進(jìn)行改進(jìn)，以最小化訪問貨架的次數(shù)。Valle等[9]研究同時(shí)將訂單和移動(dòng)存儲(chǔ)架分配給靜態(tài)揀貨員的問題，同時(shí)還考慮如何對(duì)貨架進(jìn)行排序，并提出兩種啟發(fā)式方法。目前的貨架移動(dòng)研究都基于“貨到人”模式下通過機(jī)器人對(duì)貨架進(jìn)行移動(dòng)，而“人到貨”模式下也存在通過移動(dòng)貨架來加快揀貨效率的需求，許多該模式倉庫的經(jīng)理擔(dān)心自動(dòng)揀貨系統(tǒng)的高投資成本[10]，所以這部分的問題研究仍有所空缺。

因此，本文針對(duì)“人到貨”揀貨模式和分散存儲(chǔ)策略，研究可移動(dòng)倉儲(chǔ)系統(tǒng)中的訂單揀貨路徑優(yōu)化問題，提出一個(gè)包含儲(chǔ)位選擇聯(lián)合路徑規(guī)劃優(yōu)化模型和貨架移動(dòng)優(yōu)化模型的雙層優(yōu)化模型，并設(shè)計(jì)相應(yīng)的啟發(fā)式算法對(duì)其進(jìn)行求解，最后進(jìn)行數(shù)值實(shí)驗(yàn)對(duì)算法的有效性進(jìn)行驗(yàn)證，實(shí)現(xiàn)了單日訂單揀貨量和揀貨效率的提高，以及整體倉儲(chǔ)和揀貨成本的降低。

1 模型構(gòu)建

考慮某倉庫的存儲(chǔ)策略為分散存儲(chǔ)，一種SKU可存放在倉庫多個(gè)儲(chǔ)位中，但一個(gè)儲(chǔ)位只能存放一種SKU，在對(duì)揀貨路徑進(jìn)行優(yōu)化的同時(shí)需要對(duì)儲(chǔ)位選擇進(jìn)行優(yōu)化，其中存儲(chǔ)單位為儲(chǔ)位和貨架，儲(chǔ)位是最小的存儲(chǔ)單元?？紤]可移動(dòng)式貨架，其中貨架是多個(gè)儲(chǔ)位的集合且有著不同的長度，貨架的長度等于包含的儲(chǔ)位數(shù)量，一個(gè)貨架只能存放一種SKU。貨架具有可移動(dòng)的屬性，但貨架中的儲(chǔ)位不可拆分，移送時(shí)需對(duì)貨架整體進(jìn)行移動(dòng)，而貨架的可移動(dòng)性也會(huì)導(dǎo)致倉庫從傳統(tǒng)的固定式布局轉(zhuǎn)變?yōu)榭勺兪?。揀貨通道可以是傳統(tǒng)平行通道，也可以是交錯(cuò)間隔的通道。一些流行的路由啟發(fā)式算法只能應(yīng)用于單塊和多塊傳統(tǒng)矩形倉庫，對(duì)于3塊或更多塊的非傳統(tǒng)矩形倉庫并沒有最優(yōu)算法[11]。貨架與儲(chǔ)位的關(guān)系如圖1所示 (數(shù)字代表SKU的編號(hào))。本文考慮使用儲(chǔ)位間的距離矩陣來表示倉庫的貨架布局，同時(shí)使用儲(chǔ)位間的距離來表示揀貨時(shí)的移動(dòng)時(shí)間成本。而需要解決的問題是，針對(duì)一批待揀訂單，如何移動(dòng)貨架更改SKU的存儲(chǔ)布局，使得揀貨路徑總和最短。

圖1 倉庫中的布局與貨架Figure 1 Layout and shelves in a warehouse

本文針對(duì)性地構(gòu)建一類雙層優(yōu)化模型，雙層規(guī)劃就是對(duì)兩個(gè)決策模型之間的決策層次和交互進(jìn)行分層，上層通過考慮下層的最優(yōu)解來優(yōu)化受約束的上層目標(biāo)函數(shù)[12]。在上層貨架移動(dòng)模型中優(yōu)化SKU存放的儲(chǔ)位集合，獲得未來揀選時(shí)的倉庫布局，而下層揀貨路徑模型旨在優(yōu)化此布局下的訂單揀選路徑長度總和。不難看出，上層的求解結(jié)果將會(huì)影響下層模型的距離矩陣，影響各SKU之間的揀選距離，從而影響下層模型的目標(biāo)函數(shù)；同時(shí)可以用下層優(yōu)化模型的最優(yōu)目標(biāo)值來衡量上層模型的優(yōu)化效果，以便上層模型迭代尋優(yōu)。上層優(yōu)化結(jié)果中設(shè)定移動(dòng)單元為貨架，而不同類型的貨架具有不同的長度，且一個(gè)貨架可存放多個(gè)相同SKU的儲(chǔ)位，例如圖1中SKU30存放在長度為3的貨架中，SKU35存放在長度為2的貨架中。模型中考慮長度相同的貨架可以進(jìn)行位置交換。下層優(yōu)化結(jié)果中設(shè)定揀貨單元為儲(chǔ)位，根據(jù)現(xiàn)有的訂單需求和當(dāng)前儲(chǔ)位布局，對(duì)SKU的揀貨順序和儲(chǔ)位選擇進(jìn)行決策，即對(duì)于任意一個(gè)存放在多個(gè)儲(chǔ)位上的SKU選擇一個(gè)最優(yōu)的揀選儲(chǔ)位，以完成訂單需求的揀貨任務(wù)。

1.1 上層優(yōu)化模型：貨架移動(dòng)模型

該模型對(duì)貨架進(jìn)行移動(dòng)或交換，進(jìn)而改變倉庫的SKU布局，使得揀選者能夠以更短的路徑完成訂單需求任務(wù)的揀選。對(duì)該問題作出如下假設(shè)：1) 只能夠交換長度相同的貨架；2) 貨架移動(dòng)后不能改變揀貨通道的位置；3) 貨架移動(dòng)過程的時(shí)間可忽略。本文模型中的符號(hào)定義如表1所示。

表1 模型符號(hào)定義Table 1 Symbol definitions in the model

其中，使用 θ 定義為 θms的簡寫來表示上層 模型輸出的移動(dòng)儲(chǔ)位后倉庫的SKU布局，D(θ)為該布局θ下的最短揀貨路徑，且由下層模型求解得出。上層模型如式(1)～ (7)所示。

目標(biāo)函數(shù) (1) 表示優(yōu)化問題的目標(biāo)為揀選此批訂單所需的揀選路徑長度和貨架移動(dòng)成本之和最??；約束 (2) 為交換平衡約束，即貨架m跟n交換等同于貨架n跟m交換；約束 (3) 為交換長度約束，保證交換的貨架長度相等；約束 (4) 為交換數(shù)量約束，對(duì)于任意一個(gè)貨架最多只能與其他貨架交換一次位置；約束 (5) 為交換布局約束，記錄移動(dòng)貨架后的SKU存儲(chǔ)布局。

1.2 下層優(yōu)化模型：揀貨路徑模型

該模型對(duì)需求SKU的存儲(chǔ)儲(chǔ)位進(jìn)行選擇并規(guī)劃揀貨順序，使得總揀選路程距離最短。此處作出如下假設(shè)：1) 不考慮補(bǔ)貨策略，假設(shè)在揀選過程中庫存充足；2) 不考慮揀貨容器的容量限制，因此只需考慮SKU需求的種類，不考慮需求的數(shù)量；3) 分配的訂單中所有SKU需要在一次揀貨作業(yè)中完成揀選。下層模型如式(8)～ (15)所示，模型中的符號(hào)定義見表1。

其中，目標(biāo)函數(shù) (8) 為最小化揀貨路徑總長度；約束 (9) 和 (10) 為出入口約束，揀貨員從倉庫出入口出發(fā)最后回到出入口；約束 (11) 為平衡流約束，保證對(duì)于任意儲(chǔ)位進(jìn)出相同；約束 (12) 為需求約束，滿足需求SKU的揀貨任務(wù)；約束 (13) 為消除子回路約束。

2 算法設(shè)計(jì)

針對(duì)雙層優(yōu)化模型本文提出一種雙層的元啟發(fā)式算法框架，將自適應(yīng)大鄰域搜索算法 (adaptive large neighborhood search,ALNS) 和遺傳算法 (genetic algorithm,GA) 相結(jié)合進(jìn)行求解。

2.1 算法框架

下層的揀貨路徑優(yōu)化模型中采用遺傳算法對(duì)儲(chǔ)位的選擇以及揀貨的順序進(jìn)行求解，其求解結(jié)果為某一倉庫布局下的訂單需求的最優(yōu)揀貨路徑；上層模型中采用搜索能力較強(qiáng)的自適應(yīng)大鄰域搜索算法求解。此外本算法使用Apriori關(guān)聯(lián)算法作為ALNS的初始解加快算法收斂，雙層元啟發(fā)式算法框架如圖2所示，上層ALNS算法每求解出一個(gè)儲(chǔ)位布局的鄰域結(jié)果便傳遞到下層GA算法中，下層GA算法計(jì)算該鄰域結(jié)果上的所有訂單需求的最優(yōu)揀貨路徑距離和，上層ALNS算法通過下層GA算法的返回值在不同的鄰域中進(jìn)行搜索對(duì)比，通過若干次迭代，最終選出最優(yōu)的鄰域結(jié)果作為貨架移動(dòng)后的倉庫儲(chǔ)位布局。雙層元啟發(fā)式算法框架具體包括3個(gè)算法模塊，分別為Apriori、GA和ALNS，具體算法框架的流程圖如圖3所示。

圖2 雙層元啟發(fā)式算法框架Figure 2 Framework of the bi-level meta-heuristic algorithm

圖3 雙層元啟發(fā)式算法流程圖Figure 3 Flowchart of the bi-level meta-heuristic algorithm

2.2 算法描述

初始化環(huán)節(jié)，Apriori算法通過計(jì)算數(shù)據(jù)的支持度和置信度來度量數(shù)據(jù)間的關(guān)聯(lián)性，Agrawa等[13]首次提出Apriori算法并用于大型數(shù)據(jù)庫的商品關(guān)聯(lián)規(guī)則挖掘。Wu[14]基于Apriori算法研究智能電商物流中心訂單中不同商品之間的相關(guān)性，只有支持度與置信度同時(shí)達(dá)到了最小支持度與最小置信度，此關(guān)聯(lián)規(guī)則才會(huì)被稱為強(qiáng)關(guān)聯(lián)規(guī)則。Apriori算法把滿足最小支持度的集合定義為頻繁項(xiàng)集，通過逐層迭代的方法，先找出頻繁項(xiàng)集F1，再利用F1找出頻繁項(xiàng)集F2，直到找出所有的強(qiáng)關(guān)聯(lián)性集合?；趶?qiáng)關(guān)聯(lián)性結(jié)果，根據(jù)其關(guān)聯(lián)性強(qiáng)弱按順序可以對(duì)貨架進(jìn)行交換，使得具有強(qiáng)關(guān)聯(lián)性的SKU貨架盡可能接近，以減少揀貨路徑距離。本文將根據(jù)Apriori的關(guān)聯(lián)結(jié)果對(duì)貨架進(jìn)行移動(dòng)作為后續(xù)ALNS算法的初始解，移動(dòng)方法步驟如下。

1) 定義最小支持度和最小置信度并得到強(qiáng)關(guān)聯(lián)性SKU集合，將集合按照關(guān)聯(lián)強(qiáng)度排序。

2) 按順序選擇相應(yīng)的強(qiáng)關(guān)聯(lián)SKU并進(jìn)入步驟3)，如果已完成對(duì)所有強(qiáng)關(guān)聯(lián)組合的移動(dòng)則進(jìn)入步驟5)。

3) 找出該強(qiáng)關(guān)聯(lián)組合中k個(gè)SKU距離倉庫出入口最近的貨架M1,···,Mk，令固定貨架FM=min(,···,)，其中為貨架Mk距出入口0的距離，移動(dòng)貨架集合SM=MFM。

4) 令dFM為固定貨架到其他所有貨架的距離列表并按升序排序，依次選擇dFM作為被移動(dòng)貨架，若符合條件(1)～ (3)則將被移動(dòng)貨架與移動(dòng)貨架進(jìn)行交換。

(1) 被移動(dòng)貨架從未被交換過。

(2) 被移動(dòng)貨架和移動(dòng)貨架的長度相同。

(3) 被移動(dòng)貨架距離固定貨架的距離小于移動(dòng)貨架距離固定貨架的距離；直到所有移動(dòng)貨架完成交換返回步驟2)。

5) 所有貨架移動(dòng)后的結(jié)果作為ALNS算法的初始解。在得到ALNS算法的初始解后，通過GA算法計(jì)算該初始解在需求訂單下的揀貨路徑長度，并作為判斷SKU儲(chǔ)位布局好壞的標(biāo)準(zhǔn)，即揀貨路徑長度越短，表明在該布局下能夠更快地完成對(duì)訂單的揀貨工作。由于本文倉庫的存儲(chǔ)策略為分散存儲(chǔ)，即一種SKU可以存放在多個(gè)貨架中，因此在GA算法的染色體編碼設(shè)計(jì)中不僅需要考慮揀選SKU的順序，還同時(shí)需要考慮選擇SKU對(duì)應(yīng)哪一個(gè)貨架中的儲(chǔ)位。染色體編碼如圖4所示，每個(gè)SKU片段攜帶一個(gè)儲(chǔ)位片段構(gòu)成一次揀選片段。GA算法的流程包括二元錦標(biāo)賽選擇、交叉和變異操作。染色體交叉和變異過程如圖5所示，隨機(jī)對(duì)不同染色體的交叉使得產(chǎn)生不同順序以及不同選擇儲(chǔ)位的解，對(duì)染色體進(jìn)行變異則隨機(jī)交換兩個(gè)SKU并隨機(jī)更改其選擇的儲(chǔ)位。到達(dá)迭代上限后，GA算法輸出該儲(chǔ)位布局下的揀貨總距離。

圖4 GA算法染色體編碼Figure 4 Chromosome coding of GA

圖5 GA算法交叉和變異Figure 5 Cross and mutation of GA

ALNS算法采用內(nèi)層與外層的迭代方式對(duì)鄰域進(jìn)行搜索，內(nèi)層結(jié)合模擬退火的思想，通過降溫的方式進(jìn)行搜索，外層限定終止條件，即達(dá)到最大迭代次數(shù)，不滿足終止條件就進(jìn)入內(nèi)層繼續(xù)搜索。ALNS算法的核心思想是通過不斷地破壞和修復(fù)解從而完成對(duì)解空間鄰域的搜索，并自適應(yīng)地調(diào)整破壞算子和修復(fù)算子的權(quán)重，通過該權(quán)重控制每個(gè)修復(fù)算子和破壞算子在搜索期間使用的頻率，表現(xiàn)更好的算子將獲得更高的權(quán)重，從而提高算法的搜索尋優(yōu)能力。本文基于Apriori算法結(jié)果的基礎(chǔ)上，使用ALNS算法進(jìn)一步對(duì)貨架移動(dòng)問題進(jìn)行優(yōu)化。在算法中共定義了兩個(gè)破壞算子 (隨機(jī)破壞和貪婪破壞) 和兩個(gè)修復(fù)算子 (隨機(jī)修復(fù)和貪婪修復(fù))，隨機(jī)破壞指隨機(jī)選擇多個(gè)貨架并移除；隨機(jī)修復(fù)將移除的貨架隨機(jī)插入至空閑位置；貪婪破壞指通過輪盤賭的方法選擇多個(gè)需求SKU的貨架并移除，需求中出現(xiàn)的次數(shù)越多輪盤賭選中的概率越大；貪婪修復(fù)指將移除的貨架中SKU需求數(shù)量多的優(yōu)先插入靠近出入口的空閑位置。

ALNS算法在解的接受準(zhǔn)則上，為了避免只接受最優(yōu)解而陷入局部最優(yōu)，使用模擬退火準(zhǔn)則在一定概率下接受劣解，該概率P(dE)=exp(dE/T)，其中 dE表示當(dāng)前解與最優(yōu)解之差為負(fù)值。ALNS算法在迭代時(shí)根據(jù)算子的權(quán)重使用輪盤賭的方式選擇算子，通過選擇的破壞算子和修復(fù)算子生成新的鄰域解，并通過式 (16) 動(dòng)態(tài)調(diào)整破壞算子和修復(fù)算子的權(quán)重。

其中，ρo為算子權(quán)重，uo為算子使用次數(shù)，so為算子分?jǐn)?shù)，b為權(quán)重更新系數(shù)。算子分?jǐn)?shù)由算子的表現(xiàn)情況階梯式給分，得分越高表明算子表現(xiàn)越好。算子分?jǐn)?shù)的增加分為以下4種情況：1) 新解為全局最優(yōu)解，so+1.5；2) 該解不是全局最優(yōu)解，但優(yōu)于局部最優(yōu)解，so+1.2；3) 模擬退火準(zhǔn)則接受該劣解，so+0.8；4) 拒絕該劣解，so+0.6。在本文中，因?yàn)猷徲蛩阉鞯囊?guī)模較大，若如圖3所示流程中每搜索一個(gè)鄰域解調(diào)用一次GA算法求解揀貨路徑，則會(huì)消耗大量的時(shí)間。因此為了加速ALNS算法的求解過程，考慮在對(duì)鄰域解調(diào)用GA算法前先計(jì)算其貪婪初始解Dg，貪婪初始解每次尋找離當(dāng)前最近的儲(chǔ)位。如圖6所示，其中θ 為當(dāng)前解，θ′為內(nèi)層迭代的局部最優(yōu)解，θ?為外層的全局最優(yōu)解 (文中所指的外層全局最優(yōu)解表示遺傳算法在指定精度或迭代次數(shù)下得到的算法最優(yōu)解)。若Dg(θ)＜Dg(θ′)，則認(rèn)為 θ可能為優(yōu)解，并調(diào)用GA算法求解其揀貨路徑長度D(θ)，否則采取模擬退火的接受準(zhǔn)則。若接受則同樣使用GA算法求解揀貨路徑長度，否則定義為劣解。在求解出當(dāng)前解θ 的揀貨路徑長度D(θ)后，與局部最優(yōu)解的揀貨路徑長度D(θ′)和全局最優(yōu)解的揀貨路徑長度D(θ?)進(jìn)行比較，并更新算子的權(quán)重，從而完成一次內(nèi)層的迭代。

圖6 ALNS算子分?jǐn)?shù)更新流程圖Figure 6 Flowchart of the ALNS operator score update process

3 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證本文模型和算法的有效性，設(shè)計(jì)不同規(guī)模的測(cè)試算例對(duì)模型和算法進(jìn)行實(shí)驗(yàn)。數(shù)值實(shí)驗(yàn)過程在AMD Ryzen 3500U CPU、8GB內(nèi)存的筆記本電腦上運(yùn)行，求解器使用Gurobi9.0商業(yè)求解器，啟發(fā)式算法使用Python3.8實(shí)現(xiàn)。

設(shè)計(jì)帶有1 000個(gè)儲(chǔ)位的可移動(dòng)倉儲(chǔ)系統(tǒng)，將SKU隨機(jī)分配至各個(gè)儲(chǔ)位，生成100種SKU和200種SKU的倉庫數(shù)據(jù)分別為S1000_K100和S1000_K200，在隨機(jī)分配的過程中以一定的概率將相同的SKU分配在連續(xù)的l個(gè)儲(chǔ)位上以形成一個(gè)長度為l的貨架，并提前計(jì)算出儲(chǔ)位間的距離矩陣。訂單需求數(shù)據(jù)參考Silva等[15]使用的數(shù)據(jù)集，表2為使用的訂單需求數(shù)據(jù)集，其中訂單數(shù)表示需要完成揀選的訂單數(shù)量，一個(gè)訂單需要進(jìn)行一次揀貨操作；訂單中需求數(shù)是每個(gè)訂單中包含的不同SKU的數(shù)量；需求偏斜表示不同的需求分布，采用帕累托原則將SKU分為3類，偏斜的A/B/C表示少量SKU出現(xiàn)A%，中等SKU出現(xiàn)B%，大量SKU出現(xiàn)C%。

表2 訂單需求數(shù)據(jù)集Table 2 Dataset of the order demand

為了驗(yàn)證ALNS算法在貨架交換模型上求解的有效性，對(duì)不同的倉庫數(shù)據(jù)和不同的訂單數(shù)據(jù)集測(cè)試貨架移動(dòng)后的揀貨效果，分別對(duì)比初始分布、Apriori移動(dòng)初始解和ALNS移動(dòng)結(jié)果下的揀貨路徑長度，其中總成本為揀貨路徑長度+移動(dòng)貨架的數(shù)量。表3為貨架移動(dòng)算法的對(duì)比，其中Opt表示求解結(jié)果；Move表示移動(dòng)的儲(chǔ)位數(shù)量；Dev表示算法較于前者的優(yōu)化百分比。Apriori算法移動(dòng)結(jié)果相較于初始的布局能夠給揀貨路徑帶來較大的優(yōu)化，而ALNS算法的移動(dòng)結(jié)果在有Apriori作為初始解的情況下有了進(jìn)一步的優(yōu)化，在移動(dòng)貨架的數(shù)量增多的情況下總成本也有所減小，代表實(shí)際的揀貨路徑有著較大程度的優(yōu)化，在不同的倉庫數(shù)據(jù)和不同的訂單數(shù)據(jù)集中ALNS算法都有著不錯(cuò)的表現(xiàn)。以O(shè)10_I5_D3為例，ALNS算法目標(biāo)函數(shù)為540，相較于初始解優(yōu)化了26.8%，相較于初始分布優(yōu)化了46.5%。ALNS算法的迭代過程如圖7所示，其中藍(lán)色線表示內(nèi)層局部最優(yōu)解的下降曲線，會(huì)伴隨著模擬退火接受的劣解上下波動(dòng)，而褐色線表示全局最優(yōu)解的下降曲線。

表3 貨架移動(dòng)算法對(duì)比Table 3 Comparison of shelf movement algorithms

圖7 ALNS算法迭代過程Figure 7 Iterative process of ALNS algorithm

在可移動(dòng)倉儲(chǔ)系統(tǒng)中，特別是在“人到貨”的揀貨模式下，沒辦法對(duì)貨架進(jìn)行特別頻繁的移動(dòng)操作，若沒有AGV小車可能存在更高的人工移動(dòng)成本，因此如何平衡貨架移動(dòng)頻率和帶來的揀貨效率的提升是比較重要的。在實(shí)際應(yīng)用中，倉庫會(huì)累積一定數(shù)量的訂單并分批次進(jìn)行揀選作業(yè)，而決策時(shí)間可以表示為訂單池中訂單的累積時(shí)間。表4中記錄了24 h內(nèi)不同決策時(shí)間下進(jìn)行貨架移動(dòng)的結(jié)果對(duì)比，倉庫數(shù)據(jù)使用S1000_K100，共100個(gè)訂單，每個(gè)訂單20個(gè)需求SKU，將決策時(shí)間分為6 h、12 h和24 h，表示每過6 h、12 h、24 h，針對(duì)訂單池中累計(jì)的訂單進(jìn)行一次貨架移動(dòng)模型求解。從不同決策時(shí)間的結(jié)果來看，24 h內(nèi)決策次數(shù)越多，移動(dòng)的貨架總數(shù)越多，總體的揀貨路徑距離越短。如圖8所示，揀貨路徑距離與貨架移動(dòng)數(shù)量總體呈反比，盡管看起來增加決策次數(shù)，通過移動(dòng)大量的貨架有著較好的揀貨效率的提升，但實(shí)際上還要取決于不同倉庫中移動(dòng)貨架更改倉庫存儲(chǔ)布局所帶來的成本大小，即目標(biāo)函數(shù) (1) 中的p值。若使用AGV小車，則移動(dòng)成本較小且移動(dòng)速度較快，可以通過高頻次的貨架移動(dòng)實(shí)現(xiàn)更大程度的揀貨優(yōu)化；若使用人工移動(dòng)貨架，成本較大且移動(dòng)時(shí)間較長。因此需要考慮如何合理地制定決策次數(shù)，以平衡移動(dòng)成本的增加和揀貨成本的減小。從整體上來看，雙層啟發(fā)式算法在可移動(dòng)倉儲(chǔ)系統(tǒng)的揀貨路徑優(yōu)化取得了較優(yōu)的效果，通過ALNS算法結(jié)合模擬退火加強(qiáng)貨架移動(dòng)的鄰域搜索能力，以GA算法完成鄰域解的揀貨路徑的求解，并通過內(nèi)外層的不斷迭代，獲得一個(gè)較優(yōu)的貨架移動(dòng)和揀貨方案。

表4 不同決策階段移動(dòng)結(jié)果對(duì)比Table 4 Comparison of shelf movement results at different decision stages

圖8 ALNS算法不同決策階段的結(jié)果Figure 8 Results of ALNS algorithm at different decision stages

4 結(jié)論

本文針對(duì)可移動(dòng)貨架下的儲(chǔ)位選擇與揀貨路徑聯(lián)合優(yōu)化問題，首次提出了雙層的混合整數(shù)規(guī)劃模型，包括下層訂單揀貨路徑優(yōu)化模型，上層貨架移動(dòng)優(yōu)化模型。并通過雙層的元啟發(fā)式算法完成了對(duì)模型的求解，上下兩層模型互相影響從而求解出最優(yōu)的移動(dòng)和揀貨方案。最后使用不同規(guī)模的數(shù)值實(shí)驗(yàn)完成了算法的可行性和有效性驗(yàn)證，為可移動(dòng)倉儲(chǔ)系統(tǒng)提供了貨架移動(dòng)和揀貨優(yōu)化的新思路和新方法。