饒東寧，羅南岳

（廣東工業(yè)大學 計算機學院，廣州 510006）

0 概述

隨著電子商務等行業(yè)的快速發(fā)展，物流訂單井噴、土地成本快速上升，物流企業(yè)著手對倉儲系統(tǒng)進行智能化管理。亞馬遜研究開發(fā)了Kiva Systems 倉庫機器人系統(tǒng)［1］，使用數(shù)百個自動導航車代替了工作人員完成貨物訂單的存取任務，極大地提高了貨物存取操作的效率。國內(nèi)企業(yè)如京東、?？档认群髮崿F(xiàn)了類Kiva 智能倉儲系統(tǒng)并推廣至國內(nèi)市場［2］。

針對倉儲中調(diào)度問題的建模與優(yōu)化，很多學者進行了深入的研究。文獻［3］針對倉庫中的隨機存儲情況和不同類型的堆垛機，為每個存儲或檢索的位置選擇了足夠熟練的堆垛機，從而使得總使用時間最小化。于赫年等［4］通過分析多智能體調(diào)度系統(tǒng)的任務分配模式、作業(yè)流程及任務調(diào)度的約束條件，建立了以最小化任務完成時間為主要目標的數(shù)學模型。然而上述兩種方法主要以時間作為優(yōu)化目標，沒有考慮到提高累計回報值。魯建廈等［5］通過分析穿梭車倉儲系統(tǒng)中的提升機與穿梭車的實際作業(yè)流程，建立了復合作業(yè)路徑規(guī)劃模型并通過人工魚群算法求解，有效地提高了該倉儲系統(tǒng)的運行效率。

盡管以上方法針對倉儲中相關調(diào)度問題提出了解決方案，但庫位問題方面依然存在不足。傳統(tǒng)的庫位分配通?；谌藶榻?jīng)驗，未充分考慮庫位的使用狀態(tài)和整體空間分布等，導致倉庫管理效率下降。合理的庫位安排，可以提高堆垛機的效率和可靠性，因此需要解決面向倉儲的多任務問題。

堆垛機調(diào)度動作是基于時間步的動作序列，而強化學習常用于解決序列決策問題。為了實現(xiàn)對更大狀態(tài)空間的問題實例進行更有效的求解，研究人員將深度學習的思想融入強化學習的算法中，并應用于該類調(diào)度問題中。

本文通過對堆垛機調(diào)度問題進行建模，構建倉儲環(huán)境，并針對堆垛機調(diào)度問題，提出一種基于近端策略優(yōu)化（Proximal Policy Optimization，PPO）［6］強化學習的調(diào)度方法。將調(diào)度問題視為序列決策問題，使智能體與環(huán)境進行持續(xù)交互，根據(jù)環(huán)境反饋不斷優(yōu)化動作的抉擇，從而改善實驗效果。針對調(diào)度中伴生的庫位優(yōu)化問題，提出一種基于多任務學習的調(diào)度、庫位推薦聯(lián)合算法，通過構建處理庫位推薦的Actor 網(wǎng)絡［7］，使該網(wǎng)絡與Critic 網(wǎng)絡進行交互反饋，促進整體的聯(lián)動和訓練，以實現(xiàn)該算法在調(diào)度和庫位問題場景下的應用。

1 研究背景

1.1 概率規(guī)劃

概率規(guī)劃［8］是人工智能的研究方向之一，描述的是馬爾可夫決策問題，其主要特點是概率性和并行性，目標是最大化累計回報值。概率規(guī)劃被應用于各類現(xiàn)實場景中。文獻［9］基于概率規(guī)劃的方法對股指模擬問題進行領域建模，并使用規(guī)劃器求解問題。其中在國際概率規(guī)劃比賽中表現(xiàn)最好的規(guī)劃器為SOGBOFA［10］。

1.2 強化學習

隨著人工智能的發(fā)展，研究人員提出了DQN（Deep Q-Networks）［11］、TRPO（Trust Region Policy Optimization）［12］等深度強化學習算法，并在移動機器人［13］、路徑規(guī)劃［14］、調(diào)度問題等應用場景中取得了較好的成果。例如，針對旅行商問題和有容量限制的車輛路徑問題，文獻［15］在關于路徑問題的改進啟發(fā)式算法上，構建一個基于自注意力機制的深度強化學習架構，該架構泛化性表現(xiàn)良好。文獻［16］利用深度強化學習技術對適用于作業(yè)車間調(diào)度問題的優(yōu)先調(diào)度規(guī)則進行自動學習，析取作業(yè)車間調(diào)度問題的圖表示，根據(jù)該圖表示提出了一種基于圖神經(jīng)網(wǎng)絡的模式，并將其嵌入到狀態(tài)空間。

強化學習的基本思想是使智能體在與環(huán)境交互過程中獲得最大的累計回報值，從而不斷優(yōu)化自身動作的決策［17］。其理論基于馬爾可夫決策過程，算法構成主要包括智能體、環(huán)境、狀態(tài)、動作以及獎勵等。智能體若處于狀態(tài)st，根據(jù)策略函數(shù)得到動作at并施加于環(huán)境之上，獲得返回獎勵rt+1，期望回報Gt表示在γ折扣下估計的累計獎勵。期望公式如下：

引入狀態(tài)價值函數(shù)V（s）對Gt進行估計：

同時為了評價某一個狀態(tài)或者動作的好壞，引入動作價值函數(shù)Q（s，a）：

而針對動作a為離散的現(xiàn)象，可以將其松弛化為動作空間上的連續(xù)分布的采樣。例如，用Softmax 將網(wǎng)絡輸出規(guī)范化為動作的概率分布，然后在此基礎上采樣動作并執(zhí)行獲得反饋。

1.3 近端策略優(yōu)化

在可擴展性和魯棒性等方面上，Q-Learning 在許多簡單的連續(xù)問題上表現(xiàn)較差［18］，而TRPO 相對復雜，并且與包含噪聲或者參數(shù)共享的架構不兼容。因此，研究人員在策略梯度算法的基礎上結合TRPO的優(yōu)勢，提出一種PPO 算法。

不同于基于Q值的強化學習算法，PPO 算法［6］將模型參數(shù)定義在策略函數(shù)［19］中：

式（4）表示在t時刻狀態(tài)為s，參數(shù)向量為θ時，模型選擇動作a的概率。通過更新參數(shù)向量θt，可得到更優(yōu)的策略函數(shù)，從而使得回報函數(shù)最大化。

但在訓練過程中，不合適的學習率可能會導致較差的模型表現(xiàn)。為解決此問題，PPO 使用GAE 函數(shù)［20］對優(yōu)勢函數(shù)進行了多步估計，并利用衰減因子進行組合，將偏差控制到一定的范圍內(nèi)。k步優(yōu)勢估計公式和廣義優(yōu)勢函數(shù)估計GAE（γ，λ）為：

同時，為了使該方法具有更高的數(shù)據(jù)效率性和魯棒性，PPO 提出了包含裁剪概率比率的策略網(wǎng)絡目標函數(shù)，該函數(shù)確保了策略性能的悲觀估計（即下限）。令rt（θ）表示新舊策略概率比，即：

結合上述GAE 優(yōu)勢函數(shù)，PPO 提出的主要目標函數(shù)如下：

其中：clip（rt（θ），1-ε，1+ε）是裁剪函數(shù)，對新舊策略更新過大的情況進行裁剪，使得rt（θ）穩(wěn)定在［1-ε，1+ε］區(qū)間。

1.4 多任務學習

傳統(tǒng)的機器學習方法基于單任務學習的模式進行學習，處理復雜任務時會將其分解為多個獨立的單任務，這種做法具有可行性，但忽略了任務之間的信息聯(lián)系。通過任務之間的共享表示和信息聯(lián)系，能夠使模型更好地概括原始任務，這種方式稱為多任務學習［21］，其被應用于自然語言處理［22］、語音識別［23］、計算機視覺［24］和強化學習等各種領域。例如，針對三維裝箱問題中較少的信息量和較大的動作空間的情況，YUAN等［25］將原始任務劃分為序列、方向和位置3 個有信息聯(lián)系的子任務，并基于深度強化學習的方法順序處理3 個子任務，該算法采用了多模態(tài)編碼器-解碼器的架構。

本文通過深度強化學習的方法同時對堆垛機調(diào)度和庫位推薦問題進行聯(lián)合求解，其聯(lián)合目標是在多問題環(huán)境中獲得最大化累計回報值。

2 倉儲問題

本文考慮了倉庫貨物存取的調(diào)度問題。三維倉儲模型如圖1 所示，整個倉庫對象體系包含堆垛機（即小車）、通道、內(nèi)外層庫位、入庫點和出庫點。堆垛機在通道中移動并根據(jù)訂單需求進行存貨和取貨，同時在入庫點（出庫點）進行入庫（出庫）。因此，堆垛機有關貨物的動作分為2 類：1）裝貨，即將貨物裝入堆垛機中，包括上述的入庫操作和取貨操作；2）卸貨，即從堆垛機中卸下貨物，包括出庫操作和存貨操作。入庫是指堆垛機從入庫點載入貨物，出庫是指堆垛機在出庫點卸下貨物，存儲貨物是指將貨物存儲進庫位中，取出貨物是指從庫位中拿出貨物并置于車上。

圖1 三維倉儲模型示意圖Fig.1 Schematic diagram of 3D warehouse model

堆垛機調(diào)度問題的目標是以盡可能小的堆垛機運行代價滿足盡可能多的訂單存取需求，公式化為：

其中：、、、分別表示堆垛機每次運行的移動代價、執(zhí)行代價、時間代價和成功裝卸貨物得到的收益。

移動代價是指堆垛機在倉儲環(huán)境中移動的開銷，即：

其中：nnums表示執(zhí)行了該動作的堆垛機數(shù)量。

執(zhí)行代價是指當堆垛機執(zhí)行了裝貨和卸貨操作時的開銷，即：

其中：nnum是存取操作下的貨物數(shù)量。

時間代價是指堆垛機沒有執(zhí)行操作時的空耗的開銷，即：

堆垛機完成裝貨、卸貨時都會獲得相應的收益：

本節(jié)包含的常量及其釋義如表1 所示。

表1 部分相關常量的對應含義 Table 1 Corresponding meanings of some of the related constants

3 模型構建

針對以上問題，本文對環(huán)境中的狀態(tài)空間、動作空間和獎懲規(guī)則這三大要素進行了定義。

3.1 狀態(tài)空間

狀態(tài)空間是調(diào)度過程中所有狀態(tài)的集合，狀態(tài)特征是對狀態(tài)屬性的數(shù)值表示?？梢詫顟B(tài)特征表示為一個三維矩陣的形式；第一維和第二維記錄了倉庫的平面信息，包括該平面層倉儲庫位的使用情況、出入庫點位置和貨物信息、堆垛機位置及承載情況；第三維主要記錄了垂直方向的層信息。觀測的信息包括：

與倉庫相關的觀測信息如下：

與堆垛機相關的觀測信息如下：

最終智能體觀察到的狀態(tài)信息為：

3.2 動作空間

在堆垛機調(diào)度任務中，智能體可采取的動作為調(diào)度動作。在堆垛機調(diào)度和庫位優(yōu)化的聯(lián)合任務中，智能體可采取的動作分為調(diào)度動作和庫位動作兩類。

3.2.1 調(diào)度動作空間

在堆垛機調(diào)度問題中，智能體執(zhí)行的動作與堆垛機移動和貨物存取操作相關聯(lián)，共有以下5 類動作：

1）Idle：堆垛機在原地待命。

2）Forward：在通道中前進，方向為從入庫點到出庫點；若在通道中最靠近出庫點的位置，則移動至出庫點。

3）Backward：在通道中后退，方向為從出庫點到入庫點；若在通道中最靠近入庫點的位置，則移動至入庫點。

4）Load：在入庫點的位置，將貨物裝入堆垛機中；若在通道中，則找到距離最近的待取貨庫位，從中取出貨物。

5）Unload：在出庫點的位置，堆垛機卸下貨物；若在通道中，則找到距離最近的空余庫位，并往庫位中儲存貨物（就近原則只應用在調(diào)度環(huán)境中）。

調(diào)度動作以向量a=(ac1，ac2，…，aci，…，acN)形 式表示，aci是對應堆垛機ci的動作值，ci∈C。

3.2.2 庫位動作空間

在調(diào)度和庫位優(yōu)化的雙重問題中，調(diào)度動作Unload 進行存儲貨物的操作時，存儲位置的選擇由庫位推薦網(wǎng)絡來處理。庫位優(yōu)化的動作信息由向量(bc1，bc2，…，bci，…，bcN)表示，bci是對應堆垛機ci的庫位動作值，bci∈{IL，AL，AR，IR}，如圖2 所示的IL、AL、AR 和IR，其物理意義如下：

圖2 平面?zhèn)}儲模型示意圖Fig.2 Schematic diagram of plane storage model

1）IL（Inner-Left）：當前堆垛機的左側(cè)貨架中遠離通道的庫位。

2）AL（Aisle-Left）：當前堆垛機的左側(cè)貨架中靠近通道的庫位。

3）AR（Aisle-Right）：當前堆垛機的右側(cè)貨架中靠近通道的庫位。

4）IR（Inner-Right）：當前堆垛機的右側(cè)貨架中遠離通道的庫位。

3.3 獎懲規(guī)則

在智能體與環(huán)境交互的過程中，獎勵函數(shù)決定了環(huán)境對智能體的行為給出的反饋，該反饋用以指導智能體學習。令Action=｛Idle，F(xiàn)orward，Backward，Load，Unload｝表示動作選項集合。基于式（9）的任務目標，對于智能體的動作a，本文定義其對應的反饋如下：

其中：cmovement為N輛堆垛機移動代價的總和；caction是執(zhí)行代價的總和；ctime是時間代價的總和。計算公式分別如下：

其中：l表示貨架層數(shù)，當l為0時，對應的是入庫（出庫）代價。

g是裝貨、卸貨收益的總和：

其中：nnum指的是成功處理的貨物數(shù)量。

4 網(wǎng)絡模型設計

4.1 整體結構

繼承于Actor-Critic（AC）架構，基于PPO 強化學習算法的堆垛機調(diào)度網(wǎng)絡分為調(diào)度Actor 網(wǎng)絡和Critic 網(wǎng)絡，如圖3 所示，下文簡稱為調(diào)度網(wǎng)絡。

圖3 網(wǎng)絡模型整體架構Fig.3 Overall architecture of network model

在多任務的情況下，除堆垛機調(diào)度外，還包括庫位推薦。所以，在原有的AC 框架下，本文引入了額外的庫位Actor 網(wǎng)絡用于庫位推薦，整體對應的是基于多任務強化學習的調(diào)度、庫位推薦聯(lián)合算法的網(wǎng)絡模型，簡寫為多任務網(wǎng)絡。

4.2 堆垛機調(diào)度網(wǎng)絡

4.2.1 網(wǎng)絡架構設計

根據(jù)目標函數(shù)式（8），構造一個Actor 網(wǎng)絡來生成調(diào)度行為策略，即圖3 中的調(diào)度Actor 網(wǎng)絡。網(wǎng)絡的輸入為3.1 節(jié)提到的狀態(tài)空間S，網(wǎng)絡的輸出為調(diào)度動作的概率向量。

構造一個Critic 網(wǎng)絡用于表示狀態(tài)值函數(shù)，網(wǎng)絡的輸入為狀態(tài)空間S，網(wǎng)絡的輸出為對應狀態(tài)的狀態(tài)估計值。

4.2.2 Actor 和Critic 網(wǎng)絡設計

在強化學習中，策略網(wǎng)絡和值函數(shù)網(wǎng)絡通常是少量的全連接層或者全卷積層，因為過于復雜的網(wǎng)絡層數(shù)會造成模型難以收斂。例如，PPO 在多個實驗中使用了兩層各64 個單元的全連接層。

倉儲問題環(huán)境具有三維狀態(tài)空間信息的特點，狀態(tài)空間記錄了入庫點信息、貨物信息等。每個庫位狀態(tài)表示具有相似性，所以在類似的庫位狀態(tài)下可以采用類似的策略安排貨物，而卷積可以對相似空間中的明顯數(shù)值特征進行提取。因此，本文在輸入層后加入了卷積層和池化層。

同時為了簡化計算過程、并保證網(wǎng)絡的輸入固定在一定范圍內(nèi)，緩解梯度消失，加速模型收斂，本文引入批標準化［26］處理，用以規(guī)范化網(wǎng)絡的輸入?；诰矸e層和批標準化層的引入，本文調(diào)度網(wǎng)絡模型命名為PPO-CB。如圖3 中的調(diào)度Actor 網(wǎng)絡和Critic 網(wǎng)絡所示。

4.2.3 動作策略函數(shù)

為了使調(diào)度問題中的輸出更具有穩(wěn)定性，本文在PPO 算法的基礎上，用Log-Softmax 函數(shù)重新定義目標函數(shù)中的策略函數(shù)，公式如下：

其中：φ（s，a）表示與狀態(tài)和動作輸入相關的向量；πθ表示參數(shù)向量；N為動作選項的總數(shù)。

基于該動作策略函數(shù)，調(diào)度動作從概率分布中進行采樣。相較于Softmax 方法定義的策略函數(shù)，Log-Softmax 函數(shù)在數(shù)值穩(wěn)定性、優(yōu)化性和懲罰等方面有更好的表現(xiàn)。

與其他深度強化學習算法類似，PPO 算法也采用了緩沖庫（Buffer）的思想。在每輪網(wǎng)絡開始訓練之前，將上一輪訓練后的動作策略與環(huán)境進行交互，從而獲取樣本數(shù)據(jù)，同時計算狀態(tài)估計值和優(yōu)勢值，最終將以上相關數(shù)據(jù)存儲至緩沖庫中，以備訓練需求。另外，在本輪訓練結束后，會清空緩沖庫中所有數(shù)據(jù)。

相比較其他基于緩沖庫的算法，PPO 算法根據(jù)裁剪目標函數(shù)有效地避免了訓練前后策略差異過大的情況，從而提升了采樣效率。

4.2.4 算法流程

基于PPO 的堆垛機調(diào)度算法主要內(nèi)容包括：1）收集智能體在倉儲環(huán)境中的交互數(shù)據(jù)，并存儲至緩沖庫中；2）多次調(diào)用緩沖庫中的數(shù)據(jù)并反向訓練神經(jīng)網(wǎng)絡，以獲得良好的調(diào)度策略。

算法1基于PPO 的堆垛機調(diào)度算法

輸入初始環(huán)境信息S0，訓練迭代次數(shù)K，學習率η，超參數(shù)γ、ε

輸出Actor 網(wǎng)絡參數(shù)θ，Critic 網(wǎng)絡參數(shù)φ

1.初始化Actor 網(wǎng)絡的策略參數(shù)θ0和Critic 網(wǎng)絡的值函數(shù)參數(shù)φ0，初始化數(shù)據(jù)緩沖庫，大小為M。

2.從第k 次回合開始進行迭代（k=0，1，…，K）。

3.初始化累計回報值為0，初始化入庫點貨物數(shù)量、堆垛機初始位置和貨架庫位等信息。

4.在環(huán)境中運行策略，與環(huán)境交互輸出動作，獲得對應的獎勵，計算狀態(tài)估計值和優(yōu)勢估計值，并在緩沖庫中存儲當前狀態(tài)動作序列和相關數(shù)值。根據(jù)以上步驟收集容量為M 的數(shù)據(jù)量。

5.從緩沖庫中讀取樣本數(shù)據(jù)。通過最大化目標函數(shù)來更新策略，并得到參數(shù)θk+1，此處使用隨機梯度上升的方法；通過均方誤差函數(shù)來回歸擬合值函數(shù)，并得到參數(shù)φk+1，此處使用梯度下降的方法。

6.結束當前回合，進入下一個回合。

7.結束。

4.3 多任務學習網(wǎng)絡

4.3.1 網(wǎng)絡架構設計

庫位推薦的網(wǎng)絡同樣是一個策略網(wǎng)絡，因此，構建一個Actor 網(wǎng)絡來生成庫位推薦的策略。網(wǎng)絡的輸入為多任務問題環(huán)境中觀察到的狀態(tài)空間，網(wǎng)絡的輸出為庫位動作的概率向量。在多任務問題下，環(huán)境除了堆垛機調(diào)度之外還包含了庫位相關因素。

在多任務環(huán)境（即包含堆垛機調(diào)度和庫位問題的環(huán)境）中，兩個任務是互相影響的個體，調(diào)度Actor網(wǎng)絡和庫位Actor 網(wǎng)絡與狀態(tài)值函數(shù)的Critic 網(wǎng)絡有著直接的關聯(lián)。

當智能體選擇的調(diào)度動作為Unload（且為存儲貨物）時，庫位Actor 網(wǎng)絡根據(jù)環(huán)境中狀態(tài)信息輸出位置推薦，共同對環(huán)境施加影響，進而得到reward 反饋；Critic 網(wǎng)絡根據(jù)reward 值進行狀態(tài)值的估計和優(yōu)勢值的計算。同時，該狀態(tài)估計值和估計優(yōu)勢值會作為相關反饋值，參與到兩個Actor 網(wǎng)絡的目標函數(shù)的參數(shù)訓練，整體過程如圖3 所示。本文多任務網(wǎng)絡模型命名為PPO-CB-store。

4.3.2 算法流程

基于多任務學習的調(diào)度、庫位推薦聯(lián)合算法主要內(nèi)容包括：1）初始化雙Actor 網(wǎng)絡和Critic 網(wǎng)絡參數(shù)，構建多任務網(wǎng)絡架構；2）庫位動作和調(diào)度動作產(chǎn)生聯(lián)動關系，并收集智能體在多任務問題環(huán)境中的交互數(shù)據(jù)，存儲至緩沖庫中；3）多次調(diào)用緩沖庫中數(shù)據(jù)并訓練神經(jīng)網(wǎng)絡，以獲得基于堆垛機調(diào)度和庫位推薦的策略。

算法2基于多任務學習的堆垛機調(diào)度和庫位推薦算法

5 實驗與結果分析

5.1 實驗環(huán)境和網(wǎng)絡參數(shù)設置

本文算法基于Python 語言與Tensorflow2.5 框架實現(xiàn)，并基于OpenAI-Gym 庫對倉儲環(huán)境和堆垛機調(diào)度及庫位問題進行建模。

在本文模型的網(wǎng)絡結構中，Actor 網(wǎng)絡第1 層為輸入層，接著是卷積層、標準化層、池化層，之后是三層全連接層和輸出層。Critic 網(wǎng)絡的后半部分對應的是2 個全連接層，最終輸出的是狀態(tài)估計值，如圖3 所示。參數(shù)設置如表2 所示。

表2 網(wǎng)絡模型的部分參數(shù)設置 Table 2 Some parameter settings of the network model

5.2 問題環(huán)境設置

實驗主要分為調(diào)度問題實驗和多任務問題實驗2 個部分。相對應的環(huán)境實例有調(diào)度環(huán)境和多任務問題環(huán)境2類。環(huán)境中的部分參數(shù)設置如表3所示。

表3 倉儲環(huán)境參數(shù)設置 Table 3 Parameter Settings of environment parameters

調(diào)度環(huán)境對應的動作信息為調(diào)度動作空間，實例標識為“l(fā)evel 數(shù)量×section數(shù)量×shelf數(shù)量”，以圖1 為例，該倉儲環(huán)境實例有3 層貨架（level 數(shù)量為3）、2 條通道和8 排貨架（總和section 數(shù)量為10），每個通道對應4 排貨架，即兩側(cè)各有2 排內(nèi)外層的貨架；每排貨架各有3 個庫位（shelf 數(shù)量為3），將其標識為“3×10×3”。

多任務問題環(huán)境對應的動作信息為調(diào)度動作空間和庫位動作空間，加前綴“S-”表示。

5.3 堆垛機調(diào)度實驗分析

為驗證調(diào)度模型算法的有效性，對表4 中所有實例進行實驗，改進模型算法在表中標記為PPOCB。其中，PPO-CB、PPO 對每個實例分別進行訓練以及測試。在當前實驗中，最大累計回報信息作為評價指標。選用Ran（隨機采樣方法）、基于概率規(guī)劃的SOG 算法、粒子群優(yōu)化算法PSO、PPO 與本文算法進行比較。在粒子群優(yōu)化算法［27］中，初始種群大小為200，最大迭代次數(shù)為1 000。算例實驗對比情況如表4 所示，其中，最優(yōu)調(diào)度結果以粗體顯示，—表示計算時間嚴重超時，無法求解。同時為了驗證改進網(wǎng)絡中新增的不同因素帶來的影響，對基于批標準化的PPO 模型和基于卷積的PPO 模型分別進行實驗，分別標記為PPO（BN）和PPO（CNN）。相較于PPO-CB，PPO（BN）不包括卷積和池化層，PPO（CNN）不包括批標準化層。

表4 調(diào)度問題實驗結果對比 Table 4 Comparison of experimental results of scheduling problems

分析表4 可知，本文方法模型PPO-CB 在實例環(huán)境中的表現(xiàn)明顯優(yōu)于基礎的Ran 算法。同時相較于原PPO 算法模型，本文模型雖然在1×5×5 和1×5×10實例中與原方法差距不大，但在其他實例環(huán)境中都有明顯的提升?；诟怕室?guī)劃的SOG 算法在前兩個小型實例環(huán)境中取得較好的效果，但在更大狀態(tài)空間的實例環(huán)境中，效果逐漸趨同于Ran 算法，甚至無法求解。本文算法模型相較于粒子群算法PSO，在所有實例中都有著不同程度的提升，尤其是在2×10×20、2×20×10 和2×20×20 的實例中提升較大。

在不同因素的驗證實驗中，相較于原PPO 算法模型，PPO（BN）雖然在1×10×10、2×5×5 和2×5×20 實例環(huán)境略差于原算法模型，但在其他大多數(shù)環(huán)境中都能高于原算法模型，程度不一；而PPO（CNN）在大多數(shù)環(huán)境中，表現(xiàn)效果都為良好。

由表4 可知，在2×10×20 實例中，PPO-CB相較于原算法模型，其平均累計回報值提升最為明顯，提升了58%，其隨著迭代次數(shù)的增加逐漸收斂于較高的回報值，如圖4 所示。在1×5×10 實例中，PPO-CB的提升效果最弱，其收斂曲線略微高于原方法，平均累計回報值只提升了8.9%，如圖5 所示。綜合表4 中所有實例的數(shù)據(jù)，可計算得到PPO-CB 相較于原PPO算法能收斂于更高的累計回報值，平均提升了33.6%。

圖4 2×10×20 調(diào)度問題實例中累計回報值的訓練迭代對比Fig.4 Training iteration comparison of cumulative reward values in 2×10×20 scheduling problem instances

圖5 1×5×10 調(diào)度問題實例中累計回報值的訓練迭代對比Fig.5 Training iteration comparison of cumulative reward values in 1×5×10 scheduling problem instances

在本文實驗中，實例輸入的狀態(tài)空間與對應倉庫環(huán)境大小呈正相關，同時動作空間的大小與對應環(huán)境中的堆垛機通道數(shù)量有直接關聯(lián)，所以不同實例之間的狀態(tài)、動作空間的規(guī)模差別較大。例如，實例1×5×10 與1×20×20 之間的庫位數(shù)量相差了16倍，通道數(shù)量相差了4倍。因此，在面向模型訓練時，不同實例的輸入輸出規(guī)模均不相同，所以需要對每個實例分別進行訓練和測試。

在基于不同方法的實驗時間對比中，PPO 類算法整體求解時間明顯比常規(guī)方法較長，因為需要對實例進行訓練。相較于原PPO 算法模型，PPO-CB 相對復雜的網(wǎng)絡架構導致訓練時間更長，其最短訓練時間為34 min，最長為63 min，如表5 所示。

表5 實驗平均時間對比 Table 5 Comparison of experimental mean time

綜合而言，本文提出的改進模型算法在大多數(shù)實例環(huán)境中表現(xiàn)良好，同時可以對較大狀態(tài)空間的實例環(huán)境進行求解。

5.4 調(diào)度和庫位問題實驗分析

為驗證多任務模型算法的可行性，對表6 中實例進行實驗，多任務模型在表中標記為PPO-CB-store。在當前實驗中，最大累計回報值作為評價指標。在該部分實驗，主要驗證該算法的可行性。選用Ran（隨機采樣方法）作為對比，實驗效果情況如表6 所示，其中最優(yōu)調(diào)度結果用粗體顯示。

表6 多任務問題實驗結果對比 Table 6 Experimental results for multi-task problems

由表6 分析可知，PPO-CB-store 在實例環(huán)境中能夠有正面的效果表現(xiàn)，且相對于Ran 這種基礎的抽樣方法有著明顯的提升。同時隨著實例規(guī)模的擴大，PPO-CB-store 依然能夠求解實例問題，驗證了該方法的可行性。

圖6和圖7 分別為PPO-CB-store 在2×10×10 和2×10×20 實例環(huán)境中累計回報值隨迭代次數(shù)變化的曲線。

圖6 2×10×10 多任務問題實例中累計回報值的迭代對比Fig.6 Iteration comparison of cumulative reward values in 2×10×10 multi-task problem instances

圖7 2×10×20 多任務問題實例中累計回報值的迭代對比Fig.7 Iteration comparison of cumulative reward values in 2×10×20 multi-task problem instances

從圖6 和圖7 中分析可知：PPO-CB-store 在迭代過程中可以收斂至較高的累計回報值，并且能有效地應對調(diào)度和庫位優(yōu)化的多任務場景。

6 結束語

本文針對倉儲環(huán)境問題進行建模，提出一種基于深度強化學習算法的堆垛機調(diào)度算法，來實現(xiàn)倉儲環(huán)境問題在PPO 強化學習算法中的應用，同時針對倉儲系統(tǒng)中衍生的庫位優(yōu)化問題，提出基于多任務學習的算法模型，并通過實驗驗證了該模型的可行性，為該類多任務問題提供一個有效的解決方案。由于不同實例的狀態(tài)空間規(guī)模不相同，因此在求解時間方面仍存在不足，下一步將考慮引入編碼器-解碼器架構，使單個網(wǎng)絡模型能夠?qū)Χ鄠€實例進行訓練，從而減少重復訓練，并將模型遷移到未曾訓練過的實例中實現(xiàn)模型的復用，以從根本上降低求解時間。