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

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

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

　　《物流技術與應用》(月刊)創刊于1996年，由北京科技大學主辦。本刊是物流行業知名的精品名刊;廣泛報道物流熱點、實用技術、經典案例、最新信息。

　　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算法具有以下特點：無須針對具體問題設計求解過程或者啟發函數，但可以通過針對性的設計提升對特定問題的求解效率和求解效果;搜索樹異步擴展，在分支多(更復雜)的搜索問題中比傳統算法表現更好;在已取得可行解的情況下，算法可以隨時終止，不需要等待算法最終完成來獲得最優解;屬于樹搜索算法，可以用樹搜索算法的優化方法進行優化;算法有可并行性，可以通過并行設計優化求解效果。