考慮船舶服務優先權的泊位-岸橋分配

張　迪，嚴南南（上海海事大學信息工程學院，上海201306）

考慮船舶服務優先權的泊位-岸橋分配

張迪，嚴南南
（上海海事大學信息工程學院，上海201306）

為了解決泊位與岸橋的分配問題，將船舶服務優先權作為影響因子，建立以最小化船舶等待時間，作業時間以及延遲時間為目標的優化模型，以此進一步提高集裝箱碼頭的服務質量與客戶滿意度。為求解此模型，設計一種遺傳算法，此算法將泊位-岸橋集成分配問題分解轉化為對泊位的岸橋分配主問題和船舶調度的子問題。并且通過試驗算例表明，該遺傳算法是有效的，并且能夠相對減少船舶總的在港時間，從而提高碼頭作業效率。

泊位-岸橋分配；遺傳算法；服務優先權；船舶調度

0　引言

泊位－岸橋分配問題是指在考慮泊位、岸橋是否空閑等的條件下，根據一定的優化策略，為到港的船舶制定靠泊時間、靠泊位置和分配岸橋的過程，其合理性將直接影響船舶在港時間、碼頭的運行效率以及服務水平。

Park和Kim首先提出了將泊位分配與岸橋分配結合考慮，作者離散化處理了靜態連續型的泊位-岸橋分配問題，以最小化總作業成本為目標,使用拉格朗日松弛算法從而得到近似解[1]。Rashidi提出了以拉格朗日松弛算法為基礎的啟發式,以及動態規劃決策方法,以決定泊位、靠泊時間和岸橋分配[2]。Oguz也研究了靜態連續泊位-岸橋分配問題[3]，他們認為這是一個并行機調度問題,最小化最遲完成時間,即所有船舶中最遲完工的時間。Imai在考慮岸橋能力的前提下，對于離散泊位進行分配,并提出了最小化船舶總在港時間的泊位-岸橋分配問題模型,采用遺傳算法得出問題的近似解[4]。Liang[5]考慮了離散型泊位-岸橋分配問題，以最小化船舶總的操作時間、等待時間和延遲時間之和為目標,設定船舶的停泊時間、停泊位置和分配的岸橋數目為決策變量。Bierwirth[6]調整了Branch-and-Bound算法以結合泊位計劃問題和岸橋分配問題來解決岸橋調度問題。杜玉泉[7]采用深度集成的方法建立泊位和岸橋聯合調度模型，為求解此模型，采用了外逼近算法。趙坤強、韓曉龍等[8]在研究泊位岸橋分配問題時，采用了兩階段的研究方法，以最小化岸橋移動次數和船舶在港時間為目標，提出了岸橋分配和泊位分配的混合整數規劃模型。

現有研究大多對于影響碼頭作業的因子，一般為岸橋干擾、抵達時間不確定等因素，但是對船舶自身要求較少考慮。但是在碼頭間競爭日益激烈的今天，更應該考慮提高客戶滿意度，增強自身競爭力。因此，可以選取船舶優先權作為影響因子。其中，集裝箱碼頭可以根據船舶的具體情況，分別設定其服務優先權，例如船舶服務優先權與其裝載量相關，裝載量越大服務優先權越大，或者是船舶作業緊急者服務優先權較大。

對于模型的求解，大多數研究集中在泊位-岸橋的集成分配，然而，對于整體的集成問題由于其問題的復雜性可能并不有效。而充分分解的問題，不僅可以提高解決方案的質量，同時，它還可以減少計算所需的時間。所以本文設計了一種兩級的遺傳算法，包含對于泊位進行岸橋分配的主問題以及對于泊位進行船舶調度的子問題，并通過相互關聯的遺傳算法解決這兩個問題。

所以，本文對于泊位與岸橋的分配問題，在建立目標函數時引入船舶服務優先權，目標函數選取以最小化船舶等待時間、作業時間以及延遲時間，從而建立泊位-岸橋調度模型。為了求解此模型，設計了遺傳算法。

1　問題描述

通常，在船舶抵港之前，碼頭管理者會根據碼頭現場情況與船舶到港信息等，制定優化策略將泊位和岸橋分配給各船舶。

本文選取一段時間內港口所到達的船舶作為研究對象，引入船舶服務優先權，其中通過船舶裝卸量決定船舶服務優先權，根據問題的實際情況，做出以下假設：

（1）考慮船舶離散型靠泊方式；

（2）每艘船舶有且只有一次靠泊機會，排除移泊情況；

（3）船舶到港后才能被碼頭服務；

（4）每艘船舶的到港時間確定；

（5）船舶開始作業后將不能被中斷直至結束作業。

2　優化模型

本文引入的符號如下：

設V={1，2，…，v}、B={1，2，…，b}和Q={1，2，…，q}分別為船舶集、泊位集合和岸橋集；C為岸橋總數；對于船舶i，αi為船舶i的優先服務系數，tai為預期到港時間，tdi為船舶離港時間，ei為船舶i的裝卸效率，Qmaxi為同時分配給船舶i的最大岸橋數，tgap為船舶等待作業時間不均衡上限；V0為單個岸橋的作業效率。決策變量qcj表示分配給泊位j的岸橋數目，Pik表示k號岸橋分配給船舶i的作業時間。變量thi和tfi分別表示船舶i的開始作業時間和完成作業時間。定義變量θijk，當船舶i在泊位j上被岸橋k被服務時，θijk=1，否則θi-jk=0；變量βjk，當岸橋k分配給泊位j時，βjk=1，否則βjk=0；變量mikj，當船i在船k之后在泊位j上停靠，則mikj=1，否則mikj=0。

模型的目標函數為：

約束條件為:

目標函數式（1）表示在考慮船舶優先權的情況對于所有船舶等待時間的和求最小。式（2）表示對船舶作業時間以及延遲時間求最小。

約束條件（3）計算了船舶完成作業的時間，約束條件（4）表示岸橋作業時間的計算方法。條件（5）和（6）保證了每艘船不能在到達時間之前停泊且不能在之前的船舶作業完成之前停泊。條件（7）保證了分配給泊位的岸橋數不超過分配的最大岸橋數。條件（8）保證了分配給泊位的岸橋數不超過可用的岸橋數。條件（9）～（11）定義了變量的計算方法。約束條件（12）保證了每個泊位一次只能有一艘船舶停泊，一艘船舶只能靠泊一次，作業完成之前不能離港。條件（13）保證了一個岸橋一次只能分配給一艘船舶。約束式（15）定義了船舶服務的優先權，其中σ表示裝卸箱量對船舶調度的影響因子，σ越小，裝卸箱量對船舶調度的影響越小。約束式（14）表示任意兩艘船舶的等待作業時間均不超過不均衡上限。

3　模型求解

遺傳算法將泊位-岸橋的集成問題分解為船舶調度問題和岸橋分配問題，并用迭代的方法求解。遺傳算法包含兩個部分，第一部分解決分配給泊位的岸橋問題，即為岸橋分配的遺傳算法。這是個主問題，它直接決定了每個泊位的集裝箱吞吐能力。第二部分是船舶調度的遺傳算法，即為決定船舶分配和調度的子問題。子問題的解決方案會在之后的步驟中反作用于主問題的求解。

其流程圖如圖1所示。

圖1　遺傳算法流程圖

算法步驟如下：

（1）隨機生成岸橋分配的初始種群，其染色體編碼表示如表1所示，基因的位置表示泊位位置，且從左至右遞增，基因的值表示此泊位上分配的岸橋數目。

表1　岸橋分配-染色體編碼

（2）每一個岸橋分配的染色體，將作為船舶調度的初始值輸入。

（3）在船舶調度中，初始種群也采用隨機生成的方法，其染色體編碼如表2，它表示每個泊位上船舶的分配以及服務次序，其中染色體長度為船舶數目與泊位數之和，基因在編碼時被0間隔，每個0表示一個泊位間隔，基因的值表示分配給此泊位的船舶號，其服務次序由左至右遞增。轉至Step 3.1～3.3，直到條件終止，此時得到每個岸橋分配方案下的最佳船舶調度方案。

表2　船舶調度-染色體編碼

①在為泊位分配的岸橋數目確定的條件下，對船舶調度的個體進行適應值計算。

②選擇策略，采用輪盤賭選擇法選擇個體。為避免優秀染色體被淘汰，引入精英策略。

③交叉、變異操作：采用兩點交叉法，產生子代。子代若不符合約束條件則調整，進而產生可行解，如圖2所示。變異則是在染色體中，隨機選擇一個基因變異，且變異后的子代需滿足約束條件。轉到（4）。

圖2　船舶調度-染色體變異及調整圖

（4）將船舶調度中的最優解與岸橋分配的初始解，引入到岸橋分配算法中。

（5）對于岸橋分配的個體，進行適應值計算。

（6）選擇策略，采用輪盤賭選擇法并且引入精英策略。

（7）交叉、變異操作：對于岸橋分配的個體采用單點交叉法，通過調整策略產生可行的子代，如圖3所示。變異則采取單點隨機變異。

圖3　岸橋分配-染色體變異及調整圖

（8）確定是否達到終止條件，若達到則得出最優解，若沒有，轉到步驟2重復執行。本文中采用設定進化代數的方法來結束算法運算。

4　算例分析

某集裝箱碼連續岸線頭總長1000m，岸橋7臺，泊位為4個。選擇以一段時間間隔的到港船舶數據。另根據碼頭生產經營統計數據，取v0=65箱/h。

為得出計算結果，使用MATLAB編寫程序,機器配置為CPU 2.8 GHz，內存2G。在本例中，基本設置為，種群大小pop=10，σ=200，船舶等待時間作業上限tgap=10，為遺傳迭代次數G=300；交叉概率Pc=0.25,變異概率Pm=0.1，從而得出的泊位-岸橋分配圖，如圖4。

在算法程序中，其余條件均不變，但是并不引入船舶服務優先權，即設置σ=0，得出的泊位-岸橋分配圖如圖5。

圖4　 σ=200時泊位-岸橋分配圖

將計算結果比較，如表4，可以看出，當σ=200時的船舶等待時間要比σ=0時的船舶等待時間少，即在模型中引入船舶服務優先權，可以將船舶的等待時間減少，從而總體減少船舶在港時間，減少碼頭的運營成本。所以在碼頭的實際作業中，可以引入船舶服務優先權，更有利于提高碼頭的服務水平和客戶的滿意度。

表3　到港船舶數據

表4　結果比較

5　結語

本文主要研究了在考慮船舶優先權的因素下，建立優化模型，以最小化船舶總的在港時間為目標函數，從而減少時間成本，并設計改進的遺傳算法對算例進行求解，在遺傳算法設計中，將泊位-岸橋集成分配轉化為對泊位的岸橋分配以及船舶調度，從而減少了岸橋移動的成本。最后對比計算結果，證明了模型和算法是有效的，并且表明考慮到船舶優先服務權的模型更有利于提高碼頭的作業效率。但是在本文的泊位-岸橋分配中并未考慮到實際作業中的不確定因素的影響，所以可以在今后的研究中繼續深化。

圖5　 σ=0時泊位-岸橋分配圖

[1]Rashidi，H.，Dynamic Scheduling of Automated Guided Vehicles.Ph.D.Thesis，University of Essex，Colchester，2006

[2]Oguz，C.，B azewicz，J.，Cheng，T.C.E.，Machowiak，M.，Berth Allocation as Amoldable Task Scheduling Problem.In:Proceedings of Ninth International Workshop on Project Management and Scheduling，pp.201～205，2004

[3]Imai，A.，Chen，H.C.，Nishimura，E.，Papadimitriou，S..The Simultaneous Berth and Quay Crane Allocation Problem.Transportation Research Part E.2008，44（5）:900～920

[4]Liang，C.，Huang，Y.，Yang，Y.，A Quay Crane Dynamic Scheduling Problem by Hybrid Evolutionary Algorithm for Berth Allocation Planning.Computers and Industrial Engineering，2008，56（3）:1021～1028

[5]Meisel，F.，Seaside Operations Planning in Container Terminals.Physica，Berlin et al.2009

[6]Bierwirth，C.，Meisel，F.，2009.A Fast Heuristic for Quay Crane Scheduling with Interference Constraints.Journal of Scheduling，doi:10.1007/s10951-009-0105-0.

[7]杜玉泉，陳秋雙，姬曉濤.面向服務的泊位和岸橋聯合調度[J].計算機集成制造系統，2011，17（9）:2051～2060

[8]趙坤強，韓曉龍，梁承姬.連續泊位下集裝箱港口泊位與吊橋協同調度優化研究[J].武漢理工大學學報，2011（11）:0060-06

[9]李娜，靳志宏．連續泊位調度與岸橋配置協同優化[J].中國航海，2011，34（2）：86～90

[10]樂美龍，劉菲．基于Memetic算法的泊位和岸橋分配問題[J]．武漢理工大學學報，2011，33（11）：66～71

Berth-Quay Crane Allocation;Genetic Algorithm;Service Priority;Vessel Scheduling

Berth-Quay Crane Allocation Based on the Ships'Service Priority

ZHANG Di，YAN Nan-nan
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

To solve the berth-quay crane allocation problem,formulates the mode with ships'service priority which aims to improve the service quality of container terminal and customers'satisfaction.And adopts the genetic algorithm with the heuristic algorithm for quay crane allocation for solving the problem,including the quay crane allocation and the corresponding vessel schedule in each berth.The results show that the algorithm is feasible and the turnaround time of vessels at port is less.In this connection,the efficiency of terminal operation is improved.

1007-1423（2015）14-0045-06

10.3969/j.issn.1007-1423.2015.14.011

張迪（1990-），女，安徽亳州人，碩士研究生，研究方向為港口物流優化

嚴南南（1968-），女，湖北鄂州人，博士，副教授，研究方向為智能信息處理與港口物流

2015-03-24

2015-05-12