增強學習算法在集裝箱船舶配載問題上的應用

嚴翀宇 王男男 沈一帆

集裝箱船舶配載是集裝箱碼頭生產作業的重要環節之一，其直接影響碼頭整體裝卸作業效率。目前，我國集裝箱碼頭主要采用傳統在線搜索算法解決集裝箱船舶配載問題，但此類方法在求解大規模算例時效率較低。為此，本文采用增強學習算法，將大量耗時計算前置到線下訓練階段，實際配載時則利用訓練好的網絡直接求解，從而提高求解效率。具體思路如下：首先，分析集裝箱船舶配載問題的關鍵決策因素，并從中提煉相關的配載特征向量；然后，根據集裝箱船舶配載問題的特點和約束條件，設計相應的狀態、動作和回報函數，以計算每組集裝箱-船箱位配對的Q值，并以配載特征向量作為網絡輸入，以每組集裝箱-船箱位配對的Q值作為網絡輸出，以均方誤差作為評估函數，構建增強學習網絡，并結合Q學習算法實現集裝箱船舶配載問題的增強學習算法；最后，分析該算法與傳統智能優化算法的區別，說明增強學習算法能夠高效求解集裝箱船舶配載問題。

1 研究現狀

目前，我國集裝箱碼頭主要依靠人工加計算機輔助的方式制訂集裝箱船舶配載計劃，而人工配載的一大弊端是配載結果容易受到配載員個人經驗和狀態的影響；因此，如何將配載員的個人經驗與計算機算法相結合，快速、有效地制訂合理的配載計劃有重要的研究意義。國內外學者對集裝箱船舶配載問題的研究主要集中在配載模型和配載算法方面。

1.1 配載模型的研究現狀

（1）主貝計劃配載模型 TODD等針對單港口的主貝計劃配載問題，以縱傾力矩、橫傾力矩、船舶穩性和距離位置等為約束條件，以翻箱量最小為目標函數，采用遺傳算法求解。ZHAO等針對集裝箱船舶主貝計劃配載問題，考慮船舶穩性、翻箱量和場橋作業效率等因素，建立多目標整數規劃模型；但該模型過于復雜，很難進行規劃求解，缺乏實用性。MOURA等在同時考慮主貝計劃和航線因素的情況下，以運輸成本最小化為目標函數，建立混合整數規劃模型。

（2）貝內計劃配載模型 AVRIEL等以翻箱量最小為優化目標構建簡單的整數規劃模型，并設計相應算法，通過算例驗證該算法在較小規模的情況下可以得到較好的求解效果；但該模型過于簡單，實用性不強。SHIELDS建立數學模型，并將模型求解結果與實際裝船結果進行對比，證明模型的有效性；但由于當時的船舶大多為中小型船舶，該模型已無法適應當前船舶大型化趨勢下的約束條件和優化目標。IMAI等構建0-1整數多目標配載模型，計算得到堆場翻箱量；但在配載問題中，如果存在大量0-1整數二元變量和約束條件，求解難度將加大，很難得到最優解。

1.2 配載算法的研究現狀

大多數學者采用智能優化算法求解集裝箱船舶配載問題。ALVAREZ在考慮正面吊移動距離、翻箱量和船舶質量分布的情況下，提出基于多個初始解的禁忌搜索算法，并將該算法運用到實際算例中與混合整數規劃算法進行對比。研究結果表明，其設計的算法能夠在較短時間內求解上百個箱量的算例，而混合整數規劃算法只能求解40個以內集裝箱的算例。KIM等提出運用束搜索算法求解集裝箱船舶配載問題，并在考慮場橋和翻箱量等因素的基礎上構建模型，制訂合理、有效的配載和收箱策略。LEE等利用層級理論解決集裝箱船舶配載問題，將發箱順序問題分解為小規模子問題，并設計一種將蟻群算法與禁忌搜索算法相結合的混合啟發式算法。算例驗證結果表明，該混合啟發式算法的求解效率高于單純的蟻群算法和禁忌搜索算法。衛家駿[14]設計禁忌搜索-蟻群混合算法求解集裝箱船舶配載問題，并通過仿真模擬試驗進行驗證。

1.3 小結

綜上所述，針對集裝箱船舶配載問題，現有的研究主要聚焦于構建混合整數規劃模型，并利用特殊設計的啟發式算法求解。該類算法雖然能夠在一定程度上較好地求解小規模算例，但仍然存在很大局限性，例如：只能求解特殊情況下的配載問題；大規模算例的求解效率不高；等等。為此，本文采用增強學習算法，通過訓練得到配載智能體，從而能夠在各種情況下高效求解配載問題。

2 集裝箱船舶配載問題描述

2.1 決策因素

（1）集裝箱不懸空原則 在制訂裝船作業的貝內計劃時，需要考慮集裝箱的裝船順序。如果同一列的上層船箱位的裝船順序先于下層船箱位的裝船順序，就會造成集裝箱懸空現象，致使裝船作業無法順利進行，進而導致裝船作業效率下降。

（2）海側至陸側裝船原則 在陸側已裝船集裝箱層高高于海側已裝船集裝箱層高的情況下，如果需要繼續為海側船箱位發箱，岸橋的起升高度必須超過陸側已裝船集裝箱層高，否則會造成集裝箱碰撞。為避免產生上述跨高作業，對于同一層的船箱位，配載時應當考慮從海側往陸側實施裝船作業，從而確保裝船作業的安全性和高效性。

（3）船箱位質量范圍原則 在制訂貝內計劃時，應當考慮主貝計劃確定的船舶貝位預分層質量，即每個貝位每層集裝箱的質量范圍，確保每個船箱位的集裝箱質量在此范圍內，以滿足船舶穩性和集裝箱綁扎要求。

（4）重壓輕極限原則 理論上，集裝箱船舶配載應遵循下重上輕原則；但在實際配載過程中，為方便碼頭作業，在不影響船舶穩性的前提下，允許存在少量的重壓輕。在重壓輕的情況下，上下相鄰集裝箱的質量差通常應控制在0.5～1.0t，具體可根據船型作相應調整。

2.2 優化目標

（1）艙面梯形配載 梯形配載是艙面配載的獨特工藝，指配載時應考慮按船箱位順序從海側往陸側以樓梯形式依次發箱，從而確保相鄰格柵已裝船集裝箱的層高不至于相差過大，同時降低岸橋司機的作業難度。

（2）減少翻箱頻次 翻箱作業是無用作業，是導致裝船作業效率下降的主要因素之一。對于堆場內同一箱區、同一貝位、同一列的集裝箱，配載時應盡量使上層集裝箱先發，否則會導致翻箱作業。為避免場橋頻繁翻箱，配載時應當考慮同一箱區、同一貝位、同一列的集裝箱從上往下依次發箱，從而使場橋翻箱頻次最小。

（3）減少移機頻次 此處的移機指場橋在不同箱區之間或同一箱區內的不同貝位之間移動。裝船作業時，如果相鄰發箱順序號所對應的集裝箱位于不同箱區或同一箱區內的不同貝位，就會造成移機。不合理的發箱順序會導致場橋在不同箱區之間或同一箱區內的不同貝位之間頻繁移動，使得裝船作業效率下降；因此，配載時應當考慮同一箱區內的同一貝位連續發箱，從而使場橋移機頻次最小。

3 集裝箱船舶配載問題增強學習算法設計

3.1 增強學習算法概述

設計函數Q（s，a），用于計算配載狀態s下執行

式中t為時刻；st為系統在時刻t的狀態；at為決策者在系統處于狀態st的情況下所采取的動作；rt為系統在狀態st下通過動作at獲得的回報值。

式中：t為時刻；st為系統在時刻t的狀態；at為決策者在系統處于狀態st的情況下所采取的動作。

3.2.2 配載狀態設計

在配載問題中，t為配載順序，t=0表示未配載集裝箱，t=1表示配載第1個集裝箱，t=2表示配載第2個集裝箱，以此類推。假設船箱位序號為L1～L6（見圖1），則集裝箱船舶配載問題的馬爾可夫決策過程如圖2所示。

配載動作a所得到的總回報值。在初始階段，配載智能體就像一位對集裝箱船舶配載問題一竅不通的配載員。針對配載智能體為解決配載問題所采取的每個配載動作，即集裝箱-船箱位的配對，回報函數均會反饋相應的回報值。配載智能體通過這一反饋來更新函數Q（s，a），并根據更新后的函數Q（s，a）決策下一個配載動作，這就是增強學習的迭代過程。配載智能體通過不斷地試錯，從中吸取經驗，逐漸學會在特定狀態下如何配載才能獲得最大回報值，最終使配載問題的評價迭代收斂到最優。

3.2 集裝箱船舶配載問題的馬爾可夫決策過程

3.2.1 馬爾可夫決策過程概述

馬爾可夫決策過程可表述為：在系統處于某個狀態的情況下，決策者的決策決定其所采取的動作，該動作決定系統獲得的回報值和下一時刻系統將達到的狀態。馬爾可夫決策過程的數學表達式為

馬爾可夫決策過程具有無后效性，即系統獲得的回報值以及系統從當前狀態向下一狀態轉移的概率只取決于當前狀態和動作，而與歷史狀態和動作無關。狀態轉移函數

注：s0一未配載集裝箱，船箱位為空，此時有多個動作可以選擇，即將某個集裝箱配載到某個船箱位；s1（C1，L4）—當前狀態為已配載1個集裝箱，即將集裝箱C1配載到船箱位L4；s2（C3，Ll∣s1（C1，L4））—當前狀態為已配載2個集裝箱，即在給定狀態s1（C1，L4）下，將集裝箱C3配載到船箱位L1

3.2.3 配載動作設計

在配載問題中，動作定義為集裝箱與船箱位的配對，即將某個集裝箱配載到某個船箱位。以圖2為例，若不考慮配載約束條件，配載狀態s0下可執行的配載動作有36種，即集裝箱與船箱位的配對方式有36種。

3.2.4 配載回報設計

集裝箱船舶配載問題中的回報函數設計與各個目標函數的權重以及約束條件有關。配載效果的評價指標主要包括配載完成情況、翻箱情況、移機情況、重壓輕情況等。鑒于上述指標在配載過程中的重要程度不同，設計回報函數時有不同的側重。

式（3）～（5）分別表示配載完成情況回報值、翻箱情況回報值和移機情況回報值。

3.2.5 配載值函數和動作價值函數設計

設計配載值函數和動作價值函數，即

式（10）表示所選取的在場箱的質量；式（11）表示所選取的在場箱所在船箱位的層高；式（12）表示所采取的配載動作中的集裝箱與其所在船箱位下方集裝箱的質量差；式（13）表示所采取的配載動作的潛力值，即在將該配載動作作為本次配載策略的情況下，比該配載動作中的集裝箱質量輕的集裝箱數量與該集裝箱所在船箱位上方空余船箱位數量之差，也就是當前配載動作對該配載動作中的船箱位上方集裝箱配載的影響情況；式（14）表示所采取的配載動作產生的堆場翻箱量；式（15）表示所采取的配載動作中的集裝箱的發箱順序與其左側集裝箱所

式（6）～（9）中： π為所選擇的配載策略；λ為下次配載對于當前配載的影響因子；T（s∣s，a）為從配載狀態s采取配載動作a最終到達配載狀態s的概率；R（s∣s，a）為從配載狀態s采取配載動作a最終到達配載狀態，所獲得的回報值；v（s）為在配載狀態s下采取配載動作a所獲得的期望回報值，即在該船箱位配載該集裝箱將給之后配載其他集裝箱帶來的回報值；Q（s，a）為在配載狀態s下采取配載動作a所獲得的總回報值；V*（s）為在配載狀態s下可獲得的最大回報值；V*（s，a）為在配載狀態s下采取配載動作a所獲得的最大回報值。

3.3 配載特征分析

為解決維度災難問題，本文用配載問題的9個相關特征近似表示配載狀態。以下描述的特征均針對當前配載狀態可能采取的配載動作進行說明。假設每個配載動作的特征向量為

屬區位的發箱順序差；式（16）表示所采取的配載動作中的集裝箱的發箱順序與其下方集裝箱所屬區位的發箱順序差；式（17）表示所采取的配載動作中的集裝箱是否從同區位發出；式（18）表示所采取的配載動作中的集裝箱是否與其前一配載動作中的集裝箱從同區位發出。

4 增強學習算法求解集裝箱船舶配載問題的優勢

（1）計算遷移 傳統智能算法聚焦于問題的決策階段，需要花費大量時間對問題進行求解計算。對于超大型集裝箱船舶而言，為獲得較好的配載結果，采用傳統智能算法通常要比人工配載花費更多時間。與傳統智能算法不同的是，增強學習算法聚焦于問題的學習階段，可以在任何時間段學習配載數據，從而將大量的計算遷移至學習階段，在決策階段則直接使用增強學習得到的參數集進行求解；因此，增強學習算法的求解效率較高，通常可在1s內計算上千個集裝箱的配載結果。

（2）泛化能力強 傳統智能算法通常需要人工提煉各種配載規則并劃定問題邊界，并在對各種規則和問題模型化的基礎上求解；因此，傳統智能算法對規則和邊界以外的配載問題往往難以取得較好的結果。增強學習算法則基于歷史數據學習各種配載情況，使得配載智能體能夠掌握隱藏在數據背后的規律，即使面對全新的配載樣本也具備較強的適應能力。

5 結束語

本文采用增強學習算法求解集裝箱船舶配載問題，其主要創新點如下。

（1）運用機器學習的相關理論和方法求解規劃模型，將大量的計算遷移到模型訓練學習階段，從而大幅提高決策階段的計算效率。

（2）將配載問題的目標和約束條件轉換為特征向量，使配載智能體通過增強學習從特征向量中自動提取不同狀態下的配載策略，從而避免傳統啟發式算法下因人工設計啟發規則而造成的有偏估計。

（3）相關研究思路和方法對解決集裝箱碼頭場地計劃、場橋調度、智能收箱等問題具有一定的借鑒意義。

參考文獻：

[14]衛家駿.混合蟻群算法求解集裝箱箱位分配問題[J].中國航海，2011，34（2）：96-100.