某型自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位優(yōu)化算法研究

陳儉新，黃予洛，寧蒙，李冠峰

鄭州機(jī)電工程研究所，河南 鄭州 450015

0 引 言

隨著物流行業(yè)的發(fā)展，自動(dòng)化立體倉(cāng)庫(kù)正在逐步取代傳統(tǒng)倉(cāng)庫(kù)成為物資存放的主要形式。自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位優(yōu)化問(wèn)題是物資倉(cāng)儲(chǔ)領(lǐng)域研究的熱點(diǎn)之一。朱杰等[1]從貨物出入庫(kù)時(shí)間、同組貨品距離以及貨架重心等方面建立自動(dòng)化存取系統(tǒng)貨位分配優(yōu)化模型，比較了改進(jìn)遺傳模擬退火算法、標(biāo)準(zhǔn)粒子群算法、人工魚(yú)群算法的優(yōu)化求解效果；馮愛(ài)蘭等[2]從減少訂單分批和最小化作業(yè)時(shí)間兩方面建立了自動(dòng)化立體倉(cāng)庫(kù)貨位分配優(yōu)化模型；張貴軍等[3]以貨架重心低、出入庫(kù)頻率高、貨物離出入庫(kù)口近等為原則建立了貨位分配模型，使用基于精英多策略的方法優(yōu)化貨位分配；陳月婷等[4]考慮貨架的穩(wěn)定性和出入庫(kù)效率，建立儲(chǔ)位優(yōu)化的數(shù)學(xué)模型，提出了基于Pareto 最優(yōu)解的改進(jìn)粒子群算法（PSO）來(lái)解決此問(wèn)題；焦玉玲等[5]考慮貨物出入庫(kù)作業(yè)時(shí)間、貨架整體等效重心等因素，構(gòu)建多目標(biāo)貨位分配優(yōu)化數(shù)學(xué)模型，提出了多種群遺傳算法求解貨位分配優(yōu)化數(shù)學(xué)模型；Yue 等[6]結(jié)合自動(dòng)化立體倉(cāng)庫(kù)應(yīng)力穩(wěn)定性和出庫(kù)效率建立自動(dòng)化立體倉(cāng)庫(kù)優(yōu)化數(shù)學(xué)模型，提出了基于改進(jìn)遺傳算法的儲(chǔ)位優(yōu)化算法；邱建東等[7]以自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)效率建立數(shù)學(xué)模塊，提出了基于周期性病毒遺傳算法的儲(chǔ)位優(yōu)化方法；Wu 等[8]結(jié)合貨架的穩(wěn)定性和存取貨物的效率建立數(shù)學(xué)模型，通過(guò)改進(jìn)遺傳算法實(shí)現(xiàn)對(duì)自動(dòng)化立體倉(cāng)庫(kù)貨位分配的優(yōu)化；Pan 等[9]結(jié)合貨架空間利用率和貨物揀選效率建立數(shù)學(xué)模型，通過(guò)啟發(fā)式遺傳算法實(shí)現(xiàn)對(duì)倉(cāng)庫(kù)貨位分配的優(yōu)化。以上研究的數(shù)學(xué)模型基本以運(yùn)行效率和貨架穩(wěn)定性為目標(biāo)，并且大多采用遺傳算法和模擬退火算法求解。其中遺傳算法雖然全局搜索能力強(qiáng)但過(guò)早收斂且易陷入局部最優(yōu)解；模擬退火算法局部搜索能力強(qiáng)，但收斂速度慢。

某型船用多載具自動(dòng)化立體倉(cāng)庫(kù)由平移裝置、升降裝置、儲(chǔ)具和自動(dòng)化控制設(shè)備等組成，是我國(guó)自主研發(fā)的特種立體倉(cāng)庫(kù)，主要用于存儲(chǔ)特種物資，為用戶提供容積率高、出庫(kù)便捷的物資存儲(chǔ)服務(wù)。儲(chǔ)位分配優(yōu)化是實(shí)現(xiàn)自動(dòng)化存取系統(tǒng)高效運(yùn)作的基礎(chǔ)瓶頸問(wèn)題，該問(wèn)題類似于廣義指派問(wèn)題[10]，且已被Sahni 等[11]和Feng 等[12]證明為NP 完全（NP-complete）問(wèn)題。

該型立體倉(cāng)庫(kù)系統(tǒng)初始為有序狀態(tài)，在日常運(yùn)行過(guò)程中，調(diào)度員按需隨機(jī)地對(duì)儲(chǔ)具進(jìn)行出入庫(kù)操作。因此，在使用一段時(shí)間后會(huì)造成自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)具類型擺放混亂的問(wèn)題。為保證物資出庫(kù)效率，同時(shí)解決由此引發(fā)的立體倉(cāng)庫(kù)載荷不均衡等問(wèn)題，必須在盡可能短的時(shí)間內(nèi)進(jìn)行立體倉(cāng)庫(kù)庫(kù)位優(yōu)化操作。

考慮到本系統(tǒng)對(duì)儲(chǔ)位優(yōu)化時(shí)間的要求，為解決以上問(wèn)題，本文將使用蒙特卡洛樹(shù)搜索（Monte Carlo Tree Search，MCTS）的儲(chǔ)位優(yōu)化算法求解，并在局部參考模擬退火思想，增加算法局部搜索隨機(jī)性。該方法通過(guò)可以提前預(yù)測(cè)輸入優(yōu)化步驟在模擬運(yùn)行的輸出值，然后通過(guò)蒙特卡洛樹(shù)搜索算法在等效無(wú)滯后的情況下學(xué)習(xí)控制策略，消除滯后的影響，加快響應(yīng)速度和收斂速度。

1 問(wèn)題描述及建模

1.1 問(wèn)題描述

以某型號(hào)船用自動(dòng)化無(wú)人倉(cāng)庫(kù)為研究對(duì)象，其初始狀態(tài)如圖1 所示。該倉(cāng)庫(kù)有3 個(gè)橫向作業(yè)巷道和2 個(gè)垂直巷道，出口在倉(cāng)庫(kù)左側(cè)，貨物統(tǒng)一由倉(cāng)庫(kù)左側(cè)出庫(kù)，在平衡狀態(tài)下，貨物應(yīng)基于左側(cè)進(jìn)行類別分配，其布局關(guān)于橫向巷道作業(yè)巷道對(duì)稱，即對(duì)稱作業(yè)巷道的儲(chǔ)位布局完全一致，該倉(cāng)庫(kù)為同端出/入布局，即入庫(kù)口與出庫(kù)口在巷道的同一側(cè)，貨架沿通道排列，平移裝置按指令沿通道運(yùn)行，進(jìn)行貨架上貨物的揀選作業(yè)。

圖1 某型自動(dòng)化立體倉(cāng)庫(kù)初始狀態(tài)Fig. 1 Initial state of an automated 3D warehouse

庫(kù)存盤點(diǎn)過(guò)程中，算法根據(jù)當(dāng)前庫(kù)存狀態(tài)選擇儲(chǔ)具運(yùn)行動(dòng)作，儲(chǔ)具運(yùn)行的目的就是將分布于立體倉(cāng)庫(kù)各層的同類型儲(chǔ)具進(jìn)行合并。儲(chǔ)位優(yōu)化過(guò)程中，可以通過(guò)檢查庫(kù)存狀態(tài)設(shè)置一個(gè)暫存區(qū)，該暫存區(qū)用于存放需要順序調(diào)整的儲(chǔ)具，通過(guò)不停進(jìn)行儲(chǔ)具周轉(zhuǎn)動(dòng)作，實(shí)現(xiàn)庫(kù)存的平衡有序。其中，自動(dòng)化立體倉(cāng)庫(kù)按照指令周期模式進(jìn)行運(yùn)作，通過(guò)平移裝置、儲(chǔ)具升降裝置的配合完成各指令操作。

本文自動(dòng)化立體倉(cāng)庫(kù)有R行C列(R≥3，C≥3)，各行有N(N≤C-2)個(gè)儲(chǔ)具，存放K種物資，此處K=3。自動(dòng)化立體倉(cāng)庫(kù)動(dòng)作如表1 和圖2 所示。

圖2 自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位移動(dòng)示意圖Fig. 2 Schematic diagram of automatic 3D warehouse slotting position movement

表1 自動(dòng)化立體倉(cāng)庫(kù)動(dòng)作集合Table 1 The action set of automated 3D warehouse

本文主要研究多平移裝置在多儲(chǔ)具混亂的情況下，設(shè)計(jì)合理的儲(chǔ)具運(yùn)行步驟，從庫(kù)存平衡狀態(tài)、作業(yè)時(shí)間等各方面考慮，以最小化指令周期內(nèi)存取貨物的時(shí)間距離為目標(biāo)進(jìn)行集成優(yōu)化。

1.2 模型建立

對(duì)于自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位優(yōu)化問(wèn)題，首先要達(dá)到的目標(biāo)是同類儲(chǔ)具集合存放，且對(duì)于三行儲(chǔ)具、三類儲(chǔ)具的問(wèn)題，每一行對(duì)應(yīng)各類儲(chǔ)具，以保證出庫(kù)效率；此外，應(yīng)考慮儲(chǔ)位優(yōu)化耗時(shí)最短，儲(chǔ)位優(yōu)化的總時(shí)間與采取的儲(chǔ)具移動(dòng)措施、移動(dòng)次數(shù)和路徑長(zhǎng)度有關(guān)，在速度恒定的情況下，移動(dòng)次數(shù)越少，路徑長(zhǎng)度越短，儲(chǔ)具儲(chǔ)位優(yōu)化耗時(shí)越短。因此，需要以庫(kù)存的離散度之和最小及儲(chǔ)具儲(chǔ)位優(yōu)化時(shí)間最短為目標(biāo)，建立自動(dòng)儲(chǔ)具儲(chǔ)位優(yōu)化數(shù)學(xué)模型。

計(jì)算儲(chǔ)具類內(nèi)離散度，定義第t次儲(chǔ)位優(yōu)化時(shí)第Ki類儲(chǔ)具的坐標(biāo)均值為

第t次儲(chǔ)位優(yōu)化時(shí)第Ki類型儲(chǔ)具的第j個(gè)儲(chǔ)具到均值坐標(biāo)的距離可表示為

式中：dt為 第t次儲(chǔ)位優(yōu)化時(shí)所有KI類儲(chǔ)具類內(nèi)離散距離之和；(x)為 第t次貨物優(yōu)化時(shí)第Ki類儲(chǔ)具行數(shù)的坐標(biāo)均值；(y)為第t次貨物優(yōu)化時(shí)第Ki類儲(chǔ)具列數(shù)的坐標(biāo)均值。隨后，計(jì)算類間離散度。全部KI類儲(chǔ)具的均值坐標(biāo)為Mt[x,y]，則

定義所有儲(chǔ)具類中心到Ki類儲(chǔ)具中心Mt[x,y]的離散度和的值為每類儲(chǔ)具的中心[x,y]到Mt[x,y]的距離和，則

式中：Mt(x) 為 水平方向均值坐標(biāo)值；Mt(y)為垂直方向均值坐標(biāo)值。由于儲(chǔ)具所存貨物種類繁多，需要將儲(chǔ)存相同類型貨物的儲(chǔ)具放在一起，并盡量使所有類型儲(chǔ)具均勻分散在倉(cāng)庫(kù)中并離出庫(kù)口最近，因此需要使類內(nèi)離散度盡量小，類間離散度盡量大，并使均值坐標(biāo)點(diǎn)M離出庫(kù)口距離最短。

則得到第1 個(gè)目標(biāo)函數(shù)庫(kù)存最小離散度之和minF1為

儲(chǔ)位優(yōu)化是對(duì)儲(chǔ)位重新調(diào)整的過(guò)程，儲(chǔ)具的重新擺放涉及到儲(chǔ)具的搬運(yùn)。本文主要研究平移裝置、左右兩側(cè)升降裝置運(yùn)行次數(shù)及累加的時(shí)間。為節(jié)約時(shí)間和成本，需要使搬運(yùn)時(shí)間最短。自動(dòng)化立體倉(cāng)庫(kù)移動(dòng)過(guò)程中，平移裝置移動(dòng)時(shí)間要快于左右兩側(cè)升降裝置移動(dòng)時(shí)間。

儲(chǔ)位優(yōu)化單步移動(dòng)時(shí)間分為2 種情況：

1） 循環(huán)、集合操作。2 種操作均為儲(chǔ)具集合的移動(dòng)，各儲(chǔ)具移動(dòng)均包括平移裝置移動(dòng)和升降裝置移動(dòng)，平移裝置與升降裝置并行移動(dòng)。

2） 出/入暫存區(qū)、單個(gè)儲(chǔ)具換層操作。2 種操作均為單個(gè)儲(chǔ)具的移動(dòng)，各儲(chǔ)具移動(dòng)均包括平移裝置移動(dòng)和升降裝置移動(dòng)，平移裝置與升降裝置串行移動(dòng)。

因此儲(chǔ)具移動(dòng)總時(shí)間分為2種情況。設(shè)[xKi j(t-1),[yKij(t-1)]為]第Ki類型儲(chǔ)具的第j個(gè)儲(chǔ)具的當(dāng)前坐標(biāo)，xKijt,yKijt為儲(chǔ)具移動(dòng)后的坐標(biāo)。

1） 循環(huán)、集合操作時(shí)，儲(chǔ)位優(yōu)化花費(fèi)時(shí)間為

2） 出/入暫存區(qū)、單個(gè)儲(chǔ)具換層操作，儲(chǔ)位優(yōu)化花費(fèi)時(shí)間為

因此，得到第2 個(gè)目標(biāo)函數(shù)最短儲(chǔ)具儲(chǔ)位優(yōu)化時(shí)間 minF2為

式中，Z為儲(chǔ)位優(yōu)化總步數(shù)。

最后，由式(7)和式(8)得到儲(chǔ)位優(yōu)化數(shù)學(xué)模型為

式中：t，i，j，x，y，n為約束條件，均為整數(shù)；t=1，2，3，···， 表示儲(chǔ)位優(yōu)化步數(shù)，i為儲(chǔ)具種類，j為第Ki類儲(chǔ)具中某個(gè)儲(chǔ)具，x為儲(chǔ)具水平位置，y為儲(chǔ)具垂直位置，n為第Ki類儲(chǔ)具總數(shù)；1≤i≤KI，1≤j≤n，0＜x＜C，0＜Y＜R，0＜n＜N。

模型中2 個(gè)目標(biāo)函數(shù)F1和F2的量綱不一致，需要進(jìn)行歸一化處理。其中F1為 無(wú)量綱量，F(xiàn)2的單位為s，所以只需對(duì)F2進(jìn)行歸一化處理：

式中： maxF2為系統(tǒng)允許儲(chǔ)位優(yōu)化的最長(zhǎng)時(shí)間；ε為歸一化參數(shù)，設(shè)置 ε的意義是為了防止在計(jì)算過(guò)程中出現(xiàn)數(shù)值溢出情況，本文取值ε= 0.001。

為了防止多目標(biāo)模型在求解時(shí)相互影響，需要給目標(biāo)函數(shù)添加權(quán)重系數(shù)ω，以此轉(zhuǎn)化為單目標(biāo)模型，式( 12) 為變形后的目標(biāo)函數(shù)：

其中使用層次分析法( analytic hierarchy process，AHP) 求解[4]的權(quán)重系數(shù)為 ω1= 0.647 9， ω2= 0.352 1。

2 基于模擬退火的蒙特卡洛樹(shù)算法（SA-MCTS）設(shè)計(jì)

2.1 算法選擇

根據(jù)表1 可執(zhí)行動(dòng)作信息，自動(dòng)化立體倉(cāng)庫(kù)執(zhí)行儲(chǔ)位優(yōu)化時(shí)，每步需考慮28 種可能執(zhí)行結(jié)果，對(duì)于3×9 的自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位優(yōu)化問(wèn)題，初始空庫(kù)實(shí)現(xiàn)有序入庫(kù)需至少27 步，考慮到儲(chǔ)具類型數(shù)量不平均、布局不均衡等因素，自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位優(yōu)化形成路徑搜索樹(shù)至少為 2728，約1.197×1040。因此，自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位優(yōu)化步驟搜索空間巨大，對(duì)儲(chǔ)位優(yōu)化狀態(tài)樹(shù)進(jìn)行搜索直到終局的方法并不可行，不可能對(duì)后續(xù)所有情況進(jìn)行完全統(tǒng)計(jì)。

儲(chǔ)位分配中選擇自動(dòng)儲(chǔ)具進(jìn)行庫(kù)存調(diào)整的過(guò)程可以被視為馬爾科夫決策過(guò)程（Markov decision process，MDP）[13]，上述章節(jié)建立的庫(kù)存狀態(tài)和目標(biāo)函數(shù)作為馬爾科夫過(guò)程的狀態(tài)和過(guò)程參數(shù)，來(lái)指導(dǎo)儲(chǔ)具調(diào)度。自動(dòng)化立體倉(cāng)庫(kù)內(nèi)儲(chǔ)位優(yōu)化馬爾科夫決策通過(guò)四元組描述為{S，A，P，R}，其中，S為狀態(tài)集合，A為動(dòng)作集合，P為狀態(tài)轉(zhuǎn)移函數(shù)，R為效用函數(shù)。采用蒙特卡羅樹(shù)搜索算法，基于強(qiáng)化學(xué)習(xí)模型Mv和模擬策略π，對(duì)于當(dāng)前要選擇動(dòng)作的狀態(tài)St，對(duì)每一個(gè)可能采樣的動(dòng)作a∈A，都進(jìn)行K輪采樣，這樣每個(gè)動(dòng)作a都會(huì)得到K組經(jīng)歷完整的狀態(tài)序列。即

對(duì)于每個(gè) (St,a)組合，可以基于蒙特卡洛法來(lái)計(jì)算其動(dòng)作價(jià)值函數(shù)并選擇最優(yōu)的動(dòng)作。

式中，Gt為一個(gè)模擬序列的訓(xùn)練得分。式（14）和式（15）為對(duì)k個(gè)模擬序列采樣，創(chuàng)建一個(gè)由已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)和動(dòng)作組成的樹(shù)，并評(píng)估樹(shù)內(nèi)每個(gè)狀態(tài)動(dòng)作的價(jià)值；構(gòu)建完成之后，選擇當(dāng)前狀態(tài)St所能執(zhí)行動(dòng)作中Q值最大的節(jié)點(diǎn)作為后續(xù)動(dòng)作起點(diǎn)。

MCTS 以當(dāng)前狀態(tài)為根節(jié)點(diǎn)建立搜索樹(shù)，通過(guò)向前預(yù)估可能發(fā)生的各種情況，綜合選擇最好的動(dòng)作。采用該思想只需求解從當(dāng)前狀態(tài)開(kāi)始的子MDP 過(guò)程，無(wú)需求解整個(gè)MDP 過(guò)程，因此MCTS 能夠處理狀態(tài)動(dòng)作數(shù)量較大的馬爾科夫問(wèn)題。目前，以MCTS 搜索算法為代表的強(qiáng)化學(xué)習(xí)算法已經(jīng)在電力系統(tǒng)[14]、圍棋類游戲[15-16]、計(jì)算機(jī)視覺(jué)[17]、軌跡跟蹤預(yù)測(cè)[18]等方面廣泛應(yīng)用。

2.2 基于SA-MCTS 強(qiáng)化學(xué)習(xí)

針對(duì)自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位優(yōu)化問(wèn)題，提出基于模擬退火的蒙特卡洛樹(shù)算法(simulated annealing Monte Carlo Tree search，SA-MCTS)的儲(chǔ)位優(yōu)化方法。SA-MCTS 算法源于MCTS，其求解庫(kù)存盤點(diǎn)問(wèn)題的總體思路是將庫(kù)存盤點(diǎn)過(guò)程看作一個(gè)模擬隨機(jī)落子過(guò)程，其中，以每次儲(chǔ)位優(yōu)化動(dòng)作作為一次模擬過(guò)程，以當(dāng)前狀態(tài)得分作為儲(chǔ)位優(yōu)化效果。然后依據(jù)數(shù)學(xué)模型中的約束關(guān)系制定規(guī)則，以收益最大化為優(yōu)化目標(biāo)，整個(gè)搜索過(guò)程包括選擇、擴(kuò)展、模擬和更新4個(gè)階段[19]。本文通過(guò)對(duì)MCTS 的選擇、模擬、更新步驟進(jìn)行改進(jìn)，最終實(shí)現(xiàn)自動(dòng)化立體倉(cāng)庫(kù)庫(kù)存優(yōu)化目標(biāo)。

2.2.1 選 擇

MCTS 通過(guò)樹(shù)策略選擇下一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展，從根節(jié)點(diǎn)開(kāi)始，遞歸地選擇得分最高的子節(jié)點(diǎn)或終端狀態(tài)（游戲勝負(fù)或循環(huán)時(shí)間到）。在MCTS 中遍歷樹(shù)的分?jǐn)?shù)稱為樹(shù)策略，在傳統(tǒng)的MCTS 方法中，由上限界限信心（upper confidence bound，UCB）方程給出：

式中：VUCB為 節(jié)點(diǎn)的UCB 得分；vi為節(jié)點(diǎn)v的第i個(gè)子節(jié)點(diǎn)；Q為獲取節(jié)點(diǎn)累計(jì)價(jià)值的函數(shù)；Q(vi)為在v節(jié)點(diǎn)處采用i動(dòng)作獲得的總得分；N(vi)為獲取節(jié)點(diǎn)累計(jì)訪問(wèn)次數(shù)的函數(shù)；Q(vi)/N(vi)為強(qiáng)調(diào)對(duì)歷史動(dòng)作的利用；N(v)為總模擬次數(shù)；c為用于調(diào)整加號(hào)前后兩部分在整體中的比重系數(shù)，c越大越偏向于廣度搜索，c越小越偏向于深度搜索。

單純使用MCTS 算法，容易陷入局部最大值，即使在非最優(yōu)狀態(tài)，仍然無(wú)法跳出局部最優(yōu)[19-20]。本文通過(guò)使用Metropolis 準(zhǔn)則，使當(dāng)前步驟以一定概率接收離散度較差的情況。

選擇算法設(shè)計(jì)如圖3 所示，其中，T為退火系數(shù)，q為模擬退火降溫速度；double為數(shù)據(jù)類型，rand()為取隨機(jī)數(shù)函數(shù)，RAND_MAX為隨機(jī)數(shù)的范圍。

圖3 選擇模塊算法圖Fig. 3 Algorithm diagram of selection module

2.2.2 擴(kuò) 展

如果搜索至葉節(jié)點(diǎn)SL且該節(jié)點(diǎn)遍歷次數(shù)大于等于P（P為節(jié)點(diǎn)擴(kuò)展臨界值）時(shí)，應(yīng)用選擇策略后執(zhí)行分支節(jié)點(diǎn)擴(kuò)展。根據(jù)動(dòng)作a得到狀態(tài)SCL。此時(shí)將狀態(tài)SCL擴(kuò)展為樹(shù)中葉節(jié)點(diǎn)且節(jié)點(diǎn)初始信息為{N(SL,a)=0，Q(SL,a)=0，N(SCL)=0}。如果下一個(gè)要到達(dá)的狀態(tài)為變差狀態(tài)或相同狀態(tài)，則進(jìn)行剪枝操作，并且直接結(jié)束本次尋優(yōu)控制，否則轉(zhuǎn)到模擬階段。

2.2.3 模 擬

根據(jù)表1 中自動(dòng)化立體倉(cāng)庫(kù)可執(zhí)行動(dòng)作列表，隨機(jī)選擇某一動(dòng)作作為模擬策略，模擬過(guò)程中需判斷，如果模擬結(jié)果已經(jīng)達(dá)到庫(kù)存平衡標(biāo)準(zhǔn)，則停止模擬。結(jié)束后，根據(jù)式（12）判定勝負(fù)，即獲得的收益值Vreward，并將其返回。

2.2.4 更 新

當(dāng)模擬至定義的終止?fàn)顟B(tài)時(shí)（如終止深度），信息更新從模擬的初始葉節(jié)點(diǎn)SL回溯至根節(jié)點(diǎn)S0。更新各遍歷節(jié)點(diǎn)信息：

其中，L(L,0)為葉節(jié)點(diǎn)至根節(jié)點(diǎn)距離。

通過(guò)重復(fù)上述MCTS 動(dòng)作以及不斷地?cái)M合、控制，最終蒙特卡洛搜索樹(shù)將收斂，回溯MCTS動(dòng)作可以獲得儲(chǔ)位優(yōu)化策略。綜上所述，梳理基于SA-MCTS 算法的儲(chǔ)位優(yōu)化算法流程，如圖4 所示。

圖4 基于SA-MCTS 的儲(chǔ)位優(yōu)化算法流程圖Fig. 4 SA-MCTS based slotting optimization algorithm flow chart

2.3 SA-MCTS 參數(shù)設(shè)置

設(shè)置自動(dòng)化立體倉(cāng)庫(kù)的庫(kù)存容量、緩沖區(qū)大小、模擬退火參數(shù)、蒙特卡洛搜索算法參數(shù)、儲(chǔ)具類型以及計(jì)算機(jī)模擬環(huán)境等參數(shù)。

2.3.1 自動(dòng)化立體倉(cāng)庫(kù)參數(shù)設(shè)置

1） 自動(dòng)化立體倉(cāng)庫(kù)庫(kù)存大小為3 行9 列，即該倉(cāng)庫(kù)高3 層，每層9 個(gè)儲(chǔ)位；

2） 自動(dòng)化立體倉(cāng)庫(kù)中有2 個(gè)空儲(chǔ)位作為緩沖區(qū)，該緩沖區(qū)可以在儲(chǔ)位優(yōu)化過(guò)程中靈活變動(dòng)，該緩沖區(qū)容量設(shè)置考慮了儲(chǔ)具出入庫(kù)時(shí)間，同時(shí)兼顧內(nèi)部?jī)?chǔ)具；

3） 為使問(wèn)題簡(jiǎn)單化，在儲(chǔ)具運(yùn)輸過(guò)程中不考慮庫(kù)存半箱及半箱擺放問(wèn)題，庫(kù)存包含3 類儲(chǔ)具：A 類型儲(chǔ)具、B 類型儲(chǔ)具、空儲(chǔ)具；

4） 平移裝置每移一步時(shí)間為9 s；

5） 升降裝置每移動(dòng)一層時(shí)間為13 s，平移、升降裝置時(shí)間均根據(jù)電機(jī)轉(zhuǎn)速及移動(dòng)距離計(jì)算得到。

2.3.2 SA-MCTS 算法參數(shù)設(shè)置

1） UCB 公式中參數(shù)c設(shè)置為2，c越大越偏向廣度搜索，c越小越偏向深度搜索；

2） MCTS 最 大 運(yùn) 行 深 度MAX_DEPTH設(shè) 置為70，考慮儲(chǔ)位優(yōu)化的時(shí)效問(wèn)題，將搜索最大深度設(shè)計(jì)為70；

3） MCTS 最大運(yùn)行模擬次數(shù)CHOICES設(shè)置為27，對(duì)應(yīng)該自動(dòng)化立體倉(cāng)庫(kù)可運(yùn)行所有動(dòng)作集合；

4） MCTS 最大子節(jié)點(diǎn)數(shù)MAX_CHOICE設(shè)置為27，對(duì)應(yīng)該自動(dòng)化立體倉(cāng)庫(kù)可能存在的最多子節(jié)點(diǎn)數(shù)量；

5） 模擬退火初始溫度T0=50 000，該參數(shù)參考文獻(xiàn)[4]設(shè)置；

6） 退火系數(shù)Tend= 1×10-8；

7） 模擬退火降溫速度q=0.98，實(shí)際應(yīng)用中該參數(shù)設(shè)置為0.99 或0.98，本文設(shè)置為0.98，主要考慮讓算法充分尋優(yōu)。

2.3.3 初始狀態(tài)和目標(biāo)狀態(tài)

初始狀態(tài)下自動(dòng)化立體倉(cāng)庫(kù)的3 種類型儲(chǔ)具隨機(jī)均勻分布。

目標(biāo)狀態(tài)為各行均以3 種類型中的一種儲(chǔ)具為隊(duì)列頭部，后續(xù)為同類儲(chǔ)具，同類儲(chǔ)具多于一行的情況下，可以順序存入其他行。

2.3.4 獎(jiǎng)勵(lì)函數(shù)

本文根據(jù)自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)具運(yùn)動(dòng)， minF1和minF2分別為之前和本次目標(biāo)函數(shù)運(yùn)算結(jié)果，可能存在的收益包括：收益增加、收益不變、收益減少，因此Vreward設(shè)計(jì)為

2.3.5 計(jì)算環(huán)境

計(jì)算機(jī)硬件環(huán)境為龍芯3A4000 處理器，內(nèi)存8 GB；軟件環(huán)境為中標(biāo)麒麟桌面版本V5 64 位操作系統(tǒng)。

3 仿真結(jié)果及分析

依據(jù)上述參數(shù)，應(yīng)用SA-MCTS 算法對(duì)自動(dòng)化立體倉(cāng)庫(kù)儲(chǔ)位進(jìn)行優(yōu)化排列。本文采用隨機(jī)生成的3 000 組庫(kù)存數(shù)據(jù)進(jìn)行優(yōu)化算法驗(yàn)證，庫(kù)存由盤庫(kù)算法模擬器隨機(jī)生成，軟件界面如圖5 所示。圖6 所示為儲(chǔ)位優(yōu)化的某一中間狀態(tài)，其中第2 行儲(chǔ)位缺少2 個(gè)位置,是由于已有2 個(gè)儲(chǔ)具A，B 出庫(kù)（出庫(kù)儲(chǔ)具見(jiàn)圖6 左下角），騰出暫存區(qū)導(dǎo)致。圖7 所示為儲(chǔ)位優(yōu)化完成后的庫(kù)存狀態(tài)。

圖5 儲(chǔ)位優(yōu)化算法模擬器界面Fig. 5 Slotting optimization algorithm simulator interface

圖6 儲(chǔ)位優(yōu)化運(yùn)行中間結(jié)果展示Fig. 6 Display of slotting optimization intermediate result

圖7 儲(chǔ)位優(yōu)化結(jié)果展示Fig. 7 Display of slotting optimization result

圖8 所示為蒙特卡洛搜索樹(shù)深度與收益值的比較結(jié)果，其中每條線為一次訓(xùn)練過(guò)程。由圖可見(jiàn)，在前期搜索中，隨著節(jié)點(diǎn)經(jīng)驗(yàn)信息依次累加，庫(kù)存離散程度迅速降低；在后期搜索中，隨著狀態(tài)空間不斷縮小，樹(shù)節(jié)點(diǎn)越深其收益數(shù)值變化越趨平緩，且數(shù)據(jù)波動(dòng)越趨收窄。因而說(shuō)明在儲(chǔ)位優(yōu)化中應(yīng)用SA-MCTS 能夠快速準(zhǔn)確地選擇最優(yōu)儲(chǔ)位動(dòng)作決策。

圖8 蒙特卡洛搜索樹(shù)深度與收益值的比較Fig. 8 Comparison of depth and reward value by Monte Carlo search tree algorithm

在SA-MCTS 算法真正有效地進(jìn)行儲(chǔ)位優(yōu)化之前的所有迭代，都稱為訓(xùn)練學(xué)習(xí)迭代。本文設(shè)置訓(xùn)練學(xué)習(xí)時(shí)間為1 000 次“選擇-擴(kuò)展-模擬-反向更新”尋優(yōu)過(guò)程。最后得到從SA-MCTS 控制到儲(chǔ)位優(yōu)化的最佳時(shí)間變化曲線，如圖9 所示。

圖9 收斂次數(shù)分布(頻次與正態(tài)分布圖)Fig. 9 Convergence number distribution (frequency and normal distribution map)

由圖8 和圖9 可知，隨著不斷嘗試儲(chǔ)具動(dòng)作、學(xué)習(xí)迭代，采用SA-MCTS 算法得到的儲(chǔ)位優(yōu)化時(shí)間越來(lái)越短，可確定較好的儲(chǔ)位優(yōu)化策略。

為了驗(yàn)證SA-MCTS 算法的儲(chǔ)位優(yōu)化能力，本文設(shè)計(jì)了基于貪心算法、基于魔方還原算法和傳統(tǒng)MCTS 的儲(chǔ)位優(yōu)化算法，并對(duì)4 種算法原理進(jìn)行對(duì)比。

1） 基于貪心思想的儲(chǔ)位優(yōu)化算法的主要原理是：設(shè)置一定的儲(chǔ)位優(yōu)化步驟，通過(guò)在每次優(yōu)化時(shí)，不斷嘗試換層、儲(chǔ)具出/入庫(kù)、循環(huán)等操作，實(shí)現(xiàn)同類型儲(chǔ)具的聚合，當(dāng)達(dá)到儲(chǔ)位優(yōu)化效果或達(dá)到循環(huán)次數(shù)時(shí)輸出。

2） 基于魔方還原算法的儲(chǔ)位優(yōu)化算法的主要思想是：首先，設(shè)置一定的儲(chǔ)位優(yōu)化步驟數(shù)，通過(guò)不斷的換層、循環(huán)操作，實(shí)現(xiàn)某一類儲(chǔ)具達(dá)到一定數(shù)量的聚合；隨后，設(shè)置庫(kù)內(nèi)暫存區(qū)，同樣設(shè)置一定的儲(chǔ)位優(yōu)化步驟數(shù)，在庫(kù)內(nèi)現(xiàn)有庫(kù)存基礎(chǔ)上，嘗試進(jìn)行儲(chǔ)具出入暫存區(qū)、循環(huán)等操作，實(shí)現(xiàn)庫(kù)內(nèi)同類儲(chǔ)具的聚合。

3） 基于傳統(tǒng)MCTS 的儲(chǔ)位優(yōu)化算法與本文改進(jìn)的SA-MCTS 算法的區(qū)別在于，SA-MCTS 算法主要包括選擇、擴(kuò)展、模擬、更新4 個(gè)算法模塊，傳統(tǒng)MCTS 的儲(chǔ)位優(yōu)化算法對(duì)最優(yōu)子節(jié)點(diǎn)不夠隨機(jī)化，該區(qū)別導(dǎo)致傳統(tǒng)的MCTS 算法可能無(wú)法跳出局部極大值的限制。

基于傳統(tǒng)MCTS 算法的儲(chǔ)位優(yōu)化參數(shù)設(shè)置為每次學(xué)習(xí)1 000 次，共進(jìn)行50 輪循環(huán)。采用算法模擬器隨機(jī)生成100 組隨機(jī)庫(kù)存樣本，儲(chǔ)位優(yōu)化步驟結(jié)果取均值，得到采用4 種算法進(jìn)行儲(chǔ)位優(yōu)化所需運(yùn)行步數(shù)的對(duì)比結(jié)果（表2）。

表2 各算法儲(chǔ)位優(yōu)化運(yùn)行步數(shù)對(duì)比結(jié)果Table 2 Comparison on the slotting optimization steps of four algorithms

根據(jù)表2 各算法的儲(chǔ)位優(yōu)化對(duì)比結(jié)果，基于貪心算法的儲(chǔ)位優(yōu)化算法在儲(chǔ)具規(guī)模較大時(shí)，收斂速度較慢，基于魔方還原的儲(chǔ)位優(yōu)化算法優(yōu)于基于貪心算法和傳統(tǒng)MCTS 算法，由于其通過(guò)快速換行操作在“種子行”的形成過(guò)程中，儲(chǔ)具已經(jīng)達(dá)到部分聚合，形成“種子行”后，儲(chǔ)具通過(guò)較少移動(dòng)便達(dá)到優(yōu)化效果。SA-MCTS 算法在儲(chǔ)具較少時(shí)優(yōu)勢(shì)并不明顯，當(dāng)儲(chǔ)具規(guī)模較大后，訓(xùn)練情況更多，能夠更好地選擇下一個(gè)優(yōu)化步驟，取得了較好的優(yōu)化效果。

隨后，對(duì)盤庫(kù)結(jié)果作進(jìn)一步分析，計(jì)算優(yōu)化后的庫(kù)存均值和庫(kù)存方差，這兩項(xiàng)數(shù)據(jù)均為3 層庫(kù)存數(shù)據(jù)的平均值。庫(kù)存均值計(jì)算方法為以當(dāng)前儲(chǔ)具為1，后續(xù)相同類型則繼續(xù)累加，不同則繼續(xù)為1，累加后除以儲(chǔ)具數(shù)目。通過(guò)庫(kù)存均值和庫(kù)存方差，能夠反映儲(chǔ)位優(yōu)化后庫(kù)存的整齊程度，其中，庫(kù)存越整齊，同行同類儲(chǔ)具越多均值越大；同行插花少，同類儲(chǔ)具多，則方差越小。各算法盤庫(kù)效果對(duì)比如表3 所示。

表3 各算法盤庫(kù)效果對(duì)比Table 3 Comparison on the storage optimization results of four algorithms

最后，對(duì)比上述4 種算法的時(shí)間復(fù)雜度、解出比例、平均計(jì)算時(shí)間、計(jì)算結(jié)果的儲(chǔ)位優(yōu)化耗時(shí)（以3*9 庫(kù)存為例）等參數(shù)，結(jié)果如表4 所示。時(shí)間復(fù)雜度方面，受內(nèi)部循環(huán)影響，基于MCTS算法的時(shí)間復(fù)雜度更高。解出比例方面，傳統(tǒng)MCTS 算法容易陷入局部最小，某些情況下無(wú)法給出對(duì)應(yīng)解。平均計(jì)算時(shí)間方面，SA-MCTS 算法復(fù)雜度高，模擬次數(shù)較多，因此平均計(jì)算時(shí)間較長(zhǎng)。儲(chǔ)位優(yōu)化時(shí)間方面，貪心算法未使用暫存區(qū)，且主要通過(guò)雙層循環(huán)進(jìn)行同類型儲(chǔ)具聚合，在儲(chǔ)位優(yōu)化時(shí)，每一次雙層循環(huán)需要使兩層儲(chǔ)具按照一定方向全部運(yùn)行一個(gè)儲(chǔ)位，是儲(chǔ)位優(yōu)化中最耗時(shí)的動(dòng)作，因此基于貪心算法的優(yōu)化耗時(shí)最高；而基于SA-MCTS 算法得到的優(yōu)化步數(shù)較其他算法更優(yōu)，整體儲(chǔ)位優(yōu)化耗時(shí)更少，比傳統(tǒng)的基于魔方還原算法的儲(chǔ)位優(yōu)化耗時(shí)優(yōu)化了30%。

表4 各算法儲(chǔ)位優(yōu)化效果對(duì)比Table 4 Comparison on the slotting optimization results of four algorithms

4 結(jié) 語(yǔ)

針對(duì)某型船自動(dòng)化倉(cāng)庫(kù)儲(chǔ)位優(yōu)化問(wèn)題，本文設(shè)計(jì)了一種基于SA-MCTS 的儲(chǔ)位優(yōu)化算法，從問(wèn)題的描述、數(shù)學(xué)模型的建立、算法的選擇及優(yōu)化、算法參數(shù)的設(shè)置等多角度對(duì)儲(chǔ)位優(yōu)化算法進(jìn)行了設(shè)計(jì)，并與基于貪心算法、基于魔方還原算法、基于傳統(tǒng)MCTS 算法的儲(chǔ)位優(yōu)化算法進(jìn)行了仿真對(duì)比實(shí)驗(yàn)。結(jié)果表明，本文改進(jìn)的SA-MCTS算法在儲(chǔ)位優(yōu)化時(shí)間上優(yōu)于其他方法，能夠推廣應(yīng)用于自動(dòng)化倉(cāng)庫(kù)儲(chǔ)位優(yōu)化步驟求解。

由于自動(dòng)化倉(cāng)庫(kù)庫(kù)存狀態(tài)較多，僅采用強(qiáng)化學(xué)習(xí)應(yīng)對(duì)大規(guī)模倉(cāng)庫(kù)儲(chǔ)位優(yōu)化難度較大，后續(xù)可考慮引入深度學(xué)習(xí)。通過(guò)大規(guī)模數(shù)據(jù)訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)，增加對(duì)庫(kù)存狀態(tài)的識(shí)別，隨后結(jié)合強(qiáng)化學(xué)習(xí)，進(jìn)一步優(yōu)化盤庫(kù)動(dòng)作，實(shí)現(xiàn)對(duì)大規(guī)模倉(cāng)庫(kù)儲(chǔ)位的快速優(yōu)化求解。