以自動化碼頭為中心的船舶配載優(yōu)化

丁 一，王聰

（上海海事大學物流研究中心，上海 201306）

0 引言

在全球經(jīng)濟一體化的大趨勢下，各國集裝箱貨物的海運量呈爆發(fā)式增長，世界集裝箱船隊的數(shù)量也在不斷增加，船舶也逐漸向大型化、專業(yè)化和標準化發(fā)展，一方面提高了船公司的規(guī)模效益，另一方面給碼頭帶來了更大的挑戰(zhàn)，傳統(tǒng)集裝箱碼頭也正逐步向半自動化和全自動化過渡。

自動化碼頭在傳統(tǒng)碼頭的基礎上，優(yōu)化了工藝布局。如圖1 所示，自動化碼頭將傳統(tǒng)碼頭平行于海岸線的堆場箱區(qū)布局改進成垂直于海岸線的堆場箱區(qū)布局，同時在每個箱區(qū)增設了固定的發(fā)箱點，解決了傳統(tǒng)碼頭發(fā)箱區(qū)域規(guī)劃紊亂、發(fā)箱效率低下的問題。在堆場設備上，自動化碼頭采用了軌道吊（Rail-Mounted Gantry crane，RMG），替代了傳統(tǒng)碼頭的輪胎吊（Rubber-Tyred Gantry crane，RTG），RTG 可以跨箱區(qū)作業(yè)，但在多個RTG 作業(yè)時，容易在公共作業(yè)區(qū)域發(fā)生沖突，而RMG則是各箱區(qū)專用，發(fā)生的沖突較少。

圖1 傳統(tǒng)碼頭與自動化碼頭箱區(qū)布局Fig.1 Block layouts of traditional terminal and automated terminal

在當今碼頭集裝箱貨物運輸?shù)母鱾€流程中，配載作為其中的核心環(huán)節(jié)之一，對自動化碼頭的作業(yè)效率和安全、船舶在港時間以及貨方收益等方面都有著直接影響。配載作業(yè)流程如圖2 所示，一般分為兩個階段：第一階段是船舶公司制定的預配載計劃（分類/詳細的預配載箱位圖）；第二階段是將預配載計劃作為輸入數(shù)據(jù)，由碼頭運營商制定的碼頭配載計劃。

圖2 配載作業(yè)流程Fig.2 Flow chart of stowage operation

1 相關工作

目前大部分的配載優(yōu)化研究主要是從船公司和碼頭這兩個方面考慮的。

船公司方面注重如何減少多港口運輸裝卸所導致的翻箱問題以及船舶航行中的安全問題，如計明軍等［1］圍繞配載方式進行分析，總結四種配載方式在船舶穩(wěn)性、強度和吃水差等方面的優(yōu)缺點，以此來分析減少翻箱率的方法；而樂美龍等［2］考慮翻箱和橋吊的作業(yè)時間，并以此建立整數(shù)規(guī)劃模型，使得翻箱次數(shù)最少和橋吊工作時間跨度最小。

在考慮船舶靠泊時間成本因素后，Serban 等［3］在待卸集裝箱數(shù)量和箱區(qū)的初始狀態(tài)已知的情況下，以最小化場橋的搬運時間總和為目標，利用遺傳算法確定集裝箱配載計劃；而田維等［4］研究船舶裝箱排序問題，將最小化裝船時間以及翻倒箱時間成本作為目標，對不同規(guī)模案例進行求解，獲得問題的精確解；Roberti等［5］則在滿足許多操作限制的同時，盡量減少在港口裝卸集裝箱的時間，使得集裝箱最大限度地減少不必要的配載作業(yè)。

為了提高集裝箱航線動態(tài)裝載自動調(diào)度的能力，Wang［6］提出了一種基于關聯(lián)規(guī)則信息的集裝箱航線動態(tài)裝載自動調(diào)度方法；鄭斐峰等［7］針對翻箱費用和堆棧使用費用，以船舶裝載穩(wěn)定性作為約束條件，求得最小化費用的精確解；黃森佳等［8］綜合考慮集裝箱船舶縱向強度、岸橋作業(yè)安全距離和集裝箱倒箱量對裝船作業(yè)時間的影響，構建了以裝船作業(yè)時間最短為目標的配載優(yōu)化模型，引入岸橋作業(yè)均衡參數(shù)，并使用遺傳算法對模型進行求解；孫俊清等［9］以最小化集裝箱班輪在所有停靠港口的總倒箱量為目標，將船舶穩(wěn)性作為約束條件，使用改進的遺傳算法進行求解，并通過仿真實驗比較了兩種配載方案。

碼頭方面考慮裝船作業(yè)時間的縮短以及配載結果保證船舶航行安全，如：黎明等［10］結合集裝箱的裝載位置，以集裝箱堆場的翻箱率、船舶卸載時的翻箱率以及裝船后的穩(wěn)性為目標，建立了裝船順序的多目標規(guī)劃模型；張兆民［11］通過“關鍵相鄰柜口”的配載計劃優(yōu)化、作業(yè)拖車數(shù)量的增加和分級堆場堆存等操作策略的執(zhí)行，可有效控制“關鍵相鄰柜口”的作業(yè)時間，縮短船舶在港作業(yè)時間；?；垤`等［12］以翻箱問題為切入點，致力于保證配載計劃完成的前提下，建立三種提箱順序優(yōu)化策略來達到翻箱量最小的目標；Zhao 等［13］考慮堆場周轉、輪胎吊跨箱區(qū)作業(yè)和輪胎吊移動，基于配載原理和約束，建立多目標優(yōu)化模型，建立蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）方法，根據(jù)搜索樹設計可拓、可選等5 個步驟及相應策略；李隋凱等［14］針對帶中轉排的自動化碼頭出口箱進箱選位問題，提出了一種兩倍狀態(tài)多階段動態(tài)規(guī)劃算法；周宇濤等［15］通過運用邏輯算法，設置配載策略和參數(shù)，快速進行深度運算提高配載精度，更好地滿足船公司差異化配載要求。

兩個角度研究的考慮因素、模型和方法如表1所示。

表1 不同角度船舶配載考慮因素、模型和方法對比Tab.1 Comparison of ship stowage considerations，models and methods from different perspectives

通過上述的文獻分析可知，目前大多數(shù)的研究集中于從船公司的角度出發(fā)，考慮常規(guī)約束（吃水差、穩(wěn)性和船體強度約束等）、翻箱問題和裝船時間等，從碼頭角度出發(fā)的研究較少，考慮的也多是翻箱問題、堆場堆存問題和配載裝船時間等；但由于自動化碼頭箱區(qū)的發(fā)箱點固定，需要保證各設備的合理高效使用，避免出現(xiàn)設備等待擁擠的情況，只考慮這些問題無法保證集裝箱的高效裝卸，也無法最大化利用自動化碼頭的設備資源。因此，本文在考慮常規(guī)約束的基礎下，引入箱區(qū)作業(yè)均衡性這一因素，從碼頭的角度出發(fā)，對自動化碼頭的裝船配載作業(yè)來進行分析研究。

2 問題描述

從自動化碼頭的角度來說，配載問題一般可以分成三個子問題。結合右側圖3 自動化碼頭配載作業(yè)圖來看，第一個是集裝箱由外集卡裝載通過閘門，進入堆場箱區(qū)，在哪個箱區(qū)箱位落位的箱位問題；第二個是堆場待裝集裝箱裝船的先后順序問題，即將集裝箱從堆場運至岸側橋吊工作區(qū)的先后順序問題；最后一個是集裝箱分配的船箱位問題，即集裝箱在船上放置的位置問題。從位置①-②-③-④-⑤-⑥，即算完成配載計劃中一個待裝集裝箱的裝船作業(yè)任務。

圖3 配載作業(yè)圖Fig.3 Stowage operation diagram

首先，對于集裝箱的箱區(qū)箱位問題來說，無非就是如何極大化地方便裝船作業(yè)，并且充分利用到堆場的自動化設備資源，確保在裝船作業(yè)過程中設備閑置率較低，提升堆場集裝箱作業(yè)效率。

其次，是裝船先后順序問題，顧名思義就是決定堆場箱區(qū)待裝集裝箱裝載到運輸船舶的排序問題。在裝船作業(yè)順序問題上，不得不提到翻箱問題，裝船過程中某些集裝箱存放在箱區(qū)的其他集裝箱下方，由于待裝船舶的到來，如果下方集裝箱需要優(yōu)先提箱，則會先移動該集裝箱的上方集裝箱，再提取下方的集裝箱。具體的翻箱過程可結合圖4，描述如下：堆場箱區(qū)集裝箱i位于同貝同列不同層的集裝箱j的上方，任務1 是將箱區(qū)集裝箱i由A 點運輸至船舶B 點上，任務2 是將箱區(qū)集裝箱j由C 點運輸至船舶D 點上，由于配載船圖上顯示集裝箱i在船舶的箱位仍位于集裝箱j的上方，所以要先執(zhí)行任務2，而且需要先將集裝箱i移動到箱區(qū)其他位置，這就形成了一次翻箱。

圖4 翻箱示意圖Fig.4 Schematic diagram of rehandle

而對于集裝箱分配的船箱位問題，就是解決集裝箱離場后的去處，即安排在哪一船舶箱位的問題，以便于在下一個卸貨港減少翻箱量，快速完成卸貨任務。

從圖5可以得知，配載問題作業(yè)時間是由翻箱時間、RMG提箱時間、自動牽引車（Automated Guided Vehicle，AGV）運輸時間和橋吊（Quay Crane，QC）作業(yè)時間組成的。配載問題的目標在于減少從箱區(qū)箱位到船舶箱位的作業(yè)時間，從而減少船舶在港的停留時間，節(jié)約成本。

圖5 配載流程Fig.5 Flow chart of stowage

另外，在自動化碼頭堆場中，如果同一時間段內(nèi)箱區(qū)的裝卸作業(yè)量相差過大時，就會導致箱區(qū)作業(yè)不均衡問題：一方面，對于裝卸量偏大的箱區(qū)，這些箱區(qū)的軌道吊連續(xù)工作時間過長，軌道吊的故障率上升，而且由于箱區(qū)的軌道吊作業(yè)能力有限，一旦提存箱的指令過于集中，可能會導致軌道吊作業(yè)沖突；另一方面，對于裝卸量偏小的箱區(qū)，閑置的軌道吊沒有得到充分利用，單位成本上升。因此，對于箱區(qū)作業(yè)量均衡的研究很有必要。

3 模型建立

3.1 參數(shù)

i，j為待裝集裝箱號，i=1，2，…，I，j=1，2，…J；k為貝位號，k=1，2，…，K；c為列號，c=1，2，…，C；r為層號，r=1，2，…，R；b1為箱區(qū)編號，b1=1，2，…，B1；b2為箱區(qū)區(qū)塊編號，b2=1，2，…，B2；b3為小箱區(qū)編號，b3=1，2，…，B3；b為箱區(qū)具體編號，b=(b1，b2，b3)；p為待裝集裝箱的船箱位，p=1，2，…，P；εp為箱位p的開始裝箱時間；U(p)為位于船舶箱位p(k，c，r)同貝同列上一層p(k，c，r+1)的箱位；t為表示t-1到t的時間間隔，t=1，2，…，T，?t∈T；wi為集裝箱i的重量；nbt為t時間段內(nèi)箱區(qū)b已完成場到船任務的集裝箱數(shù)量；Δi為與集裝箱i同一堆棧的上層集裝箱集合；α為箱區(qū)一個待裝集裝箱不考慮翻箱的場橋平均作業(yè)時間（場橋就位和取箱平均時間）；βbt為t時間段內(nèi)箱區(qū)b作業(yè)量與各箱區(qū)平均作業(yè)量的差值比例值，其計算式為βbt=為t時間段內(nèi)所有箱區(qū)集裝箱作業(yè)量的平均值；ρ（ρ>0）為箱區(qū)作業(yè)不均衡判定比例值；σ1為堆場箱區(qū)一次翻箱時間；σ2為不均衡箱區(qū)的集裝箱單位等待懲罰時間；W為船舶貝位中單列允許的集裝箱最大載重量；τip為集裝箱i從場箱位到船舶箱位p(k，c，r)的水平運輸時間；BLTip為安排到船箱位p的在場箱i在箱區(qū)的離開時間，BLTip=εp-τip，其中?i∈N，p∈P；φbt為箱區(qū)b在時間段t的箱區(qū)作業(yè)量閾值；γip為二維0-1 變量，按待裝船集裝箱i是否符合預配圖要求從而配載到船舶所對應的船舶箱位p(k，c，r)，滿足為1，否則為0；θip為二維0-1 變量，若待裝船集裝箱i位于箱區(qū)b，則對應的元素為1，否則為0；M為一個極大的正數(shù)。

3.2 決策變量

xip為0-1 變量，集裝箱i從箱區(qū)離場，且被安排在船舶箱位p(k，c，r)則取1，否則為0；zij為0-1變量，當集裝箱i先于j離場時取1，否則為0，其中?i∈N，j∈Δi；δbt為0-1 變量，箱區(qū)b在t時間段的作業(yè)不均衡判定變量。δbt可表示為：

3.3 假設條件

假設條件如下：

1）目前船舶在碼頭的配載作業(yè)有單船配載作業(yè)和多船配載作業(yè)兩種，本文研究的是單船配載作業(yè)，且為了避免裝卸同時進行時設備沖突的增加以及翻箱數(shù)的上升，不考慮邊裝邊卸。

2）考慮到船公司一般會為特種箱安排特定的船箱位，配載會嚴格遵循，即使船公司沒有嚴格說明，也應遵循特種箱的一般裝載要求，因此本文僅考慮普通箱的配載。

3）本文的視角是從自動化碼頭出發(fā)的，預配載計劃由船方制定，卸船較為方便，且有臨時存放點可以加快卸船速度，因此本文研究的是碼頭方裝船配載方案的優(yōu)化。

4）配載是船方與碼頭方的協(xié)同工作，預配船圖需由船方提前給予碼頭方，了解集裝箱的各種信息，如尺寸大小等，且本文主要集中于堆場部分的研究，因此假設已知船舶預配總圖、橋吊作業(yè)計劃和待裝船的在場箱信息。

3.4 目標函數(shù)及約束

以f為目標函數(shù)，建立以集裝箱船舶裝船作業(yè)時間最小為目標的優(yōu)化模型，即：

其中：目標函數(shù)式（3）表示待裝集裝箱的離場數(shù)；式（4）表示翻箱次數(shù)；式（5）表示箱區(qū)作業(yè)不均衡判定次數(shù)。

另外，約束條件為：

其中：約束（6）～（7）為箱位限制約束，即一個集裝箱只能被安排到一個有且只有一個船舶箱位中；約束（8）表示待裝集裝箱離開箱區(qū)必須符合橋吊作業(yè)的時間安排；約束（9）表示位于同一堆棧不同層數(shù)的待裝集裝箱離開箱區(qū)的先后順序和翻箱的關系；約束（10）表示待裝集裝箱在船舶箱位緊挨著的下方有集裝箱即不能懸空；約束（11）表示待裝集裝箱與船舶貝位的匹配滿足預配要求；約束（12）表示船舶同貝同列集裝箱的裝載重量不能超過單列額定重量；約束（13）表示箱區(qū)集裝箱輕不壓重的堆垛要求；約束（14）表示確保離場集裝箱數(shù)量與待裝集裝箱數(shù)量相同；約束（15）表示箱區(qū)作業(yè)量限制，防止作業(yè)量過大；約束（16）表示決策變量類型。

4 基于固定集搜索算法的模型求解方法

集裝箱船舶配載問題本身是一個NP-hard 問題，同時通過上述模型部分描述可知該問題也是一個多目標、多約束的組合優(yōu)化問題。當船舶配載的集裝箱裝卸數(shù)量較少時，可以通過Cplex 計算出較優(yōu)解，但隨著船舶大型化的發(fā)展、自動化碼頭的不斷擴容以及自動化設備的更新迭代，集裝箱裝卸的數(shù)量一般是較大的，在這種情況下，運用Cplex 求解計算時間會較長或直接無法得出較優(yōu)解。因此，本文根據(jù)實際情況設計了基于固定集搜索（Fixed Set Search，F(xiàn)SS）算法的模型求解方法。

4.1 基本原理

固定集搜索算法是在貪婪隨機自適應搜索過程（Greedy Randomized Adaptive Search Procedure，GRASP）［16］中加入學習機制的一種算法，其重點在于避免專注于特定的較優(yōu)解，而是專注于這些解中的部分元素，通過固定多次出現(xiàn)在較優(yōu)解中的部分元素，致力于尋找固定部分元素組后的最優(yōu)解。

4.1.1 前提條件

使用固定集搜索算法需要滿足兩個前提條件：

前提一 通過固定所得解集中的部分解，可以降低正在搜索的解集空間大小，縮短目標函數(shù)完成時間；

前提二 有一部分高質(zhì)量的解集中的固定解容易識別，不需要通過過多的比對。

4.1.2 貪婪隨機自適應搜索

隨機組合箱區(qū)箱位和船舶箱位一一對應來形成解集，在匹配組合過程中，將已經(jīng)確定的組合放入一個集合中，直至該集合包含所有的待裝集裝箱的安排組合，檢查是否符合約束條件，符合再計算目標函數(shù)的結果，記錄目標解與解集，如此反復，每次排列完需要對解集進行檢索，是否為已有解集，是否是新的最優(yōu)解。

4.1.3 固定集

通過固定出現(xiàn)在大量較優(yōu)解集中相同的部分組合，形成固定的部分解的集合，以此來縮小搜索空間，當然固定集的形成需要滿足三個條件：

條件一 生成的固定集需要包含高質(zhì)量的解集的部分解；

條件二 一個生成的固定集至少能夠用來生成一個可行解；

條件三 固定集的規(guī)模是可以控制和變化的。

固定集具體的表現(xiàn)形式如圖6所示。

圖6 固定集表現(xiàn)形式Fig.6 Expression form of fixed set

圖6中，數(shù)字1～10代表箱區(qū)的待裝集裝箱，帶有相同特殊標記的區(qū)域代表堆場與船舶位置的固定，未帶標記的需要進行繼續(xù)組合搜索，船舶貝位中打“×”的代表位置已有其他集裝箱存放。從圖6得知，箱區(qū)1號集裝箱已固定存放至右側船舶貝位06 列14 層中，5 號集裝箱固定至該貝位04 列18 層中，6 號集裝箱固定至該貝位03 列20 層，9 號集裝箱固定至該貝位05列12層，10號集裝箱固定至該貝位07列20層。

4.1.4 算法終止準則

算法的終止判定條件如下：

1）首先，判斷最優(yōu)解搜索是否已經(jīng)停滯，如果是，將固定集規(guī)模大小設置為下一個值，需要注意的是如果當前固定集規(guī)模大小已經(jīng)是最大值，則返回最小值。

2）接著，更新固定集規(guī)模大小前，檢驗在尋找高質(zhì)量解時是否出現(xiàn)了停滯，如果停滯，即使用固定集所得解不是更優(yōu)解，再檢驗所得解是不是已知最優(yōu)解集合中的一個解，如果不是，且這個固定集規(guī)模大小還是最小值，則將當前固定集規(guī)模大小從固定集規(guī)模大小的集合中移除。

3）最后，當固定集規(guī)模大小的集合為空集時，則增加迭代次數(shù)，達到最大迭代次數(shù)時，終止算法。

4.2 算法設計

4.2.1 參數(shù)設置

船舶配載的相關數(shù)據(jù)包括：具體的箱區(qū)在場箱數(shù)量與可用船箱位數(shù)量，箱區(qū)在場箱的箱位位置與船舶箱位位置，集裝箱各自對應的卸貨港、貨物的尺寸以及船箱位的橋吊開始作業(yè)時間等，這些數(shù)據(jù)都是自動化碼頭和船方分別提供匹配出來的結果。因此解的表達式需要包含兩者的信息，采用第一行“i”行的碼頭箱區(qū)集裝箱信息與第二行“p”行的船舶箱位信息一一對應的方式來表示，解的具體表達形式如下：

碼頭與船方箱位信息的對應關系如圖7所示。

圖7 碼頭與船方箱位信息對應解的形式Fig.7 Corresponding solution form of terminal and ship’s slot information

4.2.2 搜索改進

由于貪婪隨機搜索的隨機性過強，計算時間可能較長，需對搜索方法進行改進。在搜索初始可行解時，使用隨機的集裝箱與船舶箱位匹配，擴大可行解的搜索范圍，對不滿足約束的解進行二次匹配，改為鄰域交換和平滑匹配（首尾依次匹配）。

根據(jù)實際情況，其實待裝集裝箱是有許多不同屬性的，如尺寸不同、卸貨港不同等，一般相近屬性的集裝箱是存放在較近的位置的，為了避免跨度較大，對所有的同貝同層不同列的待裝集裝箱進行劃分處理，將前一半歸為I 類，后一半歸為II類，基于預配載為初始參考解，如圖8 所示，將I類和II類分別進行鄰域交換和平滑匹配，對同類同貝同層不同列的集裝箱進行位置的交換，交換后的解仍然滿足預配和輕壓重約束，以此來尋找與預配結果持平或比預配更好的解。

圖8 箱位匹配Fig.8 Slot matching

4.3 基本步驟

4.3.1 參數(shù)定義

算法參數(shù)的具體定義如下：

P表示所有生成解（總體）的集合；Pn定義為n個最優(yōu)解的集合，Pn=Selectn(P)；D為最大迭代次數(shù)；Skn定義為從Pn隨機選取k個解的集合，Skn=Selectk(Pn)，Skn={S1，S2，…，Sk} ；B為從m個最優(yōu)生成解的集合Pm中任意選取一個隨機解B，其中，B=Select(Pm)，B={e1，e2，…}且B∈Pm，e1代表一個箱位安排；V代表待裝集裝箱總數(shù)；C(ex，S)為0-1 變量，如果ex屬于S為1，否則為0；O(ex，Skn)表 示ex在Skn中出現(xiàn)的次數(shù)，Sizes為固定集規(guī)模大小集合，Sizes[i]=|V|-，其中i為大于0 的整數(shù)，用來根據(jù)當前所得解對Sizes大小進行更改；F為能夠在搜索中使用固定集，具體的表達式為F=Fix(B，Skn，Sizes)，表示大小為Sizes、初始解B中在Skn中出現(xiàn)最多次的箱位安排；S表示使用固定集F而得到的解，S=RGF(F)；T表示生成解的目標函數(shù)值集合。

4.3.2 具體步驟

在對固定集搜索算法中的一些參數(shù)進行定義并得到基本解之后，就可以利用算法對基本解進行迭代優(yōu)化，首先獲得初始基本解，通過迭代得到初始可行解，最后通過迭代獲得能夠接受的最優(yōu)解。具體的迭代步驟如下：

步驟1 設置模型與算法參數(shù)，將箱位可安排集合設為Candidates，待裝集裝箱總數(shù)為V，確定最大迭代次數(shù)D，且初始迭代次數(shù)d=0，固定集集合為F，固定集大小集合為Sizes，固定集大小為Size，固定集大小影響參數(shù)為i，集合為I，且初始參數(shù)i=1，最大值為Imax，GRASP中的箱位交換初始次數(shù)為f=0，最大交換次數(shù)為fmax，解的集合為P。

步驟2 輸入初始基本解x0（船方提供的預配數(shù)據(jù)），當前解xf=x0。

步驟3 判斷當前解xf是否滿足堆場箱區(qū)作業(yè)量閾值和船舶單列最大重量約束，即判斷是否為可行解，是則進入步驟5，否則進入步驟4(GRASP)。

步驟4 進入步驟4.1；

步驟4.1 將同卸貨港同尺寸大小的集裝箱（箱位）作為同一類別集裝箱（箱位）進行處理，提取當前輸入數(shù)據(jù)的集裝箱的所有類別CC，在每一個類別中，提取該類別中的所有貝位CB和層數(shù)CT，進入步驟4.2；

步驟4.2 記錄層號CT中存在兩個及兩個以上集裝箱的層號為Tier，進入步驟4.3；

步驟4.3 隨機交換Tier中兩個集裝箱的位置，記錄f=f+1，得到新的箱位排列，生成當前解xf，返回步驟3。

步驟5 計算當前解xf的目標函數(shù)值Vf，其中Vf=Value(xf)，將各個目標函數(shù)值放入集合T，將當前解xf放入解的集合P，判斷是否f大于等于fmax，是則進入步驟6，否則返回步驟4。

步驟6 記錄迭代次數(shù)d=d+1，判斷當前迭代次數(shù)d是否大于等于最大迭代次數(shù)D：若是，則算法結束，比較各個最優(yōu)解BSd和最優(yōu)函數(shù)值BSVd，輸出在迭代D次之后的最終最優(yōu)解UBSd和最優(yōu)函數(shù)值UBSVd；否則進入步驟7。

步驟7 從n個最優(yōu)生成解的集合Pn中隨機選取k個解得到Skn，從m個最優(yōu)生成解的集合Pm中任意選取一個隨機解B，固定集大小為Sizes[i]，進入步驟8。

步驟8 利用F=Fix(B，Skn，Sizes)，確定固定集F，剔除Candidates中固定集F的箱位安排，即排除掉已經(jīng)確定位置的箱區(qū)箱位位置和船舶箱位位置，根據(jù)同卸貨港和箱位尺寸進行箱位安排生成解S，S=RGF(F)，進入步驟9。

步驟9 判斷當前解S是否滿足約束，即判斷是否為可行解：若是，進入步驟11；否則進入步驟10。

步驟10 進入步驟10.1；

步驟10.1 更新輸入數(shù)據(jù)的集裝箱的所有類別NCC，同一類別中提取更新后的所有貝位NCB和層數(shù)NCT，進入步驟10.2；

步驟10.2 記錄層號NCT中存在兩個及兩個以上集裝箱的層號為NewTier，進入步驟10.3；

步驟10.3 在NewTier中任選一個層號，計算該層待裝集裝箱數(shù)量num，選定劃分位置mod(num，2)，前一半鄰域交換，后一半平滑匹配，進行箱位交換，得到新的箱位排列，生成當前解S，返回步驟9。

步驟11 計算解S的目標函數(shù)值VS=Value(S)，將解S加入到生成解集合P，將VS與集合T中最小值Tmin比較：若VS更小，則i=i+1，且記錄當前最優(yōu)解BSd=S，最優(yōu)函數(shù)值為BSVd=VS，將VS加入T，進入步驟15；否則進入步驟12。

步驟12 判斷S是否為Pn或Pm中的一個解：若是，則i=i+1，進入步驟15；否則進入步驟13。

步驟13 判斷i是否為當前影響參數(shù)集合的最小值Tmin：若是，則從I中刪除當前i，進入步驟14；否則i=i+1，進入步驟15。

步驟14 判斷I是否為空集：若是，則f=0，返回步驟2；否則i=i+1，進入步驟15。

步驟15 判斷當前i是否大于Imax：若是，則i=Imin；否則i不變，返回步驟7。

5 算例分析

本文根據(jù)上海某集裝箱碼頭的實際配載數(shù)據(jù)進行分析，通過FSS與Cplex 的算例計算結果對比以及固定集搜索算法、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法、遺傳算法（Genetic Algorithm，GA）和蟻群優(yōu)化（Ant Colony Optimization，ACO）算法之間的算例計算結果分析，驗證本文所提模型與FSS 的有效性。實驗所使用的電腦配置為Windows 1064 位操作系統(tǒng)，8 GB 運行內(nèi)存，處理器為Inter Core i5-8265U，CPU 頻率為1.6 GHz，使用軟件為IBMI LOG Cplex Optimization Studio 12.2和Matlab 2018a。

5.1 數(shù)據(jù)說明

本文將上海洋山港某碼頭提供的配載數(shù)據(jù)作為實例研究，整理出6組規(guī)模不等的實例，詳細的數(shù)據(jù)說明如表2所示。其中，箱量是數(shù)據(jù)梳理后的待裝集裝箱數(shù)量，箱區(qū)數(shù)表示這些待裝集裝箱所屬的不同箱區(qū)數(shù)，LD 表示該組實例的待裝集裝箱在堆場箱區(qū)中最左下角的位置，RU表示該組實例的待裝集裝箱在堆場箱區(qū)中最右上角的位置，2D 表示同一實例中只有2 個集裝箱的堆棧數(shù)比例，3D 表示同一實例中只有3 個集裝箱的堆棧數(shù)比例。

表2 實例數(shù)據(jù)說明Tab.2 Data description of real instances

首先為了方便統(tǒng)計數(shù)據(jù)將時間段t設置為1 h，作為單位時間段，參考上海洋山深水港四期自動化碼頭的實際配載數(shù)據(jù)來確定模型的部分相關參數(shù)，設定箱區(qū)單位時間內(nèi)的最大作業(yè)箱量為20 箱，箱區(qū)一個待裝集裝箱不考慮翻箱的場橋平均作業(yè)時間即平均場橋就位和取箱時間為2 min，箱區(qū)的一個待裝集裝箱從堆場到橋吊工作區(qū)的水平運輸時間為3 min，箱區(qū)內(nèi)一次翻箱時間為3 min，箱區(qū)不平衡可能導致的集裝箱單位懲罰時間定為2 min。模型參數(shù)確定后，運用Cplex 對模型進行求解。鑒于問題復雜性較大，可能導致Cplex 無法求解，因此設定Cplex 的最大運行時間為1 h，同時設定算法的相關參數(shù)如下：最大迭代次數(shù)D=50，固定集大小的影響參數(shù)最大值Imax=10，GRASP中的箱位最大交換次數(shù)fmax=200。

5.2 實例結果分析

在參數(shù)ρ=0.5的情況下，F(xiàn)SS 與Cplex 的實例求解的最終解結果如表3所示。

表3 不同算法實例計算結果的對比Tab.3 Computational result comparison of different algorithms on real instances

表3 的實例計算結果包括翻箱量、不均衡程度、目標函數(shù)值和求解時間，在計算中，由于Cplex 求解模型的限制，將Cplex 的求解時間設定為1 h，求解結束后返回目標值，若超過1 h，則無最優(yōu)結果。首先，對Cplex 與所提算法兩者的求解時間作了對比，從表3 可以看出，箱量從100～600 箱的6 個實例中，所提算法的計算時間在18.7 s～161.6 s，而Cplex最短計算時間為178.1 s，仍超過了算法的最大計算時間，尤其箱量為600 時Cplex 計算時間超過了1 h，顯示無結果，相比之下FSS卻有著很好的求解結果和求解效率。相較于Cplex，F(xiàn)SS 求解的翻箱數(shù)和不均衡箱數(shù)都較小，實例A5 減少了最多的7 次翻箱，且實例A5 減少了最多的13 個不均衡箱數(shù)；FSS 的目標函數(shù)值一直是較小，最大差距74 min，只有規(guī)模較小的實例A1兩者計算的差距不大，最小差距42 min。綜上，不同規(guī)模的實例下，F(xiàn)SS 算法相較于Cplex，翻箱量和不均衡箱數(shù)分別平均減少了22.3%和11.7%，目標函數(shù)值平均優(yōu)化了6.5%。

5.3 不同算法對比

鑒于Cplex求解的時間較長且存在無法求解的情況，增加粒子群優(yōu)化（PSO）算法、遺傳算法（GA）和蟻群優(yōu)化（ACO）算法對案例的計算分析，與本文所提的固定集搜索算法進行比較，參數(shù)ρ取0.5，粒子群算法PSO 的種群規(guī)模取200，最大迭代次數(shù)為50，慣性權重為0.7189，加速常數(shù)為1.1503；遺傳算法的種群規(guī)模取200，最大迭代次數(shù)為50，以目標函數(shù)的倒數(shù)作為適應度值，交叉概率為0.9，變異概率為0.3；蟻群算法的種群規(guī)模取200，最大迭代次數(shù)為50，信息因子為1，期望因子為5，信息揮發(fā)因子為0.1。詳細的數(shù)據(jù)對比見表4。

從表4 可以看出，在箱量較小的案例中，各算法的四個指標差距不大，且在案例A1 中，遺傳算法的目標函數(shù)值最小為348 min，不均衡箱數(shù)和求解時間也是最低的，分別為16 箱和17.9 s；但隨著箱量的增加，翻箱次數(shù)和不均衡箱數(shù)的差距不斷拉大，固定集搜索算法的優(yōu)勢逐漸顯示出來，四個指標的值一直是最小值。總的來說，相較于其他三種算法，固定集搜索算法的穩(wěn)定性更好，在翻箱數(shù)和不均衡箱數(shù)的優(yōu)化上更優(yōu)，求解的質(zhì)量更高，目標函數(shù)值平均優(yōu)化了2.1%。

表4 不同算法的優(yōu)化結果對比Tab.4 Optimization result comparison of different algorithms

5.4 虛擬案例分析

鑒于實例數(shù)據(jù)缺少變化性，需要對實例的數(shù)據(jù)進行處理分組，增加一些不同情況下的虛擬案例進行分析研究。與此同時，為了更加方便直觀地了解港口的運作情況，根據(jù)洋山港四期提供的數(shù)據(jù)對自動化碼頭進行模擬布局，具體布局如圖9所示。

圖9 算例配載箱區(qū)圖Fig.9 Instance stowage block diagram

由圖9 可知，箱區(qū)的區(qū)域范圍是很大的，箱區(qū)從1 到B 有11個箱區(qū)，這11個箱區(qū)可以分成122個小箱區(qū)，如101就是箱區(qū)10 的第一個小箱區(qū)，根據(jù)距離待裝船舶的遠近對箱區(qū)進行分類編號，如表5所示。

表5 箱區(qū)距離編號Tab.5 Number of block distance

接下來，對實例進行如下處理，構成虛擬案例，進行多樣性分析：

1）重新安排同一實例中具有2 個和3 個待裝集裝箱的堆棧分布；

2）將實例中有2個和3個的集裝箱堆棧比例進行調(diào)整。

第一步，堆棧分布按照箱區(qū)距離待裝船舶的距離遠近進行正態(tài)分布處理，如圖10所示，橫坐標d表示箱區(qū)與待配載船只的距離，縱坐標代表那些待裝集裝箱的分布概率n，越靠近作業(yè)船舶的待裝集裝箱概率就越大，但n值也有最大值為M，用來避免集裝箱數(shù)量過多，碼頭負荷運作。隨著距離d變化的集裝箱分布概率n的正態(tài)分布函數(shù)表示為：

圖10 箱區(qū)待裝集裝箱正態(tài)分布Fig.10 Normal distribution of containers to be loaded in block

根據(jù)碼頭箱區(qū)集裝箱分布的實際情況，取μ為0、σ為，則M為1，將分布概率控制在區(qū)間［0，1］。

第二步，調(diào)節(jié)堆棧比例，堆棧配置所示如表6所示。

表6 堆棧配置Tab.6 Configuration of stacks

每組堆棧配置下進行兩次正態(tài)分布的待裝集裝箱安排，則每組實例如箱量為100 的A1 就有a1、a2、b1、b2、c1、c2 這6個虛擬案例分析，由于數(shù)組過多，取6 個虛擬案例的平均值作為每一組的比較數(shù)據(jù)，具體的計算結果如表7所示。

表7 虛擬案例計算結果Tab.7 Computational results of virtual instances

由表7 可知，虛擬案例將待裝集裝箱的堆場箱位集中在距離待裝船舶較近的箱區(qū)，四個指標數(shù)據(jù)都高于原本的實例數(shù)據(jù)，但差距不是很大。固定集搜索算法依舊優(yōu)于其他三種算法的計算，目標函數(shù)值平均減少了22 min，翻箱次數(shù)平均減少了16.1%，不均衡箱數(shù)最多減少了16 箱，求解時間平均減少了14.7 s。

6 結語

傳統(tǒng)碼頭與自動化碼頭在布局、設備與作業(yè)工藝等方面的不同，導致自動化碼頭在配載問題上需要更多考慮設備與場地的充分利用。為了減少碼頭的運營成本，快速完成配載工作，因此以最小化翻箱次數(shù)、箱區(qū)集裝箱作業(yè)量的不均衡程度和總裝船時間為目標，建立相應的配載優(yōu)化模型，設計固定集搜索算法進行求解，且分別通過與Cplex、粒子群算法、遺傳算法和蟻群算法的對比，驗證了本文所提固定集算法的高效性。與此同時，為了增加算例的多樣性，設置了虛擬案例，與另外三種算法相比，固定集搜索算法的不均衡箱數(shù)平均減少了19.3%，目標函數(shù)值即總裝船時間平均減少了22 min，求解時間平均減少了14.7 s。

綜上，無論是在求解效率還是在求解效果方面，本文所構建的自動化碼頭船舶配載混合整數(shù)規(guī)劃模型與固定集搜索算法都有較優(yōu)的配載結果，縮短了碼頭裝船時間與船舶靠泊時間，為后續(xù)不確定情況下的船舶配載優(yōu)化研究提供參考。