基于禁忌搜索算法的自動化集裝箱碼頭船舶配載研究

俞 宙，許冬敏，張 瓊，丁 一，林丹萍

（1.上海冠東國際集裝箱碼頭有限公司，上海 201306；2.上海外國語大學 賢達經濟人文學院，上海 201306；3.上海海事大學 物流研究中心，上海 201306；4.上海海事大學 物流工程學院，上海 201306）

引 言

船舶大型化和港口作業智能化趨勢下，集裝箱碼頭對船舶的裝卸作業效率提出了高難度要求。因此，如何有效地提高碼頭運作效率，縮短船舶在港作業時間便成了集裝箱碼頭亟待解決的問題。在新形勢下，傳統碼頭的運作模式已經難以適應未來趨勢的發展，世界大港均通過建造自動化碼頭解決該難題。

自動化集裝箱碼頭通過對作業計劃的優化的做法，解決作業過程中堆場沖突、岸橋作業效率低下等問題。碼頭通過將生產運營“事中控制”向“事前計劃”的轉變，極大地提高碼頭運營效率，使各項生產要素得到更加合理的配置。自動化碼頭作業計劃的核心問題包括：岸橋調度計劃、船舶配載計劃以及堆場作業計劃。本文將對船舶的自動配載問題進行研究。

船舶配載計劃是一個NP-Hard問題[1]，現有的文獻主要有船舶的預配計劃與碼頭的實配計劃研究。關于實配計劃的研究，Imai等（2006）[2]運用加權法對所建立的多目標配載整數規劃模型進行求解，并得到近似優解。Ambrosino（2006）[3]提出了一個基于三個層次的分層算法，以船舶的總裝載時間最短為目標，考慮重量、箱型尺寸、穩性等約束條件，選用熱那亞港的數據進行算例分析。Sciomachen等（2006）[4]運用三維裝箱方法，以裝船總時間和橋吊利用率為優化目標，考慮集裝箱和船舶的結構、作業約束，提出了一種優化建模方法。Ambrosino等（2009）[5]以最小化總裝載時間為目標，以船舶重量分布、箱型尺寸和穩性為約束，提出了一個三階段算法。首先將整船按區分配在場箱，以縮小搜索空間。其次建立各區裝載計劃的整數規劃模型。最后將局部搜索交換策略算法結合。álvarez等（2006）[6]充分考慮了翻箱作業、正面吊運輸、以及船上重量原則，應用禁忌搜索算法研究了碼頭以正面吊為裝卸設備的集裝箱船舶配載問題。Lee等（2009）[7]在研究配載問題前，對集裝箱堆場布局進行優化，運用整數規劃模型以及分支算法來對集裝箱堆場的布置問題進行求解。Ambrosino等（2010）[8]針對配載問題提出禁忌搜索算法的設計理念，并用啟發式和蟻群優化算法求解問題。楊杰敏等（2011）[9]研究了基于多項作業原則的配載優化問題，提出了3層規劃模型，重點研究堆場取箱作業，充分考慮重量原則、作業沖突原則，建立數學模型，采用分支定界進行求解。Delgado等（2012）[10]將配載問題分解為兩個階段，第一階段為主貝計劃，為集裝箱分配貝塊；第二階段為船槽分配階段，為貝塊中的集裝箱分配具體的箱位。Monaco等（2014）[11]研究了堆場裝卸設備為跨運車的集裝箱船舶實配問題，提出用兩步啟發式算法進行模型求解。何鋼等（2015）[12]構建了貝內配載問題的數學模型，設計了一種改進的混合遺傳算法，融入A*算法的啟發式搜索思想。并以某自動化碼頭為研究實例，對貝內配載問題進行求解。Francisco Parre?o等[13]研究了班輪船舶配載問題，提出了新的整數規劃模型和貪婪隨機自適應搜索算法，該方法能夠在1 s之內找到高效方案。

在集裝箱船舶配載研究方面，現有的研究文獻從碼頭角度對集裝箱裝船實配問題的研究甚少。同時，國內外學者對配載問題的研究重點大多集中在集裝箱與船箱位的位置對應關系，綜合考慮堆場作業沖突和作業過程中的翻箱等因素較少。因此，本文將從船舶配載作業均衡角度出發，對自動化集裝箱碼頭的配載優化問題展開研究工作。

1 問題描述

集裝箱實配是碼頭裝船作業的重要一環，是在需要裝船的集裝箱及其堆場位置已知的前提下，符合船方預配要求的同時綜合考慮堆場工藝、裝卸設備及翻箱等因素，尋求最優的配載決策，為堆場帶裝船集裝箱分配合理的船舶位置。裝船開工前，碼頭需制作配載計劃。配載計劃就是在預配船圖確定后，根據船艙箱位的配載規則進行實配的方案，由配載圖形式表示。

實配是帶復雜約束的多目標優化問題。制定配載計劃的已知信息包括船公司預配船圖、船舶現有積載信息、待裝船集裝箱信息以及碼頭設備資源狀況與裝卸工藝。碼頭制定配載計劃的核心是保證滿足泊位策劃制定的船期要求，盡可能保證橋吊作業計劃按原有時間開展，保證橋吊的連續作業。同時，減少堆場出箱沖突，并降低堆場裝船翻箱率，使配載圖既滿足船舶穩性、強度等船方要求，又滿足碼頭組織生產的效率要求,使得總的裝船速度最快。

通過對自動化集裝箱碼頭實際狀況的綜合考量，其制定配載計劃的決策目標主要包括最小化堆場翻箱量、最小化水平運輸距離及均衡堆場箱區間作業量。配載計劃需要同時滿足船方和碼頭的要求，在保證船舶適航性的同時提高作業效率。其制定需遵循滿足預配要求與碼頭實際作業要求原則。預配圖給出了船箱位預配位置要求和船舶結構等信息，要求配載保證船舶穩性、滿足船體強度要求、保證船舶吃水差及避免倒箱作業。同時需符合碼頭堆場取箱規則、符合碼頭單船作業計劃要求、盡可能保證作業路順利作業。

2 模型建立

2.1 模型假設

假定以下條件已知：

1）集裝箱船舶的結構和船箱位信息；

2）待配載集裝箱的信息（堆場位置、箱型、重量等級、箱號、目的港等）；

3）預配船圖信息；

4）橋吊開路計劃與作業計劃。

為便于建模，同時考慮問題求解的實現條件，做出以下合理假設：

1）港口機械設備配置合理，有足夠的碼頭作業機械保證配載效率不受影響，且無需考慮作業過程中機械設備的故障或維修情況；

2）待配出口箱數量不超過計劃可裝載的船箱位數量；

3）危險品箱、冷藏箱等特殊箱在船上的配載位置已設定，且不考慮墊腳箱；

4）不考慮不同箱型集裝箱作業工藝的不同且假定作業時間相同；

5）預配中已考慮船舶穩定性等指標。

2.2 參數定義

1）定義集合

N—堆場內所有待配集裝箱的集合，

P—船箱位的集合，p∈P,p≡ (x,r,y)；

Ψ(l)—屬于船棧l的船箱位集合，ψ(l) ?P；

D—配載中涉及的船艙的集合，D= ｛ 1 ,…d｝；

?(d)—屬于船艙d的船箱位集合，?(d) ?P；

cp—預配中規定船箱位p可放置的集裝箱屬性（包含卸貨港、箱尺寸、箱型、空箱或重箱）；

N(p)—可配載到船箱位p上的集裝箱的集合，其中ci=cp；

P(i)—可配載集裝箱i的船箱位的集合，其中ci=cp；

Δ(i)—同集裝箱i位于堆場同一場棧，且所處位置在集裝箱i上方的集裝箱集合，Δ（i）?N；

B—堆場箱區的集合；

T—時間段的集合，時間段由t（第t小時）表示，｛1,2 ,. .. ,tmax｝。

2）定義參數

rjk—船箱位，r為貝號，j為列號，k為層號；

θp—船箱位p裝船作業時間；

τip—將集裝箱i從其場箱位配載到船箱位p所需水平運輸時間；

Wl—船棧l可承載的重量上限值；

Wd—船艙d可承載的重量上限值；

?i—集裝箱i的重量；

π(p)—同船箱位p位于同一船棧且所處位置在船箱位p正上方的船箱位，即若p=(r,j,k)，則π(p)=(r,j,k+1)；

σ—堆場翻一次箱所需時間；

b—堆場箱區編號；

ubi—在t時間段箱區b的最大預設作業時間；

M—充分大的正數。

2.3 決策變量

xip—0-1變量，當且僅當集裝箱i被配載到船箱位p上時為1，否則為0。

zij—0-1變量，當且僅當集裝箱i在集裝箱j之前配載時為1，否則為0。其中j∈ Δ （i）。

vpbj—第t時間段箱區b完成對應船箱位p配載任務的作業時間。

γbt—在第t時間段箱區b的剩余可作業時間。

功能性成分測定：氨基酸含量和核苷酸含量的測定分別參考文獻[7]和[8]的方法；多糖含量和多酚含量的測定分別參考文獻[9]和[10]以及[11]和[12]的方法。

γtmin—在第t時間段內所有堆場箱區中最小的剩余可作業時間。

2.4 數學模型

目標函數：

約束條件：

式(2)表示每個集裝箱只能被配載到一個船箱位上。

式(3)表示每個船箱位只能配載一個集裝箱。

式(4)表示集裝箱船上位于同一船棧的集裝箱要求輕箱壓重箱。

式(6)定義了堆場翻箱。

式(7)表示船艙配載的集裝箱重量小于該艙的重量極限。

式(8)保證配載的集裝箱類型與船箱位類型一致。

式(9)定義箱區剩余可作業時間γbt。

式(10)表示在某一時間段內所有堆場箱區中的最小剩余可作業時間。

式(11)和(12)定義了相關決策變量為0-1變量。

式(13)表示相關變量的取值范圍。

通過上述模型看，船舶配載問題是帶復雜約束條件的組合優化問題。由于配載模型的高復雜性、計算量大、搜索速度慢等特點，因而如何提高搜索效率，得到最優解（近似最優解）成為解決配載問題的關鍵。鑒于禁忌搜索算法作為一種不依賴于問題的高效尋優算法，能有效地解決大型組合優化和整數規劃問題，且在集裝箱碼頭生產計劃與作業計劃方面有著廣泛且良好的應用。因此，本文將采用禁忌搜索算法對該配載模型進行求解。

3 算法設計

基于配載模型，本節將設計禁忌搜索算法對自動化集裝箱碼頭船舶配載問題進行求解，通過尋找滿意的配載方案，最終得到待配集裝箱與船箱位之間的匹配關系。

首先，初始化配載狀態，包括堆場待配載集裝箱信息、船舶貝位的船箱位信息、迭代次數等已知參數。

3.1 編碼方式

本文解決集裝箱船舶配載問題的核心在于確定待裝船箱在船上的位置，使配載計劃方案能夠滿足船公司和碼頭方的相關技術和理論要求，因此編碼應包含配載位置信息。

由于橋吊作業計劃已得到確定，故各作業船貝的作業順序和作業開始時間也隨著得到確定。故每個船箱位都可得到一個預估的作業時間，船箱位配載次序已得到確定。為得到場箱位與船箱位的匹配關系，本文采用1～n的自然數對場箱位進行實數編碼，用l代表編碼序列。編碼的每一位分別代表船箱位，每一位的值代表場箱位。圖1展示了n個場箱位的編碼序列。

圖1 編碼序列

圖1表示第1位船箱位裝載場箱位為3的集裝箱，第5位船箱位裝載場箱位為n的集裝箱。按照上述方法進行編碼的任意序列都代表了配載問題的決策結果（配載位置），為后續操作奠定了基礎。

3.2 適配值函數的構造

適配值函數用來界定搜索狀態的優劣性。本文選用目標函數作為適配值函數，根據本文模型，將適配值函數設計為：

式(14)中：s1，s2，s3為子決策目標，α1，α2，α3是各子決策目標權重系數。權重系數的設立方法遵循適應性權重，即根據當前候選解集的信息進行適應性調整，計算步驟如下：

若最大決策目標不等于最小決策目標：

若最大決策目標等于最小決策目標：

3.3 初始解的獲得

由于禁忌搜索算法的性能在較大程度上由初始解的質量決定。因此，本文在配載計劃制定的初始階段，通過在多個隨機解中選擇翻時間與水平運輸時間最短的解作為初始解，以提高算法收斂的速度，提高解的質量。

3.4 鄰域移動

對于船舶配載問題，本文通過隨機交換兩個場箱位編號實現鄰域移動，隨機交換場箱位編號需滿足模型約束條件。具體的操作方式如圖2所示。

圖2 交叉操作示意

3.5 禁忌表的設置

禁忌表的設置包括禁忌對象與禁忌長度的設置。對于本文所研究的船舶配載問題，根據鄰域移動的設計特點，以每次迭代過程進行交換的場箱位編號對為禁忌對象。例如：當圖2中場箱位編號8和43進行位置交換時，編號對(8,43)將加入到禁忌表中，設定該編號對在規定迭代次數內不得被再次訪問。本文選用固定長度法設定禁忌長度。根據編碼步驟可知，若本文的問題規模n=100，則本文的禁忌長度t=10。

3.6 選擇策略

對于船舶配載問題，若當新解計算得到的適配值比原解對應的適配值小，則將該新解作為本次迭代的鄰域最好解。用公式表示為：

式(15)中：l為當前解，l’為選出的鄰域最好解，s（l）為候選解集，為鄰域V的一個子集，f′（s（l））為s（l）的適配值函數。

3.7 藐視準則

本文選取基于適配值的藐視準則對優良狀態實行解禁，當禁忌候選解適配值優于當前最優解時，則將其從禁忌表中剔除。例如：當交換編碼對(8,43)經過多次迭代后，計算得到的適配值大于當前最優值時，即f（s（l））＜f（l*），將編碼對(8,43)從禁忌表中剔除。

3.8 終止準則

本文通過設置算法最大迭代次數作為終止準則，并從當前代選出代表最佳配載位置的編碼序列作為輸出。

4 算例分析

4.1 初始數據

為驗證本文所提出模型額正確性與有效性，選取艾伯特馬士基（ALBE MSK）、航次為632W的集裝箱船01艙中的31個集裝箱位為配載計劃研究對象進行算例分析。算例中，關于船舶 01艙的預配（圖3）、船箱位信息（表1）、在場箱信息（表2）均為已知條件。

圖3 預配船示意

01艙31個預配船箱位信息如表1所示。主要包括：船箱位、卸貨港、尺寸（20 ft、40 ft）、箱型（高箱、平箱）、空箱或重箱；“箱型”一列中，G代表平箱，H代表高箱。“空/重”一列中，F代重箱，E代表空箱。

表1 船箱位信息

需要配載到01艙的31個在場箱信息如表2。

表2 在場箱信息

根據該碼頭的實際操作情況，設置模型中涉及的參數。其中，由 AGV的平均水平移動速度為v=6 m/min及集裝箱所在箱區與船貝之間的距離，可獲得配載過程中每個集裝箱的水平運輸時間τip。假定橋吊每小時可完成 24個動作，處理一個集裝箱任務需2.5 min，則根據橋吊作業計劃及配載規則可得出每個船箱位的開始裝船作業時間θp。堆場翻箱時間σ=3.3 min。式(14)中權重系數設置情況為：α1=0.4，α2=0.3，α3=0.3。對禁忌搜索算法參數設置如下：取迭代次數Tmax=300，禁忌長度H=10，鄰域個數U=10。

4.2 結果分析

基于以上數據，在實驗環境為Intel(R) Core(TM)i3-2350M CPU@2.30 GHz、內存為4G的個人計算機上，采用MATLAB軟件對所提出的禁忌搜索算法進行程序開發工作，求解算例。利用禁忌搜索算法進行計算，對01艙的31個集裝箱的配載計劃進行求解，通過多次試驗，得到最優的配載結果。進而可得出總目標函數值與各個子目標函數值，如表3所示。

表3 目標函數結果

按船貝圖的形式圖形化展示配載方案。從船貝配載角度看，01艙位的配載結果如圖4所示，圖中數字編號代表來自不同場箱位的集裝箱編號，船箱位與所需裝船的集裝箱相匹配。

圖4 船貝配載結果示意

為了進一步分析模型中堆場箱區間作業時間均衡約束對配載計劃的影響，根據配載結果，從堆場配載角度，還可以繪制出01艙位配載結果所對應的堆場箱區發箱點分布圖，以了解在配載過程中發箱點聚和散的問題，基于均衡約束進行船舶配載，可以有效分散箱區作業量，減少堆場翻箱時間和水平運輸時間。從而避免產生水平運輸擁堵和堆場機械作業繁忙，減少作業沖突，也有效縮短了集裝箱的裝船作業時間。基于堆場發箱點的分布，可預估堆場作業沖突，使得全場船舶作業過程中盡量的減少作業沖突和實現作業沖突的預警。

為檢驗禁忌搜索算法的收斂性，根據待配載集裝箱數量設計5組不同規模的算例，進行多次實驗，通過數據統計，得到禁忌搜索算法中目標函數值與迭代次數之間的關系，如圖5所示。

圖5 目標函數收斂曲線

由圖 5 可知，設定Tmax= 3 0 0，隨著迭代次數的增加目標函數的值先不斷減小，后呈現平穩狀態，在迭代達到120次時第一次搜索到最優解。從整個目標函數收斂曲線圖可知，隨著迭代次數的增加，算法采樣規模擴大，估計值逐漸趨于精確，在一定代數后找到較優的解。表明禁忌搜索算法可在指定迭代次數內搜索到最優解，驗證了本文所設計的禁忌搜索算法具有可靠性。

綜上所述，根據自動化集裝箱碼頭船舶配載模型和設計的禁忌搜索算法，計算結果滿足模型中作業約束條件，實現了決策目標，表明所提出的模型和算法是有效并且可靠的。

5 結 論

本文研究了自動化集裝箱碼頭集裝箱船舶配載問題。基于自動化集裝箱碼頭的研究背景，首先對實配問題進行抽象，充分考慮作業均衡因素，以最小化翻箱時間、水平運輸時間和均衡堆場箱區間作業時間為決策目標，綜合考慮預配規定與實配原則，建立了自動化集裝箱碼頭船舶配載的多目標混合整數規劃模型。設計基于配載位置的禁忌搜索算法進行求解，并詳細闡述了算法的實現步驟。以名為艾伯特馬士基的集裝箱船舶配載為實例進行算例分析，得到了最優的配載結果，并用圖形直觀展示了 01艙的配載計劃。通過不同規模的算例得出該算法可有效求解自動化集裝箱碼頭船舶配載問題。在集裝箱船舶配載計劃制定過程中，本文所提出的數學模型以及設計的禁忌搜索算法具有實際借鑒意義。