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

　　摘要：針對(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)

　　《物流技術(shù)與應(yīng)用》(月刊)創(chuàng)刊于1996年，由北京科技大學(xué)主辦。本刊是物流行業(yè)知名的精品名刊;廣泛報(bào)道物流熱點(diǎn)、實(shí)用技術(shù)、經(jīng)典案例、最新信息。

　　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)化求解效果。