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

張新宇， 林 俊， 郭子堅， 陳 向

(1.大連海事大學 航海動態(tài)仿真與控制交通部重點實驗室，遼寧 大連 116026；2.大連理工大學 水利工程學院，遼寧 大連 116024； 3.龍巖學院 機電工程學院， 福建 龍巖 364012)

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

張新宇1,2， 林 俊3， 郭子堅2， 陳 向1

(1.大連海事大學 航海動態(tài)仿真與控制交通部重點實驗室，遼寧 大連 116026；2.大連理工大學 水利工程學院，遼寧 大連 116024； 3.龍巖學院 機電工程學院， 福建 龍巖 364012)

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

水路運輸;單向航道；協(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)部門和學者的關(guān)注。相關(guān)研究主要集中在以下幾個方面。

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

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

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

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

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

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

1.1模型假設(shè)

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

1.2模型建立

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

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

2) 當船舶到達VTS監(jiān)控水域時，VTS根據(jù)航道和泊位此時的狀態(tài)安排船舶進港靠泊或在錨地拋錨等待，直到進港船舶完成靠泊作業(yè)或出港船舶離開港口水域為止。

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

模型中的決策變量如下。

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

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

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

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

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

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

2.1算法設(shè)計

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

2.2仿真試驗

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

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

4 結(jié)束語

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

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

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

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

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

[5] 徐國裕,郭涂城,吳兆麟. 單向水道船舶進出港最佳排序模式[J]. 大連海事大學學報, 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]. 上海:上海海事大學, 2007.

[12] 王冠儒. 基于遺傳算法的VTS船舶調(diào)度的設(shè)計與實現(xiàn)[D]. 大連:大連海事大學, 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

國家自然科學基金(51309043)；中國博士后科學基金(2014M551095)；遼寧省高校杰出青年學者成長計劃(LJQ2014052)；遼寧省教育廳重點實驗室基礎(chǔ)研究項目(LZ2015009)

張新宇(1978—)，男，吉林長春人，副教授，博士生，研究方向為交通信息工程及控制。E-mail:41544391@qq.com

1000-4653(2016)01-0026-05

U692.43

A