宓為建+王郡嫻+張曉華+梁梟+夏孟玨

摘要：

針對煤碼頭泊位分配問題，考慮泊位與機械的聯(lián)合調(diào)度.綜合考慮煤種類對船舶靠泊位置的影響、航道開放時間和如開設(shè)機械雙線作業(yè)等特殊原則，以最大化岸線利用率和機械利用率以及最小化船舶在港時間為目標，建立泊位與機械的聯(lián)合調(diào)度模型.設(shè)計具有自適應性的多目標遺傳算法進行求解.利用天津港煤碼頭實際案例分析驗證模型的可行性和算法的有效性.該方法可為大多數(shù)散貨碼頭的生產(chǎn)運營管理提供借鑒.

關(guān)鍵詞：

煤碼頭；泊位分配；機械調(diào)度；多目標遺傳算法

中圖分類號：U691.31

文獻標志碼：A 收稿日期：20150414 修回日期：20150609

0引言

隨著我國煤炭需求量的激增，煤炭碼頭發(fā)展規(guī)劃水平不斷提升.作為煤炭運輸?shù)闹修D(zhuǎn)站，碼頭泊位作業(yè)系統(tǒng)的高效化愈發(fā)重要.[1]然而，目前鮮有針對散貨碼頭泊位分配問題的科學合理的優(yōu)化調(diào)度方案.散貨碼頭泊位分配問題與集裝箱碼頭的十分相似，而集裝箱碼頭泊位分配問題和岸橋分配問題一直是港口研究熱點.[2]

BIERWIRTH等[2]依據(jù)岸線布局將泊位分配問題分為離散型和連續(xù)型.針對前者，通常以最小化所有到港船舶總在港時間為目標，建立混合整數(shù)規(guī)劃模型，并利用啟發(fā)式算法、模擬退火算法、遺傳算法進行求解；韓笑樂等[3]基于先到先服務（FirstComeFirstService，F(xiàn)CFS）修改后的規(guī)則生產(chǎn)初始解，結(jié)合禁忌搜索和模擬退火法求解.針對連續(xù)型泊位問題，IMAI等[4]建立整數(shù)規(guī)劃模型，指出連續(xù)泊位調(diào)度計劃的高效性；ZHEN等[5]考慮船舶到達與作業(yè)時間的不確定性，提出兩階段模型，利用亞啟發(fā)式算法求解；DU等[6]考慮船舶燃油消耗，提出混合整數(shù)二階錐規(guī)劃模型；HENDRIKS等[7]同步考慮泊位分配和堆場計劃.

實際上，泊位分配與機械調(diào)度相互影響[8]，船舶靠泊作業(yè)時間很大程度上由所分配的機械數(shù)量決定，因此在泊位分配問題中必須同時考慮機械調(diào)度.針對集裝箱碼頭泊位與岸橋這兩個港口關(guān)鍵資源約束，ZHANG等[9]考慮了岸橋覆蓋范圍，并用梯度優(yōu)化技術(shù)求解；CHANG等[10]依據(jù)滾動水平方法編出程序模型，利用混合并行遺傳算法求解；RAA等[11]考慮船舶的優(yōu)先權(quán)，提出混合整數(shù)線性規(guī)劃模型.

散貨碼頭的泊位和岸邊機械分配問題雖然與集裝箱碼頭的相似，但其仍然具有自身的特殊性[12]，例如：散貨種類影響裝卸機械的選型、船舶?？康陌毒€位置、航道開放時間等.因此，有必要針對散貨碼頭的特殊性，在決策船舶靠泊方案時考慮岸邊機械資源，建立船舶與岸邊機械的聯(lián)合調(diào)度模型，以使調(diào)度方案更加合理.

1問題描述

煤碼頭在散貨碼頭中占據(jù)重要地位，出口型煤碼頭布局見圖1，其中泊位系統(tǒng)主要包括碼頭岸線、裝卸機械設(shè)備（移動式裝船機、皮帶輸送裝置等）以及到港服務的船舶，其調(diào)度計劃的兩項基本工作是了解船舶動態(tài)和編制晝夜作業(yè)計劃，而碼頭現(xiàn)存人工調(diào)度計劃由于工作人員個人工作能力的差別使得制訂出的泊位計劃不盡合理.

煤碼頭所運輸?shù)拿嚎煞譃槟┟汉蛪K煤兩種，末煤由裝船機作業(yè)，塊煤由門機作業(yè)，而裝船機在左側(cè)，門機在碼頭右側(cè)，即末煤船舶靠泊在左，塊煤船舶靠泊在右.船舶作業(yè)時間與岸邊裝卸機械的分配有關(guān)，岸邊機械可在合適情況下開設(shè)雙線作業(yè).一般情況下載質(zhì)量≥3.0萬t，船艙數(shù)≥4個的船舶比較適合采用雙線作業(yè)方式裝船.例如，當某臺裝船機處于空閑狀態(tài)時，可以動態(tài)安排到鄰近船舶進行輔助裝船作業(yè)，以縮短船舶在港時間.航道每隔兩小時變換一次航道開放狀態(tài)，見表1.

此外，為便于計算，假設(shè)：碼頭岸線泊位為連續(xù)直線型泊位，以10m為一個岸壁線單元，以1h為一個時間單位；待排船均已到達港口錨地（靜態(tài)調(diào)度）；任意時刻，某一岸壁線單元僅能被一艘船占用；每艘船所需機械數(shù)量有上限和下限，由該船配載艙數(shù)決定；內(nèi)外貿(mào)船舶進出港手續(xù)辦理時間不一樣；航道深度滿足所有船的需求；?？吭诖a頭上的船舶，船身占有的泊位長度可以從該船映射的纜繩樁頭尾之間的距離來確定，并將此長度反映為均勻的纜繩樁之間距離的整數(shù)倍，一個樁位只可用于一艘船.抵港船舶的靠泊作業(yè)流程見圖2.

因此，與已有的研究[13]相比，進一步考慮在散貨煤碼頭分開靠泊塊煤、末煤船舶，航道開放時間，允許適當開設(shè)雙線協(xié)同作業(yè)等實際特點，同時考慮岸線、機械利用率最大和船舶總在港時間最短等多個目標.

2模型建立

2.1參數(shù)及變量

參數(shù)定義：i代表待安排靠泊計劃的船舶，I為錨地待排船舶總數(shù)，1≤i≤I；j為岸線被分割的岸壁線單元，J為分割的岸壁線單元總數(shù)，1≤j≤J；t表示某一時刻；L為岸線總長度；li為船i的長度（包括水平安全距離）；Ci為船i裝載量；Hi為船i辦理進出港手續(xù)時間；ta和tb分別為內(nèi)、外貿(mào)船舶辦理進離港手續(xù)時間；ri為01變量，ri為0時是內(nèi)貿(mào)船，否則是外貿(mào)船；Pi為01變量，Pi為1時指船上貨物種類為塊煤，否則為末煤；ti為船i從錨地到靠泊位置所需時間；v為機械（裝船機或門機）作業(yè)速率；v1和v2分別代表裝船機和門機作業(yè)速率；ni為預配船艙數(shù)量，其中nit代表任意時刻需要裝艙的船艙數(shù)量，超過某數(shù)量級別才能開設(shè)雙線作業(yè)；A為裝船機臺數(shù)；G為門機臺數(shù)；B為岸壁線單元的長度.

自變量：Qit為t時刻為船i服務的機械數(shù)量；Si為船i?？康钠鹗及侗诰€單元；bi為船i靠泊時刻.

因變量：Xjit為01變量，t時刻若船i占用泊位j則Xjit為1，否則為0；Ei為船i?？康慕Y(jié)束岸壁線單元；Ti為船i作業(yè)總時間；di為船i離港時刻；F1，F(xiàn)2和F3為3個目標函數(shù).

2.2約束條件

泊位與機械聯(lián)合調(diào)度模型的約束條件如下：

li/B代表岸壁線單元在船i所?？康钠鹬拱毒€內(nèi)；bi≤t≤bi+Ti指船i的?？繒r間；若滿足岸壁線單元與時間的約束范圍，則泊位j被占用，Xjit為1，否則為0.式（2）保證船i結(jié)束位置在最后一個岸壁線單元內(nèi).式（3）滿足船i在作業(yè)總時間Ti內(nèi)的裝載作業(yè)量必須大于船i的計劃裝載量，即在規(guī)定時間內(nèi)完成作業(yè)任務.式（4）表示岸邊機械作業(yè)速率.式（5）和（6）分別表示某時刻所有船舶所分配的裝船機和門機的總數(shù)量不超過實際數(shù)量.式（7）表示若船i需要裝艙的數(shù)量小于nit，則船上機械不多于1臺，若船i需要裝艙的數(shù)量大于等于nit，則船上機械不多于2臺.式（8）是船i辦理進離港手續(xù)時間公式.式（9）保證船i在離港前完成作業(yè)，并辦完離港手續(xù).式（10）和（11）分別表示船i進港與離港時刻必須在規(guī)定的進離港時間段內(nèi)，否則必須等待.式（12）表示岸壁線單元的連續(xù)性約束.式（13）保證任意兩艘船在位置和空間上的互不交叉，如圖3所示，i1和i2代表任意兩艘船，Si與Ei分別指船i?？科鹗己徒Y(jié)束岸壁線單元，兩矩形框分別表示兩艘船在空間和時間上的位置，而這兩艘船的互不碰撞表現(xiàn)為兩個矩形無重疊區(qū)域，即同一時刻同一位置只有一艘船被服務.

2.3模型目標

式（14）的目標是岸線利用率最大.根據(jù)《海港總平面設(shè)計規(guī)范》，岸線利用率=（在泊船長×在泊時間）/（碼頭岸線總長度×船舶在港時間）.式（14）中：Ei-Si+1代表在泊船長；di-bi代表船舶的在泊時間；η=maxdi-maxbi，即用所有船的最晚離港時間減去最早靠泊時間，得到所有船的在泊時間.式（15）的目標是機械利用率最大，即盡量使分配給所有船的岸邊裝船機和門機處于忙期，提高工作效率.機械利用率=（所有機械實際工作時間）/（總機械數(shù)量×所有船的在港時間）.式（16）的目標是船舶總在港時間最短.實際上碼頭方希望船舶的在港時間最短，不僅要盡量減少船舶作業(yè)時間，而且要減少船舶等待時間.

3算法設(shè)計

最優(yōu)化處理是尋找目標的最優(yōu)解，若優(yōu)化目標超過一個并需同時進行優(yōu)化處理，則稱為多目標優(yōu)化.用遺傳算法解決該問題時產(chǎn)生了一類新的研究和應用，稱為遺傳多目標優(yōu)化.由于各目標之間無法比較，一個解可能對某個目標函數(shù)是最好的，但對其他目標函數(shù)是最差的，這一系列解稱作非支配解（nondominatedsolutions）.判據(jù)空間有一個特殊的點，叫做正理想解（positiveidealsolution），用z*k=（z*1，z*2，…，z*q）表示，其中z*k=sum{fk（x）/x∈S}，k=1，2，…，q.對每個目標來說，尋找z*k是可能的，但是尋找一個能夠同時最大化每個fk（x）（k=1，2，…，q）的點z*通常是非常復雜的.通過給定偏好，將非支配解集中可選的解進行排序，然后獲得最終決策結(jié)果，此最終解稱作最優(yōu)妥協(xié)解（bestcompromisedsolution）.權(quán)重和方法（weightedsumapproach）是一種有效的適應值分配機制.在多目標優(yōu)化中，用該方法來獲得最優(yōu)妥協(xié)解.權(quán)重和方法被應用到遺傳算法中時，其缺點可以被遺傳算法基于種群搜索和進化搜索的力量削弱.權(quán)重和方法包括固定權(quán)重方法、隨機權(quán)重方法和適應性權(quán)重方法.采用適應性權(quán)重方法，可以更全面地利用遺傳算法的搜索能力，利用當前種群中一些有用的信息來重新調(diào)整權(quán)重，從而獲得朝向正理想解的搜索壓力.

3.1遺傳算法編碼

泊位與機械分配問題的目的是找到最合適的船舶靠泊順序、靠泊位置以及確定船舶動態(tài)作業(yè)的機械數(shù)量.染色體編碼中需包含船舶靠泊順序和靠泊位置信息，因此采用自然數(shù)編碼方式.子染色體1表示船舶的靠泊順序（VO），子染色體2表示船舶?？康钠鹗嘉恢茫╒L）.表2為8艘船的染色體編碼.例如，根據(jù)得出的編碼，船6（長度100m）首先進行靠泊，并?？吭谄鹗及侗诰€單元（長度10m）為從31～40的10個岸壁線單元上.針對Xjit，利用編碼中的船舶進港順序依次安排進港，岸線位置排滿后，后續(xù)船舶必須等前面的船舶作業(yè)完成并離港后，在進港時間段內(nèi)進港，其計算以岸線上船舶的最早離港時間為基準，得出每艘船的靠泊時間.船i是否占用泊位單元j由船長決定.子染色體2表示j的起始值，根據(jù)船長計算出所有被占用的j的值.

3.2適應度函數(shù)

在適應性權(quán)重法中，首先對目標函數(shù)進行轉(zhuǎn)化，將各子目標函數(shù)化歸為[0，1]之間的實數(shù).令Z1=F1和Z2=F2，這兩個利用率的值在[0，1]之間.F3則是所有船舶的在港時間，是較大的實數(shù).令Z3=Ii=1dimaxdiI，由于目標Z3是求最小值，將其轉(zhuǎn)化為求最大值，即令

因為轉(zhuǎn)化后的目標函數(shù)滿足適應度函數(shù)設(shè)計要求，所以可令適應度函數(shù)為Z（x），目標函數(shù)即為令其最大化，其理論最大值為3.利用適應性確定多目標權(quán)重的方法，同時結(jié)合了生產(chǎn)式求解思路和啟發(fā)式?jīng)Q策思路的優(yōu)點，在進化過程中，每代Zmaxk和Zmink變化時，也相應動態(tài)調(diào)整權(quán)重，即在進化過程中，根據(jù)當前有用信息對目標偏好進行持續(xù)調(diào)整，獲得向正理想解搜索的壓力，不同于傳統(tǒng)的固定權(quán)重多目標優(yōu)化.

3.3選擇、交叉與變異操作

采用輪盤賭的方法選出下一代.對染色體1采用次序雜交（ordercrossover），以避免交叉后染色體產(chǎn)生不可行解，見圖4.適用于自然數(shù)編碼的變異算子有反轉(zhuǎn)變異、插入變異和交換變異，該算法中采用交換變異，具體見圖5.

3.4染色體初始化及修復

染色體1的初始值是船舶編號的一個隨機順序，染色體2的初始值是根據(jù)染色體1的初始順序和船舶長度依次生成的隨機整數(shù)ξ，

即該隨機起始位置在未被占用的岸壁線單元數(shù)內(nèi).由于岸線為連續(xù)泊位，編碼形式采取的是自然數(shù)編碼.在交叉和變異后，由于受船舶靠泊位置的約束，會產(chǎn)生大量不可行解，因此對染色體2編碼段進行修復，使之較快找到較優(yōu)停泊位置.重新計算連續(xù)的空閑岸壁線單元，如果該空閑段的長度能夠滿足停下一艘最小的船舶，則在該岸壁線單元內(nèi)隨機生成起始基因位，如果生成的解不滿足任何一個約束條件，則對該解設(shè)置懲罰系數(shù)以淘汰該解，以此方法修復染色體.

4.1算例數(shù)據(jù)

根據(jù)天津港煤碼頭實際船舶晝夜裝卸計劃及配

載數(shù)據(jù)，整理出20艘船的裝卸數(shù)據(jù)，見表3.全岸線長1100m，0～550m靠泊末煤船，550～1100m靠泊塊煤船，則共有110個岸壁線單元（岸壁線單元長度是10m）；單臺裝船機額定能力為6700t/h，門機額定能力1600t/h；貨類中“1”代表塊煤，“2”代表末煤；需要裝貨的船的船艙數(shù)代表船的級別.

4.2算例結(jié)果及分析

對于大量的在港船舶，人工無法快速制訂靠泊方案，而智能算法能夠迅速找到較優(yōu)的船舶靠泊方案.通過編寫的算法程序，將試驗在Itel（R）Core（TM）i5CPU@2.53GHz和4GB內(nèi)存的個人電腦上，應用eMplant軟件運行求解.遺傳算法的初始種群規(guī)模為40，迭代次數(shù)為450，交叉概率為0.85，變異概率為0.01，多次運行算法程序，每次計算時間為2～5min，靠泊方案計算結(jié)果見表4.例如，船舶編號為20的“百盛”首先進行靠泊，靠泊起始位置在10m處，其開始作業(yè)時間為17：00，經(jīng)過144min裝卸作業(yè)完成.

聯(lián)合調(diào)度方案見圖6.由圖6可直觀觀察到港

船舶的靠泊位置、靠泊時間以及等待和機械分配情

況.例如船16為運輸塊煤的船舶，其停靠所占用的

岸線位置為930～1090m；為方便機械較快地對靠泊船舶進行作業(yè)，允許船舶提前靠泊等待.

船1，3，6均開設(shè)了雙線作業(yè)，即當1臺可移動裝船機處于工作空閑期時，可把它調(diào)度到鄰近的較大船舶處協(xié)助作業(yè).

原則上，船舶靠泊后會有已經(jīng)安排好的機械對其進行作業(yè)，如果沒有，則需等待機械空閑時動態(tài)調(diào)度鄰近的空閑機械對其進行作業(yè).例如船1和19，當船19作業(yè)完成且后續(xù)船舶還未進港時，可動態(tài)調(diào)度船19上的作業(yè)機械對船1進行作業(yè).雙線作業(yè)的開設(shè)即為某時刻動態(tài)調(diào)整機械的作業(yè).

其次，對程序算法的魯棒性和適應度函數(shù)進行評價.算例規(guī)模分別為10艘船和20艘船，遺傳算法的初始種群規(guī)模為40，迭代次數(shù)為450，交叉概率為0.85，變異概率為0.01，分別運行程序5次.算例每代最優(yōu)個體適應度函數(shù)值的收斂曲線見圖7.由于三個目標函數(shù)經(jīng)過歸一化處理，因而適應度函數(shù)值無量綱.圖中結(jié)果顯示，不同參數(shù)和算例規(guī)模下的模型運算結(jié)果的收斂曲線均能收斂到3，證明算法在深度和廣度上具有良好的收斂性，模型系統(tǒng)具有較好魯棒性.綜上可得，所設(shè)計的適應性權(quán)重的多目標遺傳算法適用于解決散貨碼頭連續(xù)泊位岸線上的船舶與機械聯(lián)合調(diào)度問題.

5結(jié)束語

綜合考慮不同貨類對船舶?？课恢玫挠绊?、航道開放時間和如開設(shè)機械雙線作業(yè)等原則，根據(jù)模

型的復雜性和多目標的特點，設(shè)計多目標遺傳算法.利用實數(shù)編碼、次序交叉、交換變異算子，采用適應性權(quán)重方法，迫使算法向正方向收斂.利用天津港煤碼頭數(shù)據(jù)驗證模型和算法的可行性及有效性.采用圖形化的信息顯示方式，結(jié)合手動調(diào)整進一步確定優(yōu)化方案，得到較好的人機結(jié)合效果.本文的研究不僅對散貨碼頭的運營具有借鑒意義，而且對同類不確定性多項式問題的解決具有指導意義.

參考文獻：

[1]王煜，鄭惠強，李強.基于知識工程的煤炭碼頭堆場分配策略[J].上海海事大學學報，2012，33（3）：2630.

[2]BIERWIRTHC，MEISELF.Asurveyofberthallocationandquaycraneschedulingproblemsincontainerterminal[J].EuropeanJournalofOperationalResearch，2010，202（3）：615627.

[3]韓笑樂，陸志強，奚立峰.具有服務優(yōu)先級別的動態(tài)離散泊位調(diào)度優(yōu)化[J].上海交通大學學報，2009，43（6）：902905.

[4]IMAIA，SUNX，NISHIMURAE，etal.Berthallocationinacontainerport：usingacontinuouslocationspaceapproach[J].TransportationResearchPartB：Methodological，2005，39（3），199221.

[5]ZHENL，LEELH，CHEWEP.Adecisionmodelforberthallocationunderuncertainty[J].EuropeanJournalofOperationalResearch，2011，212（1）：5468.

[6]DUY，CHENQ，QUANX，etal.Berthallocationconsideringfuelconsumptionandvesselemissions[J].TransportationResearchPartE：LogisticsandTransportationReview，2011，47（6）：10211037.

[7]HENDRIKSMPM，LEFEBERE，UDDINGJT.Simultaneousberthallocationandyardplanningattacticallevel[J].ORSpectrum，2013，35（2）：441456.

[8]邱波.集裝箱碼頭泊位系統(tǒng)資源配置與調(diào)度優(yōu)化研究[D].大連：大連海事大學，2014.

[9]ZHANGC，ZHENGL，ZHANGZ，etal.Theallocationofberthsandquaycranesbyasubgradientoptimizationtechnique[J].Computers&IndustrialEngineering，2010，58（1）：4050.

[10]CHANGD，JIANGZ，YANW，etal.Integratingberthallocationandquaycraneassignments[J].TransportationResearchPartE：LogisticsandTransportationReview，2010，46（6）：975990.

[11]RAAB，DULLAERTW，SCHAERENRV.Anenrichedmodelfortheintegratedberthallocationandquaycraneassignmentproblem[J].ExpertSystemswithApplications，2011，38（11）：1413614147.

[12]李強，宓超，趙寧，等.自動化散貨裝船機物位檢測技術(shù)[J].上海海事大學學報，2013，34（3）：1316，89.

[13]唐晨.天津港煤碼頭泊位作業(yè)系統(tǒng)生產(chǎn)組織優(yōu)化研究[D].大連：大連海事大學，2013.