張　迪，嚴(yán)南南（上海海事大學(xué)信息工程學(xué)院，上海201306）

考慮船舶服務(wù)優(yōu)先權(quán)的泊位-岸橋分配

張迪，嚴(yán)南南
（上海海事大學(xué)信息工程學(xué)院，上海201306）

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

泊位-岸橋分配；遺傳算法；服務(wù)優(yōu)先權(quán)；船舶調(diào)度

0　引言

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

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

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

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

所以，本文對(duì)于泊位與岸橋的分配問題，在建立目標(biāo)函數(shù)時(shí)引入船舶服務(wù)優(yōu)先權(quán)，目標(biāo)函數(shù)選取以最小化船舶等待時(shí)間、作業(yè)時(shí)間以及延遲時(shí)間，從而建立泊位-岸橋調(diào)度模型。為了求解此模型，設(shè)計(jì)了遺傳算法。

1　問題描述

通常，在船舶抵港之前，碼頭管理者會(huì)根據(jù)碼頭現(xiàn)場(chǎng)情況與船舶到港信息等，制定優(yōu)化策略將泊位和岸橋分配給各船舶。

本文選取一段時(shí)間內(nèi)港口所到達(dá)的船舶作為研究對(duì)象，引入船舶服務(wù)優(yōu)先權(quán)，其中通過船舶裝卸量決定船舶服務(wù)優(yōu)先權(quán)，根據(jù)問題的實(shí)際情況，做出以下假設(shè)：

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

（2）每艘船舶有且只有一次靠泊機(jī)會(huì)，排除移泊情況；

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

（4）每艘船舶的到港時(shí)間確定；

（5）船舶開始作業(yè)后將不能被中斷直至結(jié)束作業(yè)。

2　優(yōu)化模型

本文引入的符號(hào)如下：

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

模型的目標(biāo)函數(shù)為：

約束條件為:

目標(biāo)函數(shù)式（1）表示在考慮船舶優(yōu)先權(quán)的情況對(duì)于所有船舶等待時(shí)間的和求最小。式（2）表示對(duì)船舶作業(yè)時(shí)間以及延遲時(shí)間求最小。

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

3　模型求解

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

其流程圖如圖1所示。

圖1　遺傳算法流程圖

算法步驟如下：

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

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

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

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

表2　船舶調(diào)度-染色體編碼

①在為泊位分配的岸橋數(shù)目確定的條件下，對(duì)船舶調(diào)度的個(gè)體進(jìn)行適應(yīng)值計(jì)算。

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

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

圖2　船舶調(diào)度-染色體變異及調(diào)整圖

（4）將船舶調(diào)度中的最優(yōu)解與岸橋分配的初始解，引入到岸橋分配算法中。

（5）對(duì)于岸橋分配的個(gè)體，進(jìn)行適應(yīng)值計(jì)算。

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

（7）交叉、變異操作：對(duì)于岸橋分配的個(gè)體采用單點(diǎn)交叉法，通過調(diào)整策略產(chǎn)生可行的子代，如圖3所示。變異則采取單點(diǎn)隨機(jī)變異。

圖3　岸橋分配-染色體變異及調(diào)整圖

（8）確定是否達(dá)到終止條件，若達(dá)到則得出最優(yōu)解，若沒有，轉(zhuǎn)到步驟2重復(fù)執(zhí)行。本文中采用設(shè)定進(jìn)化代數(shù)的方法來結(jié)束算法運(yùn)算。

4　算例分析

某集裝箱碼連續(xù)岸線頭總長(zhǎng)1000m，岸橋7臺(tái)，泊位為4個(gè)。選擇以一段時(shí)間間隔的到港船舶數(shù)據(jù)。另根據(jù)碼頭生產(chǎn)經(jīng)營(yíng)統(tǒng)計(jì)數(shù)據(jù)，取v0=65箱/h。

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

在算法程序中，其余條件均不變，但是并不引入船舶服務(wù)優(yōu)先權(quán)，即設(shè)置σ=0，得出的泊位-岸橋分配圖如圖5。

圖4　 σ=200時(shí)泊位-岸橋分配圖

將計(jì)算結(jié)果比較，如表4，可以看出，當(dāng)σ=200時(shí)的船舶等待時(shí)間要比σ=0時(shí)的船舶等待時(shí)間少，即在模型中引入船舶服務(wù)優(yōu)先權(quán)，可以將船舶的等待時(shí)間減少，從而總體減少船舶在港時(shí)間，減少碼頭的運(yùn)營(yíng)成本。所以在碼頭的實(shí)際作業(yè)中，可以引入船舶服務(wù)優(yōu)先權(quán)，更有利于提高碼頭的服務(wù)水平和客戶的滿意度。

表3　到港船舶數(shù)據(jù)

表4　結(jié)果比較

5　結(jié)語

本文主要研究了在考慮船舶優(yōu)先權(quán)的因素下，建立優(yōu)化模型，以最小化船舶總的在港時(shí)間為目標(biāo)函數(shù)，從而減少時(shí)間成本，并設(shè)計(jì)改進(jìn)的遺傳算法對(duì)算例進(jìn)行求解，在遺傳算法設(shè)計(jì)中，將泊位-岸橋集成分配轉(zhuǎn)化為對(duì)泊位的岸橋分配以及船舶調(diào)度，從而減少了岸橋移動(dòng)的成本。最后對(duì)比計(jì)算結(jié)果，證明了模型和算法是有效的，并且表明考慮到船舶優(yōu)先服務(wù)權(quán)的模型更有利于提高碼頭的作業(yè)效率。但是在本文的泊位-岸橋分配中并未考慮到實(shí)際作業(yè)中的不確定因素的影響，所以可以在今后的研究中繼續(xù)深化。

圖5　 σ=0時(shí)泊位-岸橋分配圖

[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(xiàn).，Seaside Operations Planning in Container Terminals.Physica，Berlin et al.2009

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

[7]杜玉泉，陳秋雙，姬曉濤.面向服務(wù)的泊位和岸橋聯(lián)合調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，2011，17（9）:2051～2060

[8]趙坤強(qiáng)，韓曉龍，梁承姬.連續(xù)泊位下集裝箱港口泊位與吊橋協(xié)同調(diào)度優(yōu)化研究[J].武漢理工大學(xué)學(xué)報(bào)，2011（11）:0060-06

[9]李娜，靳志宏．連續(xù)泊位調(diào)度與岸橋配置協(xié)同優(yōu)化[J].中國航海，2011，34（2）：86～90

[10]樂美龍，劉菲．基于Memetic算法的泊位和岸橋分配問題[J]．武漢理工大學(xué)學(xué)報(bào)，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-），女，安徽亳州人，碩士研究生，研究方向?yàn)楦劭谖锪鲀?yōu)化

嚴(yán)南南（1968-），女，湖北鄂州人，博士，副教授，研究方向?yàn)橹悄苄畔⑻幚砼c港口物流

2015-03-24

2015-05-12