雙向通航港口船舶調(diào)度優(yōu)化模型與算法

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

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

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

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

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

因此，本文在對多個港口進(jìn)行調(diào)研的基礎(chǔ)上，分析港口雙向通航船舶調(diào)度需求，建立雙向通航港口船舶調(diào)度優(yōu)化多目標(biāo)數(shù)學(xué)模型，設(shè)計多目標(biāo)遺傳算法獲取最佳調(diào)度方案。

1 問題描述

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

2 模型建立

2.1 模型假設(shè)

影響港口船舶調(diào)度的因素多且復(fù)雜，本文提取關(guān)鍵因素，作以下假設(shè)。

1) 針對某時間段內(nèi)出現(xiàn)的船舶調(diào)度問題進(jìn)行建模。

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

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

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

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

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

(1) 視程

(2) 風(fēng)力≥W1；

(3) 單船船寬≥Y1；

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

2.2 目標(biāo)函數(shù)

經(jīng)調(diào)研發(fā)現(xiàn)，由于港口船舶調(diào)度涉及眾多部門，對調(diào)度結(jié)果的期望各不相同。在形成統(tǒng)一的船舶調(diào)度方案時，從整體上看，總調(diào)度時間和總等待時間越短，表明調(diào)度效率越高。因此，從高效性出發(fā)，建立總調(diào)度時間最少和總等待時間最少的目標(biāo)函數(shù)。

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

(1)

(2)

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

2.3 約束條件

2.3.1模式轉(zhuǎn)換約束

由于雙向通航是有條件的，不可避免地會出現(xiàn)單向通航的情況，因此模式轉(zhuǎn)換約束是雙向通航港口船舶調(diào)度的必然要求。根據(jù)假設(shè)中的通航規(guī)則，建立單向/雙向通航模式轉(zhuǎn)換約束為

(3)

2.3.2連續(xù)性約束

船舶在港作業(yè)是一個連續(xù)的過程，一旦開始調(diào)度時刻確定，在船舶航速、船舶當(dāng)前位置、船舶到達(dá)航道和泊位的距離已知的情況下，船舶到達(dá)航道、泊位的時刻即可確定。

2.3.2.1 開始時刻約束

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

2.3.2.2 航行時刻約束

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

(12)

2.3.3安全性約束

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

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

2.3.3.2 不同通航模式轉(zhuǎn)換下的安全約束

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

3 算法設(shè)計

雙向通航港口船舶調(diào)度多目標(biāo)遺傳算法流程見圖1。

4 模型與算法驗證

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

4.1 基礎(chǔ)數(shù)據(jù)

調(diào)度基礎(chǔ)數(shù)據(jù)庫中建立4個錨地的信息、34個泊位的信息和50艘船舶的基本信息。

4.2 調(diào)度試驗

為對調(diào)度方案進(jìn)行可行性驗證，設(shè)置調(diào)度試驗的參數(shù)如下。

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

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

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

表2按照調(diào)度時間先后的序列給出Pareto1解的詳細(xì)調(diào)度方案。

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

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

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

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

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

5 結(jié)束語

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

[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ìn)出港最佳排序模式[J].大連海事大學(xué)學(xué)報, 2008,34(4):150-153.

[6] 王金濤.基于單向航道的船舶調(diào)度優(yōu)化模型與算法研究[D].大連:大連海事大學(xué), 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.