賴品諺，張大力，趙思翔

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

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

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

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

1 模型構(gòu)建

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

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

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

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

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

表1 模型符號定義Table 1 Symbol definitions in the model

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

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

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

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

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

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

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

2.1 算法框架

下層的揀貨路徑優(yōu)化模型中采用遺傳算法對儲位的選擇以及揀貨的順序進(jìn)行求解，其求解結(jié)果為某一倉庫布局下的訂單需求的最優(yōu)揀貨路徑；上層模型中采用搜索能力較強(qiáng)的自適應(yīng)大鄰域搜索算法求解。此外本算法使用Apriori關(guān)聯(lián)算法作為ALNS的初始解加快算法收斂，雙層元啟發(fā)式算法框架如圖2所示，上層ALNS算法每求解出一個(gè)儲位布局的鄰域結(jié)果便傳遞到下層GA算法中，下層GA算法計(jì)算該鄰域結(jié)果上的所有訂單需求的最優(yōu)揀貨路徑距離和，上層ALNS算法通過下層GA算法的返回值在不同的鄰域中進(jìn)行搜索對比，通過若干次迭代，最終選出最優(yōu)的鄰域結(jié)果作為貨架移動后的倉庫儲位布局。雙層元啟發(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ī)則才會被稱為強(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)弱按順序可以對貨架進(jìn)行交換，使得具有強(qiáng)關(guān)聯(lián)性的SKU貨架盡可能接近，以減少揀貨路徑距離。本文將根據(jù)Apriori的關(guān)聯(lián)結(jié)果對貨架進(jìn)行移動作為后續(xù)ALNS算法的初始解，移動方法步驟如下。

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)，如果已完成對所有強(qiáng)關(guān)聯(lián)組合的移動則進(jìn)入步驟5)。

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

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

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

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

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

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

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

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

ALNS算法采用內(nèi)層與外層的迭代方式對鄰域進(jìn)行搜索，內(nèi)層結(jié)合模擬退火的思想，通過降溫的方式進(jìn)行搜索，外層限定終止條件，即達(dá)到最大迭代次數(shù)，不滿足終止條件就進(jìn)入內(nèi)層繼續(xù)搜索。ALNS算法的核心思想是通過不斷地破壞和修復(fù)解從而完成對解空間鄰域的搜索，并自適應(yīng)地調(diào)整破壞算子和修復(fù)算子的權(quán)重，通過該權(quán)重控制每個(gè)修復(fù)算子和破壞算子在搜索期間使用的頻率，表現(xiàn)更好的算子將獲得更高的權(quán)重，從而提高算法的搜索尋優(yōu)能力。本文基于Apriori算法結(jié)果的基礎(chǔ)上，使用ALNS算法進(jìn)一步對貨架移動問題進(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) 動態(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算法求解揀貨路徑，則會消耗大量的時(shí)間。因此為了加速ALNS算法的求解過程，考慮在對鄰域解調(diào)用GA算法前先計(jì)算其貪婪初始解Dg，貪婪初始解每次尋找離當(dāng)前最近的儲位。如圖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ī)模的測試算例對模型和算法進(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è)儲位的可移動倉儲系統(tǒng)，將SKU隨機(jī)分配至各個(gè)儲位，生成100種SKU和200種SKU的倉庫數(shù)據(jù)分別為S1000_K100和S1000_K200，在隨機(jī)分配的過程中以一定的概率將相同的SKU分配在連續(xù)的l個(gè)儲位上以形成一個(gè)長度為l的貨架，并提前計(jì)算出儲位間的距離矩陣。訂單需求數(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算法在貨架交換模型上求解的有效性，對不同的倉庫數(shù)據(jù)和不同的訂單數(shù)據(jù)集測試貨架移動后的揀貨效果，分別對比初始分布、Apriori移動初始解和ALNS移動結(jié)果下的揀貨路徑長度，其中總成本為揀貨路徑長度+移動貨架的數(shù)量。表3為貨架移動算法的對比，其中Opt表示求解結(jié)果；Move表示移動的儲位數(shù)量；Dev表示算法較于前者的優(yōu)化百分比。Apriori算法移動結(jié)果相較于初始的布局能夠給揀貨路徑帶來較大的優(yōu)化，而ALNS算法的移動結(jié)果在有Apriori作為初始解的情況下有了進(jìn)一步的優(yōu)化，在移動貨架的數(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)解的下降曲線，會伴隨著模擬退火接受的劣解上下波動，而褐色線表示全局最優(yōu)解的下降曲線。

表3 貨架移動算法對比Table 3 Comparison of shelf movement algorithms

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

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

表4 不同決策階段移動結(jié)果對比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é)論

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