張新宇， 林 俊， 郭子堅(jiān)， 陳 向

(1.大連海事大學(xué) 航海動(dòng)態(tài)仿真與控制交通部重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116026；2.大連理工大學(xué) 水利工程學(xué)院，遼寧 大連 116024； 3.龍巖學(xué)院 機(jī)電工程學(xué)院， 福建 龍巖 364012)

基于模擬退火多種群遺傳算法的港口船舶調(diào)度優(yōu)化

張新宇1,2， 林 俊3， 郭子堅(jiān)2， 陳 向1

(1.大連海事大學(xué) 航海動(dòng)態(tài)仿真與控制交通部重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116026；2.大連理工大學(xué) 水利工程學(xué)院，遼寧 大連 116024； 3.龍巖學(xué)院 機(jī)電工程學(xué)院， 福建 龍巖 364012)

為協(xié)調(diào)港口航道與泊位資源，提高港口船舶調(diào)度效率，從單向航道出發(fā)，根據(jù)先后調(diào)度的2艘船舶的進(jìn)出港方向和所?？坎次坏倪h(yuǎn)近區(qū)分兩船間的相對關(guān)系，建立以總等待時(shí)間最少為目標(biāo)的調(diào)度優(yōu)化數(shù)學(xué)模型。設(shè)計(jì)適用于港口船舶調(diào)度優(yōu)化的模擬退火多種群遺傳算法(Simulated Annealing and Multiple Polulation Genetic Algorithm,SAMPGA)，模擬某港口不同調(diào)度規(guī)模的船舶進(jìn)行仿真試驗(yàn)，與先到先服務(wù)規(guī)則(First Come First Served,FCFS)和簡單遺傳算法(Simple Genetic Algorithm,SGA)進(jìn)行比較，證明SAMPGA在解決航道和泊位協(xié)調(diào)調(diào)度問題上的適用性。結(jié)果表明：在現(xiàn)有的調(diào)度規(guī)則下對航道和泊位進(jìn)行協(xié)調(diào)調(diào)度能減少船舶的等待時(shí)間和總調(diào)度時(shí)間，但實(shí)際調(diào)度規(guī)則需要考慮的限制因素更多，需對模型作進(jìn)一步優(yōu)化。

水路運(yùn)輸;單向航道；協(xié)調(diào)調(diào)度；船舶調(diào)度優(yōu)化；模擬退火多種群遺傳算法

Abstract: In order to improve the operation efficiency of the vessels and ports a mathematical model is established reflecting the relation between the vessel scheduling and the channel-berth allocation on the assumption of one-way channel. After determining the positional relationship between two successive vessels based on their sailing directions and the distances to the berths, this model solves the problem by means of the Simulated Annealing and Multiple Population Genetic Algorithm (SAMPGA) with the objective of minimum total waiting time. Simulation tests with vessels of different scales are conducted. The results indicate that the SAMPGA is more effective in coordinating channel and berth resources than the Simple Genetic Algorithm (SGA) or the "First-come, First-served" principle.

Keywords: waterway transportation; One-way channel; coordinated scheduling; vessel scheduling optimization; SAMPGA

隨著船舶逐漸大型化和港口吞吐量不斷提升，港口船舶調(diào)度問題備受有關(guān)部門和學(xué)者的關(guān)注。相關(guān)研究主要集中在以下幾個(gè)方面。

1) 航道通過能力方面：劉敬賢等[1]從港口航道系統(tǒng)特征和船舶交通流特征出發(fā)建立基于船舶行為特征的港口航道通過能力模型；代君等[2]從船舶領(lǐng)域出發(fā)提出一種受限航道通過能力計(jì)算方法；宋向群等[3]研究通航歷時(shí)對沿海散貨港區(qū)航道通過能力的影響，結(jié)果表明單線航道通過能力與通航歷時(shí)呈負(fù)指數(shù)關(guān)系，雙線航道通過能力不受通航歷時(shí)的影響。以上研究對港口建設(shè)有一定的指導(dǎo)意義。

2) 航道使用效率方面：王小平等[4]以船閘調(diào)度為研究對象建立三峽-葛洲壩水利樞紐聯(lián)合調(diào)度模型，但沒有考慮船舶通過航道的時(shí)間，不適用于一般航道的船舶調(diào)度；徐國裕等[5]在船舶調(diào)度中引入優(yōu)先級理論，根據(jù)船舶種類、噸位、吃水、裝載狀況及泊位距離推定綜合權(quán)重，運(yùn)用工作排序理論建立單向航道船舶進(jìn)出港最佳排序模式，該模式在提高通航效率方面優(yōu)于人工排序模式。

3) 泊位分配與其他港口資源協(xié)調(diào)調(diào)度方面：ETSUKO等[6]和IMAI等[7-8]對公共碼頭、集裝箱碼頭中的泊位分配問題進(jìn)行研究，探討泊位分配中的服務(wù)優(yōu)先權(quán)問題；HAN等[9]建立基于不連續(xù)泊位的具有不同服務(wù)優(yōu)先權(quán)的整數(shù)規(guī)劃模型，解決船舶到達(dá)時(shí)刻和裝卸作業(yè)時(shí)間不確定情況下的泊位與岸橋協(xié)調(diào)調(diào)度問題；JIN等[10]基于集裝箱碼頭泊位調(diào)度問題研究岸橋動(dòng)態(tài)優(yōu)化調(diào)度問題；王中華[11]在泊位調(diào)度模型的基礎(chǔ)上建立基于動(dòng)態(tài)船舶作業(yè)時(shí)間和船舶加權(quán)在港時(shí)間的船舶調(diào)度模型，并設(shè)計(jì)改進(jìn)遺傳算法進(jìn)行求解，得到船舶調(diào)度近似最優(yōu)解；王冠儒[12]基于泊位分配問題建立船舶調(diào)度數(shù)學(xué)模型，利用遺傳算法(Simple Genetic Algorithm,SGA)實(shí)現(xiàn)船舶的自動(dòng)分配，生成合理的船舶調(diào)度序列。上述研究僅針對泊位及其他碼頭資源的調(diào)度，忽略了船舶密集到港時(shí)航道對船舶調(diào)度的影響。

綜上，已有的船舶調(diào)度研究主要針對的是單一的航道或泊位，而港口船舶調(diào)度是一個(gè)連續(xù)的過程，應(yīng)通過協(xié)調(diào)航道與泊位資源來解決船舶在港作業(yè)時(shí)航道和泊位使用沖突。這里在現(xiàn)有航道與泊位分配研究的基礎(chǔ)上，基于單向航道對港口船舶優(yōu)化問題進(jìn)行研究。

1 港口船舶調(diào)度模型

實(shí)際的船舶進(jìn)出港是一個(gè)連續(xù)、受多種因素影響的過程，而船舶調(diào)度是港口管理中的重要環(huán)節(jié)，可在滿足港口管理規(guī)則的前提下提高船舶的通航效率、保證船舶安全航行。船舶調(diào)度與泊位是否空閑、船舶到達(dá)時(shí)刻及船舶當(dāng)前位置與航道間的距離等諸多因素有關(guān)。目前船舶泊位作業(yè)計(jì)劃是由碼頭公司制定的，而船舶交通管理(Vessel Traffic Service，VTS)中心則負(fù)責(zé)指揮船舶進(jìn)出航道、錨泊和靠離泊。因此，船舶調(diào)度作業(yè)主要由這2個(gè)部門協(xié)調(diào)完成，其中：VTS中心主要負(fù)責(zé)船舶在航道航行期間的安全；而碼頭公司則主要考慮船舶在港作業(yè)的效率。對此，建立基于航道和泊位資源協(xié)調(diào)的船舶調(diào)度模型，其關(guān)鍵在于對進(jìn)出港船舶進(jìn)行排序，確定船舶進(jìn)出港的時(shí)機(jī)，在保證船舶安全航行的前提下使其盡快完成作業(yè)計(jì)劃。

1.1模型假設(shè)

對模型作以下假設(shè):有多個(gè)錨地，且錨地容量無限;航道水深滿足船舶進(jìn)出港的要求;引航員和拖船可隨時(shí)到位;碼頭已制定好靠泊作業(yè)計(jì)劃;其他人為因素和環(huán)境因素均不對調(diào)度過程產(chǎn)生影響。

1.2模型建立

建立的調(diào)度模型示意圖見圖1。

1) 船舶向VTS中心發(fā)送預(yù)計(jì)抵港報(bào)告，碼頭公司根據(jù)抵達(dá)報(bào)告的時(shí)間安排船舶靠泊。

2) 當(dāng)船舶到達(dá)VTS監(jiān)控水域時(shí)，VTS根據(jù)航道和泊位此時(shí)的狀態(tài)安排船舶進(jìn)港靠泊或在錨地拋錨等待，直到進(jìn)港船舶完成靠泊作業(yè)或出港船舶離開港口水域?yàn)橹埂?/p>

該模型的核心在于根據(jù)船舶的到港順序合理安排船舶進(jìn)出航道，減少單向航道的進(jìn)出轉(zhuǎn)換時(shí)間，在保證安全的前提下使盡可能多的船舶在較短的時(shí)間內(nèi)完成港口作業(yè)計(jì)劃。模型中各變量的含義分別為：Numberv為調(diào)度船舶總數(shù);Numberb為泊位數(shù);ta為船舶到達(dá)時(shí)刻;ts為調(diào)度開始時(shí)刻;t0為靠泊時(shí)間;tc1為上航道時(shí)間;tc2為下航道時(shí)間;d為錨地與航道起點(diǎn)間距離;c1為航道長度;tgap0為同向安全時(shí)間間隔;tgap1為反向安全時(shí)間間隔;tf為調(diào)度完成時(shí)刻;L為船舶長度;V為在港航行平均速度;S為航道終點(diǎn)到泊位的距離;M為極大值。

模型中的決策變量如下。

1) 決策變量IO表示船舶進(jìn)出港方向。IOi=0表示船舶進(jìn)港；IOi=1表示船舶出港。

2) 決策變量R表示泊位遠(yuǎn)近的關(guān)系。Ri(i-1)=1表示第i艘船舶?？康牟次惠^上一艘調(diào)度船舶(i-1)?？康牟次贿h(yuǎn)；Ri(i-1)=0表示第i艘船舶?？康牟次惠^上一艘調(diào)度船舶(i-1)?？康牟次唤?。

3) 決策變量kij表示船舶i?？坎次籮。kij=1表示泊位空閑；kij=0表示泊位正在使用。

調(diào)度數(shù)學(xué)模型為

(1)

Subject to.

tgap0=6Li/vi-1

(2)

tgap1=6max{Li-1,Li}/vi-1

(3)

tc1i=tsi+(IOi)di/vi+(1-IOi)si/vi

(4)

tc2i=tc1i+cl/vi

(5)

tfi=tc2i+(IOi)si/vi

(6)

(7)

(8)

tc2i-1+tgap1≤tc1i

(9)

(10)

tai≤tsi

(11)

式(1)為目標(biāo)函數(shù)，表示所有船舶的總等待時(shí)間最少；式(2)為同向航行時(shí)兩船間安全航行的時(shí)間間隔，根據(jù)港口航行規(guī)則要求，同向航行的兩船在空間上必須保證6倍于前船船長的安全間距，轉(zhuǎn)化為時(shí)間約束即為兩船之間的時(shí)間間隔；式(3)為反向航行時(shí)兩船間的安全時(shí)間間隔；式(4)為船舶i上航道時(shí)刻，即船舶到達(dá)航道起點(diǎn)的時(shí)刻；式(5)為船舶i下航道時(shí)刻，即船舶到達(dá)航道終點(diǎn)的時(shí)刻；式(6)為調(diào)度結(jié)束時(shí)刻，即船舶靠上泊位或離開港口航道的時(shí)刻；式(7)為先后進(jìn)港的兩船之間的安全約束；式(8)為先后出港的兩船之間的安全約束；式(9)為出港船舶先調(diào)度、進(jìn)港船舶后調(diào)度時(shí)的安全約束，即反向航行的兩船在航道起點(diǎn)處相遇且出港船舶(i-1)先調(diào)度、進(jìn)港船舶后調(diào)度，在航道起點(diǎn)保持反向的安全間距；式(10)為進(jìn)港船舶先調(diào)度、出港船舶后調(diào)度時(shí)的安全約束，即反向航行的兩艘船在港池處相遇且進(jìn)港船舶(i-1)先調(diào)度、出港船舶后調(diào)度，兩船在靠近泊位處保持反向的安全間距；式(11)表示船舶調(diào)度開始時(shí)刻不早于船舶到達(dá)時(shí)刻。

2 協(xié)調(diào)航道與泊位的船舶調(diào)度

2.1算法設(shè)計(jì)

遺傳算法具有很強(qiáng)的并行計(jì)算和全局搜索能力，適于求解各種復(fù)雜的問題，已在很多領(lǐng)域得到應(yīng)用。為解決遺傳算法容易陷入局部最優(yōu)及后期收斂較慢的問題，采用多種群遺傳算法并加入退火機(jī)制，即模擬退火多種群遺傳算法(Simulated Annealing and Multiple Population Genetic Algorithm,SAMPGA)。由于其前期搜索空間較大、退火溫度高、適應(yīng)度值的變化范圍大，因此可保證算法不會(huì)陷入局部最優(yōu)的情況；隨著溫度不斷下降，搜索空間會(huì)急劇縮小，算法后期可發(fā)揮遺傳算法局部搜索的能力，從而保證最終結(jié)果收斂到最優(yōu)解的區(qū)間。在SAMPGA中，為使每次搜索都能達(dá)到理想狀態(tài)，其退火速度必須足夠慢，因此冷卻系數(shù)最好取接近于1的值。

2.2仿真試驗(yàn)

由于沒有直接可用的數(shù)據(jù)來驗(yàn)證模型和算法，因此模擬某港口航道的船舶調(diào)度數(shù)據(jù)進(jìn)行驗(yàn)證，具體為：第1錨地(A1)距離航道起點(diǎn)6 n mile，第2錨地(A2)距離航道起點(diǎn)8 n mile，航道長度cl為6 n mile，共18個(gè)泊位。船舶到港時(shí)間間隔服從負(fù)指數(shù)分布，其參數(shù)λ取20，時(shí)間段為09:00-10:00。為銜接每個(gè)時(shí)間段，還需考慮初始狀態(tài)航道上是否有船。假設(shè)初始狀態(tài)航道上有船，船舶初始狀態(tài)基本信息見表1。泊位信息及初始忙閑狀態(tài)見表2，其中距離指口門與泊位間的距離，n mile。本階段調(diào)度船舶的信息見表3。

將上述數(shù)據(jù)讀入程序中進(jìn)行計(jì)算，算法的基本參數(shù)為：種群大小250，代溝0.9，交叉概率0.9，變異概率0.05，最大遺傳代數(shù)500，退火初始溫度為100 °C，冷卻系數(shù)0.9。最優(yōu)調(diào)度方案見表4,算法收斂結(jié)果見圖2。

表1 船舶初始狀態(tài)信息

表2 泊位信息及初始忙閑狀態(tài)

表3 調(diào)度船舶的信息

表4 最優(yōu)解調(diào)度方案

3 結(jié)果分析

從以上優(yōu)化結(jié)果看，當(dāng)泊位資源有限時(shí)，整體上停靠同一泊位的船舶先出后進(jìn)，局部范圍內(nèi)調(diào)度趨于先快后慢，出港船舶按照泊位先近后遠(yuǎn)的規(guī)律，進(jìn)港船舶按照泊位先遠(yuǎn)后近的規(guī)律，符合實(shí)際的港口調(diào)度流程。將SAMPGA與SGA進(jìn)行比較，結(jié)果如圖2所示。從圖2中可看出，SAMPGA有多個(gè)種群同時(shí)搜索，110代左右收斂；SGA僅有1個(gè)種群搜索，經(jīng)過250代搜索后仍未找到最優(yōu)解；相對而言，SAMPGA收斂較快。從表5和圖3中可看出，SAMPGA的優(yōu)化效果較SGA和先到先服務(wù)規(guī)則(First Come First Served,FCFS)好，總等待時(shí)間為1 188 min，較后者分別下降86%和31%；總調(diào)度時(shí)間為325 min，與FCFS和SGA相比分別下降69%和21%，且最長等待時(shí)間為176 min。SAMPGA的調(diào)度優(yōu)化效果明顯優(yōu)于FCFS和SGA。從算法的角度看，SAMPGA能在較短的時(shí)間內(nèi)完成調(diào)度優(yōu)化作業(yè)，但其數(shù)學(xué)模型是在一定簡化基礎(chǔ)上得出的，縱然對實(shí)際港口的作業(yè)具有參考和輔助決策的作用，但就實(shí)際需要的調(diào)度系統(tǒng)來說還有很多需要完善的地方。

圖2 仿真結(jié)果

表5 SAMPGA調(diào)度優(yōu)化、SGA調(diào)度優(yōu)化與FCFS調(diào)度結(jié)果

圖3 3種調(diào)度方法用時(shí)對比

4 結(jié)束語

從單向航道出發(fā)協(xié)調(diào)航道與泊位資源，根據(jù)先后調(diào)度的2艘船舶的進(jìn)出港方向和泊位遠(yuǎn)近區(qū)分二者之間的相對關(guān)系，建立以總等待時(shí)間最少為目標(biāo)的調(diào)度優(yōu)化數(shù)學(xué)模型。設(shè)計(jì)適用于港口船舶調(diào)度優(yōu)化的模擬退火多種群遺傳算法，主要設(shè)計(jì)順序編碼算子和染色體修復(fù)算子等。模擬某港口不同調(diào)度規(guī)模的船舶,進(jìn)行相關(guān)試驗(yàn)，結(jié)果表明：依靠該模型和算法能大幅度減少船舶總調(diào)度時(shí)間和總等待時(shí)間，有效提高港口船舶調(diào)度效率。與先到先服務(wù)規(guī)則和簡單遺傳算法相比，該模型和算法趨于先出后進(jìn)、先快后慢，出港船舶按照泊位先近后遠(yuǎn)的規(guī)律，進(jìn)港船舶按照泊位先遠(yuǎn)后近的規(guī)律。

[1] 劉敬賢,文元橋. 基于船舶行為特征的港口航道通過能力仿真[J]. 大連海事大學(xué)學(xué)報(bào), 2009,35(2): 31-33.

[2] 代君,王當(dāng)利,劉克中. 基于船舶領(lǐng)域模型的港口受限航道通過能力計(jì)算方法[J]. 武漢理工大學(xué)學(xué)報(bào):交通科學(xué)與工程版, 2009,33(4):679-682.

[3] 宋向群,張靜,郭子堅(jiān),等. 通航歷時(shí)對沿海散貨港區(qū)航道通過能力的影響分析[J]. 港工技術(shù), 2010,47(2):18-20.

[4] 王小平,齊歡,肖恒輝，等. 基于串聯(lián)排隊(duì)網(wǎng)絡(luò)的三峽-葛洲壩水利樞紐聯(lián)合調(diào)度模型[J]. 交通運(yùn)輸工程學(xué)報(bào),2006,6(3):82-86.

[5] 徐國裕,郭涂城,吳兆麟. 單向水道船舶進(jìn)出港最佳排序模式[J]. 大連海事大學(xué)學(xué)報(bào), 2008,34(4):150-153.

[6] ETSUKO N, IMAI A, PAPADIMITRIOU S. Berth Allocation Planning in the Public Berth System by Genetic Algorithms[J]. European Journal of Operational Research,2001(131):282-292.

[7] IMAI A, NISHIMURA E, PAPADIMITRIOU S. Berth Allocation with Service Priority[J]. Transportation Research Part B, 2003,37:437-457.

[8] IMAI A, SUN X, NISHIMURA E,etal. Berth Allocation in a Container Port: Using a Continuous Location Space Approach[J]. Transportation Research Part B, 2005,39:199-221.

[9] HAN Xiaole, LU Zhiqiang, XI Lifeng. A Proactive Approach for Simultaneous Berth and Quaycrane Scheduling Problem with Stochastic Arrival and Handling Time[J]. European Journal of Operational Research, 2010,207: 1327-1340.

[10] JIN Zhihong, LI Na. Optimization of Quay Crane Dynamic Scheduling Based on Berth Schedules in Container Terminal[J]. Journal of Transportation System Enginering and Information Technology, 2011, 11(3):58-64.

[11] 王中華. 基于遺傳算法的港口船舶調(diào)度優(yōu)化問題研究[D]. 上海:上海海事大學(xué), 2007.

[12] 王冠儒. 基于遺傳算法的VTS船舶調(diào)度的設(shè)計(jì)與實(shí)現(xiàn)[D]. 大連:大連海事大學(xué), 2012.

VesselSchedulingOptimizationBasedonSimulatedAnnealingandMultiplePopulationGeneticAlgorithm

ZHANGXinyu1,2,LINJun3，GUOZijian2,CHENXiang1

(1. Key Laboratory of Maritime Dynamic Simulation and Control of Ministry of Transportation, Dalian Maritime University, Dalian 116026, China; 2. School of Hydraulic Engineering, Dalian University of Technology, Dalian 116024, China; 3. School of Mechanical and Electrical Engineering, Longyan University, Longyan 364012,China)

2015-11-18

國家自然科學(xué)基金(51309043)；中國博士后科學(xué)基金(2014M551095)；遼寧省高校杰出青年學(xué)者成長計(jì)劃(LJQ2014052)；遼寧省教育廳重點(diǎn)實(shí)驗(yàn)室基礎(chǔ)研究項(xiàng)目(LZ2015009)

張新宇(1978—)，男，吉林長春人，副教授，博士生，研究方向?yàn)榻煌ㄐ畔⒐こ碳翱刂?。E-mail:41544391@qq.com

1000-4653(2016)01-0026-05

U692.43

A