雙向通航港口船舶調度優化模型與算法

張新宇, 李瑞杰, 林 俊, 陳 向

(1. 大連海事大學 航海動態仿真與控制交通行業重點實驗室， 遼寧 大連 116026； 2. 龍巖學院 機電工程學院， 福建 龍巖 364012)

海上運輸是國際貿易中最主要的貨物運輸方式，近年來國內外各港口為適應不斷擁擠的海上交通，或擴大建設規模，或不斷拓寬航道，從單向航道逐步發展到雙向航道，甚至是復式航道。雙向航道在減少船舶在港待航時間、提高航道利用率和緩解通航壓力等方面相對單向航道有很大優勢。在港口實際操作中，雙向通航港口船舶進出航道需考慮眾多因素，涉及多個部門之間的協調，目前缺少一個協調高效的優化調度方法。同時，針對雙向通航港口船舶調度優化的研究相對很少，相關研究主要有雙向通航安全、港口船舶調度優化建模和調度模型求解算法等。

在雙向通航安全方面：GAAFARY等[1]從船舶操縱控制方面分析土耳其海峽雙向通航的可行性；OZGECAN等[2]對航行條件復雜且交通擁擠的伊斯坦布爾海峽的船舶交通進行風險分析：OZGECAN等[3]研究一種關于船舶進出伊斯坦布爾海峽順序的調度算法。這些研究大多針對海峽或船閘的通航安全，并不完全適于解決一般雙向通航港口的船舶調度問題。

港口船舶調度模型主要用來提高船舶通過港區可航水域的效率和碼頭資源調度效率。FILIPOWIC[4]將受限水域抽象為包括多個節點的圖形結構，利用種群學習算法實現過往船舶對不同節點的選擇來平衡或緩解局部航段的擁擠，達到均衡交通流的效果；徐國裕等[5]在船舶調度中引入優先級，用船舶種類、噸位、吃水、裝載狀況和泊位距離等參數推定綜合權重，應用工作排序理論建立單向水道船舶進出港最佳排序模式；王金濤[6]利用容量轉換和協同決策思想建立多目標船舶調度模型，對單向航道船舶調度問題進行優化。這些提高航道使用效率的調度模型或基于受限水域、交匯水域，或基于單向航道，并不適用于雙向通航港口的船舶調度。在碼頭資源調度優化方面，IMAI等[7-8]針對泊位優先權、連續泊位等泊位分配問題開展一系列研究。盡管船舶調度優化模型方面的研究成果較多，但主要針對的是泊位和岸橋等碼頭資源的調度，而港口船舶作業是一個連續的過程，滿足碼頭作業效率最大化可能導致船舶進出航道順序不合理，降低船舶整體的調度效率。為此，ZHANG等[9]對單向航道和泊位資源協調調度進行優化建模，結果表明協調航道和泊位等港口資源形成統一的船舶調度方案，確實能提高船舶調度效率。

因此，本文在對多個港口進行調研的基礎上，分析港口雙向通航船舶調度需求，建立雙向通航港口船舶調度優化多目標數學模型，設計多目標遺傳算法獲取最佳調度方案。

1 問題描述

航道實施雙向通航是有條件的，雙向通航港口船舶調度必須考慮單向通航與雙向通航的轉換問題。船舶在港作業是一個連續的過程，一個安全可行的船舶調度方案應能提前預知并避免船舶在航道上面臨緊迫形勢或進港之后沒有泊位停靠的問題。雙向通航港口船舶調度的關鍵在于確定船舶通航模式(單向/雙向)、協調各港口資源、合理安排船舶進出航道的順序和時間，在保證安全的情況下使盡可能多的船舶盡快進出港，提高船舶進出港效率。

2 模型建立

2.1 模型假設

影響港口船舶調度的因素多且復雜，本文提取關鍵因素，作以下假設。

1) 針對某時間段內出現的船舶調度問題進行建模。

2) 港口有多個錨地且容量無限。

3) 進港船舶在錨地等候進港，出港船舶在泊位等候出港(基于此，進港船舶的航行距離為錨地到泊位的距離，出港船舶的航行距離為泊位到航道起點的距離)。

4) 航道水深滿足船舶進出港要求。

5) 船舶申請進出港時刻，引航員、拖船和泊位等已分配好并準備就緒。

6) 采用雙向通航港口規則，其中對單向通航和雙向通航的規定為：除下列情況只允許單向通航外，其它均為雙向通航。

(1) 視程

(2) 風力≥W1；

(3) 單船船寬≥Y1；

(5) 擬相對航行的兩船船寬之和≥Y2。

2.2 目標函數

經調研發現，由于港口船舶調度涉及眾多部門，對調度結果的期望各不相同。在形成統一的船舶調度方案時，從整體上看，總調度時間和總等待時間越短，表明調度效率越高。因此，從高效性出發，建立總調度時間最少和總等待時間最少的目標函數。

minT1=max(fi)-[Ijmin(t1j)+

(1)

(2)

式(1)和式(2)中：總調度時間T1是最遲完成調度時刻與最早開始調度時刻的差值；總等待時間T2包括所有進港船舶在錨地等待進港時間和出港船舶在泊位等待出港時間。前者為開始進港時刻與申請進港時刻之差；后者為開始出港時刻與申請出港時刻之差。

2.3 約束條件

2.3.1模式轉換約束

由于雙向通航是有條件的，不可避免地會出現單向通航的情況，因此模式轉換約束是雙向通航港口船舶調度的必然要求。根據假設中的通航規則，建立單向/雙向通航模式轉換約束為

(3)

2.3.2連續性約束

船舶在港作業是一個連續的過程，一旦開始調度時刻確定，在船舶航速、船舶當前位置、船舶到達航道和泊位的距離已知的情況下，船舶到達航道、泊位的時刻即可確定。

2.3.2.1 開始時刻約束

式(4)為船舶i開始進港時刻不得早于其申請進港時刻，且船舶i進港時，其所停靠的泊位必須是空閑的，否則船舶i必須在錨地等待。式(5)為船舶i開始出港時刻不得早于其申請出港時刻。

2.3.2.2 航行時刻約束

通常情況下，船舶到達航道起點、航道終點、靠泊和離泊時須向交通管理中心(Vessel Traffic Service, VTS)報告。在建模時，選擇航道起點、航道終點和泊位等作為關鍵點，主要計算船舶上航道時刻、下航道時刻、到達泊位時刻、靠好泊位時刻和完成調度時刻等。計算方法分別為

(12)

2.3.3安全性約束

2.3.3.1 任意2艘船舶之間的安全約束

為保證船舶在航道中安全航行，任意2艘船舶之間必須保持一定的安全間距，包括縱向安全間距和橫向安全間距。縱向安全間距根據船舶航向的異同分為異向安全間距和同向安全間距。[10]通過從空間到時間的轉換，將安全間距轉換為安全時間間隔，在連續性約束的基礎上調整船舶調度開始時刻，以避免形成緊迫形勢。從空間到時間轉換主要考慮單向/雙向通航模式、船舶進出港方向、相遇位置和泊位遠近。

2.3.3.2 不同通航模式轉換下的安全約束

單向通航涉及同向安全間距和異向安全間距，雙向通航涉及同向安全間距和橫向安全間距。

3 算法設計

雙向通航港口船舶調度多目標遺傳算法流程見圖1。

4 模型與算法驗證

由于港口船舶調度的實際情況十分復雜，采用模擬數據驗證模型的合理性和算法的有效性。在對多個港口進行調研的基礎上，模擬港口數據建立船舶調度基礎數據庫，模擬港口的航道條件、到港船舶等情況進行調度試驗。

4.1 基礎數據

調度基礎數據庫中建立4個錨地的信息、34個泊位的信息和50艘船舶的基本信息。

4.2 調度試驗

為對調度方案進行可行性驗證，設置調度試驗的參數如下。

1) 港口參數：航速最低5 kn，最高10 kn；船舶數量10艘；V=5 000，W=6；調度期間為0:00—12:00，E=2，C=6；g0=5，g1=5。

2) 遺傳算法參數：種群大小為200代，父代與子代之間的代溝為0.9，交叉概率為0.9，變異概率為0.05，終止代數為200代。

圖2為港口船舶調度試驗結果。由圖2可知，有3個Pareto最優解，其中，最小總調度時間為733 min，最小總等待時間為107 min，平均每艘船舶的等待時間約為10 min。由種群均值的變化可知，種群在不斷地尋找最優解；由種群進化圖可知，第一目標值在20代左右收斂，第二目標值在60代左右收斂。這說明雙向通航港口船舶調度多目標遺傳算法能有效搜索雙向通航情況下船舶進出航道的調度方案。

表2按照調度時間先后的序列給出Pareto1解的詳細調度方案。

1) 一般安全性檢驗：航速調整是針對同向先后航行的船舶調整其航速，避免船舶在航道上追越，如編號為4的船舶緊隨編號為3的船舶進港上航道，編號為4的船舶的航速不應超過編號為3的船舶的航速，航速由7.7 kn調整為5.5 kn。只有船舶申請進出港之后才可對其進行調度，如按照同向安全時間間隔的約束，編號為5的出港船舶在編號為2的船舶上航道之后的一個同向安全時間間隔之后(00:30)即可上航道，但由于編號為5的船舶此時尚未申請調度，因此不能安排其出港，直到其申請出港時(01:05)方可安排出港。

2) 雙向通航安全性檢驗：雙向通航進港船舶與雙向通航出港船舶之間只需在航道上保持規定橫向安全距離即可，彼此上航道時刻不受約束，如編號為1的進港船舶在01:31時刻上航道(航道起點處)，編號為2的出港船舶可在00:25時刻上航道(航道終點處)。但是，同是雙向通航進港或雙向通航出港的船舶，先后2艘船舶上航道時刻之間至少保持1個同向安全時間間隔，如編號為2及5的雙向通航出港船舶和編號為4及6的雙向通航進港船舶均滿足要求。

3) 雙向通航與單向通航轉換的安全性檢驗：當調度中出現單向通航的船舶時，不允許反向的單向通航船舶或雙向通航船舶進出航道，但允許同向的單向通航船舶或雙向通航船舶進出航道，且同向航行的船舶上航道時刻之間至少保持1個同向安全時間間隔，既保證安全又提高調度效率。如編號為3的單向通航船舶進港時，在上航道至下航道期間(02:46—03:52)均沒有單向通航出港船舶或雙向通航出港船舶，但編號為4的雙向通航進港船舶可緊隨其后，相應地上航道時刻之間保持1個同向安全時間間隔(5 min)。

表2 Pareto最優解調度優化方案

以上分析表明，所研究的調度方案具有可行性，雙向通航港口船舶調度多目標遺傳算法能有效求解雙向通航港口船舶調度優化模型，求解結果滿足模型中的目標要求和約束條件，并在保證船舶安全航行的情況下有效提高其進出港效率，從而驗證模型的合理性和算法的有效性。需指出，在實際操作中，港口調度部門可根據實際需求選擇相應的Pareto最優解。例如，若要求總調度時間最短，則可選擇Pareto3解作為調度方案。

5 結束語

本文研究雙向通航港口船舶調度問題，建立以總調度時間和總等待時間最少為目標，以單向/雙向通航轉換、連續性和安全性為約束的雙向通航港口船舶調度優化數學模型。針對雙向通航船舶調度問題多約束、多目標和大規模的特點，設計雙向通航港口船舶調度多目標遺傳算法，搜索船舶進出航道的最佳調度方案。試驗結果表明，本文提出的雙向通航港口船舶調度優化方法具有合理性和可行性，符合港口船舶調度規律，且能在保證船舶安全航行的前提下有效提高港口船舶調度效率。但是，本文所建模型相對簡單，需進一步加以完善。此外，如何在電子海圖上進行調度試驗來驗證本文所提出優化方法的可行性也是今后研究的方向。

[1] GAAFARY M M, MOLESH M. Ship Hydrodynamics and Optimal Control During Two-Way Traffic - A Proposed System of Navigation in Suez Canal [J]. Ocean Engineering and Coastal Resources, 2008,1:37-45.

[2] ULUSCU O S, OZBAS B, ALTIOK T, et al. Risk Analysis of the Vessel Traffic in the Strait of Istanbul[J].Risk Analysis, 2009,29(10):1454-1472.

[3] ULUSCU O S, OZGECAN S. Transit Vessel Scheduling in the Strait of Istanbul[J]. Journal of Navigation, 2009,62(1):59-77.

[4] FILIPOWIC W. Vessel Traffic Control Problems [J]. Journal of Navigation, 2004,57(1):15-24.

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

[6] 王金濤.基于單向航道的船舶調度優化模型與算法研究[D].大連:大連海事大學, 2014.

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

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

[9] ZHANG Xinyu, LIN Jun, GUO Zijian, et al. Vessel Transportation Scheduling Optimization Based on Channel-Berth Coordination [J]. Ocean Engineering, 2016,112:145-152.

[10] LIN Jun, ZHANG Xinyu, YIN Yong, et al. Optimization of Ship Scheduling Based on One-Way Fairway [J]. Lecture Notes in Computer Science,2014:479-486.