以自動化碼頭為中心的船舶配載優化

丁 一，王聰

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

0 引言

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

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

圖1 傳統碼頭與自動化碼頭箱區布局Fig.1 Block layouts of traditional terminal and automated terminal

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

圖2 配載作業流程Fig.2 Flow chart of stowage operation

1 相關工作

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

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

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

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

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

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

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

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

2 問題描述

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

圖3 配載作業圖Fig.3 Stowage operation diagram

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

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

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

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

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

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

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

3 模型建立

3.1 參數

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

3.2 決策變量

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

3.3 假設條件

假設條件如下：

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

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

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

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

3.4 目標函數及約束

以f為目標函數，建立以集裝箱船舶裝船作業時間最小為目標的優化模型，即：

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

另外，約束條件為：

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

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

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

4.1 基本原理

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

4.1.1 前提條件

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

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

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

4.1.2 貪婪隨機自適應搜索

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

4.1.3 固定集

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

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

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

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

固定集具體的表現形式如圖6所示。

圖6 固定集表現形式Fig.6 Expression form of fixed set

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

4.1.4 算法終止準則

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

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

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

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

4.2 算法設計

4.2.1 參數設置

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

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

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

4.2.2 搜索改進

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

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

圖8 箱位匹配Fig.8 Slot matching

4.3 基本步驟

4.3.1 參數定義

算法參數的具體定義如下：

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

4.3.2 具體步驟

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

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

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

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

步驟4 進入步驟4.1；

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

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

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

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

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

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

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

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

步驟10 進入步驟10.1；

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

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

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

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

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

步驟13 判斷i是否為當前影響參數集合的最小值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 算例分析

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

5.1 數據說明

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

表2 實例數據說明Tab.2 Data description of real instances

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

5.2 實例結果分析

在參數ρ=0.5的情況下，FSS 與Cplex 的實例求解的最終解結果如表3所示。

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

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

5.3 不同算法對比

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

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

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

5.4 虛擬案例分析

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

圖9 算例配載箱區圖Fig.9 Instance stowage block diagram

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

表5 箱區距離編號Tab.5 Number of block distance

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

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

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

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

圖10 箱區待裝集裝箱正態分布Fig.10 Normal distribution of containers to be loaded in block

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

第二步，調節堆棧比例，堆棧配置所示如表6所示。

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

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

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

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

6 結語

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

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