基于邊裝邊卸工藝的集裝箱船配載決策

金健 宓為建 夏孟玨

摘要：針對超大型集裝箱船邊裝邊卸（dual cycling，DC）工藝下的配載問題，以DC工藝下集裝箱船艙內配載規劃為研究對象，構建以最小化場內翻箱數、設備移動次數等為目標的配載模型，并提出一種可行的蒙特卡洛樹搜索（Monte Carlo tree search， MCTS）算法對該模型進行求解。通過實際算例證明了模型和算法的有效性，且本研究的相關成果已應用于碼頭實際生產，應用效果良好。本研究思路對集裝箱碼頭相關計劃調度研究及實現有借鑒意義。

關鍵詞：集裝箱碼頭; 船舶配載規劃; 邊裝邊卸工藝; 蒙特卡洛樹搜索（MCTS）

中圖分類號： U691.7

文獻標志碼： A

Abstract： Aiming at the stowage issue of very large container ships under dual cycling （DC） process， taking stowage planning in the container ship cabin under DC process as the research object， a stowage model is constructed， where the model objective is to minimize the number of overturning containers in yards， the number of equipment movement and so on. A feasible Monte Carlo tree search （MCTS） algorithm is proposed to solve the model. The effectiveness of the model and the algorithm is proved by a practical example， the related results of this study have been applied to the actual production of terminals， and the application effect is good. This research idea has reference significance for the research and realization of container terminal task planning and scheduling.

0 引 言

隨著集裝箱船的大型化，集裝箱碼頭單船每日集裝箱作業箱量由不到1 000 TEU轉為超過1 500 TEU，而集裝箱碼頭的裝卸設備并未根據箱量進行更新和重新設計。同時，國內各集裝箱碼頭的服務特性對集裝箱碼頭裝卸效率提出了更高的要求，如潮期、晚截關、零截關等要求碼頭更高效地進行生產組織。然而，集裝箱碼頭裝卸效率在設備和操作層面已很難提升，在不更換硬件設備的條件下如果想一步提升裝卸效率只能對裝卸工藝進行改進。邊裝邊卸（dual cycling，DC）工藝作為提升集裝箱碼頭裝卸效率的特殊裝卸工藝，成為各集裝箱碼頭針對船舶大型化普遍采取的工藝模式。

DC工藝是通過提升工藝循環過程中的有效作業占比，從而提升整個工藝作業效率的方法，具體指在滿足條件的情況下單個岸橋在一個循環中同時進行裝船和卸船作業的工藝流程。DC工藝具有能減少設備空駛從而減少能耗、提升效率的優點。DC工藝的應用需要滿足一定的作業條件：卸空甲板箱，同時在艙內留有兩列箱的空位;為岸橋同時配備裝卸船箱區和設備;有針對性地制訂設備和資源調度計劃。

集裝箱船配載問題是集裝箱碼頭的關鍵決策問題，針對此問題的研究已有很多：王鴻鵬[1]運用知識推理技術設計了集裝箱船自動配積載專家系統 ，并介紹了該系統的設計思想和實現原理;KANG等[2]和KIM等[3]分別提出了貪婪算法和樹型搜索算法求解配載問題;AMBROSINO等 [4]強調主貝計劃問題（master bay plan problem， MBPP），針對此問題提出基于規則方法的決策支持系統，使用約束滿足方法求得可行解;WINTER[5]提出考慮裝載的配載計劃，主要用于優化岸橋的作業量均衡;CHO[6]和BOTTER等 [7]對集裝箱船配載問題做了相應的假設和簡化，構建了線性規劃配載模型;AVRIEL等[8-9]建立了配載問題的0-1整數規劃模型，并設計了一種啟發式算法進行求解，大量仿真算例表明該算法求解效率和求解效果均較優;AMBROSINO等[10]以最小化總配載時間為優化目標，考慮箱型、船舶承載限制等實際作業約束建立了配載模型，但其將同一卸貨港的集裝箱配載于同一船貝的假設與實際操作有較大差別;SCIOMACHEN等[11]考慮三維裝箱問題（three-dimensional bin packing problem， 3D-BPP），以裝船總時間最短和岸橋利用率最高為目標優化配載計劃;PACINO等[12]和DELGADO等[13]將配載分為解決多港口MBPP和完成船箱位計劃兩個階段，首先通過解決MBPP處理不同港口集裝箱沖突，再將MBPP處理結果作為船箱位計劃的輸入，從而進一步明確每個集裝箱的具體船箱位;ZHAO等[14]在PACINO等[12]和DELGADO等[13]研究的基礎上，將配載問題分為取箱點計算問題和發箱決策問題，考慮出口箱在箱區內的分布以及具體作業要求，設計了箱組貝配載模型;PARREO等[15]引入了集裝箱平鋪的特殊工藝，考慮危險貨物集裝箱，設計了一種

貪婪隨機自適應搜索算法（greedy randomized adaptive search procedure， GRASP）求解船公司集裝箱預配計劃問題;SHEN等[16]設計了一種深度增強學習方法用于求解配載問題;COHEN等[17]把配載問題分為主計劃和詳細計劃兩個階段，設計了一種遺傳算法（genetic algorithm，GA），先解決主計劃問題，再在詳細計劃中為每個集裝箱分配具體位置; HELO等[18]針對集裝箱貨物屬性和集裝箱運輸的特點，提出了一種新的配載效果評價標準。綜上，目前對集裝箱船配載問題的研究著重考慮船舶穩性等與船公司預配計劃有關的決策因素，強調配載計劃的可行性，對集裝箱碼頭作業工藝、作業成本和作業效率的要求關注度不夠。另外，目前并無針對超大型集裝箱船配載特殊性的研究。

針對上述研究現狀，本文以基于DC工藝的集裝箱船配載問題作為研究對象，在超大型集裝箱船對集裝箱碼頭裝卸效率提出更高要求的背景下，以DC工藝作為集裝箱船裝卸作業工藝要求，通過分析集裝箱船在DC工藝下配載的重要決策因素構建配載模型，并設計算法求解此配載問題，通過算例分析證明所提出模型和算法的有效性。本文研究思路對研究集裝箱碼頭其他相關決策問題具有一定的參考意義。

1 模型構建

1.1 集裝箱船配載問題的特點

集裝箱船配載問題具有以下特點：求解維度較多，問題復雜，解空間較大。本文研究的配載問題涉及在場箱、船箱位、配載順序等3個維度，與常見的分配問題相比更復雜。問題約束多，采用傳統智能搜索算法求解獲得不可行解的情況較多。問題約束復雜，不可行解向可行解轉化的機制復雜，算法迭代過程中將不可行解處理為可行解的難度較大。在規定時間內至少需要獲得可行解。實際配載決策過程需要在限制時間內至少獲得較優的可行解，以保證生產的正常進行。

1.2 集裝箱船配載的主要決策因素

（1）場內翻箱。堆場內作業時如果先裝船的集裝箱位于后裝船的集裝箱正下方，則裝船過程中需要挪開位于上方的集裝箱，即翻箱。翻箱會增加設備的移動次數，降低裝卸效率。

（2）堆場設備移動。堆場設備移動主要指堆場主要作業設備——場橋大車在箱區貝位之間的水平移動。

（3）船舶穩性。為保證按配載計劃裝船后船舶的穩性，在制訂配載計劃時，按船舶穩性要求預先計算集裝箱船最優質量分布，最終集裝箱船各箱位實際配載的集裝箱質量盡量接近該箱位的預估質量，以保證最終配載計劃滿足船舶的適航性要求。

1.3 模型假設

（1）待配集裝箱數量等于預配船圖中給定的船舶貝內箱位數量。（2）各個待配集裝箱在堆場中的具體堆存位置已知。（3）各類型待配集裝箱的總數量與預配船各箱型箱位的總數量一致，即僅考慮箱型，存在可行的配載方案。（4）作業過程中機械設備均正常運行，不考慮故障或維修情況。（5）水平運輸車輛數量滿足岸橋裝卸的基本要求。（6）岸橋裝卸工藝為雙20英尺（或單40英尺，1英尺=0.304 8 m）裝卸工藝;場橋作業工藝為單箱作業工藝，即一次循環作業起吊一個集裝箱。

1.4 符號定義

模型維度：I為堆場內待配集裝箱的集合，i，i′∈I;J為待配載集裝箱船箱位的集合，j，j′∈J;L為船舶貝內箱位所屬列的集合，l，l′∈L;S為所有配箱次序的集合，s和s′為集裝箱的配載順序號，即s，s′∈S。

模型參數：Ti為0-1變量，表示集裝箱i的箱型，其中1表示集裝箱i為40英尺箱，0表示集裝箱i為20英尺箱;Di為0-1變量，其中1表示集裝箱i是高箱，0表示集裝箱i是平箱; Hl為船舶貝內第l列的高箱數量;Gi為船舶貝內第l列的平箱數量;

Mj表示船舶貝內箱位j所能承載的質量上限;Mj表示船舶貝內箱位j所能承載的質量下限;Ri表示集裝箱i的實際質量;Wj表示船舶貝內箱位j在預配階段被預分的質量;Vj為0-1變量，若船上的箱位j為墊腳位則用1表示，否則用0表示;δ用于表示在船舶貝內單列上下兩個箱位上重箱壓輕箱的質量差上限值;ξ用于表示岸橋在進行雙20英尺箱作業時，所要起吊的兩個集裝箱的質量差上限值;Wl表示船舶貝內單列所能承載的質量上限值;Yi表示集裝箱i在堆場內的貝位號;Bi表示集裝箱i在堆場內的箱區號;Cjj′為0-1變量，表示船箱位j與j′的作業位置關系，其中1表示船箱位j與j′的作業位置同屬于一個作業大貝，0表示船箱位j與j′的作業位置不屬于同一貝位;Pjj′為0-1變量，用于表示船舶貝內任意兩個箱位在豎直方向上的位置關系，若箱位j所處位置在箱位j′的正上方，則取值為1，否則為0; Qii′為0-1變量，用于表示在堆場箱區貝內的任意兩個集裝箱之間在豎直方向上的關系，若集裝箱i在堆場的位置處于集裝箱i′的正上方，則取值為1，否則為0;Sjl為0-1變量，若箱位j屬于l列，則取值為1，否則為0;Di表示集裝箱i所屬箱組的編號;Es表示第s個集裝箱配載順序的數字編號。

決策變量：Xisj為0-1決策變量，當第i個集裝箱以順序s配載到第j個船箱位時Xisj為1，否則為0。

輔助變量：αii′表示第i個集裝箱與第i′個集裝箱的發箱序號差;βii′為0-1變量，用于表示任意兩個集裝箱配載的先后順序關系，當第i個集裝箱比第i′個集裝箱先配載時，取值為1，否則為0;s表示相鄰順序配載的集裝箱所在區位的序號差;

φs為0-1變量，用于描述相鄰順序配載的集裝箱是否在同一個區位內，若這兩個集裝箱不在同一個區位內則取值為1，否則為0;

Ψjj′表示船箱位j與j′上所配載的集裝箱的質量差;ε1為每個配載船箱位上集裝箱實際質量與預配質量的差;ε2為實際配載的集裝箱質量與船箱位預配質量范圍差值的上限;ε3為實際配載的集裝箱質量與船箱位預配質量范圍差值的下限。

1.5 集裝箱船配載模型

基于DC工藝的集裝箱船配載總模型如下：

式（1）、（4）、（7）為目標函數，其中：式（1）為最小化堆場內無效翻箱數目標，式（4）為最小化堆場內設備移動次數目標，式（7）為最小化船箱位質量差以保證穩性目標。式（8）～（22）依次表示單列內高箱和平箱數量限制、船箱位質量限制、重壓輕質量限制、配載不懸空、單列總承載限制、作業順序限制和雙20英尺箱裝卸順序和質量限制約束。

2 算法設計

2.1 蒙特卡洛樹搜索算法概述

蒙特卡洛樹搜索（Monte Carlo tree search，MCTS）算法是一種在決策空間中隨機采樣并且根據結果構建搜索樹，在給定結果域中尋找到最佳決策的方法[19]。MCTS算法具有以下特點：無須針對具體問題設計求解過程或者啟發函數，但可以通過針對性的設計提升對特定問題的求解效率和求解效果;搜索樹異步擴展，在分支多（更復雜）的搜索問題中比傳統算法表現更好;在已取得可行解的情況下，算法可以隨時終止，不需要等待算法最終完成來獲得最優解;屬于樹搜索算法，可以用樹搜索算法的優化方法進行優化;算法有可并行性，可以通過并行設計優化求解效果。

MCTS算法包括選擇策略（selection policy）、擴展策略（expansion policy）、剪枝策略（pruning policy）、模擬策略（simulation policy）、回溯策略（backpropagation policy）等5個策略。通過把基于DC工藝的集裝箱船配載模型目標和約束轉換為樹搜索結構所支持的表現形式，并集成嵌入到樹搜索算法中，即可構建用于MCTS算法的基于DC工藝的集裝箱船配載搜索樹，對該配載問題進行決策。具體的算法流程見圖1。

2.2 配載問題處理

選擇策略。用于MCTS的選擇策略有多種，本文選擇UCT （upper confidence bound applied to trees）作為基于DC工藝的集裝箱船配載選擇策略：

式中：Xi為收益平均值，由模擬后獲得的目標函數值確定;ρ為搜索廣度系數。該選擇策略從搜索樹根節點開始，每一步選擇回報值較優的節點作為下一個節點。

擴展策略。擴展策略指當前節點更新后，搜尋下一步所有可能的決策，即搜索當前節點所有可能的葉子節點的過程。在配載搜索樹中，擴展策略為在當前配載狀態下找出下一步存在哪個集裝箱、具體以何種順序配載到哪個具體船箱位，且該步配載滿足前述配載模型中的所有約束。

剪枝策略。剪枝策略指在某些狀態下對無解或解明顯較差的節點作放棄處理。常用的剪枝方法有絕對修剪和相對修剪兩種。因為配載問題專業性較強，需要相關的專業知識積累，所以本文選擇使用配載領域知識進行針對性剪枝，修剪已知回報值較差的結果。具體剪枝策略為：根據配載約束限制，判斷保留當前節點是否仍可能存在較好的配載結果，若不存在較好的配載結果，則修剪當前節點。

模擬策略。模擬策略指在當前節點的可用葉子節點中隨機選擇，選擇原則為盡可能實現對現實世界的無偏估計。某葉子節點的總評價值Qi，對該總評價值進行最大值化處理。采用輪盤賭的方式，計算每個葉子節點被選擇的概率Qi，采樣概率為pi：

3 案例分析

為驗證所提出模型的有效性和算法的計算效果，本文選取寧波大榭招商國際集裝箱碼頭實際生產數據，用所提出的算法求解該基于DC工藝的集裝箱船配載結果，并對求解結果進行分析。

3.1 算例描述

該算例為某集裝箱船06H艙內配載數據。其預配信息和集裝箱場地分布已知，集裝箱分布于9個箱區內，總箱量為56 TEU。船箱位預配信息見圖2，集裝箱場地分布信息見圖3，深色區域表示待配載的集裝箱，集裝箱上數據為集裝箱質量。算例的實驗環境為：處理器Intel Core i7 CPU，四核2.70 GHz，16.00 GB內存，Win7 64位操作系統。

3.2 結果分析

利用上節提出的算法對算例進行求解，最終配載順序結果見圖4。堆場內配載區位順序依次為：1B→2D→4E→4D→8D→1G→1B→3E→2H→6H。場內翻箱次數為2;場橋大車總移動次數為9次，僅1B需場橋重復進入兩次，即非整取箱區情況只出現1次，所有船箱位所配載集裝箱均滿足質量約束，且符合重壓輕極限原則。其算法迭代的收斂曲線見圖5。

收斂曲線顯示，該算法在迭代至約1 400次時收斂至一個近似最優解，1 400次后適應度值呈現平穩狀態，并未發現更優解，驗證了算法的收斂性。

對同一算例重復計算10次，由于該算法為隨機算法，每次收斂情況和最優解不同，多次實驗搜索到最佳適應度值的平均迭代次數為1 389，平均最優適應度值0.392，平均運行時間137.2 s。算法在多次計算中得到的結果波動范圍在可接受范圍內，且收斂特性體現較為統一，說明MCTS算法在解決本問題中表現較為穩定，證明了MCTS算法的穩定性。同時，平均計算用時137.2 s體現了該算法較高的計算效率。以上求解結果分析和效果分析表明，MCTS算法在求解基于DC工藝的集裝箱船配載問題中具有較好的計算效果和較高的計算效率，計算穩定性在可接受范圍內。

因為配載問題有求解時間要求，所以針對不同規模算例給定一個求解時間上限，在限制計算時間的條件下求解算例。不同規模算例求解效果見表1（僅列舉多目標中更重要且易量化分析的目標函數）。

不同規模算例的求解結果顯示，針對較大規模的算例，MCTS算法也能在有限時間內獲得可接受的求解結果，翻箱率可以限制在7%以內。

在實際生產應用方面，本文提出的MCTS算法被改進集成于集裝箱碼頭智能配載系統中，已應用于上海港振東碼頭、明東碼頭和寧波大榭招商國際集裝箱碼頭實際生產，實際效果達到甚至超過人工配載水平，對5 000 TEU以上級別的集裝箱船（裝卸最高箱量超過3 000 TEU級別）可實現智能配載，大大減少人工決策負擔，提高了集裝箱碼頭智能化水平。

4 結 論

本文核心研究內容和成果總結如下：

（1）通過分析基于邊裝邊卸（DC）工藝的集裝箱船裝卸作業工藝特點，結合碼頭裝卸作業要求和配載的基本原則，以降低場內翻箱數、減少堆場設備移動次數、保證船舶穩性為決策目標，提出了基于DC工藝的集裝箱船配載模型。

（2）針對集裝箱船配載問題的特點，將問題進行轉換處理，應用目前人工智能領域廣泛采用的蒙特卡洛樹搜索（MCTS）算法，在使用更少人工經驗的條件下求解集裝箱船配載問題。

（3）使用提出的MCTS算法求解實際生產中的基于DC工藝的集裝箱船配載問題算例，驗證了算法的收斂性、有效性。

綜上所述，本文所提出的針對超大型集裝箱船DC工藝下的配載問題的模型和相應算法，可以有效解決基于DC工藝的集裝箱船艙內配載這一復雜規劃問題。從理論研究角度看，該研究思路和方法對于根據實際問題特性建模求解特殊的復雜混合規劃問題有一定的借鑒意義;從應用研究角度看，該研究對實際生產作業中超大型集裝箱船配載計劃的制訂以及集裝箱碼頭智能計劃調度均具有實際應用價值。

參考文獻：

[1]王鴻鵬. 基于知識的集裝箱船自動配積載專家系統[J]. 上海海事大學學報， 2002， 23（1）： 46-49.

[2]KANG J G， KIM Y D. Stowage planning in maritime container transportation[J]. Journal of the Operational Research Society， 2002， 53（4）： 415-426. DOI： 10.1057/palgrave.jors.2601322.

[3]KIM K H， KANG J S， RYU K R. A beam search algorithm for the load sequencing of outbound containers in port container terminals[J]. OR Spectrum， 2004， 26（1）： 93-116. DOI： 10.1007/s00291-003-0148-0.

[4]AMBROSINO D， SCIOMACHEN A. A constraints satisfaction approach for master bay plans[J]. Maritime Engineering and Ports， 1998， 36： 155-164.

[5]WINTER T. Online and real-time dispatching problems[D]. Berlin： Technical University of Braunschweig， 1999.

[6]CHO D W. Development of a methodology for containership load planning[D]. Oregon： Oregon State University， 1984.

[7]BOTTER R C， BRINATI M A. Stowage container planning： a model for getting an optimal solution[C]//7th International Conference on Computer Applications in the Automation of Shipyard Operation and Ship Design. IFIP Transactions B： Computer Applications in Technology， 1992： 217-229.

[8]AVRIEL M， PENN M. Exact and approximate solutions of the container ship stowage problem[J]. Computers & Industrial Engineering， 1993， 25： 271-274. DOI： 10.1016/0360-8352（93）90273-Z.

[9]AVRIEL M， PENN M， SHPIRER N， et al. Stowage planning for container ships to reduce the number of shifts[J]. Annals of Operations Research， 1998， 76： 55-71. DOI： 10.1023/A：1018956823693.

[10]AMBROSINO D， SCIOMACHEN A， TANFANI E. Stowing a containership： the master bay plan problem[J]. Transportation Research A， 2004， 38（2）： 81-99. DOI： 10.1016/j.tra.2003.09.002.

[11]SCIOMACHEN A， TANFANI E. A 3D-BPP approach for optimizing stowage plans and terminal productivity[J]. European Journal of Operational Research， 2007， 183： 1433-1446. DOI： 10.1016/j.ejor.2005.11.067.

[12]PACINO D， DELGADO A， JENSEN R M， et al. Fast generation of near-optimal plans for eco-efficient stowage of large container vessels[C]//Proceedings of the Second International Conference on Computational Logistics， 2011. Berlin， Heidelberg： Springer-Verlag， ICCL11： 286-301. DOI： 10.1007/978-3-642-24264-9_22.

[13]DELGADO A， JENSEN R M， JANSTRUP K， et al. A constraint programming model for fast optimal stowage of container vessel bays[J]. European Journal of Operational Research， 2012， 220： 251-261. DOI： 10.1016/j.ejor.2012.01.028.

[14]ZHAO Ning， MI Weijian， MI Chao， et al. Study on vessel slot planning problem in stowage process of outbound containers[J]. Journal of Applied Sciences， 2013， 13（20）： 26-43. DOI： 10.3923/jas.2013.4278.4285.

[15]PARREO F ， PACINO D ， ALVAREZ-VALDES R . A GRASP algorithm for the container stowage slot planning problem[J]. Transportation Research Part E： Logistics and Transportation Review， 2016， 94： 141-157. DOI： 10.1016/j.tre.2016.07.011.

[16]SHEN Yifan， ZHAO Ning， XIA Mengjue， et al. A deep Q-learning network for ship stowage planning problem[J]. Polish Maritime Research， 2017， 24（s1）. DOI： 10.1515/pomr-2017-0111.

[17]COHEN M W， COELHO V N， DAHAN A， et al. Container vessel stowage planning system using genetic algorithm[C]//European Conference on the Applications of Evolutionary Computation. Springer， Cham： Applications of Evolutionary Computation， 2017： 557-572. DOI： 10.1007/978-3-319-55849-3_36.

[18]HELO P， PAUKKU H， SAIRANEN T. Containership cargo profiles， cargo systems， and stowage capacity： key performance indicators[J]. Maritime Economics & Logistics， 2018： 1-21. DOI： 10.1057/s41278-018-0106-z.

[19]BROWNE C B， POWLEY E， WHITEHOUSE D， et al. A survey of Monte Carlo tree search methods[J]. IEEE Transactions on Computational Intelligence & AI in Games， 2012， 4（1）： 1-43. DOI： 10.1109/TCIAIG.2012.2186810.

（編輯 賈裙平）