張新宇， 王志強， 鄧志鵬

(大連海事大學 海上智能交通研究組， 遼寧 大連 116026)

神華黃驊港煤炭港區(qū)5萬噸級重載雙向航道工程于2012年10月26 日通過海事部門驗收并通航成功。[1]但是,鑒于航道自然地理條件的限制，根據(jù)港口有關規(guī)定，航道部分航段只允許單向通航，其余航段實行有條件的雙向通航。[2]由于航道船舶交通狀況等條件的限制，當前該港區(qū)仍執(zhí)行單向通航。為此，如何提高該港區(qū)限制性雙向航道船舶進出港作業(yè)效率是亟待解決的問題。

目前，針對黃驊港煤炭港區(qū)航道船舶交通組織優(yōu)化問題的研究較少，大部分研究集中在黃驊港煤炭港區(qū)航道通航安全和通過能力分析、評價或仿真方面[3-6]，缺少從全局角度開展對航道水域船舶交通組織方法的理論研究，因此不能提供整體航道交通效率最優(yōu)的船舶交通組織解決方案。國內外缺少針對在限制性航道條件下船舶交通組織問題的研究，但對單一類型航道(如單向、雙向和復式航道)船舶交通組織問題有部分研究。文獻[7]和文獻[8]針對單向航道船舶進出港調度優(yōu)化問題，構建單向航道船舶進出港最優(yōu)序列模型；文獻[9]和文獻[10]考慮船舶等待時間和船型優(yōu)先權等因素，建立雙向通航條件下的船舶進出港數(shù)學優(yōu)化模型；文獻[11]、文獻[12]和文獻[13]研究復式航道中船舶的航行方式和交通沖突，構建船舶調度多目標數(shù)學優(yōu)化模型。通過分析，單一類型航道船舶交通組織問題需考慮進出港船舶流量轉換、單/雙向/復式通航模式轉化、船舶間安全時隙和警戒區(qū)會遇船舶協(xié)調避讓等問題。相比之下，在限制性航道條件下，研究船舶交通組織問題除了要考慮單一類型航道船舶交通組織問題以外，還需考慮航道存在的限制性關鍵航路風險點，并識別限制性航道的限制性通航航段和單一性通航航段(單向/雙向通航航段)，確保船舶在限制性通航模式與單一性通航模式之間轉化時，在限制性單/雙向通航模式切換時和在航道各限制性關鍵航路風險點航行時的安全性和效率性。在船舶交通組織優(yōu)化算法方面，EDUARDO等[14]設計雙向航道水域混合整數(shù)線性規(guī)劃數(shù)學模型，并采用模擬退火算法進行求解。MEISEL等[15]針對雙向船舶交通調度問題，提出變航速、側線段容量和船舶等待時間限制的優(yōu)化策略，采用啟發(fā)式算法求解。ZHANG等[16-17]協(xié)調航道和泊位等資源構建數(shù)學優(yōu)化模型，采用模擬退火和遺傳算法求解。通過對船舶交通組織優(yōu)化算法進行歸納發(fā)現(xiàn)，所采用的求解算法大都為模擬退火算法和遺傳算法等常規(guī)的智能優(yōu)化算法，在面對較為復雜的船舶交通組織優(yōu)化問題時，常出現(xiàn)收斂速度慢和陷于局部最優(yōu)等問題。

綜上，本文在現(xiàn)有船舶交通組織優(yōu)化理論的基礎上，考慮黃驊港煤炭港區(qū)雙向航道限制性條件，構建限制性雙向通航模式下的船舶交通組織優(yōu)化模型，并提出改進的雙鏈量子遺傳算法(Improved Double Chains Quantum Genetic Algorithm, IDCQGA)，高效地求取模型的最優(yōu)方案。

1 模型建立

1.1 問題描述

目前,該港區(qū)采用先出后進(First out Last in, FoLi)方式集中調度進港或出港船舶，航道通航效率較低，實際到港船舶需先在錨地拋錨等候進港；航道最大流速出現(xiàn)在口門(32#浮筒)附近，對于在22#浮筒附近剛上線不久的進港空載船舶而言，其航速較慢，受風流影響較大，易給重載出港船舶造成視覺誤差；航道40#浮筒附近有1個5°轉向點，應避免一艘船轉向給另一艘船造成視覺誤差； 47#浮筒以內至一期、二期碼頭前沿為港池連接水域，此處富余水深略顯不足，可航水域狹小，船舶操作性差；22#浮筒以外區(qū)域相距泊位較遠，已無雙向通航的意義?；谝陨戏治觯瑲w納出影響航道通航安全和效率的限制性關鍵航路風險點主要包括進航道口(Key0 )、防沙堤口門(Key2)、航道5°轉向點(Key3)和港池連接水域(Key4)，見圖1。圖1中，Key1為Key0與Key2的中點。

圖1 黃驊港煤炭港區(qū)航道限制性雙向通航示意

《黃驊港煤炭港區(qū)航道雙向通航推進會紀要》對航道雙向通航條件的規(guī)定：

1) 在22#浮筒附近上線處至32#浮筒口門位置航段，船舶需執(zhí)行單向通航。航道32#浮筒以內區(qū)域中的外航道段(32#～40#浮筒) 和內航道段(40#～47#浮筒)船舶執(zhí)行5萬噸級有條件雙向通航。

2) 航道同向進出港船舶前后安全距離至少保持1.5 n mile。

3) 雙向通航兩船暫限船長小于225.0 m，船寬不大于32.3 m。

綜上，該港區(qū)限制性航道具有全局雙航段異類通航(限制性單/雙向通航)和局部單航段有條件通航等限制性通航的特點，從而使航道通航模式在單向/限制性通航模式間轉化,在限制性單/雙向通航模式間切換。單向/限制性通航模式在航道物理條件、船舶類型(船型尺度、船舶載態(tài)、船舶吃水和載運危險物等)和水文氣象等因素的影響下發(fā)生轉化；限制性單/雙向通航模式在船舶從航道單向航段航行過渡到雙向航段時切換。

考慮以上航道通航安全和效率影響因素以及船舶限制性雙向通航條件，結合港方和船方在船舶進出港過程中的利益訴求，在對黃驊港煤炭港區(qū)實際船舶進出港流程進行實地調研的基礎上，提煉出該港區(qū)限制性雙向航道船舶交通組織優(yōu)化的關鍵是確定最佳的船舶進出港序列，確保船舶在限制性通航和單向通航模式下以及在航道各航路風險點附近的航行安全性和效率性，縮短船舶總的調度時間和其在港的總等待時間，從而更好地提高船舶進出港作業(yè)效率。

1.2 模型假設

本文建模所需的假設條件包括：

1) 水文氣象條件滿足船舶進出港作業(yè)要求。

2) 引航員、拖船和錨地容量充足，不影響船舶進出港計劃。

3) 船舶靠泊作業(yè)計劃已提前制訂，即不考慮泊位指派問題。

1.3 變量和符號定義

船舶集合N={1,2,…，n}，n為按船舶申請進出港的時間順序確定的船舶編號；泊位集合B={1,2,…，z}，z為泊位編號。Tpi為船舶申請進出港時間，即船舶完全就緒時刻。Tsi為船舶開始被調度時刻。Tfi為船舶完成進出港時刻，對于進港船舶指船舶停靠泊位時刻，對于出港船舶指船舶出航道時刻。δ0為船舶同向安全時隙。Tgk為船舶異向安全時隙,若k=1,表示限制性雙向通航單向通航階段的平均時隙;若k∈{0,3,4},表示關鍵航路風險點0、3和4附近的異向安全時隙。Δtki為船舶在航道各關鍵航路風險點之間的航行時間，k∈{0,1,2,3,4}，其中:若k=0，對于進港船表示從錨地航行至進航道位置的時間，對于出港船表示從進航道位置航行到出航道位置的時間；若k∈{1,2,3,4}，表示進出港船舶在航路風險點k-1與k之間的航行時間。ΔBti為船舶在港池連接水域與泊位之間的航行時間。Tki為船舶航行到航道關鍵航路風險點k的時刻，k∈{0,1,2,3,4}。x為船舶航行方向，其中:x=1為進港；x=0為出港。y為船舶航行模式，其中:y=0為單向通航；y=r為限制性通航，r=1指限制性單向通航，r=2指限制性雙向通航。Bi=1，為進港船舶i將要停靠的泊位可用；Bi=0，為進港船舶i所要?？康牟次灰驯皇褂?。A為任意一個足夠大的整數(shù)。

1.4 優(yōu)化模型

本文構建的在限制性雙向通航模式下船舶交通組織優(yōu)化模型(Ship Traffic Organization Optimization Model under Restricted Two-Way Navigation, STOOMRTWN)見式(1)～式(9)。

[STOOMRTWN]:

min:[S,W]

(1)

(2)

式(1)和式(2)中：S和W分別為第一月目標值和第二目標值。

s.t.

(3)

(4)

(5)

(6)

(7)

(8)

(9)

式(1)和式(2)為目標函數(shù)，分別為總船舶進出港調度時間和總船舶在港等待的最短時間；式(3)表示每艘船舶的開始調度時間不早于其申請進出港的時間，且每艘船舶調度結束時間等于其在航行過程中各關鍵航路風險點之間的航行時間累加，以確保船舶在航行過程中的時間連續(xù)性；式(4)～式(9)表示船舶i均在船舶j和m之后調度;式(4)為模式切換約束，用于判斷當限制性通航兩異向船舶切換為限制性單向通航模式時，通過調整船舶到達指定航路風險點的時刻，以保證兩船在整個限制性單向航段只能保持單向航行；式(5)和式(6)為關鍵航路風險點交通沖突消解；式(5)表示限制性通航兩異向船舶在指定關鍵航路風險點處保持異向安全時隙;式(6)表示進出港兩船在航道單向通航模式下，各關鍵航路風險點處保持同向安全時隙；式(7)為泊位沖突消解，表示船舶i進港時，其所?？康牟次槐仨毧捎茫皇?8)和式(9)為模式轉換約束；式(8)為限制性通航模式分別轉換為單向進港通航模式和單向出港通航模式;式(9)為單向進港通航模式和單向出港通航模式轉換為限制性通航模式。

2 模型求解

船舶交通組織優(yōu)化問題為典型的NP-hard問題[14]，采用常規(guī)精確求解工具求解較為困難，而傳統(tǒng)的智能化算法存在收斂速度慢、易陷于局部最優(yōu)等情況。鑒于此，本文基于IDCQGA的并行性、疊加性和量子位雙概率幅編碼等優(yōu)勢[18]，針對STOOMRTWN模型的特點，提出改進的IDCQGA，其主要思路如下：雙鏈量子編碼之后，對于1條染色體上的n個基因位，有2n個(-1,1)范圍內的概率幅，通過將概率幅大小按升序排列，并取回原來數(shù)在排序后序列中所處的位置，將原染色體轉化為整數(shù)序列，種群中每條染色體可代表所調度進出港船舶的排序情況；將量子位編碼、量子旋轉門和量子非門等操作與SGA(Simple Genetic Algorithm)的算子串聯(lián)，最終實現(xiàn)1次迭代、2次種群更新和2次目標值尋優(yōu)。IDCQGA的關鍵算子操作流程見圖2。

1) 船舶交通組織雙鏈量子編碼。量子位的概率幅被用來進行編碼操作，概率幅用(cost,sint)表示,其中t=2π×rand，rand為(0,1)內的一個隨機數(shù)。被初始化之后的每條染色體擁有2條基因序列，即

圖2 IDCQGA的關鍵算子操作流程

picos=(costi1,costi2,…,costin)

(10)

pisin=(sinti1,sinti2,…,sintin)

(11)

式(10)和式(11)中：i∈{1,2,…,m};j∈{1,2,…,n}； 種群的大小用m表示；每條染色體量子的位數(shù)代表1個周期所要調度的進出港船舶數(shù)量n。

2) 船舶交通組織解空間變換。船舶交通組織優(yōu)化問題的解空間變換發(fā)生在離散域，對于已初始化的每條染色體上的n個基因位，有2n個(-1,1)范圍內的概率幅，將概率幅大小按升序排列，并取回原來數(shù)在排序后序列中所處的位置，將原染色體轉化為整數(shù)序列，通過解空間轉換，使產生的種群中每條染色體可代表2組被調度的進出港船舶序列，序列中每一位表示1艘進出港船舶編號。

3) 適應度函數(shù)。針對所構建模型的特點，取個體目標函數(shù)值的倒數(shù)作為適應度值，并將模型各約束條件轉化為適應度函數(shù)的懲罰項。

4) SGA選擇、交叉和變異。選擇算子采用輪盤賭選擇方法，交叉算子采用部分映射交叉方法，變異算子采取二元變異方法。

5) 量子相位旋轉、變異更新染色體。利用旋轉門操作更新量子比特，采用轉角步長函數(shù)確定轉角的方向和大小，量子變異采用量子非門操作。

3 模型與算法驗證

3.1 試驗數(shù)據(jù)處理

本文基于黃驊港煤炭港區(qū)獲取相應的試驗仿真數(shù)據(jù)，建立30艘船舶交通仿真基礎數(shù)據(jù)庫。設計船舶航行時間挖掘算法獲取模型的關鍵輸入參數(shù)，其中通過對港區(qū)船舶自動識別系統(tǒng)(Automatic Identification System,AIS)數(shù)據(jù)進行條件判斷，篩選出煤炭散貨船的船長、航速、吃水和經緯度位置等數(shù)據(jù)；設置航道船舶全球定位系統(tǒng)(Global Positioning System,GPS)位置門限，提取出航道各關鍵航路風險點間船舶航行時間參數(shù)；根據(jù)進出港船舶速度變化特征過濾出船舶所?？坎次唤浘暥戎档龋⑼ㄟ^聚類等操作獲取港池內船舶航行時間參數(shù)。船舶航行時間挖掘算法流程如下：

1) 對2018年2月黃驊港煤炭港區(qū)500多萬條進出港船舶AIS暗文數(shù)據(jù)進行解碼，按照itu-rm.1371協(xié)議轉化為明文，并將其存儲為csv格式數(shù)據(jù)。

2) 按照不同類型船舶?？坎次晃恢貌煌?、疏浚船等特殊作業(yè)船在港區(qū)航行區(qū)域比較固定等條件，篩選出進出黃驊港煤炭港區(qū)的煤炭散貨船。

3) 將船舶按屬性分為靈便型散貨船和巴拿馬型散貨船，依次合理設置航道相鄰關鍵航路風險點之間進出港船舶GPS位置門限，并分別挖掘出每個區(qū)域內每艘船舶AIS數(shù)據(jù)的時間序列，最長時間與最短時間之差即為相應關鍵航路風險點之間所要挖掘的時間參數(shù)。

4) 基于上述得到的AIS數(shù)據(jù)，篩選出港池內散貨船AIS數(shù)據(jù)，按照進出港船船速隨時間變化特征不同篩選出船舶的航行時間和其所?？康牟次唤浘暥戎档茸侄?，采用k-means聚類方法，根據(jù)該港區(qū)散貨船泊位數(shù)量設置聚類簇，對上述篩選出的泊位經緯度特征值聚類，并與實際泊位位置相對比得到實際泊位編號，最后計算出進港船舶航行到實際泊位或出港船離開港池的時間。

3.2 模型和算法參數(shù)設置

設置船舶調度時間從0時刻開始；基于黃驊港規(guī)定的航道船舶安全間距(使用固定距離為1.5 n mile)、第3.1節(jié)挖掘出的航道第1個單向通航航段船舶航行時間的上限值為28.4 min、航道5°彎段實際距離為1.7 n mile、碼頭前沿距離為1.0 n mile，按航道和港池船舶航行平均速度轉換為對應的安全時隙并設定δ0為8 min，Tg0為8 min，Tg1為30 min，Tg3為9 min，Tg4為25 min；設置種群為100，量子位數(shù)為30，轉角步長初值為0.01×π，交叉概率為0.95，變異概率為0.05，終止代數(shù)為300代。

3.3 仿真結果和分析

3.3.1模型求解性能和求解方案分析

采用IDCQGA和SGA對模型進行求解，重復運行50次中具有一般性和代表性的一次運行結果見圖3。由圖3可知：IDCQGA對模型求解出的目標值均值隨迭代次數(shù)的變化較為均勻，且其第一目標值和第二目標值最優(yōu)解約在100代收斂，收斂速度明顯快于SGA，根據(jù)試驗運行結果得到的平均質量統(tǒng)計對比見表1。由表1可知：IDCQGA算法下50次試驗運行結果第一目標值和第二目標值最優(yōu)解的平均值和標準差均明顯小于SGA，表明SGA目標值每一次尋優(yōu)結果的差距較大，穩(wěn)定性較差，而IDCQGA算法50次試驗尋優(yōu)結果明顯集中，穩(wěn)定性較強；在算法運行時間上，IDCQGA比SGA稍長，原因是IDCQGA算法1次迭代進行2次尋優(yōu)計算；綜合比較得出IDCQGA算法在解決船舶交通組織優(yōu)化問題中具有收斂快、解的質量高等優(yōu)點。

a) S隨迭代次數(shù)變化 b) W隨迭代次數(shù)變化 c) IDCQGA帕累托前沿面

表1 根據(jù)試驗運行結果得到的平均質量統(tǒng)計對比 min

模型求解出的Pareto最優(yōu)解集中的每個最優(yōu)解均代表一種優(yōu)化方案。在實際應用中:若港口期望總調度時間最短，可選用第一目標值最優(yōu)的優(yōu)化方案；若需特別考慮船舶在港等待時間最短，可選用第二目標值較小的優(yōu)化方案。為驗證模型求解方案的高效性，將IDCQGA算法求解出的Pareto最優(yōu)解集中第一目標最優(yōu)下的船舶進出港優(yōu)化方案與該港區(qū)規(guī)定的在限制性雙向通航條件下船舶交通組織相關部門常采用的先到先服務(First Come First Served，F(xiàn)CFS)和FoLi調度策略相比較，其中船舶進出港序列為FCFS(0-29)和FoLi (0, 2, 3, 4, 5, 8, 9, 12, 19, 20, 21, 28, 29, 1, 6, 7, 10,11,13, 14, 15, 16, 17, 18, 22, 23, 24, 25, 26, 27)。

FCFS方法和FoLi方法的總船舶調度時間和總船舶等待時間最優(yōu)解如表1所示。通過比較可知，IDCQGA算法的總船舶調度時間和總船舶等待時間最優(yōu)解分別比FCFS方法下降22.6%和30.8%，比FoLi方法下降26.3%和31.5%，這表明采用IDCQGA算法求解出模型優(yōu)化方案具有高效性。

3.3.2模型驗證

對模型的驗證主要是分析IDCQGA，求解出船舶交通組織優(yōu)化方案見表2。表2為Pareto最優(yōu)解集中第一目標最優(yōu)方案的前20條船舶信息。

表2 船舶交通組織優(yōu)化方案 min

(1) 通航模式轉換驗證：12#出港船舶載重噸大于5萬dWT，被安排為單向通航，下一艘21#出港船舶的載重噸小于5萬dWT，被安排為限制性雙向通航，單向出港轉化為限制性雙向出港，兩船在關鍵航路風險點4保持預設的至少8 min港池同向安全時隙；21#出港船舶和7#進港船舶的載重噸小于5萬dWT，均被安排為限制性雙向通航，下一艘15#進港船舶的載重噸大于5萬dWT，被安排為單向通航，這時限制性通航轉化為單向通航，且15#船舶與21#船舶和7#船舶在關鍵航路風險點0位置保持預設的至少8 min港池異向安全時隙；最后，經驗證其他船的通航模式轉換約束也能得到保證。

(2) 其他模型約束驗證：3#出港船舶和10#進港船舶的載重噸大于5萬dWT，均被安排為單向通航，而2艘船所?？坎次幌嗤鶕?jù)泊位沖突消解約束3#出港船舶被調度時間早于10#進港船舶，且兩船各自被調度總時間等于其在航道各關鍵航路風險點和港池航行時間的總和；21#出港船舶和7#進港船舶的載重噸小于5萬dWT，均被安排為限制性雙向通航，且兩船開始被調度時間均晚于其申請進出港時間，同時,兩船在關鍵航路風險點1、3和4分別保持至少30 min、9 min和25 min的安全時隙，從而保證限制性通航2艘異向船切換到限制性單向通航后的整個限制性單向航段(Key0與Key2之間)只能保持單向航行，并消解限制性通航2艘異向船舶在關鍵航路風險點3和4附近的交通沖突消解；15#和27#進港船舶載重噸大于5萬dWT，均被安排為單向通航，兩船開始被調度時間均晚于其申請進港時間，且兩船在航道關鍵航路風險點0～4各位置保持至少8 min的同向安全時隙；最后，經驗證其他模型約束也能得到保證。

4 結束語

本文考慮黃驊港煤炭港區(qū)影響航道通航安全和效率的因素，構建限制性雙向通航模式下的船舶交通組織優(yōu)化模型，并設計船舶航行時間挖掘算法；提出改進的IDCQGA算法，實現(xiàn)雙鏈量子編碼、量子旋轉門和量子非門等操作與SGA之間的耦合，快速高效地求取船舶進出港優(yōu)化方案。試驗結果表明：提出的限制性雙向航道船舶交通組織優(yōu)化方法合理、有效，能保證在船舶安全航行的前提下有效提高船舶的進出港作業(yè)效率。然而，港口船舶交通組織問題涉及面較廣，本文主要研究限制性雙向通航進出港船舶在航道航行的安全性和效率性、船舶?？坎次粵_突等問題，理論成果可為進一步協(xié)調港口航道、泊位、拖船、引航和錨地等眾多資源，構建更為復雜、更貼近實際情況的港口限制性航道船舶交通組織優(yōu)化模型奠定基礎。