金健 宓為建 夏孟玨

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

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

中圖分類號(hào)： U691.7

文獻(xiàn)標(biāo)志碼： 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 引 言

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

DC工藝是通過提升工藝循環(huán)過程中的有效作業(yè)占比，從而提升整個(gè)工藝作業(yè)效率的方法，具體指在滿足條件的情況下單個(gè)岸橋在一個(gè)循環(huán)中同時(shí)進(jìn)行裝船和卸船作業(yè)的工藝流程。DC工藝具有能減少設(shè)備空駛從而減少能耗、提升效率的優(yōu)點(diǎn)。DC工藝的應(yīng)用需要滿足一定的作業(yè)條件：卸空甲板箱，同時(shí)在艙內(nèi)留有兩列箱的空位;為岸橋同時(shí)配備裝卸船箱區(qū)和設(shè)備;有針對(duì)性地制訂設(shè)備和資源調(diào)度計(jì)劃。

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

貪婪隨機(jī)自適應(yīng)搜索算法（greedy randomized adaptive search procedure， GRASP）求解船公司集裝箱預(yù)配計(jì)劃問題;SHEN等[16]設(shè)計(jì)了一種深度增強(qiáng)學(xué)習(xí)方法用于求解配載問題;COHEN等[17]把配載問題分為主計(jì)劃和詳細(xì)計(jì)劃兩個(gè)階段，設(shè)計(jì)了一種遺傳算法（genetic algorithm，GA），先解決主計(jì)劃問題，再在詳細(xì)計(jì)劃中為每個(gè)集裝箱分配具體位置; HELO等[18]針對(duì)集裝箱貨物屬性和集裝箱運(yùn)輸?shù)奶攸c(diǎn)，提出了一種新的配載效果評(píng)價(jià)標(biāo)準(zhǔn)。綜上，目前對(duì)集裝箱船配載問題的研究著重考慮船舶穩(wěn)性等與船公司預(yù)配計(jì)劃有關(guān)的決策因素，強(qiáng)調(diào)配載計(jì)劃的可行性，對(duì)集裝箱碼頭作業(yè)工藝、作業(yè)成本和作業(yè)效率的要求關(guān)注度不夠。另外，目前并無針對(duì)超大型集裝箱船配載特殊性的研究。

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

1 模型構(gòu)建

1.1 集裝箱船配載問題的特點(diǎn)

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

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

（1）場內(nèi)翻箱。堆場內(nèi)作業(yè)時(shí)如果先裝船的集裝箱位于后裝船的集裝箱正下方，則裝船過程中需要挪開位于上方的集裝箱，即翻箱。翻箱會(huì)增加設(shè)備的移動(dòng)次數(shù)，降低裝卸效率。

（2）堆場設(shè)備移動(dòng)。堆場設(shè)備移動(dòng)主要指堆場主要作業(yè)設(shè)備——場橋大車在箱區(qū)貝位之間的水平移動(dòng)。

（3）船舶穩(wěn)性。為保證按配載計(jì)劃裝船后船舶的穩(wěn)性，在制訂配載計(jì)劃時(shí)，按船舶穩(wěn)性要求預(yù)先計(jì)算集裝箱船最優(yōu)質(zhì)量分布，最終集裝箱船各箱位實(shí)際配載的集裝箱質(zhì)量盡量接近該箱位的預(yù)估質(zhì)量，以保證最終配載計(jì)劃滿足船舶的適航性要求。

1.3 模型假設(shè)

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

1.4 符號(hào)定義

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

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

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

決策變量：Xisj為0-1決策變量，當(dāng)?shù)趇個(gè)集裝箱以順序s配載到第j個(gè)船箱位時(shí)Xisj為1，否則為0。

輔助變量：αii′表示第i個(gè)集裝箱與第i′個(gè)集裝箱的發(fā)箱序號(hào)差;βii′為0-1變量，用于表示任意兩個(gè)集裝箱配載的先后順序關(guān)系，當(dāng)?shù)趇個(gè)集裝箱比第i′個(gè)集裝箱先配載時(shí)，取值為1，否則為0;s表示相鄰順序配載的集裝箱所在區(qū)位的序號(hào)差;

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

Ψjj′表示船箱位j與j′上所配載的集裝箱的質(zhì)量差;ε1為每個(gè)配載船箱位上集裝箱實(shí)際質(zhì)量與預(yù)配質(zhì)量的差;ε2為實(shí)際配載的集裝箱質(zhì)量與船箱位預(yù)配質(zhì)量范圍差值的上限;ε3為實(shí)際配載的集裝箱質(zhì)量與船箱位預(yù)配質(zhì)量范圍差值的下限。

1.5 集裝箱船配載模型

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

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

2 算法設(shè)計(jì)

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

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

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

2.2 配載問題處理

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

式中：Xi為收益平均值，由模擬后獲得的目標(biāo)函數(shù)值確定;ρ為搜索廣度系數(shù)。該選擇策略從搜索樹根節(jié)點(diǎn)開始，每一步選擇回報(bào)值較優(yōu)的節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)。

擴(kuò)展策略。擴(kuò)展策略指當(dāng)前節(jié)點(diǎn)更新后，搜尋下一步所有可能的決策，即搜索當(dāng)前節(jié)點(diǎn)所有可能的葉子節(jié)點(diǎn)的過程。在配載搜索樹中，擴(kuò)展策略為在當(dāng)前配載狀態(tài)下找出下一步存在哪個(gè)集裝箱、具體以何種順序配載到哪個(gè)具體船箱位，且該步配載滿足前述配載模型中的所有約束。

剪枝策略。剪枝策略指在某些狀態(tài)下對(duì)無解或解明顯較差的節(jié)點(diǎn)作放棄處理。常用的剪枝方法有絕對(duì)修剪和相對(duì)修剪兩種。因?yàn)榕漭d問題專業(yè)性較強(qiáng)，需要相關(guān)的專業(yè)知識(shí)積累，所以本文選擇使用配載領(lǐng)域知識(shí)進(jìn)行針對(duì)性剪枝，修剪已知回報(bào)值較差的結(jié)果。具體剪枝策略為：根據(jù)配載約束限制，判斷保留當(dāng)前節(jié)點(diǎn)是否仍可能存在較好的配載結(jié)果，若不存在較好的配載結(jié)果，則修剪當(dāng)前節(jié)點(diǎn)。

模擬策略。模擬策略指在當(dāng)前節(jié)點(diǎn)的可用葉子節(jié)點(diǎn)中隨機(jī)選擇，選擇原則為盡可能實(shí)現(xiàn)對(duì)現(xiàn)實(shí)世界的無偏估計(jì)。某葉子節(jié)點(diǎn)的總評(píng)價(jià)值Qi，對(duì)該總評(píng)價(jià)值進(jìn)行最大值化處理。采用輪盤賭的方式，計(jì)算每個(gè)葉子節(jié)點(diǎn)被選擇的概率Qi，采樣概率為pi：

3 案例分析

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

3.1 算例描述

該算例為某集裝箱船06H艙內(nèi)配載數(shù)據(jù)。其預(yù)配信息和集裝箱場地分布已知，集裝箱分布于9個(gè)箱區(qū)內(nèi)，總箱量為56 TEU。船箱位預(yù)配信息見圖2，集裝箱場地分布信息見圖3，深色區(qū)域表示待配載的集裝箱，集裝箱上數(shù)據(jù)為集裝箱質(zhì)量。算例的實(shí)驗(yàn)環(huán)境為：處理器Intel Core i7 CPU，四核2.70 GHz，16.00 GB內(nèi)存，Win7 64位操作系統(tǒng)。

3.2 結(jié)果分析

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

收斂曲線顯示，該算法在迭代至約1 400次時(shí)收斂至一個(gè)近似最優(yōu)解，1 400次后適應(yīng)度值呈現(xiàn)平穩(wěn)狀態(tài)，并未發(fā)現(xiàn)更優(yōu)解，驗(yàn)證了算法的收斂性。

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

因?yàn)榕漭d問題有求解時(shí)間要求，所以針對(duì)不同規(guī)模算例給定一個(gè)求解時(shí)間上限，在限制計(jì)算時(shí)間的條件下求解算例。不同規(guī)模算例求解效果見表1（僅列舉多目標(biāo)中更重要且易量化分析的目標(biāo)函數(shù)）。

不同規(guī)模算例的求解結(jié)果顯示，針對(duì)較大規(guī)模的算例，MCTS算法也能在有限時(shí)間內(nèi)獲得可接受的求解結(jié)果，翻箱率可以限制在7%以內(nèi)。

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

4 結(jié) 論

本文核心研究內(nèi)容和成果總結(jié)如下：

（1）通過分析基于邊裝邊卸（DC）工藝的集裝箱船裝卸作業(yè)工藝特點(diǎn)，結(jié)合碼頭裝卸作業(yè)要求和配載的基本原則，以降低場內(nèi)翻箱數(shù)、減少堆場設(shè)備移動(dòng)次數(shù)、保證船舶穩(wěn)性為決策目標(biāo)，提出了基于DC工藝的集裝箱船配載模型。

（2）針對(duì)集裝箱船配載問題的特點(diǎn)，將問題進(jìn)行轉(zhuǎn)換處理，應(yīng)用目前人工智能領(lǐng)域廣泛采用的蒙特卡洛樹搜索（MCTS）算法，在使用更少人工經(jīng)驗(yàn)的條件下求解集裝箱船配載問題。

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

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

參考文獻(xiàn)：

[1]王鴻鵬. 基于知識(shí)的集裝箱船自動(dòng)配積載專家系統(tǒng)[J]. 上海海事大學(xué)學(xué)報(bào)， 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.

（編輯 賈裙平）