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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

2 模型建立

2.1概念解釋

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

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

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

2.2模型假設

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

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

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

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

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

(1)

Min(bi-t0i)

(2)

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

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

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預計到達航道入口的時間; 式(8)～式(10)為保證模型的連續(xù)性構(gòu)建的初始化約束； 式(11)～式(14)為流量轉(zhuǎn)換約束，主要實現(xiàn)進出港船舶的流量在時間上的轉(zhuǎn)換； 式(15)～式(18)為時隙分配約束，用于協(xié)調(diào)先后調(diào)度的2艘船舶同向航行時的安全問題，主要考慮安全時間間隔、船舶的先后次序和泊位遠近；式(19)為泊位沖突消解約束，保證任意一艘進港船舶調(diào)度開始時刻，其將要?？康牟次皇强臻e的。

3 算法設計

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

4 實例驗證

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

圖1 多目標遺傳算法流程圖

假設上一階段最后一艘船舶的進出港開始時刻為07:00。表2給出了上一階段最后一艘船舶的相關信息。

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

泊位是碼頭集團按照申請預先分配完成的，且泊位的條件都滿足要?？看暗囊蟆１?給出了本階段調(diào)度開始時刻泊位的空閑和占用狀態(tài)，模擬數(shù)據(jù)假設共有18個泊位。

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

將上述數(shù)據(jù)讀入程序進行運算，參數(shù)為:種群大小200,代溝0.9,交叉概率0.95,變異概率0.05,最大遺傳代數(shù)200。運行結(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，此時總等待時間的適應度值為24.776 7 h。在總等待時間方向上，最優(yōu)解為23.012 4 h，此時總調(diào)度時間為2.698 5 h。這符合多目標遺傳算法結(jié)果的特點：當一個目標改進時,另一個目標會相應地衰退。由于船舶準備調(diào)度時刻比較集中，因此雖然能增加船舶可調(diào)度時間段，但同時也會造成船舶等待時間延長。

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

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

表4 Pareto 最優(yōu)解

5 結(jié)束語

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

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

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

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

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

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

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

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

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

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

1000-4653(2015)03-0033-04

U691+.3

A