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

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

引 言

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

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

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

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

1 問題描述

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

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

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

2 模型建立

2.1 模型假設(shè)

假定以下條件已知：

1）集裝箱船舶的結(jié)構(gòu)和船箱位信息；

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

3）預(yù)配船圖信息；

4）橋吊開路計劃與作業(yè)計劃。

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

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

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

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

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

5）預(yù)配中已考慮船舶穩(wěn)定性等指標(biāo)。

2.2 參數(shù)定義

1）定義集合

N—堆場內(nèi)所有待配集裝箱的集合，

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

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

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

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

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

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

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

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

B—堆場箱區(qū)的集合；

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

2）定義參數(shù)

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

θp—船箱位p裝船作業(yè)時間；

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

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

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

?i—集裝箱i的重量；

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

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

b—堆場箱區(qū)編號；

ubi—在t時間段箱區(qū)b的最大預(yù)設(shè)作業(yè)時間；

M—充分大的正數(shù)。

2.3 決策變量

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

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

vpbj—第t時間段箱區(qū)b完成對應(yīng)船箱位p配載任務(wù)的作業(yè)時間。

γbt—在第t時間段箱區(qū)b的剩余可作業(yè)時間。

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

γtmin—在第t時間段內(nèi)所有堆場箱區(qū)中最小的剩余可作業(yè)時間。

2.4 數(shù)學(xué)模型

目標(biāo)函數(shù)：

約束條件：

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

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計

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

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

3.1 編碼方式

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

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

圖1 編碼序列

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

3.2 適配值函數(shù)的構(gòu)造

適配值函數(shù)用來界定搜索狀態(tài)的優(yōu)劣性。本文選用目標(biāo)函數(shù)作為適配值函數(shù)，根據(jù)本文模型，將適配值函數(shù)設(shè)計為：

式(14)中：s1，s2，s3為子決策目標(biāo)，α1，α2，α3是各子決策目標(biāo)權(quán)重系數(shù)。權(quán)重系數(shù)的設(shè)立方法遵循適應(yīng)性權(quán)重，即根據(jù)當(dāng)前候選解集的信息進(jìn)行適應(yīng)性調(diào)整，計算步驟如下：

若最大決策目標(biāo)不等于最小決策目標(biāo)：

若最大決策目標(biāo)等于最小決策目標(biāo)：

3.3 初始解的獲得

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

3.4 鄰域移動

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

圖2 交叉操作示意

3.5 禁忌表的設(shè)置

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

3.6 選擇策略

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

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

3.7 藐視準(zhǔn)則

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

3.8 終止準(zhǔn)則

本文通過設(shè)置算法最大迭代次數(shù)作為終止準(zhǔn)則，并從當(dāng)前代選出代表最佳配載位置的編碼序列作為輸出。

4 算例分析

4.1 初始數(shù)據(jù)

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

圖3 預(yù)配船示意

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

表1 船箱位信息

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

表2 在場箱信息

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

4.2 結(jié)果分析

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

表3 目標(biāo)函數(shù)結(jié)果

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

圖4 船貝配載結(jié)果示意

為了進(jìn)一步分析模型中堆場箱區(qū)間作業(yè)時間均衡約束對配載計劃的影響，根據(jù)配載結(jié)果，從堆場配載角度，還可以繪制出01艙位配載結(jié)果所對應(yīng)的堆場箱區(qū)發(fā)箱點分布圖，以了解在配載過程中發(fā)箱點聚和散的問題，基于均衡約束進(jìn)行船舶配載，可以有效分散箱區(qū)作業(yè)量，減少堆場翻箱時間和水平運輸時間。從而避免產(chǎn)生水平運輸擁堵和堆場機械作業(yè)繁忙，減少作業(yè)沖突，也有效縮短了集裝箱的裝船作業(yè)時間?；诙褕霭l(fā)箱點的分布，可預(yù)估堆場作業(yè)沖突，使得全場船舶作業(yè)過程中盡量的減少作業(yè)沖突和實現(xiàn)作業(yè)沖突的預(yù)警。

為檢驗禁忌搜索算法的收斂性，根據(jù)待配載集裝箱數(shù)量設(shè)計5組不同規(guī)模的算例，進(jìn)行多次實驗，通過數(shù)據(jù)統(tǒng)計，得到禁忌搜索算法中目標(biāo)函數(shù)值與迭代次數(shù)之間的關(guān)系，如圖5所示。

圖5 目標(biāo)函數(shù)收斂曲線

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

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

5 結(jié) 論

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