基于深度強化學習的自動化集裝箱碼頭集成調度方法*

尹 星 張 煜,2 鄭倩倩 唐可心▲

（1. 武漢理工大學交通與物流工程學院 武漢 430063;2. 廣東省內河港航產業(yè)研究有限公司 廣東 韶關 512000）

0 引 言

集裝箱碼頭是連接海路運輸?shù)闹匾獦屑~，其作業(yè)效率關乎港口的運營效益和碼頭競爭力。岸橋、水平運輸工具，以及場橋是進行集裝箱碼頭裝卸船作業(yè)的重要自動化設備，對于全自動化集裝箱碼頭而言，碼頭的運作效率和運作成本很大程度上由這3 種設備之間的協(xié)調性決定，因此3 種設備的資源分配與協(xié)同調度一直是集裝箱碼頭的研究熱點。

集裝箱調度過程涉及多個環(huán)節(jié)，岸橋對海側集裝箱進行裝卸，集卡對集裝箱進行運輸，場橋負責集裝箱在堆場的取放作業(yè)。部分學者對單一作業(yè)環(huán)節(jié)進行研究，如高雪峰[1]對2臺場橋存取混合作業(yè)模式進行了建模和求解；丁一等[2]研究自動化集裝箱碼頭自動導引運輸車（automated guided vehicle,AGV）調度問題，分析AGV路徑選擇和調度策略對港口裝卸效率的影響；夏孟玨等[3]重點研究了岸橋故障突發(fā)情況下裝卸船作業(yè)重調度策略。但集裝箱碼頭調度是1 個聯(lián)合作業(yè)過程，僅考慮單一作業(yè)環(huán)節(jié)無法實現(xiàn)碼頭整體生產的優(yōu)化，一些專家側重于從2階段設備協(xié)同作業(yè)角度進行集裝箱調度優(yōu)化，比如，梁承姬等[4]對多船作業(yè)模式下岸橋和集卡協(xié)同調度問題進行研究；陳超等[5]對港口泊位分配與集卡路徑規(guī)劃進行研究。也有學者對岸橋、運輸小車，以及場橋3階段作業(yè)聯(lián)合調度過程展開研究，如常祎妹等[6]將岸橋間、場橋間干涉和集卡速度變化等不確定性因素考慮在內，研究裝卸作業(yè)模式下集裝箱碼頭集成調度問題。

傳統(tǒng)的求解集裝箱調度的方法主要有精確算法、元啟發(fā)式和啟發(fā)式算法、仿真方法，Kim等[7]提出了1 種分枝界定方法來獲得岸橋調度問題最優(yōu)解；秦天保等[8]從約束規(guī)劃角度對岸橋、集卡和場橋的集成調度進行建模，并使用CPLEX 求解器進行求解。但由于2階段及以上的集裝箱聯(lián)合調度問題屬于典型的NP 難組合優(yōu)化問題[9]，精確算法難以在有效時間內進行求解。啟發(fā)式與元啟發(fā)式算法在NP 難問題求解方面有著廣泛的應用，也取得了良好的效果，如鐘祾充等[10]使用改進布谷鳥算法求解碼頭3 階段集成調度問題；陳超等[11]提出1種雙層遺傳算法對岸橋、集卡和場橋3種設備數(shù)量配置。楊彩云等[12]使用Anylogic 仿真平臺，對自動化碼頭內部智能運輸機器 人（artificial intelligence robot of transportation,ART）動態(tài)調速問題進行研究，但仿真方法優(yōu)化能力有限且無法直接給出調度方案。

隨著人工智能的發(fā)展，一些學者開始探索使用強化學習方法來解決港口調度問題。強化學習是1種具有自主決策能力的機器學習方法[13]，與環(huán)境交互為目標，從智能體自身經驗中進行學習，更加適用于復雜的動態(tài)環(huán)境。目前在港口調度領域使用較為廣泛的強化學習算法主要有Q-Learning、deep Q-network（DQN）和Actor-Critic 算法。張華勝[14]將Actor-Critic 深度強化學習與啟發(fā)式算法進行結合，設計算法框架，對自動化跨運車和場橋集成作業(yè)過程進行優(yōu)化；尚晶等[15]提出了基于Q-Learning 算法的集卡調度強化學習模型，仿真結果顯示該算法能夠對集卡調度策略進行明顯優(yōu)化。Q-Learning 是1 種基于表格型的方法，面對大規(guī)模調度環(huán)境時，龐大的動作空間會導致“維數(shù)災難”問題，為了解決這個問題，DQN 引入神經網絡來擬合Q 值[16]，文獻[1]使用改進搜索策略和采樣方法的DQN 算法來解決自動化堆場雙場橋協(xié)同調度問題。

綜上，集裝箱裝卸作業(yè)是1 個多環(huán)節(jié)的聯(lián)合調度問題，使用簡單啟發(fā)式和靜態(tài)優(yōu)化方法對碼頭3階段調度問題求解易陷入局部最優(yōu)，且算法搜索時間較長。強化學習能夠實現(xiàn)與動態(tài)調度環(huán)境的自主交互，且目前已有一些學者將強化學習成功應用于碼頭實際調度過程，但研究側重于單一作業(yè)環(huán)節(jié)，缺乏對自動化集裝箱碼頭多環(huán)節(jié)聯(lián)合調度問題的研究。

因此建立岸橋、ART，以及場橋的3 階段集成調度模型，更有利于從整體優(yōu)化集裝箱調度過程，降低港口運作成本。針對集裝箱卸船作業(yè)的特點，以車間調度領域的混合流水車間理論[17]為基礎，以最小化總完工時間為目標，建立自動化碼頭集裝箱3 階段混合流水車間集成調度模型。考慮到集成調度問題的離散性和調度環(huán)境實時性、動態(tài)性的特點，設計貼合碼頭實際調度環(huán)境的深度強化學習算法（double deep Q-network，DDQN）進行求解。

1 問題描述與模型構建

1.1 集成調度問題

天津港C 段自動化集裝箱碼頭前沿布局見圖1。卸船作業(yè)流程為：船舶靠岸后，單小車岸橋移動到指定貝位，將集裝箱從船上抓起后卸載到ART上，然后由ART運送該集裝箱至堆場指定場區(qū)，由雙懸臂場橋將集裝箱從ART卸下放置于堆場指定位置。集裝箱裝船作業(yè)可以看作是上述操作的反向過程。

圖1 碼頭前沿布局示意圖Fig.1 Layout diagram of wharf front

集裝箱卸船作業(yè)可以被模擬為工件在流水線上加工的過程。見圖2，將n個集裝箱視為不同的工件，依次通過岸橋、ART，以及場橋這3 個階段的設備處理，完成卸船作業(yè)，且每個集裝箱對每個階段的設備均只經歷1 次，同一階段的設備屬于并行機。因此，本文將運用混合流水車間原理及其方法來建立自動化集裝箱碼頭卸貨過程中岸橋、ART，以及場橋3個階段的集成調度模型。

圖2 集裝箱卸貨過程3階段流水車間調度示意圖Fig.2 Schematic diagram of three-stage flow shop scheduling about container unloading process

1.2 集成調度模型

考慮集裝箱港口調度過程中存在許多實際約束條件，因此需要在傳統(tǒng)混合流水車間調度問題中加入額外設備作業(yè)約束。描述如下：①船上處于同一位置（行號和列號相同）的集裝箱之間存在作業(yè)順序制約，上層集裝箱優(yōu)先作業(yè)；②ART運送集裝箱到達堆場時需在相應位置等待，直至有完成上1 個裝卸任務的岸橋出現(xiàn)，ART才能釋放集裝箱。

考慮到多設備集成調度的復雜性，將實際場景簡化，對模型做如下假設。

1）集裝箱都是同一類型標準箱。

2）將處于同一貝位中、作業(yè)類型相同（在堆場擺放于同一箱區(qū)）的集裝箱劃分為1個作業(yè)集，岸橋在對某1個作業(yè)集操作完成之前，不會移動到下1個作業(yè)集。

3）由于各階段設備的準備時間較長，比如岸橋和場橋的移動時間等，所以計算總完工時間時考慮設備準備時間。

4）不考慮設備故障等突發(fā)情況。

5）不考慮翻、倒箱時間。

6）集裝箱轉移到堆場的目的位置是已知的，且同一作業(yè)集的集裝箱運送到堆場同1個箱區(qū)。

模型參數(shù)定義及說明見表1。

表1 3 階段混合流水車間調度模型參數(shù)及說明Tab.1 Parameters and description of three-stage hybrid flow shop scheduling model

目標函數(shù)為

約束條件為

以下為決策變量取值區(qū)間。

式（1）為目標函數(shù)，表示最小化最大完工時間；式（2）為各階段設備選取虛擬作業(yè)集O作為起始作業(yè)集；式（3）為各階段設備選取虛擬作業(yè)集V作為終止作業(yè)集；式（4）為每個階段、每個作業(yè)集有且僅有1臺設備操作它；式（5）為作業(yè)集先后作業(yè)順序，也就是各階段設備的作業(yè)序列；式（6）為每1個正在被服務的作業(yè)集有且僅有1 個作業(yè)集在其之前和之后；式（7）為階段1 中的作業(yè)集由優(yōu)先級Φ約束；式（8）為前后2 階段中，作業(yè)集i開始被服務的時間關系；式（9）為各階段中每臺設備最早可開始工作時間；式（10）為各階段中每個任務的結束時間；式（11）為同1個作業(yè)集在前后2 個階段中的作業(yè)時間約束；式（12）為在同一階段中，作業(yè)集i開始被操作的時間小于/等于其結束被操作的時間；式（13）和式（14）為若同一階段k中，先后2個作業(yè)集i和j分配給同一設備m操作，則操作時間要錯開相應的準備時間；式（15）和式（16）為決策變量的取值。

2 基于深度強化學習的調度算法設計

2.1 深度強化學習算法簡介

在自動化集裝箱碼頭裝卸系統(tǒng)中，將岸橋作業(yè)系統(tǒng)、ART 水平作業(yè)系統(tǒng)和場橋作業(yè)系統(tǒng)看作3 階段智能體決策系統(tǒng)，將集裝箱調度過程使用強化學習進行描述，見圖3。智能體采取動作作用于碼頭集成調度環(huán)境，然后轉移到下1個狀態(tài)，環(huán)境給出即時獎勵，如此循環(huán)往復，最終由各階段設備確定的集裝箱任務操作序列便是最佳調度方案。

圖3 基于深度強化學習的集裝箱集成調度機制Fig.3 Container integrated scheduling mechanism based on deep reinforcement learning

2.2 馬爾科夫決策模型構建

馬爾科夫決策過程（Markov decision processes,MDP）是強化學習問題理想化的數(shù)學表達形式[18]，前文所述的自動化集裝箱碼頭3階段調度問題可轉化為1 個馬爾科夫決策過程，對馬爾科夫決策過程的狀態(tài)空間、動作空間、獎勵函數(shù)做出如下定義。

2.2.1 狀態(tài)空間設計

狀態(tài)特征和動作空間的設計與調度問題密切相關，一般需要遵循以下原則：①狀態(tài)特征要有代表性，能夠描述碼頭調度環(huán)境的主要特點和變化；②狀態(tài)特征是對設備狀態(tài)變化的數(shù)值表示，可以用相對統(tǒng)一的尺度描述，并且易于計算。

結合碼頭實際作業(yè)情況，將階段k中的設備Mk的第h個特征記為fk,h，為各階段設備定義不同的特征值，包括反映碼頭整體調度環(huán)境變化的全局特征和反映設備特點的局部特征：為階段1 的設備定義8個特征（1 ≤h≤8），對于階段2的設備定義10個特征（1 ≤h≤10），對于階段3 的設備定義10 個特征（1 ≤h≤8,h=11,12）。

狀態(tài)特征具體定義如下。

式中：Ωk={1,2,···,}為當前在設備Mk排隊的集裝箱作業(yè)集集合，絕對值表示數(shù)量。該狀態(tài)特征描述各階段設備上集裝箱的數(shù)量分布。

該狀態(tài)特征表示當前分配在各階段設備上的平均工作負載。

式（19）和（20）為在各設備上等待的集裝箱作業(yè)集最長/最短操作時間。

式（21）和（22）為隊列Ωk中等待的作業(yè)集中剩余最長/最短操作時間的歸一化表示。

式中：為正在設備上加工的集裝箱作業(yè)集的剩余操作時間，為作業(yè)集在該設備上的已加工時間。若fk,7=0，則表示該階段設備空閑。

式（24）為即使在有作業(yè)集等待加工的情況下，是否讓當前設備保持空閑（比如岸橋作業(yè)區(qū)域劃分）。

式（25）為ART 是否可以采取Johnson 啟發(fā)式規(guī)則1定義的動作。

式（26）為ART 是否可以采取Johnson 啟發(fā)式規(guī)則2定義的動作。

式（25）和式（26）中：Q1和Q2為將船上的集裝箱作業(yè)集按照作業(yè)時間進行劃分，Q1為在堆場作業(yè)時間大于岸橋作業(yè)時間的作業(yè)集，其余作業(yè)集劃分為Q2。

式中：trat,2為ART 到達堆場的剩余時間；twait,3為場橋發(fā)生干涉時ART 的等待時間。按照ART 預計達到堆場指定位置的剩余時間和ARMG 發(fā)生干涉時ART 的等待時間，將當前隊列分為A1和A2，A1表示等待時間大于剩余達到時間的作業(yè)集集合，其余劃分到A2。該狀態(tài)特征決定ARMG是否可以采取Johnson啟發(fā)式規(guī)則3定義的動作。

式（28）為ARMG 是否可以采取Johnson 啟發(fā)式規(guī)則4定義的動作。

2.2.2 動作空間設計

動作空間就是智能體在當前狀態(tài)下可以采取的動作候選集合，在碼頭集成調度問題中，智能體執(zhí)行的動作是依據(jù)調度規(guī)則優(yōu)先選擇要操作的集裝箱作業(yè)集。啟發(fā)式調度規(guī)則時間復雜度較低，但混合調度規(guī)則比單一調度規(guī)則的求解效果好[19]，且目前已有一些將混合啟發(fā)式調度規(guī)則應用于強化學習算法中，并在車間調度問題與資源投入調度領域取得了良好的效果[20-24]。因此本文選擇了5 條被廣泛使用的單一調度規(guī)則，并在此基礎上結合碼頭實際作業(yè)情況，為ART 階段和場橋階段增添了復合調度規(guī)則，見表2。因此，單小車岸橋能夠采用的行為集合是，ART 能 夠 采 用 的 行 為 集 合 是，場橋能夠采用的行為集合是

表2 調度規(guī)則Tab.2 Scheduling rules

2.2.3 獎勵函數(shù)設計

獎勵函數(shù)定義適當與否與調度效果密切相關，本文的調度目標為式（1），即最小化最大卸船作業(yè)完工時間，這一目標可通過最大化加工設備利用率來進行轉換。對于集裝箱碼頭來說，提高各階段設備的利用率是提升碼頭整體裝卸效率的關鍵，因此使用平均設備利用率來表示調度目標。借鑒文獻[20]中的表達方式，將平均設備利用率表示為集裝箱作業(yè)集在各階段設備上的總操作時間與整體最大完工時間之比，數(shù)值表示具體如下。

式中：Si,m,k為集裝箱作業(yè)集i在階段k中對應設備m上的開始操作時間；Ei,m,k為集裝箱作業(yè)集i在階段k中對應設備m上的終止操作時間；Mk為階段k中設備數(shù)量。

由式（30）可見：設備利用率與最大完工時間為反比關系，設備利用率越高，最大完工時間越小。

2.3 算法流程

Q-Learning 采用Q 表來存儲狀態(tài)集合，進而通過更新動作-值函數(shù)Qπ( )s,a來進行動作選擇。但調度環(huán)境的狀態(tài)集合規(guī)模大，大量的狀態(tài)-行為信息超過了Q 表的存儲容量，從而導致“維數(shù)災難”問題。為了解決這個問題，DDQN（double DQN）算法采用帶參數(shù)的神經網絡來近似擬合動作-值函數(shù)Qπ(s,a|θ)[21]。同時為了避免過估計（over estimation），算法使用雙網絡模式，將動作選擇（當前Q網絡）與動作評估（目標Q 網絡）分離開，并引入經驗回放機制打破數(shù)據(jù)之間的相關性，使神經網絡訓練過程更加穩(wěn)健。神經網絡的輸入層為每臺設備對應的狀態(tài)特征；之后連接4 個全連接層，激活函數(shù)使用relu 函數(shù)；輸出層為對應輸入狀態(tài)的動作預測value值。

DDQN 算法中的目標Q 網絡的參數(shù)（θQ）是隔一段時間從當前Q 網絡（θQ′）中復制而來，2 個Q 網絡的結構相同。設定n步之后，采用軟更新（soft-update）的方式來更新。

式中：τ為更新系數(shù)，一般取值較小，比如取值0.1或0.01。

多智能體DDQN算法流程見圖4。

圖4 調度算法流程圖Fig.4 Flow chart of scheduling algorithm

3 算例分析

3.1 各階段設備參數(shù)

為了驗證所提出模型和算法的有效性和可行性，根據(jù)天津港實際調研情況設計實驗算例。天津港C段碼頭采用單小車岸橋-ART-雙懸臂場橋的裝卸工藝，每臺岸橋1 次可吊起1 個FEU 或2 個TEU，每輛ART 1次可運載1個FEU或2個TEU，堆場一共有8 個箱區(qū)，每臺場橋1 次可裝卸1 個FEU 或2 個TEU。各設備作業(yè)時間見表3。

表3 集裝箱碼頭各階段設備運作效率Tab.3 Operation time of equipment at each stage of container terminal

表4為碼頭前沿與堆場各箱區(qū)之間的距離。

表4 碼頭前沿距各箱區(qū)的距離Tab.4 Distance from wharf apron to each container area

3.2 DDQN算法訓練與求解

依據(jù)3.1節(jié)自動化碼頭相關參數(shù)，以1個規(guī)模為300 個集裝箱的算例進行驗證。假設300 個集裝箱分布在同1 艘船舶的15 個貝位中，每個貝位包含20個集裝箱，分為2 個作業(yè)集，則一共有30 個作業(yè)集，配套使用4臺岸橋、15輛ART和8臺場橋（每個箱區(qū)1臺）進行卸船作業(yè)，設定ART在岸橋和場橋下的停留時間均為20 s。

調度算法采用Python3.7 語言實現(xiàn)，在Tensor-Flow2.0 框架中實現(xiàn)，運行于Windows11 64 位操作系統(tǒng)，處理器為Intel Corei5-9400 CPU2.90GHz，RAM 為8GB 的PC 機。調度環(huán)境使用OpenAI 的Gym搭建。參數(shù)的設置對算法的訓練時間和求解質量有著重要影響，按照一般設置原則[24]，深度強化學習調度算法參數(shù)設置見表5。

表5 算法參數(shù)設置Tab.5 Algorithm parameter setting

算法收斂曲線見圖5。由圖5可見：隨著迭代次數(shù)的增加，算法能夠使調度目標以較快的速度減少，約1 200代時達到較優(yōu)結果并收斂。

圖5 算法收斂圖Fig.5 Algorithm convergence graph

深度強化學習算法調度結果見圖6。

圖6 調度結果甘特圖Fig.6 Gantt chart of dispatching results

單小車岸橋調度方案見表6，ART 指派結果見表7，雙懸臂場橋調度方案見表8。

表6 單小車岸橋調度方案Tab.6 Single trolley quay crane dispatching scheme

表7 ART 指派結果Tab.7 Art assignment results

表8 雙懸臂場橋調度方案Tab.8 Double cantilever yard crane dispatching scheme

由調度結果可知，3 階段設備總作業(yè)時間為13 550 s，其中第1階段4臺岸橋利用率很高，負荷較為均勻，第2階段ART平均利用率為98%，負荷較為均衡，第3階段場橋平均利用率為71%，最低負荷率為54%，最高為84%，說明ART的配置數(shù)量能夠滿足岸橋作業(yè)速度，減少了岸橋等待時間。實際作業(yè)中，天津港C段自動化碼頭目標效率（90% TEU） 為每小時489 箱（平均每臺岸橋不低于27 TEU/h），DDQN算法每臺岸橋作業(yè)效率為34 TEU/h，說明調度結果能夠滿足實際應用要求。

4 模型驗證

4.1 與精確算法求解比較

為了驗證所提算法的有效性和模型的正確性，設計10 個小規(guī)模算例，并將Gurobi 求解結果和深度強化學習算法求解結果進行對比，對比結果見表9。表9 中n×Q×A×M為所設計案例的規(guī)模，即集裝箱作業(yè)數(shù)×單小車岸橋數(shù)量×ART 數(shù)量×雙懸臂場橋數(shù)量；e1，e2分別為Gurobi 和深度強化學習算法的求解結果；t1，t2分別為Gurobi 和深度強化學習算法對算例的求解時間為深度強化學習算法求解結果對Gurobi求解結果的相對誤差。

由表9 的小規(guī)模案例求解對比結果可見：所提出的深度強化學習算法在多數(shù)情況下能夠得到與Gurobi 非常接近的最優(yōu)解，平均求解誤差為1.99%。但隨著案例規(guī)模逐漸增加，Gurobi 求解器的計算時間顯著偏高，說明所提出DDQN 算法在求解較大規(guī)模算例時具有一定時間優(yōu)勢。

表9 小規(guī)模算例下Gurobi 和深度強化學習算法求解結果對比Tab.9 Comparison of solution results between gurobi and deep reinforcement learning algorithms for small-scale examples

4.2 與單一調度規(guī)則求解比較

為進一步驗證算法的優(yōu)越性，對天津港C段3艘船舶的集裝箱進行驗證，由于Gurobi在表10設置的3種大規(guī)模的實例環(huán)境（集裝箱作業(yè)數(shù)×單小車岸橋數(shù)量×ART數(shù)量×雙懸臂場橋數(shù)量）下無法實現(xiàn)精確求解，因此對DDQN 算法和使用5 種單一調度規(guī)則的策略、粒子群算法（particle swarm optimization,PSO）進行性能測試，每個實例進行10次仿真實驗并取平均值記錄，測試結果見表10。表10中所用的粒子群算法采用文獻[25]推薦的參數(shù)，慣性權重ω=0.729，加速因子c1=c2=1.494 45。

表10 較大規(guī)模算例求解對比Tab.10 Comparison of large-scale numerical examples

由表10可見：隨著集裝箱任務數(shù)量和設備數(shù)量的增多，DDQN算法的求解效果均好于單一調度規(guī)則與粒子群算法，顯現(xiàn)出一定的優(yōu)越性，3 個算例中DDQN 與下界值的差距分別為6.0%，5.6%，4.6%。特別說明的是，強化學習算法訓練需要耗費時間較長，但訓練好的算法能夠在20 s 內得到最優(yōu)結果。

為進一步驗證算法穩(wěn)定性，對算例60×12×26×14 分別進行100次求解，得到求解結果與理論下界差距箱型圖，見圖7。從圖7 可見：相對于使用單一啟發(fā)式調度規(guī)則，DDQN 算法與理論下界值差距的下限和中位數(shù)小，且數(shù)據(jù)分布較為集中，無明顯異常值。表明DDQN 算法具有較好的穩(wěn)定性，且具有明顯的求解優(yōu)勢。

圖7 6種策略與理論下界值差距箱型圖Fig.7 Box plot of the gap between six strategies and the theoretical lower bound

為分析所使用的啟發(fā)式調度規(guī)則在深度強化學習算法中的作用，統(tǒng)計求解所有實驗算例過程中9種啟發(fā)式動作的使用頻率，見圖8。由圖8 可見：使用頻次較 多的為Johnson1 和Johnson2，Johnson3 和Johnson4，SPT，LPT，MWKR，說明這些規(guī)則對產生最優(yōu)調度結果貢獻較大，而FIFO和LWKR使用頻次較少，效果不太突出，后續(xù)可以考慮增添其他啟發(fā)式行為進行替換。

圖8 啟發(fā)式行為使用頻率統(tǒng)計Fig.8 Heuristic behavior usage frequency statistics

5 結束語

針對集裝箱碼頭卸船過程中岸橋、ART 和場橋設備的集成調度問題，建立了以混合流水車間為基礎的3 階段混合整數(shù)規(guī)劃模型，以天津港C段自動化碼頭實際調研數(shù)據(jù)為基礎，設計不同規(guī)模算例進行求解，通過與Gurobi 求解結果對比，驗證了模型和算法的有效性；為進一步驗證復合調度規(guī)則的優(yōu)越性，對比7 種算法的求解方案，結果表明所提DDQN 算法更具優(yōu)勢，求解的完工時間更接近理論下界值。此外，由于每個港口的操作工藝不同，因此針對不同港口需要對模型和算法的細節(jié)進行調整，后續(xù)會進一步考慮算法在其他港口集成調度問題適用性。