泊位—岸橋多目標聯合調度

樂美龍,于 航， 黃 薇

(上海海事大學 物流研究中心,上海 201306)

泊位和岸橋的聯合調度問題(berth allocation and quay crane assignment problem,BACAP)是指碼頭計劃人員根據碼頭的泊位和岸橋等約束條件,利用相關的優化方法為在一定時期內靠泊的船舶確定其靠泊位置、時間和服務于該船舶的岸橋數目.與單純的泊位分配問題(berth allocation problem,BAP)和岸橋分配問題(quay crane allocation problem,QCAP)相比,泊位和岸橋的聯合調度把兩者看成一個整體來考慮,能有效反映其相互制約的關系.同一艘船安排的岸橋數目與船舶的在港時間成反比.增加岸橋數目可以減少在港時間,但不一定縮短了服務成本.把泊位和岸橋聯合調度更符合碼頭的實際運作.

國外對于泊位和岸橋的聯合調度問題研究,如文獻[1]中對離散的BACAP建立了優化模型,并用遺傳算法進行求解；文獻[2]中建立了以船舶作業時間、船舶等待時間和船舶推遲離港時間之和最小化為目標,并采用遺傳算法與啟發式算法相結合來求解；文獻[3]中從船舶靠泊位置對岸橋作業效率的影響,建立了以船舶服務費用最小化為目標的優化模型,并用啟發式算法求解；文獻[4]中建立了一個整數規劃泊位和岸橋聯合調度的優化模型,用拉格朗日松弛的啟發式算法進行求解.

國內對于泊位和岸橋的聯合調度的研究相對較少,如文獻[5]中研究了隨機環境下集裝箱碼頭泊位和岸橋調度的優化,以船舶等待時間最小化為目標建立模型,并用遺傳算法求解;文獻[6]中以船舶最小在港時間為目標建立了模型,并用免疫遺傳算法求解,得到了協調調度優化比單獨調度優化更好的結果.

目前,絕大多數研究將泊位分配和岸橋分配分開考慮,兩者的協調調度研究較少,而且大多也是基于最小化船舶在港時間為目標的優化.所以,在實際的情況下,文中提出了同時最小化船舶在港時間和碼頭運營成本的優化模型,以尋求碼頭綜合效益最大的泊位和岸橋的分配方案.

1 問題描述

提高連續泊位和岸橋調度的效率,可以有效地減少港口運作成本,提高港口的競爭力.連續泊位和岸橋的調度問題可用圖1說明.在這個時間空間的二維圖里,矩形代表在港的船舶;矩形的高代表船長;ai為船舶靠泊時間;xi為船舶靠泊位置;bi為船舶偏好靠泊位置;si為船舶作業結束時間;每個黑色小矩形表示一個岸橋的工時,如船舶1在靠泊作業的8個小時內,依次分配的岸橋數是4,4,4,4,3,3,2,2.

圖1 船舶泊位和岸橋的聯合調度二維圖Fig.1 Time-space diagram for a continuous BACAP

為了便于問題的分析,更好的建立模型,文中做出以下假設:①每艘船必須僅被服務一次;②船舶到達后進行靠泊服務;③每艘船都有一個偏好靠泊位置;④岸線上各處的水深完全符合任何船舶的靠泊要求,即船舶可以在任意的位置靠泊;⑤船舶的靠泊位置加上船長不能超過泊位的長度;⑥每艘船都有最少和最多安排的岸橋數目;⑦岸橋的移動時間可以忽略;⑧碼頭上的岸橋移動均位于一軌道上,不能跨越交叉.

船舶一般會希望靠泊在靠近特定堆場的泊位,這個位置就是船舶偏好的靠泊位置.如果實際分配的靠泊位置與偏好位置不一致,將增加集卡運輸距離和岸橋工時,導致整體作業效率下降,從而船舶需要更多的岸橋工時.所以,引入靠泊位置偏離因子β,船舶的靠泊位置與偏好位置的偏差量Δ=|xi-bi|,其單位距離單位工時的懲罰成本為c3i,則可表示為c3i·(1+β|xi-bi|).當β=0.01時,若靠泊位置偏離其偏好位置一單位,其懲罰成本就增加1%.

當幾個岸橋同時服務一艘船時,相互之間也會產生干擾,在1985年Schonfeld和Sharafeldien引入了岸橋干擾指數α(0≤α≤1),當每小時安排q個岸橋給一艘船,則需要qα個岸橋作業時間.

2 多目標優化數學模型

根據港口的實際運營情況,文中提出了多目標連續泊位和岸橋聯合調度的混合整數規劃模型,為了方便建立模型,引入以下符號:

1)集合與參數

2)決策變量

xi為船i實際系泊位置;ti為船i實際系泊時間;zit為在t時間內安排給船舶i的岸橋數目;ritq∈{0,1}，在t時間內有q個岸橋服務船i，則ritq=1；否則ritq=0;δij∈{0,1}，在時間軸上,若船i泊位于船j的左邊，則δij=1；否則δij=0;σij∈{0,1}，在位置軸上,若船i泊位于船j的下方，則σij=1；否則σij=0.

3)目標函數

在模型假設和模型符合定義的前提下,建立了如下的多目標泊位和岸橋聯合調度模型:

(1)

(2)

4)約束函數

xi+li≤L?i∈V

(3)

ai≤ti≤T?i∈V

(4)

xi+li≤xj+M(1-δij) ?i,j∈V,i≠j

(5)

si≤tj+M(1-σij) ?i,j∈V,i≠j

(6)

δij+δji+σij+σji≥1 ?i,j∈V,i≠j

(7)

(8)

(9)

(10)

si≤di?i∈V

(11)

(12)

(13)

-1≤rit(q-1)+rit(q+1)-ritq≤1

?q∈Q,i∈V,t∈T

(14)

δij,δji,σij,σji∈{0,1} ?i,j∈V,i≠j

(15)

ti,xi,qi≥0 ?i∈V

(16)

目標函數(1)表示最小化船舶總的在港運營成本,為了方便計算，可以將目標函數化簡，轉化為線性函數，轉化后模型為

minf1=

(17)

約束條件:

(18)

將約束條件式(18)代入約束條件式(9)，也可線性化簡轉化為

(19)

3 算例

文中船舶的泊位和大小的實時數據采集于寧波某著名集裝箱港口,其碼頭長度為1 600 m,岸橋14臺,船舶的偏好位置是隨機產生的,岸橋的裝卸速率v=35箱/h,以1 h作為一個時間窗.根據文獻[7],文中將成本系數c1i，c3i分別設定為＄2 000li/230和＄10li/230.根據碼頭運營數據統計,取c2=100元,表示每臺岸橋的運作費用.船舶資料以2012年7月16日的數據為基礎(表1).

表1 到港船舶數據Table 1 Data for the arrival vessels

注:船長包括船與船之間的安全距離.

3.1 單目標優化求解

根據文中的模型和相關數據，利用Gurobi軟件進行求解,首先對單目標1和單目標2分別進行求解,目標1的最優化結果為6 315元,目標2的最優化結果為63 h,目標2的優化結果見表2.

3.2 多目標優化求解

多目標優化求解是在目標1優化的情況下,將其改為約束,對目標2進行優化，即對船舶總的在港時間最小化進行求解,求解結果見表3.

表2 目標2優化結果Table 2 Optimization results of objective 2

表3 目標1優化后的求解數據Table 3 Optimized solution data of objective 1

計算結果顯示,在單目標2的優化值為63,其中有4艘船偏離了船舶偏好位置.在目標函數1優化下,目標函數2的值為70,船舶總等待時間為8 h,處理時間為62 h,14艘船舶里面也只有4艘船舶偏離泊位偏好位置,船1偏離60 m,船7偏離137 m,船9偏離104 m,船10偏離64 m.由于目標函數值越小,越能符合優化的效果,而單目標優化在港時間小于多目標優化的在港時間,偏差量為11.1%.所以,多目標優化結果劣于單目標的優化結果.但是,多目標優化更符合實際情況,同時考慮了船舶在港時間和碼頭運營成本的最小化,使碼頭獲得更大的綜合效益.圖2是多目標優化泊位和岸橋分配的二維圖.

圖3是每個時間窗岸橋的利用情況,從圖中可以看出,在時段1,9～12,18,19和24岸橋的利用率相對較低,說明這些時段船舶達到率不高,其他時段岸橋利用率較大,船舶的到達比較集中.岸橋的最大利用量為12,而實際的岸橋總數為14,最大利用率是86%,而在實際碼頭運營中,岸橋的利用率也是不可能達到100%,因為岸橋都要定時進行檢查和維護.所以,如果在船舶到達更集中的情況下,岸橋的數量就會不夠,從碼頭的長遠發展來看,可以適當的增加1～2臺岸橋,以提高船舶的作業效率,使碼頭獲得更大的綜合效益,符合碼頭決策者的需求.

圖2 多目標優化計算結果Fig.2 Multi-objective optimization results

圖3 QC的利用量Fig.3 Utilization of QC

4 結論

文中研究了集裝箱港口泊位與岸橋聯合調度,同時考慮最小化船舶的在港時間和運營成本,建立了相應的多目標優化模型,并采用 Gurobi進行求解,分析了單目標優化和多目標優化的差異性,并且多目標優化更符合碼頭實際的運營情況.但是,在該模型中沒有考慮岸橋跨越范圍與集卡和龍門吊調度的耦合關系.在以后的研究中,可以將整個港口為研究對象,將這些因素綜合考慮,使之更符合實際情況,有利于指導港口的實際工作.

[1] Imai A,Chen H C,Nishimura E，et al. The simultaneous berth and quay crane allocation problem [J].TransportationResearchPartE,2008(44):900-920.

[2] Liang C,Huang Y,Yang Y.A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning [J].Computers&IndustrialEngineering,2009(56):1021-1028.

[3] Meisel F,Bierwirth C. Heuristic for the integration of crane productivity in the berth allocation problem[J].TransportationResearchPartE,2009,45(4):196-209.

[4] Park Y M,Kim K H. A scheduling method for berth and quay cranes[J].ORSpectrum,2003(25):1-23.

[5] 周鵬飛,康海貴. 面向隨機環境的集裝箱碼頭泊位—岸橋分配方法[J].系統工程理論與實踐,2008(1):161-169.

Zhou Pengfei,Kang Haigui.Study on berth and quay-crane allocation under stochastic environments in container terminal[J].SystemEngineering-theory&Practice,2008(1):161-169.(in Chinese)

[6] 韓駿,孫曉娜,靳志宏.集裝箱碼頭泊位與岸橋協調調度優化[J].大連海事大學學報,2008,34(2):117-121.

Han Jun,Sun Xiaona,Jin Zhihong.Coordinated optimization method for berth and quay crane allocation in container terminal[J].JournalofDalianMaritimeUniversity,2008,34(2)：117-121.(in Chinese)

[7] Bierwirth C,Meisel F.A survey of berth allocation and quay crane scheduling problem in container terminals[J].EuropeanJournalofOperationalResearch,2010(202):615-627.

[8] Lee Derhorng,Wang Huiqiu.Integrated discrete berth allocation and quay crane scheduling in port container terminals[J].EngineeringOptimization,2010,42(8):747-761.

[9] Tavakkoli-Moghaddam R,Makui A,Salshi S,et al.An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports [J].Computers&IndustrialEngineering,2009(56):241-248.

[10] 樂美龍，劉菲.基于Memetic算法的泊位和岸橋分配問題[J].武漢理工大學學報，2011，33(1)：60-65.

Le Meilong,Liu Fei.Integrated berth allocation and quay crane scheduling by memetic algorithms[J].JournalofWuhanUniversityofTechnology,2011,33(11)：60-65.(in Chinese)

[11] 雷德明,嚴新平.多目標智能優化算法及其應用[M].北京:科學出版社,2009:30-105.