某型自動化立體倉庫儲位優化算法研究

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

鄭州機電工程研究所，河南 鄭州 450015

0 引 言

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

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

該型立體倉庫系統初始為有序狀態，在日常運行過程中，調度員按需隨機地對儲具進行出入庫操作。因此，在使用一段時間后會造成自動化立體倉庫儲具類型擺放混亂的問題。為保證物資出庫效率，同時解決由此引發的立體倉庫載荷不均衡等問題，必須在盡可能短的時間內進行立體倉庫庫位優化操作。

考慮到本系統對儲位優化時間的要求，為解決以上問題，本文將使用蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）的儲位優化算法求解，并在局部參考模擬退火思想，增加算法局部搜索隨機性。該方法通過可以提前預測輸入優化步驟在模擬運行的輸出值，然后通過蒙特卡洛樹搜索算法在等效無滯后的情況下學習控制策略，消除滯后的影響，加快響應速度和收斂速度。

1 問題描述及建模

1.1 問題描述

以某型號船用自動化無人倉庫為研究對象，其初始狀態如圖1 所示。該倉庫有3 個橫向作業巷道和2 個垂直巷道，出口在倉庫左側，貨物統一由倉庫左側出庫，在平衡狀態下，貨物應基于左側進行類別分配，其布局關于橫向巷道作業巷道對稱，即對稱作業巷道的儲位布局完全一致，該倉庫為同端出/入布局，即入庫口與出庫口在巷道的同一側，貨架沿通道排列，平移裝置按指令沿通道運行，進行貨架上貨物的揀選作業。

圖1 某型自動化立體倉庫初始狀態Fig. 1 Initial state of an automated 3D warehouse

庫存盤點過程中，算法根據當前庫存狀態選擇儲具運行動作，儲具運行的目的就是將分布于立體倉庫各層的同類型儲具進行合并。儲位優化過程中，可以通過檢查庫存狀態設置一個暫存區，該暫存區用于存放需要順序調整的儲具，通過不停進行儲具周轉動作，實現庫存的平衡有序。其中，自動化立體倉庫按照指令周期模式進行運作，通過平移裝置、儲具升降裝置的配合完成各指令操作。

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

圖2 自動化立體倉庫儲位移動示意圖Fig. 2 Schematic diagram of automatic 3D warehouse slotting position movement

表1 自動化立體倉庫動作集合Table 1 The action set of automated 3D warehouse

本文主要研究多平移裝置在多儲具混亂的情況下，設計合理的儲具運行步驟，從庫存平衡狀態、作業時間等各方面考慮，以最小化指令周期內存取貨物的時間距離為目標進行集成優化。

1.2 模型建立

對于自動化立體倉庫儲位優化問題，首先要達到的目標是同類儲具集合存放，且對于三行儲具、三類儲具的問題，每一行對應各類儲具，以保證出庫效率；此外，應考慮儲位優化耗時最短，儲位優化的總時間與采取的儲具移動措施、移動次數和路徑長度有關，在速度恒定的情況下，移動次數越少，路徑長度越短，儲具儲位優化耗時越短。因此，需要以庫存的離散度之和最小及儲具儲位優化時間最短為目標，建立自動儲具儲位優化數學模型。

計算儲具類內離散度，定義第t次儲位優化時第Ki類儲具的坐標均值為

第t次儲位優化時第Ki類型儲具的第j個儲具到均值坐標的距離可表示為

式中：dt為 第t次儲位優化時所有KI類儲具類內離散距離之和；(x)為 第t次貨物優化時第Ki類儲具行數的坐標均值；(y)為第t次貨物優化時第Ki類儲具列數的坐標均值。隨后，計算類間離散度。全部KI類儲具的均值坐標為Mt[x,y]，則

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

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

則得到第1 個目標函數庫存最小離散度之和minF1為

儲位優化是對儲位重新調整的過程，儲具的重新擺放涉及到儲具的搬運。本文主要研究平移裝置、左右兩側升降裝置運行次數及累加的時間。為節約時間和成本，需要使搬運時間最短。自動化立體倉庫移動過程中，平移裝置移動時間要快于左右兩側升降裝置移動時間。

儲位優化單步移動時間分為2 種情況：

1） 循環、集合操作。2 種操作均為儲具集合的移動，各儲具移動均包括平移裝置移動和升降裝置移動，平移裝置與升降裝置并行移動。

2） 出/入暫存區、單個儲具換層操作。2 種操作均為單個儲具的移動，各儲具移動均包括平移裝置移動和升降裝置移動，平移裝置與升降裝置串行移動。

因此儲具移動總時間分為2種情況。設[xKi j(t-1),[yKij(t-1)]為]第Ki類型儲具的第j個儲具的當前坐標，xKijt,yKijt為儲具移動后的坐標。

1） 循環、集合操作時，儲位優化花費時間為

2） 出/入暫存區、單個儲具換層操作，儲位優化花費時間為

因此，得到第2 個目標函數最短儲具儲位優化時間 minF2為

式中，Z為儲位優化總步數。

最后，由式(7)和式(8)得到儲位優化數學模型為

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

模型中2 個目標函數F1和F2的量綱不一致，需要進行歸一化處理。其中F1為 無量綱量，F2的單位為s，所以只需對F2進行歸一化處理：

式中： maxF2為系統允許儲位優化的最長時間；ε為歸一化參數，設置 ε的意義是為了防止在計算過程中出現數值溢出情況，本文取值ε= 0.001。

為了防止多目標模型在求解時相互影響，需要給目標函數添加權重系數ω，以此轉化為單目標模型，式( 12) 為變形后的目標函數：

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

2 基于模擬退火的蒙特卡洛樹算法（SA-MCTS）設計

2.1 算法選擇

根據表1 可執行動作信息，自動化立體倉庫執行儲位優化時，每步需考慮28 種可能執行結果，對于3×9 的自動化立體倉庫儲位優化問題，初始空庫實現有序入庫需至少27 步，考慮到儲具類型數量不平均、布局不均衡等因素，自動化立體倉庫儲位優化形成路徑搜索樹至少為 2728，約1.197×1040。因此，自動化立體倉庫儲位優化步驟搜索空間巨大，對儲位優化狀態樹進行搜索直到終局的方法并不可行，不可能對后續所有情況進行完全統計。

儲位分配中選擇自動儲具進行庫存調整的過程可以被視為馬爾科夫決策過程（Markov decision process，MDP）[13]，上述章節建立的庫存狀態和目標函數作為馬爾科夫過程的狀態和過程參數，來指導儲具調度。自動化立體倉庫內儲位優化馬爾科夫決策通過四元組描述為{S，A，P，R}，其中，S為狀態集合，A為動作集合，P為狀態轉移函數，R為效用函數。采用蒙特卡羅樹搜索算法，基于強化學習模型Mv和模擬策略π，對于當前要選擇動作的狀態St，對每一個可能采樣的動作a∈A，都進行K輪采樣，這樣每個動作a都會得到K組經歷完整的狀態序列。即

對于每個 (St,a)組合，可以基于蒙特卡洛法來計算其動作價值函數并選擇最優的動作。

式中，Gt為一個模擬序列的訓練得分。式（14）和式（15）為對k個模擬序列采樣，創建一個由已經訪問過的節點和動作組成的樹，并評估樹內每個狀態動作的價值；構建完成之后，選擇當前狀態St所能執行動作中Q值最大的節點作為后續動作起點。

MCTS 以當前狀態為根節點建立搜索樹，通過向前預估可能發生的各種情況，綜合選擇最好的動作。采用該思想只需求解從當前狀態開始的子MDP 過程，無需求解整個MDP 過程，因此MCTS 能夠處理狀態動作數量較大的馬爾科夫問題。目前，以MCTS 搜索算法為代表的強化學習算法已經在電力系統[14]、圍棋類游戲[15-16]、計算機視覺[17]、軌跡跟蹤預測[18]等方面廣泛應用。

2.2 基于SA-MCTS 強化學習

針對自動化立體倉庫儲位優化問題，提出基于模擬退火的蒙特卡洛樹算法(simulated annealing Monte Carlo Tree search，SA-MCTS)的儲位優化方法。SA-MCTS 算法源于MCTS，其求解庫存盤點問題的總體思路是將庫存盤點過程看作一個模擬隨機落子過程，其中，以每次儲位優化動作作為一次模擬過程，以當前狀態得分作為儲位優化效果。然后依據數學模型中的約束關系制定規則，以收益最大化為優化目標，整個搜索過程包括選擇、擴展、模擬和更新4個階段[19]。本文通過對MCTS 的選擇、模擬、更新步驟進行改進，最終實現自動化立體倉庫庫存優化目標。

2.2.1 選 擇

MCTS 通過樹策略選擇下一個節點進行擴展，從根節點開始，遞歸地選擇得分最高的子節點或終端狀態（游戲勝負或循環時間到）。在MCTS 中遍歷樹的分數稱為樹策略，在傳統的MCTS 方法中，由上限界限信心（upper confidence bound，UCB）方程給出：

式中：VUCB為 節點的UCB 得分；vi為節點v的第i個子節點；Q為獲取節點累計價值的函數；Q(vi)為在v節點處采用i動作獲得的總得分；N(vi)為獲取節點累計訪問次數的函數；Q(vi)/N(vi)為強調對歷史動作的利用；N(v)為總模擬次數；c為用于調整加號前后兩部分在整體中的比重系數，c越大越偏向于廣度搜索，c越小越偏向于深度搜索。

單純使用MCTS 算法，容易陷入局部最大值，即使在非最優狀態，仍然無法跳出局部最優[19-20]。本文通過使用Metropolis 準則，使當前步驟以一定概率接收離散度較差的情況。

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

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

2.2.2 擴 展

如果搜索至葉節點SL且該節點遍歷次數大于等于P（P為節點擴展臨界值）時，應用選擇策略后執行分支節點擴展。根據動作a得到狀態SCL。此時將狀態SCL擴展為樹中葉節點且節點初始信息為{N(SL,a)=0，Q(SL,a)=0，N(SCL)=0}。如果下一個要到達的狀態為變差狀態或相同狀態，則進行剪枝操作，并且直接結束本次尋優控制，否則轉到模擬階段。

2.2.3 模 擬

根據表1 中自動化立體倉庫可執行動作列表，隨機選擇某一動作作為模擬策略，模擬過程中需判斷，如果模擬結果已經達到庫存平衡標準，則停止模擬。結束后，根據式（12）判定勝負，即獲得的收益值Vreward，并將其返回。

2.2.4 更 新

當模擬至定義的終止狀態時（如終止深度），信息更新從模擬的初始葉節點SL回溯至根節點S0。更新各遍歷節點信息：

其中，L(L,0)為葉節點至根節點距離。

通過重復上述MCTS 動作以及不斷地擬合、控制，最終蒙特卡洛搜索樹將收斂，回溯MCTS動作可以獲得儲位優化策略。綜上所述，梳理基于SA-MCTS 算法的儲位優化算法流程，如圖4 所示。

圖4 基于SA-MCTS 的儲位優化算法流程圖Fig. 4 SA-MCTS based slotting optimization algorithm flow chart

2.3 SA-MCTS 參數設置

設置自動化立體倉庫的庫存容量、緩沖區大小、模擬退火參數、蒙特卡洛搜索算法參數、儲具類型以及計算機模擬環境等參數。

2.3.1 自動化立體倉庫參數設置

1） 自動化立體倉庫庫存大小為3 行9 列，即該倉庫高3 層，每層9 個儲位；

2） 自動化立體倉庫中有2 個空儲位作為緩沖區，該緩沖區可以在儲位優化過程中靈活變動，該緩沖區容量設置考慮了儲具出入庫時間，同時兼顧內部儲具；

3） 為使問題簡單化，在儲具運輸過程中不考慮庫存半箱及半箱擺放問題，庫存包含3 類儲具：A 類型儲具、B 類型儲具、空儲具；

4） 平移裝置每移一步時間為9 s；

5） 升降裝置每移動一層時間為13 s，平移、升降裝置時間均根據電機轉速及移動距離計算得到。

2.3.2 SA-MCTS 算法參數設置

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

2） MCTS 最 大 運 行 深 度MAX_DEPTH設 置為70，考慮儲位優化的時效問題，將搜索最大深度設計為70；

3） MCTS 最大運行模擬次數CHOICES設置為27，對應該自動化立體倉庫可運行所有動作集合；

4） MCTS 最大子節點數MAX_CHOICE設置為27，對應該自動化立體倉庫可能存在的最多子節點數量；

5） 模擬退火初始溫度T0=50 000，該參數參考文獻[4]設置；

6） 退火系數Tend= 1×10-8；

7） 模擬退火降溫速度q=0.98，實際應用中該參數設置為0.99 或0.98，本文設置為0.98，主要考慮讓算法充分尋優。

2.3.3 初始狀態和目標狀態

初始狀態下自動化立體倉庫的3 種類型儲具隨機均勻分布。

目標狀態為各行均以3 種類型中的一種儲具為隊列頭部，后續為同類儲具，同類儲具多于一行的情況下，可以順序存入其他行。

2.3.4 獎勵函數

本文根據自動化立體倉庫儲具運動， minF1和minF2分別為之前和本次目標函數運算結果，可能存在的收益包括：收益增加、收益不變、收益減少，因此Vreward設計為

2.3.5 計算環境

計算機硬件環境為龍芯3A4000 處理器，內存8 GB；軟件環境為中標麒麟桌面版本V5 64 位操作系統。

3 仿真結果及分析

依據上述參數，應用SA-MCTS 算法對自動化立體倉庫儲位進行優化排列。本文采用隨機生成的3 000 組庫存數據進行優化算法驗證，庫存由盤庫算法模擬器隨機生成，軟件界面如圖5 所示。圖6 所示為儲位優化的某一中間狀態，其中第2 行儲位缺少2 個位置,是由于已有2 個儲具A，B 出庫（出庫儲具見圖6 左下角），騰出暫存區導致。圖7 所示為儲位優化完成后的庫存狀態。

圖5 儲位優化算法模擬器界面Fig. 5 Slotting optimization algorithm simulator interface

圖6 儲位優化運行中間結果展示Fig. 6 Display of slotting optimization intermediate result

圖7 儲位優化結果展示Fig. 7 Display of slotting optimization result

圖8 所示為蒙特卡洛搜索樹深度與收益值的比較結果，其中每條線為一次訓練過程。由圖可見，在前期搜索中，隨著節點經驗信息依次累加，庫存離散程度迅速降低；在后期搜索中，隨著狀態空間不斷縮小，樹節點越深其收益數值變化越趨平緩，且數據波動越趨收窄。因而說明在儲位優化中應用SA-MCTS 能夠快速準確地選擇最優儲位動作決策。

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

在SA-MCTS 算法真正有效地進行儲位優化之前的所有迭代，都稱為訓練學習迭代。本文設置訓練學習時間為1 000 次“選擇-擴展-模擬-反向更新”尋優過程。最后得到從SA-MCTS 控制到儲位優化的最佳時間變化曲線，如圖9 所示。

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

由圖8 和圖9 可知，隨著不斷嘗試儲具動作、學習迭代，采用SA-MCTS 算法得到的儲位優化時間越來越短，可確定較好的儲位優化策略。

為了驗證SA-MCTS 算法的儲位優化能力，本文設計了基于貪心算法、基于魔方還原算法和傳統MCTS 的儲位優化算法，并對4 種算法原理進行對比。

1） 基于貪心思想的儲位優化算法的主要原理是：設置一定的儲位優化步驟，通過在每次優化時，不斷嘗試換層、儲具出/入庫、循環等操作，實現同類型儲具的聚合，當達到儲位優化效果或達到循環次數時輸出。

2） 基于魔方還原算法的儲位優化算法的主要思想是：首先，設置一定的儲位優化步驟數，通過不斷的換層、循環操作，實現某一類儲具達到一定數量的聚合；隨后，設置庫內暫存區，同樣設置一定的儲位優化步驟數，在庫內現有庫存基礎上，嘗試進行儲具出入暫存區、循環等操作，實現庫內同類儲具的聚合。

3） 基于傳統MCTS 的儲位優化算法與本文改進的SA-MCTS 算法的區別在于，SA-MCTS 算法主要包括選擇、擴展、模擬、更新4 個算法模塊，傳統MCTS 的儲位優化算法對最優子節點不夠隨機化，該區別導致傳統的MCTS 算法可能無法跳出局部極大值的限制。

基于傳統MCTS 算法的儲位優化參數設置為每次學習1 000 次，共進行50 輪循環。采用算法模擬器隨機生成100 組隨機庫存樣本，儲位優化步驟結果取均值，得到采用4 種算法進行儲位優化所需運行步數的對比結果（表2）。

表2 各算法儲位優化運行步數對比結果Table 2 Comparison on the slotting optimization steps of four algorithms

根據表2 各算法的儲位優化對比結果，基于貪心算法的儲位優化算法在儲具規模較大時，收斂速度較慢，基于魔方還原的儲位優化算法優于基于貪心算法和傳統MCTS 算法，由于其通過快速換行操作在“種子行”的形成過程中，儲具已經達到部分聚合，形成“種子行”后，儲具通過較少移動便達到優化效果。SA-MCTS 算法在儲具較少時優勢并不明顯，當儲具規模較大后，訓練情況更多，能夠更好地選擇下一個優化步驟，取得了較好的優化效果。

隨后，對盤庫結果作進一步分析，計算優化后的庫存均值和庫存方差，這兩項數據均為3 層庫存數據的平均值。庫存均值計算方法為以當前儲具為1，后續相同類型則繼續累加，不同則繼續為1，累加后除以儲具數目。通過庫存均值和庫存方差，能夠反映儲位優化后庫存的整齊程度，其中，庫存越整齊，同行同類儲具越多均值越大；同行插花少，同類儲具多，則方差越小。各算法盤庫效果對比如表3 所示。

表3 各算法盤庫效果對比Table 3 Comparison on the storage optimization results of four algorithms

最后，對比上述4 種算法的時間復雜度、解出比例、平均計算時間、計算結果的儲位優化耗時（以3*9 庫存為例）等參數，結果如表4 所示。時間復雜度方面，受內部循環影響，基于MCTS算法的時間復雜度更高。解出比例方面，傳統MCTS 算法容易陷入局部最小，某些情況下無法給出對應解。平均計算時間方面，SA-MCTS 算法復雜度高，模擬次數較多，因此平均計算時間較長。儲位優化時間方面，貪心算法未使用暫存區，且主要通過雙層循環進行同類型儲具聚合，在儲位優化時，每一次雙層循環需要使兩層儲具按照一定方向全部運行一個儲位，是儲位優化中最耗時的動作，因此基于貪心算法的優化耗時最高；而基于SA-MCTS 算法得到的優化步數較其他算法更優，整體儲位優化耗時更少，比傳統的基于魔方還原算法的儲位優化耗時優化了30%。

表4 各算法儲位優化效果對比Table 4 Comparison on the slotting optimization results of four algorithms

4 結 語

針對某型船自動化倉庫儲位優化問題，本文設計了一種基于SA-MCTS 的儲位優化算法，從問題的描述、數學模型的建立、算法的選擇及優化、算法參數的設置等多角度對儲位優化算法進行了設計，并與基于貪心算法、基于魔方還原算法、基于傳統MCTS 算法的儲位優化算法進行了仿真對比實驗。結果表明，本文改進的SA-MCTS算法在儲位優化時間上優于其他方法，能夠推廣應用于自動化倉庫儲位優化步驟求解。

由于自動化倉庫庫存狀態較多，僅采用強化學習應對大規模倉庫儲位優化難度較大，后續可考慮引入深度學習。通過大規模數據訓練深度神經網絡，增加對庫存狀態的識別，隨后結合強化學習，進一步優化盤庫動作，實現對大規模倉庫儲位的快速優化求解。