中文題目：基于圖指針網絡的分層課程強化學習方法求解穿梭油輪調度問題

論文題目：Graph Pointer Network Based Hierarchical Curriculum Reinforcement Learning Method Solving Shuttle Tankers Scheduling Problem

錄用期刊/會議： Complex System Modeling and Simulation (CAA A類期刊)

原文DOI： 10.23919/CSMS.2024.0017

原文鏈接：https://ieeexplore.ieee.org/document/10820942/

錄用/見刊時間：2024年12月31日

作者列表：

1）高小永 中國石油大學（北京）自動化系 教師

2）楊一旭 中國石油大學（北京）自動化系 碩21

3）彭   雕 中國石油大學（北京）自動化系 碩21

4）李尚赫 中國石油大學（北京）自動化系 博23

5）檀朝東 中國石油大學（北京）自動化系 教師

6）李菲菲 山東預見智能科技有限公司

7）陳   韜 英國薩里大學過程與化學工程系 教師

文章簡介:

海上石油生產離不開穿梭油輪進行拉油作業，穿梭油輪調度問題是個經典的組合優化問題，當較大規模需要考慮時求解難度很大。為此，本文首次將GPN引入STSP領域，提出了一種新穎的 HCRL 優化框架來解決 STSP 的復雜性，并將 STSP 劃分為航行和操作階段，以及一種異步訓練策略來解決航行階段和操作階段之間的耦合問題。實驗對比結果顯示，所提出的HCRL方法所得解更優，約12%的耗時降低。

摘要:

穿梭油輪調度是海上油氣運輸過程中的重要任務，涉及操作時間窗口的滿足、最優運輸規劃以及恰當的庫存管理。然而，傳統的混合整數線性規劃（MILP）或元啟發式算法往往因運行時間過長而難以勝任。本文提出了一種基于圖指針網絡（GPN）的分層課程強化學習（HCRL）方法來解決穿梭油輪調度問題（STSP）。該模型經過訓練，能夠將STSP分解為航程和操作階段，并依次生成航線和庫存管理決策。為解決各階段之間的耦合問題，開發了一種異步訓練策略。對比實驗表明，所提出的HCRL方法與啟發式算法相比，平均行程長度縮短了12%。另外的實驗驗證了其對未見過實例的泛化能力和對更大實例的可擴展性。

背景與動機:

針對組合優化問題的傳統強化訓練策略在復雜的約束條件和過多的影響因素下往往失效。要解決 STSP 問題，決策者必須確保時間窗的滿足，避免庫存容量超限，并考慮包括浮式生產儲卸油船（FPSOs）的存儲容量、生產率、運行率和運行時間窗、穿梭油輪的庫存容量以及 FPSOs 與陸上終端之間的距離等因素來優化石油運輸成本。為了解決這個問題，引入了被稱為課程學習（CL）和分層強化學習（HRL）的策略。一方面，獎勵函數首先設計為包括時間窗的滿足和庫存控制，并在滿足一定條件后納入成本優化，這類似于神經網絡模型的課程設置。另一方面，穿梭油輪船隊的決策將分為兩個連續的階段，以便在航行階段首先生成路徑決策，然后將其反饋給網絡作為輸入，這在 HRL 范例中被稱為一種選擇，以在操作階段生成庫存管理決策。

設計與實現:

1.基于GPN的HRL策略

提出了一種基于GPN的HRL策略來解決STSP。該策略將STSP分為航行和操作階段，并依次生成路徑規劃和庫存管理決策，這將大大降低穿梭油輪調度的復雜性。該模型的基本結構如圖1所示。在編碼器中，穿梭油輪的特征將通過LSTM進行編碼，LSTM的隱藏狀態 h 將作為查詢向量 q1 傳遞給解碼器中的Ptr-Net 1。節點的特征將通過GNN進行嵌入，輸出的高層向量上下文將分別用作兩個 Pet-Nets 的參考向量 r1 和 r2，而向量 r2 是基于 Ptr-Net 1 生成的 （s,n） 決策從向量 r1 中提取的片段。

在解碼器中，Ptr-Net 1 負責根據第一個生成的概率分布 P（s,n） 為其選擇一個油輪 s 和一個節點 n 以供其訪問。然后，s 和 n 的信息將從整個上下文向量中提取出來，以簡化 Ptr-Net 2 的計算過程。Ptr-Net 2 負責根據由 Ptr-Net 第二層生成的概率分布 P(t) 為航程（s，n）生成運行時間 t。（s，n，t）是基于 MDP 上下文下當前狀態選擇的操作，并將反饋給環境以更新穿梭油輪和節點的特征。（s，n，t）是油輪 s 整個計劃的一部分，這意味著油輪 s 從當前位置航行到節點 n 并運行時間 t，而聚合（S，N，T）是穿梭油輪的整體時間表。

 

圖1 HCRL 模型的圖示

2.針對 STSP 的 CL 策略

由于穿梭油輪路徑規劃問題中路由與庫存管理之間的緊密耦合，穿梭油輪路徑規劃問題的約束比典型的車輛路徑問題（VRP）或旅行商問題（TSP）問題框架要復雜得多，其解空間也受到約束相關參數的極大影響。如果解空間（即強化學習范例下的動作空間）過于復雜和不規則，神經網絡模型的訓練過程將會耗時，甚至無法收斂。為了解決這個問題，一些策略被提出，例如傳統組合優化中常用的懲罰函數法，以及將一些復雜的約束放松到損失函數中，以確保神經網絡訓練過程中動作空間的基本穩定性。

然而，這種策略將約束的復雜性轉移到了損失函數中，這也使得在訓練過程中難以收斂。為了解決這個問題，本文引入了 CL 策略。該策略將整個訓練過程分為幾個階段。首先是確保解決方案是可行的，然后尋找最優解。

圖2 分層強化學習策略下的遞歸過程

整個訓練過程將被劃分為若干層，每一層都有不同的損失函數。后一層的損失函數包含前一層的損失函數。在較低層，約束組將被轉化為幾個懲罰函數，并添加到損失函數中。在前一層的強化學習層訓練完成后，相應的模型，也稱為前一層的策略，將被保存并用于為所有后續層生成參考隱藏輸出向量。每一層都會根據當前的狀態轉移概率模型（MDP）以及前一層的參考隱藏向量生成自己的輸出向量。該策略的詳細示意圖如圖2所示。

通過這種方式，在將包括油輪庫存能力懲罰、浮式生產儲卸油船庫存能力懲罰和時間窗口懲罰在內的所有懲罰函數添加到損失函數中，并學習將其最小化為零之后，解決方案的可行性將得到保證。然后，將數學模型中的原始目標函數作為最高強化學習層損失函數的最后一項引入。

實驗結果及分析:

在我們的實驗中，為了降低不必要的代碼復雜性，除了原始特征嵌入參數外，GNN、LSTM 和 Ptr-Net 中的所有可學習參數都被設置為Rd×d，其中 d = 128。穿梭油輪包含五個原始特征，而浮式生產儲卸油船（FPSOs）則包含八個原始特征，這意味著原始特征嵌入參數分別被設置為R5×d和R8×d。

1.變比例 STSP 實驗

我們使用不同大小的多選擇背包問題實例對模型進行了訓練，并在一個配備 R7-4800H CPU 和單個 NVIDIA GTX 1660Ti GPU 的平臺上運行了對比測試。為了評估所提出的模型，我們將所提出的 HCRL 模型的性能與通過 Gurobi 10.0.1 求解的多選擇背包問題模型以及改進的人工魚群算法（AFSA）進行了比較。人工魚的數量設置為20，并且Gurobi的時間限制被設定為1800秒。

基于CL架構，我們將訓練過程分為兩組迭代。在前五個迭代中，神經網絡的參數在損失函數的約束下進行初始化和更新，該損失函數將油輪庫存能力懲罰、浮式生產儲卸油船庫存能力懲罰和時間窗口懲罰相加，旨在確保生成解決方案的可行性。在接下來的十五個迭代中，總行程長度將被添加到損失函數中，并訓練神經網絡生成一個可行且最優的解決方案。我們在4艘穿梭油輪與5艘浮式生產儲卸油船、8艘穿梭油輪與12艘浮式生產儲卸油船以及10艘穿梭油輪與16艘浮式生產儲卸油船的規模下進行了實驗。不同規模的STSP的兩個訓練階段的成本曲線如圖3所示。

表1 不同方法下變比例 STSP 的比較

圖3 不同規模的 STSP 的懲罰階段和優化階段的成本曲線。

在相同的隨機生成的原始數據下，不同方法的總路徑長度和運行時間的比較結果列于表1中。加粗的結果為最短的路徑長度和運行時間。蟻群算法的求解時間是首次在表中獲得最優解所需的時間。表1顯示，在小規模問題上，HCRL方法的求解結果與MILP方法接近，但其求解速度比MILP方法快得多。隨著問題規模的增加，HCRL方法的求解結果逐漸不如MILP方法，而AFSA方法的求解性能隨著問題規模的增加下降得比HCRL方法快，其求解速度也與HCRL方法存在一定差距。

2.HRL 結構的異步優化策略

由于所提出的模型依賴于兩個 Ptr-Net，在生成一個整體動作的結構中，Ptr-Net 1 和 Ptr-Net 2 之間不可避免地存在強耦合，這可能會減緩收斂速度，甚至在極端情況下導致發散。為了解決這個問題，開發了一種基于采樣和貪心方法的異步優化策略。

驗證實驗是在具有 10 艘穿梭油輪和 16 艘浮式生產儲卸油船規模的 STSP 上進行的。結果如圖 4 所示。

圖4 一批 S10F16 STSP 實例在不同優化策略下的懲罰層成本曲線

3.CL 策略驗證

對于高度受限的問題，如CVRPTW或MIRP，約束的滿足往往與目標函數的優化相沖突。當這兩個組成部分從一開始就納入損失函數時，確定梯度下降算法的方向就變得具有挑戰性。圖5所示的CL架構的驗證結果證明，引入的CL策略顯著提高了HRL 模型的性能。

 

圖5 不同學習策略下的一批 S10F16 STSP 實例的優化層的成本曲線

結論:

我們提出了一種基于 GPN 的 HCRL 模型來解決 STSP 問題。為了處理穿梭油輪艦隊內部的交互，我們使用 LSTM 來嵌入穿梭油輪的特征。此外，引入圖神經網絡來嵌入浮式生產儲卸油船（FPSOs）的特征。為了解決航程中路由決策之間的強耦合在運營階段的階段和庫存管理決策中，我們提出了一種異步優化策略，并通過合理的實驗驗證了其有效性。實驗表明，所提出的 HCRL 方法優于傳統的元啟發式算法，并且在更短的時間內產生了接近精確方法的令人滿意的結果。此外，對比性能分析實驗驗證了我們提出模型的可擴展性。

除了本文已經考慮的場景外，一些實際案例可能需要將建模范圍擴大到包括多個港口和可變需求。另一方面，為穿梭油輪及其目的地提出的順序決策過程引入了一個潛在的不公平或偏好的問題，因為通常較早被選擇的穿梭油輪通常會獲得更大的行動空間。

通訊作者簡介:

高小永，人工智能學院副院長，教授，博士生導師，石大學者，校青年拔尖人才，自動化專業及控制科學與工程學科建設負責人，擔任北京自動化學會常務理事、中國自動化學會過程控制專業委員會委員、中國自動化學會教育工作委員會委員、中國化工學會信息技術應用專業委員會副秘書長、中國系統工程學會過程系統工程專業委員會委員等。研究領域為復雜石油石化工業過程智能制造，主要方向有：機理與數據驅動的故障診斷、復雜工業過程建模與優化控制、工業過程計劃與調度優化等。主持國家自然科學基金項目2項、北京市自然科學基金面上項目1項、校企聯合項目20多項，發表SCI/EI等各類論文50多篇。

Email：x.gao@cup.edu.cn