張新宇, 郭子堅, 王金濤, 林 俊(. 大連海事大學(xué) 航海動態(tài)仿真和控制交通行業(yè)重點(diǎn)實(shí)驗(yàn)室， 遼寧 大連 606； . 大連理工大學(xué) 水利工程學(xué)院， 遼寧 大連 603)

基于航道與泊位資源協(xié)調(diào)調(diào)度的船舶交通優(yōu)化

張新宇1,2, 郭子堅2, 王金濤1, 林 俊1
(1. 大連海事大學(xué) 航海動態(tài)仿真和控制交通行業(yè)重點(diǎn)實(shí)驗(yàn)室， 遼寧 大連 116026； 2. 大連理工大學(xué) 水利工程學(xué)院， 遼寧 大連 116023)

將港口航道與泊位資源協(xié)調(diào)利用，可最大限度地提高港口運(yùn)營效率。對此，以所有船舶總在港時間和等待時間最少為目標(biāo)，建立基于單向航道的多目標(biāo)船舶調(diào)度優(yōu)化模型。根據(jù)港口不同區(qū)域的交通流特征，建立初始化約束、流量轉(zhuǎn)換約束、時隙分配約束和泊位沖突消解約束等多個約束模型。設(shè)計多目標(biāo)遺傳算法進(jìn)行求解，并設(shè)計有針對性的模擬場景進(jìn)行驗(yàn)證；以港口某一繁忙時段的20艘船舶為例，進(jìn)行調(diào)度試驗(yàn)。最終得到8個Pareto最優(yōu)解和2個目標(biāo)的最優(yōu)解：總調(diào)度時間為2.618 6 h，添加懲罰后總等待時間為23.012 4 h。結(jié)果表明:該模型及算法給出的調(diào)度方案能有效提高船舶的調(diào)度效率。

水路運(yùn)輸； 單向航道； 船舶調(diào)度優(yōu)化； 多目標(biāo)遺傳算法； 時隙分配； 流量轉(zhuǎn)換

海上運(yùn)輸是目前國際貨物運(yùn)輸中最主要的方式，其服務(wù)質(zhì)量很大程度上受港口對船舶進(jìn)出港服務(wù)效率的影響。目前關(guān)于船舶進(jìn)出港調(diào)度的研究主要側(cè)重于航道流量和泊位分配中的單一方面，而對于兩者協(xié)調(diào)調(diào)度的研究相對較少。

在航道通過能力方面：邵俊崗等[1]運(yùn)用排隊(duì)論對港口通過能力進(jìn)行了綜合評估；李子強(qiáng)[2]通過分析交通流，對航道通過能力進(jìn)行了研究；代君等[3]運(yùn)用船舶領(lǐng)域模型對港口受限航道通過能力的計算方法進(jìn)行了探討。這些研究針對的是靜態(tài)模型，不能反映動態(tài)交通情況。此外，張瑋等[4-6]分別針對蘇北大運(yùn)河、長江三峽和葛洲壩的單向航段進(jìn)行了規(guī)劃研究，研究重點(diǎn)是通航閘口管制，無須考慮航道通過時間，并不適用于單向航道的船舶調(diào)度問題。

在航道使用效率方面：徐國裕等[7]根據(jù)船載自動識別系統(tǒng)(Automatic Identification System，AIS)提供的與船舶航行安全相關(guān)的資料，以泊位遠(yuǎn)近、船舶大小、船舶類型和船舶吃水等因素為權(quán)重，提出了單向水道船舶進(jìn)出港最佳排序模式；LLOYD等[8-9]對保持安全水域空間、構(gòu)建整合系統(tǒng)和減少排序沖突給予了充分關(guān)注；OZGECAN等[10]采用多種排隊(duì)模型分析了伊斯坦布爾海峽的狹長水道內(nèi)船舶航行的風(fēng)險和效率，并針對水道中突發(fā)的交通阻塞問題進(jìn)行了多種中斷排隊(duì)優(yōu)化。PULUGURTHAL等[11]從航道流量角度進(jìn)行了船舶調(diào)度優(yōu)化，側(cè)重于航道的運(yùn)輸效率，忽略了船舶進(jìn)入泊位的作業(yè)效率。

在模型求解方面：李平等[12]將遺傳算法和混合優(yōu)化策略應(yīng)用到了求解集裝箱港口的泊位調(diào)度問題中；KAP等[13]以船舶因延誤離港而導(dǎo)致的罰金與因不合理停泊導(dǎo)致的額外搬運(yùn)集裝箱費(fèi)用之和最小為目標(biāo)，提出了一種基于模擬退火算法的泊位分配模型；CHUANG等[14]設(shè)計了模糊遺傳算法求解航線調(diào)度優(yōu)化模型，可為船舶航線調(diào)度問題提供輔助支持。

綜上所述，目前關(guān)于船舶進(jìn)出港調(diào)度的研究主要側(cè)重于航道容量和泊位分配中的單一方面，在實(shí)際的港口調(diào)度中，船舶進(jìn)出港管理效率較低。對此，以航道為切入點(diǎn)，協(xié)調(diào)泊位資源，構(gòu)建多目標(biāo)港口船舶調(diào)度優(yōu)化模型，設(shè)計適于求解的多目標(biāo)遺傳算法，并設(shè)計模擬數(shù)據(jù)進(jìn)行驗(yàn)證。

1 問題描述

船舶調(diào)度的目的是在遵循航道管理規(guī)則和保證港口水域通航安全的條件下，使船舶盡快、盡量多地通過航道，減少船舶延誤。對于單向航道，在港口繁忙的情況下，港口船舶調(diào)度的核心問題是泊位和航道資源的優(yōu)化配置。交通量的大小受船舶進(jìn)出港初始狀態(tài)、同向船舶的安排協(xié)調(diào)、進(jìn)出流量的安排控制以及泊位沖突消解等因素的制約。因此，港口船舶調(diào)度問題是典型的NP-Hard (Non-deterministic Polynomial-time Hard)問題。

2 模型建立

2.1概念解釋

1) 單向航道：同一時間只允許同一個方向通航的航道。

2) 時隙分配：這里的一個時隙指從一艘船舶開始進(jìn)出港到下一艘船舶開始進(jìn)出港的時間間隔。

3) 流量轉(zhuǎn)換：船舶進(jìn)港流量和出港流量的協(xié)調(diào)。

2.2模型假設(shè)

1) 港口已做好船舶靠泊作業(yè)計劃，船舶交通管理中心負(fù)責(zé)港口船舶進(jìn)出港調(diào)度。

2) 天氣對港口船舶調(diào)度沒有影響，拖船和引航員充足且能準(zhǔn)時到位。

2.3船舶調(diào)度模型建立

2.3.1目標(biāo)函數(shù)的建立

港口方和船方在船舶調(diào)度過程中的利益訴求不同。單純從時間的維度考慮，港口方希望所有船舶完成調(diào)度的時間最短，而船方則希望各自船舶在港的等待時間最短。這里根據(jù)兩利益方關(guān)心的問題，構(gòu)建多目標(biāo)目標(biāo)函數(shù)Min[F,W]

(1)

Min(bi-t0i)

(2)

式(1)～式(2)中：F為所有船舶完成進(jìn)出港的最少總時間；W為修正后所有船舶等候進(jìn)出港的最少時間總和；bi為第i艘船舶進(jìn)/出港開始時刻;fi為第i艘船舶進(jìn)/出港結(jié)束時刻;t0i為船舶i進(jìn)入報告線的時刻;s為報告線與航道入口間的距離;si為理論上第i艘船舶的泊位與航道入口間的距離;vi為理論上第i艘船舶從進(jìn)入航道到抵達(dá)泊位處的平均速度;b0為上一時間段內(nèi)最后一艘船舶進(jìn)港(出港)開始時刻;f0為上一時間段內(nèi)最后一艘船舶進(jìn)港(出港)結(jié)束時刻;h0為本階段第一艘船舶與上一階段最后一艘船舶的安全時間間隔。

式(1)表示本階段所有船舶完成進(jìn)出港所使用的總時間最少；式(2)表示所有船舶等候進(jìn)出港時間總和最少。這里的船舶等候進(jìn)出港時間指船舶實(shí)際使用的進(jìn)出港時間與理論上船舶最快進(jìn)出港時間的差值，即船舶在港浪費(fèi)的時間成本。

2.3.2船舶調(diào)度模型約束的建立

IOi=(0,1)i=1,2,3,…,n

(3)

Rij=(0,1)i=1,2,3,…,n

(4)

Bij=(0,1)i=1,2,3,…,n

(5)

Berthim=(0,1)i=1,2,3,…,n

(6)

(7)

(bi-b0-h-Bijh1)×[1-(IOi-IO0)2]≥0

i=1,2,3,…,n

(8)

(fi-f0-h-Bijh1)×[1-(IOi-IO0)2]≥0

i=1,2,3,…,n

(9)

(10)

fi-bi-pi≥0i=1,2,3,…,n

(11)

(12)

(13)

(IOi-IOj)2≥0i

(14)

(bi-bj+MRij-h-Bijh1)×[1-

(IOi-IOj)2]≥0i

(15)

[-bi+bj+M(1-Rij)-h-Bijh1]×[1-

(IOi-IOj)2]≥0i

(16)

(fi-fj+MRij-h-Bijh1)×

[1-(IOi-IOj)2]≥0i

(17)

[-fi+fj+M(1-Rij)-h-Bijh]×[1-

(IOi-IOj)2]≥0i

(18)

(1-Berthin)+M(1-IOi)>0t=bi

(19)

式(7)為船舶i開始調(diào)度時刻必須晚于船舶i預(yù)計到達(dá)航道入口的時間; 式(8)～式(10)為保證模型的連續(xù)性構(gòu)建的初始化約束； 式(11)～式(14)為流量轉(zhuǎn)換約束，主要實(shí)現(xiàn)進(jìn)出港船舶的流量在時間上的轉(zhuǎn)換； 式(15)～式(18)為時隙分配約束，用于協(xié)調(diào)先后調(diào)度的2艘船舶同向航行時的安全問題，主要考慮安全時間間隔、船舶的先后次序和泊位遠(yuǎn)近；式(19)為泊位沖突消解約束，保證任意一艘進(jìn)港船舶調(diào)度開始時刻，其將要停靠的泊位是空閑的。

3 算法設(shè)計

遺傳算法具有較好的并行計算能力，是在多目標(biāo)優(yōu)化領(lǐng)域應(yīng)用最成功的算法之一。這里針對港口船舶調(diào)度設(shè)計遺傳算法進(jìn)行求解。為模型設(shè)計的多目標(biāo)遺傳算法流程圖見圖1。

4 實(shí)例驗(yàn)證

使用MATLAB 2010b設(shè)計港口船舶調(diào)度多目標(biāo)遺傳算法程序，基于MATLAB GUI實(shí)現(xiàn)計算結(jié)果的可視化。對某港口某天某時段的船舶進(jìn)行調(diào)度試驗(yàn)，模擬20艘船舶(14進(jìn)6出)準(zhǔn)備時刻的間隔服從λ=20的負(fù)指數(shù)分布規(guī)律的場景。準(zhǔn)備時刻是指只要泊位和航道條件允許，即可調(diào)度船舶的時刻；航行距離是指航道起點(diǎn)與泊位間的距離。模擬數(shù)據(jù)的船舶信息見表1。

圖1 多目標(biāo)遺傳算法流程圖

假設(shè)上一階段最后一艘船舶的進(jìn)出港開始時刻為07:00。表2給出了上一階段最后一艘船舶的相關(guān)信息。

表2 上一階段最后一艘船舶信息

泊位是碼頭集團(tuán)按照申請預(yù)先分配完成的，且泊位的條件都滿足要停靠船舶的要求。表3給出了本階段調(diào)度開始時刻泊位的空閑和占用狀態(tài)，模擬數(shù)據(jù)假設(shè)共有18個泊位。

表3 泊位開始時刻的空閑和占用狀態(tài)

將上述數(shù)據(jù)讀入程序進(jìn)行運(yùn)算，參數(shù)為:種群大小200,代溝0.9,交叉概率0.95,變異概率0.05,最大遺傳代數(shù)200。運(yùn)行結(jié)果見圖2?？煽闯龉灿?個Pareto最優(yōu)解，20艘船舶調(diào)度完成所用總時間為2.618 6 h，添加懲罰后的總等待時間為23.012 4 h；種群在不斷尋優(yōu)，并在200代以內(nèi)收斂。

8個Pareto最優(yōu)解見表4。在總調(diào)度時間的方向上，最優(yōu)解為2.618 6 h，此時總等待時間的適應(yīng)度值為24.776 7 h。在總等待時間方向上，最優(yōu)解為23.012 4 h，此時總調(diào)度時間為2.698 5 h。這符合多目標(biāo)遺傳算法結(jié)果的特點(diǎn)：當(dāng)一個目標(biāo)改進(jìn)時,另一個目標(biāo)會相應(yīng)地衰退。由于船舶準(zhǔn)備調(diào)度時刻比較集中，因此雖然能增加船舶可調(diào)度時間段，但同時也會造成船舶等待時間延長。

對于單向航道，航道上的船舶不能對遇，在進(jìn)行流量轉(zhuǎn)換前必須保證航道上沒有船舶，進(jìn)而會消耗較多的時間。因此，理論上對于較長的單向航道而言，流量轉(zhuǎn)換的次數(shù)越少，所有船舶完成調(diào)度所用時間就越短。8個Pareto最優(yōu)解的調(diào)度方案都只進(jìn)行3次流量轉(zhuǎn)換，大大提高了船舶的調(diào)度效率。

每個Pareto最優(yōu)解代表一個調(diào)度方案，經(jīng)檢驗(yàn)，8個Pareto最優(yōu)解均符合以上約束，可保證船舶的安全。在實(shí)際應(yīng)用中，若港口追求總調(diào)度時間最短，可選用第1目標(biāo)值較小的調(diào)度方案Pareto1；若兼顧每艘船舶的等待時間，可選用第2目標(biāo)值較小的調(diào)度方案Pareto8。

表4 Pareto 最優(yōu)解

5 結(jié)束語

研究了基于單向航道和泊位資源協(xié)調(diào)調(diào)度的船舶交通管理問題，建立了以所有船舶總在港時間和等待時間最少為目標(biāo)的基于單向航道的多目標(biāo)船舶調(diào)度優(yōu)化模型。使用MATLAB 2010b編寫了港口船舶調(diào)度多程序，基于MATLAB GUI實(shí)現(xiàn)了計算結(jié)果的可視化。經(jīng)驗(yàn)證，該模型能大大提高船舶進(jìn)出港作業(yè)的效率。

[1] 邵俊崗, 許小兵，王煜，等. 洋山港區(qū)運(yùn)營階段的港口通過能力[J]. 上海海事大學(xué)學(xué)報， 2008, 29(4): 25-28.

[2] 李子強(qiáng). 基于交通流分析的航道通過能力研究[J]. 山東交通學(xué)院學(xué)報，2009，17(4)：32-35.

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

[4] 張瑋, 廖鵬，吳玲莉，等. 船閘通過能力主要影響因素[J].交通運(yùn)輸工程學(xué)報， 2004, 4(3): 108-110.

[5] 胡洋. 三峽工程五級船閘通過能力初步分析和提高樞紐綜合通過能力的對策[J]. 水運(yùn)工程, 2004(10): 74-77.

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

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

[8] LLOYD D N.Integrating VTS with Port Operation[Z]. Hongkong: Proceedings of VTS 2004,2004: 44-52.

[9] MEINE J,KRAMER M.Creation of a Regionee VTS with Data Fusion and Integration of Vessel Data and Movement Details Over the Area of Several Independent Ports, Coastal And Inland Waterways[Z]. Hongkong: Proceedings of VTS 2004,2004: 235-248.

[10] OZGECAN S U T. Performance Modeling and Risk Analysis of Transit Vessel Traffic in the Istanbul Strait: Studies on Queues with Multiple Types of Interruptions [D]. New Brunswick: Rutgers the State University of New Jersey, 2011.

[11] PULUGURTHAL S S, NAMBISAN S S. Using Genetic Algorithms to Evaluate Aircraft Ground Holding Policy Under Static Conditions[J]. Journal of Transportation Engineering, 2011,127(5): 433-441.

[12] 李平, 孫俊清, 韓梅 .泊位調(diào)度問題的GATS混合優(yōu)化策略[J] .天津理工大學(xué)學(xué)報, 2009, 22(4): 58-61.

[13] KAP H K, KYUNG C. Moon Beth Scheduling by Simulated Annealing[J]. Transportation Research Part B, 2012(37): 541-560.

[14] CHUANG T N, LIN C T, KUNG J Y,etal. Planning the Route of Container Vessels: A Fuzzy Genetic Approach[J]. Expert Systems with Applications, 2010(37): 2948-2956.

OptimizationofVesselSchedulingBasedonCoordinationofOne-WayChannelandBerths

ZHANGXinyu1,2,GUOZijian2，WANGJintao1，LINJun1
(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 116023, China)

Careful coordinating the channel and berths can maximize the efficiency of a port. With the objective that total sum of time of all vessels spending in the harbor and waiting for available channel is minimized, a multi-objective optimization model of vessel scheduling based on one-way channel is built. Initialization constraints, traffic conversion constraints, slot allocation constraints and berths conflict resolution models are defined respectively based on traffic flow characteristics in different regions of the port. A multi-objective genetic algorithm is designed to solve the proposed model, and a practical scenario of 20 vessels at a peak period is designed to validate the reasonability and effectiveness of the model. The simulation results show that there are 8 Pareto optimal scheduling scheme options as the optimal solution, in which the total of time is 2.6186 hours and the waiting time is 23.0124 hours. The results of experiment suggest that the proposed scheduling model is of great value to improve the efficiency of vessel traffic.

waterway transportation; one-way channel; vessel scheduling optimization; multi-objective genetic algorithm; slot allocation; traffic flow transition

2015-05-11

國家自然科學(xué)基金(51309043);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(3132014202); 交通部應(yīng)用基礎(chǔ)研究項(xiàng)目(2014329225020);中國博士后科學(xué)基金(2014M551095);遼寧省自然科學(xué)基金(2014025005);遼寧省高校杰出青年學(xué)者成長計劃(LJQ2014052)

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

1000-4653(2015)03-0033-04

U691+.3

A