基于多目標遺傳算法的煤碼頭泊位與機械聯合調度

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

摘要：

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

關鍵詞：

煤碼頭；泊位分配；機械調度；多目標遺傳算法

中圖分類號：U691.31

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

0引言

隨著我國煤炭需求量的激增，煤炭碼頭發展規劃水平不斷提升.作為煤炭運輸的中轉站，碼頭泊位作業系統的高效化愈發重要.[1]然而，目前鮮有針對散貨碼頭泊位分配問題的科學合理的優化調度方案.散貨碼頭泊位分配問題與集裝箱碼頭的十分相似，而集裝箱碼頭泊位分配問題和岸橋分配問題一直是港口研究熱點.[2]

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

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

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

1問題描述

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

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

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

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

2模型建立

2.1參數及變量

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

自變量：Qit為t時刻為船i服務的機械數量；Si為船i停靠的起始岸壁線單元；bi為船i靠泊時刻.

因變量：Xjit為01變量，t時刻若船i占用泊位j則Xjit為1，否則為0；Ei為船i?？康慕Y束岸壁線單元；Ti為船i作業總時間；di為船i離港時刻；F1，F2和F3為3個目標函數.

2.2約束條件

泊位與機械聯合調度模型的約束條件如下：

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

2.3模型目標

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

3算法設計

最優化處理是尋找目標的最優解，若優化目標超過一個并需同時進行優化處理，則稱為多目標優化.用遺傳算法解決該問題時產生了一類新的研究和應用，稱為遺傳多目標優化.由于各目標之間無法比較，一個解可能對某個目標函數是最好的，但對其他目標函數是最差的，這一系列解稱作非支配解（nondominatedsolutions）.判據空間有一個特殊的點，叫做正理想解（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*通常是非常復雜的.通過給定偏好，將非支配解集中可選的解進行排序，然后獲得最終決策結果，此最終解稱作最優妥協解（bestcompromisedsolution）.權重和方法（weightedsumapproach）是一種有效的適應值分配機制.在多目標優化中，用該方法來獲得最優妥協解.權重和方法被應用到遺傳算法中時，其缺點可以被遺傳算法基于種群搜索和進化搜索的力量削弱.權重和方法包括固定權重方法、隨機權重方法和適應性權重方法.采用適應性權重方法，可以更全面地利用遺傳算法的搜索能力，利用當前種群中一些有用的信息來重新調整權重，從而獲得朝向正理想解的搜索壓力.

3.1遺傳算法編碼

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

3.2適應度函數

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

因為轉化后的目標函數滿足適應度函數設計要求，所以可令適應度函數為Z（x），目標函數即為令其最大化，其理論最大值為3.利用適應性確定多目標權重的方法，同時結合了生產式求解思路和啟發式決策思路的優點，在進化過程中，每代Zmaxk和Zmink變化時，也相應動態調整權重，即在進化過程中，根據當前有用信息對目標偏好進行持續調整，獲得向正理想解搜索的壓力，不同于傳統的固定權重多目標優化.

3.3選擇、交叉與變異操作

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

3.4染色體初始化及修復

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

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

4.1算例數據

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

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

4.2算例結果及分析

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

聯合調度方案見圖6.由圖6可直觀觀察到港

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

況.例如船16為運輸塊煤的船舶，其?？克加玫?/p>

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

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

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

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

5結束語

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

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

參考文獻：

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

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

[3]韓笑樂，陸志強，奚立峰.具有服務優先級別的動態離散泊位調度優化[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]邱波.集裝箱碼頭泊位系統資源配置與調度優化研究[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]李強，宓超，趙寧，等.自動化散貨裝船機物位檢測技術[J].上海海事大學學報，2013，34（3）：1316，89.

[13]唐晨.天津港煤碼頭泊位作業系統生產組織優化研究[D].大連：大連海事大學，2013.