串行式混合類型航道船舶交通組織優(yōu)化

王志強 張新宇 李倍瑩 王婧贇

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

0 引 言

隨著水路運量的不斷上升以及港口船舶的大型化、高速化、密集化,港口航道類型開始由單一類型向多樣化、復雜化的混合類型趨勢發(fā)展,使得現(xiàn)有規(guī)模以上港口出現(xiàn)了單、雙向航道通過能力不足、航道中船舶交叉與會遇頻繁,大大增加了船舶交通組織與管理的復雜性。例如2019年,寧波舟山港累計完成貨物吞吐量11.19億噸,成為目前全球唯一年貨物吞吐量超11億噸的超級大港,船舶進出港約71萬艘次,每天交通流量超過2 000艘次[1],這些船舶主要通過蝦峙門等五個主要航門,客船、危險品船、液化天然氣船、集裝箱船等船種齊全,此外小型船舶、漁船數(shù)量眾多,造成核心港區(qū)主要航道通航環(huán)境十分復雜。鑒于此,船舶交管部門嘗試利用基于單一類型航道(單向/雙向航道)的混合航道交通組織方式來提高船舶交通的安全及效率?；旌项愋秃降酪话愦嬖趦煞N較為典型的類型：(1) 串行式簡單混合類型航道(黃驊港煤炭港區(qū),圖1；拉普拉塔港口,圖2)。此類型航道僅在串行方向上存在單/雙航道混合情況。(2) 交叉式復雜混合類型航道(寧波舟山港混合航道,圖3)。此類型航道基于串行式簡單混合類型航道存在多條單/雙通航航道交叉的情況。

圖1 黃驊港(煤炭港區(qū))混合航道

圖2 拉普拉塔港口混合航道

圖3 寧波舟山港混合航道

近年來,國內(nèi)外針對混合航道水域船舶交通組織的相關研究較少,但對于單一航道類型(單向/雙向航道)條件下船舶交通組織問題有部分研究。鄭紅星等[2]針對單向航道散貨港口的泊位利用率,考慮船舶間安全距離、進出港時段交替條件和成簇進出港規(guī)則等約束,以進港船舶總等待時間最小為目標,構建了混合整數(shù)線性規(guī)劃模型。Jia等[3]基于單向航道通航能力的特點,以進出港船舶的懲罰費用為目標,建立了混合整數(shù)線性規(guī)劃數(shù)學模型。張新宇等[4]考慮船舶屬性和船舶交通狀況等因素,分別構建了以總船舶調(diào)度時間和總船舶在港等待時間最小為目標的單和雙向航道船舶交通組織優(yōu)化模型。Uluscu等[7]考慮船舶等待時間長短和船型優(yōu)先權等因素,建立了雙向通航條件下船舶進出港數(shù)學模型。通過分析,單一類型航道船舶交通組織問題須考慮進出港船舶流量轉換、單/雙向通航模式轉化、船舶間安全時隙以及警戒區(qū)會遇船舶協(xié)調(diào)避讓等問題,相比之下,混合類型航道條件下船舶交通組織問題除要基于單一類型航道船舶交通組織問題外,還須特別考慮單向/混合通航模式轉化、混合航道異類子航道間通航模式切換、港池連接水域船舶交通沖突等問題,以確保船舶在混合航道單向子航段和雙向子航段、航道重要交通沖突區(qū)域的航行安全性和效率性。在船舶交通組織優(yōu)化算法方面,Meisel等[8]針對雙向航道船舶交通調(diào)度問題,提出了變航速、側線段容量和船舶等待時間限制的優(yōu)化策略,并采用啟發(fā)式算法求解。Lalla-Ruiz等[9]針對上海外高橋水域雙向航道,設計了混合整數(shù)線性規(guī)劃數(shù)學模型并利用模擬退火算法進行求解。Sluiman[10]提出了一種船舶交通調(diào)度算法,用以應對雙向航道貨物吞吐量的負面影響。Zhang等[11]考慮船舶調(diào)度的安全性、效率性和公平性,協(xié)調(diào)航道和泊位資源構建了船舶交通調(diào)度優(yōu)化模型并采用模擬退火和遺傳算法求解。通過歸納發(fā)現(xiàn)所采用的求解算法大都為模擬退火和遺傳算法等常規(guī)的智能優(yōu)化算法,其在面對較為復雜的船舶交通組織優(yōu)化問題時,常存在收斂速度慢、陷于局部最優(yōu)等情況。

綜上,國內(nèi)外缺少針對港口混合類型航道船舶交通組織問題的研究,鑒于此,本文通過調(diào)研國內(nèi)外港口混合類型航道,抽象出一種串行式簡單混合類型航道作為研究對象。在現(xiàn)有船舶交通組織優(yōu)化理論基礎上,構建以單向/混合通航模式轉化、混合航道異類子航道間通航模式切換、港池連接水域船舶交通沖突消解等為約束的串行式簡單混合類型航道船舶交通組織優(yōu)化模型,并提出一種Spark分布式多目標遺傳算法,高效地求取模型的最優(yōu)方案。

1 模型建立

1.1 問題描述

通過調(diào)研混合航道船舶進出港調(diào)度流程,基于現(xiàn)有船舶交通組織理論,提煉出串行式混合航道船舶交通組織的關鍵問題包括以下三點：

(1) 單向/混合通航模式轉化：混合航道水域船舶通航模式受到航道物理條件、船舶類型(船型尺度、船舶載態(tài)、船舶吃水及載運危險物等)、水文氣象等因素影響,這些因素的綜合作用使得混合航道在單向通航模式與混合通航模式之間轉換。

(2) 混合航道異類子航道間通航模式切換：通常情況下,一般3、5萬噸左右的小船可雙向通行,而大型客船、油船只能單向通行,同時此類航道通常會在異類子航道分界處設置會遇點,當小船和大船會遇時,先讓小船在會遇點拋錨或漂航等候直到大船通過再航行。

(3) 港池連接水域船舶交通沖突消解：連接水域在航道與港池之間,形成梯形可航水域,此處多船會遇情況下連接水域的富余程度略顯不足、可航水域狹小,同時船舶進出方向、所靠泊位、載態(tài)各異、速度較低,操作性差,所形成的交通局面極為復雜。

基于以上對串行式混合類型航道水域船舶交通組織問題的分析,得出串行式混合類型航道船舶交通組織優(yōu)化的關鍵在于確定最佳的船舶進出港序列,確保船舶在單向/混合通航模式轉化時、混合航道異類子航道間通航模式切換時,以及港池連接水域航行時的安全性、效率性、連續(xù)性。為便于建模，設置航道關鍵點1-6,其中關鍵點2和5分別取1-3和4-6的中點,如圖4所示。

圖4 串行式簡單混合航道示意圖

1.2 模型假設

(1) 進港船舶調(diào)度起止時間為錨地到泊位,出港船舶調(diào)度起止時間為泊位到出航道位置。(2) 水文氣象條件滿足船舶進出港作業(yè)要求。(3) 引航員、拖輪、錨地容量充足,不影響船舶進出港計劃。(4) 船舶靠泊作業(yè)計劃已提前制定,即不考慮泊位指派問題。

1.3 變量及符號定義

N:船舶集合N={1,2,…，n},n為按照船舶申請進出港時間順序確定的船舶編號。

Tpi:船舶i申請進出港時間,也即船舶完全就緒時刻,?i∈N。

Tsi:船舶i開始被調(diào)度時刻,?i∈N。

Tfi:船舶i完成進出港時刻,對于進港船,指船舶?？坎次粫r刻；對于出港船,指船舶出航道時刻,?i∈N。

Tg0:船舶最小同向安全時隙。

Tg1:船舶最小異向安全時隙。

Tg13:表示混合航道單向子航段(關鍵點1-3)的平均時隙。

Tg46:表示港池連接水域(關鍵點4-6)的平均時隙。

Dk:航道關鍵點k和k-1之間的距離,D1表示錨地到上航道位置的距離,?k∈{1,2,…,6}。

vi:船舶i在航道航行速度,Avi和Bvi分別指船舶在錨地和港池航行平均速度,?i∈N。

ΔBdi:船舶在港池關鍵點6和?？坎次恢g距離,?i∈N。

IOij=0表示船舶i和j進出港方向相同,IOij=1表示船舶i和j進出港方向不同。

Xi:船舶i航行方向,Xi=1為進港，Xi=0為出港。

y:船舶航行模式,y=0為單向通航，y=r為混合通航,其中:r=1指混合通航模式下船舶在單向子航段航行,r=2指混合通航模式下船舶在雙向航段航行。

1.4 優(yōu)化模型

基于前文問題分析,本文構建的串行式簡單混合航道船舶交通組織優(yōu)化模型(Ship Traffic Organization Optimization Model Under Serial Simple Mixed Channel,STOOMSSMC)如式(1)-式(8)所示。

(1)

s.t.

Tpi≤Tsi,?i∈N

(2)

?

(3)

?i∈N

(4)

(5)

(6)

(7)

(8)

式(1)為目標函數(shù),表示總船舶進出港調(diào)度時間最少。式(2)至式(8)中進出港船舶i均在j之后調(diào)度。式(2)-式(4)各項分別表示每艘船舶的開始調(diào)度時間不早于其完全就緒時間、每艘船舶調(diào)度結束時間等于其航行過程中各個關鍵點之間的航行時間累加、進出港兩船在航道混合通航模式/單向通航模式下航行保持同向安全時隙以確保船舶在航行過程中的時間安全性和連續(xù)性。式(5)為模式切換約束,用于判斷當混合通航兩異向船舶切換到混合通航模式下單向子航段航行時,通過調(diào)整船舶到達航道關鍵點2的時刻以保證兩船在整個混合通航單向子航段只能保持單向航行。式(6)為港池連接水域交通沖突消解,用于避免兩異向船在港池連接水域產(chǎn)生會遇沖突。式(7)和式(8)為模式轉換約束,混合通航模式和單向通航模式轉換發(fā)生在進航道位置(關鍵點1)和港池與航道交界位置(關鍵點4),其中式(7)表示混合通航模式分別轉換為單向進港或單向出港通航模式,式(8)表示單向進港或單向出港通航模式轉換為混合通航模式。

2 模型求解

近年來比較熱門的并行技術Spark是一種基于內(nèi)存計算的開源分布式并行計算框架,其特有的彈性分布式數(shù)據(jù)集RDD(Resilient Distributed Datasets)運算機制是一種具備高效容錯性的分布式彈性存儲系統(tǒng)[12],它將大量數(shù)據(jù)分布式地存儲在不同計算節(jié)點的本地內(nèi)存中,使得每次迭代的中間結果可保存在內(nèi)存中直接供下一次的迭代運算調(diào)用。

本文針對STOOMSSMC模型特點,基于Spark并行計算框架的多計算節(jié)點本地內(nèi)存化等優(yōu)勢,結合NSGA-II種群、遺傳操作天然并行性特點[13],借助于Scala編程語言使Spark分布式計算框架嵌入NSGA-II算法實現(xiàn)一種Spark分布式多目標遺傳算法(Nondominated Sorting Genetic Algorithm II on Spark,SK-NSGA-II),以便將全部種群分散在多個子種群中,在多節(jié)點上并行地執(zhí)行遺傳算法的選擇、交叉和變異等操作,從而保證存在子種群可避免淘汰優(yōu)秀個體,以便繼續(xù)有效地進行后續(xù)遺傳操作,可一定程度上防止算法過早收斂到局部最優(yōu)值的現(xiàn)象,大大提高算法的搜索范圍和執(zhí)行速度。SK-NSGA-II設計流程如圖5所示,SK-NSGA-II中遺傳算子操作如算法1所示，Spark算子操作步驟如算法2所示。

圖5 SK-NSGA-II設計流程

算法1遺傳算子操作

Step1船舶交通組織染色體編碼采用排列編碼。對于一條染色體,每一個基因位代表船舶的編號,基因位的順序代表船舶進出港的順序。

Step2適應度函數(shù)。對于本文船舶交通組織模型的目標函數(shù),數(shù)值越小則代表越優(yōu),因此取個體目標函數(shù)值的倒數(shù)作為個體的適應度值,并將模型中各約束條件轉化為適應度函數(shù)的懲罰項。

Step3其他遺傳算子。選擇算子采用錦標賽選擇法,交叉算子采用部分映射交叉的方法,變異算子采取二元變異方法。

算法2Spark算子操作

Step1通過SparkContext實例對象中textFile函數(shù)從HDFS(分布式文件系統(tǒng))中讀取n個排列編碼的種群小文件,生產(chǎn)RDD,隨機分配到各個節(jié)點,以作為初始代種群。

Step2使用Spark的API函數(shù)Map在各個節(jié)點上進行求取個體適應度值,并以形式保存到新生成的RDD。

Step3對Step2產(chǎn)生的RDD進行去重,并使用Spark的API函數(shù)mapPartitions對每個分區(qū)個體先進行非支配排序,再循環(huán)執(zhí)行選擇、交叉、變異操作生產(chǎn)子代種群,然后利用Scala的API函數(shù)map依次進行適應度值求取和子父代種群合并操作。

Step4對合并后的種群依次進行非支配排序操作和種群裁剪操作,更新父代種群,直到滿足終止條件,輸出最優(yōu)解。

3 模型與算法驗證

3.1 模型合理性分析

本文從實際出發(fā)，基于國內(nèi)外實際混合航道實例，抽象出一種含有混合航道共性特征的串行式混合類型航道。例如，寧波舟山港混合航道基于串行式混合航道，存在多條單/雙通航航道交叉的情況，而國內(nèi)黃驊港煤炭港區(qū)混合航道和國外拉普拉多混合航道均為串行式混合航道實例，該串行式混合航道具有全局雙航段異類通航(單/雙向通航)和局部單航段有條件雙向通航等通航特點。以黃驊港煤炭港區(qū)串行式混合航道為例，具體來說，該航道由于船舶交通、自然地理等條件限制，按照《黃驊港煤炭港區(qū)航道雙向通航推進會紀要》規(guī)定，航道22#浮筒附近上線處至32#浮筒口門位置航段船舶實行單向通航，其余航段船舶實行有條件雙向通航，而本文所抽象出的混合類型航道對航道布置和走向、錨地和港池的位置及數(shù)量等特殊情況進行了簡化，重點突出影響串行式混合航道通航效率的通航模式切換、港池連接水域沖突等關鍵因素。

基于抽象出的混合類型航道所構建的優(yōu)化模型中，關于模型目標函數(shù)，混合類型航道各種因素的作用直接影響到港口船舶交通組織相關部門對進出港船舶調(diào)度的時間，從而關系到船舶在港作業(yè)的效率，鑒于此，本文選取的總船舶調(diào)度時間優(yōu)化目標符合交通組織部門的需求；關于模型約束條件，影響混合類型航道船舶交通組織效率的因素區(qū)別于常規(guī)單一類型航道，主要表現(xiàn)在混合類型航道單向/混合通航模式轉化、混合航道異類子航道間通航模式切換、港池連接水域船舶交通沖突等問題，鑒于此，本文優(yōu)化模型充分考慮以上混合類型航道船舶交通組織問題，以保證進出港船舶在串行式混合類型航道航行的安全性和效率性。

因此，本文基于當前港口實際混合航道情況抽象出的串行式混合類型航道具有現(xiàn)實依據(jù)，且針對抽象出的混合類型航道所構建的優(yōu)化模型具有合理性。

3.2 實驗預處理

本文基于黃驊港煤炭港區(qū)(串行式簡單混合航道)獲取相應的實驗仿真數(shù)據(jù),建立30艘船舶交通仿真基礎數(shù)據(jù)庫,部分船舶數(shù)據(jù)如表1所示。

表1 船舶基礎信息

此外,對模型及算法參數(shù)進行設置如下：設船舶調(diào)度時間從0時刻開始；基于黃驊港航道船舶安全間距(港區(qū)規(guī)定安全距離1.5海里)、錨地-關鍵點1(2.9海里)、關鍵點1-3(5.6海里)、關鍵點3-4(10.2海里)、港池連接水域范圍(1.0海里)，按錨地、航道和港池船舶航行平均速度(依次對應4.9節(jié),11.3節(jié),3節(jié))轉換為對應的安全時隙并設定Tg0=Tg1=8 min、Tg13=30 min、Tg46=20 min(關鍵點3-4間航行時間按實際對應船速計算)；為測試算法收斂性和穩(wěn)定性,對30艘船舶仿真實驗重復進行50次；在多次實驗基礎上對模型求解的算法參數(shù)進行調(diào)優(yōu),設置SK-NSGA-II可讀取的HDFS中種群小文件數(shù)30個,并可動態(tài)調(diào)整種群數(shù)以測試SK-NSGA-II和NSGA-II的性能,設置兩種算法交叉概率為0.95,變異概率為0.05,終止代數(shù)300。

3.3 仿真結果及分析

(1) 算法性能分析。在對30艘船舶仿真實驗重復進行50次基礎上,從SK-NSGA-II和NSGA-II運行結果平均質(zhì)量的統(tǒng)計、算法運行時間隨種群規(guī)模和迭代次數(shù)的變化等角度,對兩種算法收斂性、穩(wěn)定性、運行時間等方面進行分析。50次仿真重復實驗結果所得解的平均質(zhì)量統(tǒng)計如表2所示,其中具有一般性和代表性的一次運行的結果如圖6所示。由圖6可以看出兩種算法對模型求解出的目標值最優(yōu)解及均值在不斷地尋優(yōu),SK-NSGA-II下目標值的平均值變化較為均勻,且其目標值最優(yōu)解于50代左右收斂到最優(yōu)解,收斂速度明顯快于NSGA-II,而NSGA-II目標值最優(yōu)解最終陷入局部最優(yōu)。這是因為SK-NSGA-II中的任一并行度都對應一個種群,并行度的擴增會使種群的計算能力和搜索范圍得到提高,這在一定程度上避免了算法遺傳操作早熟的現(xiàn)象發(fā)生。由表2可以看出SK-NSGA-II下實驗運行結果的平均值和標準差均明顯小于NSGA-II。相比之下,NSGA-II得到的目標值最優(yōu)解分布離散程度較高、分布區(qū)間明顯較大,說明NSGA-II目標值每一次尋優(yōu)結果的差距較大,穩(wěn)定性較差,而SK-NSGA-II50次實驗尋優(yōu)結果明顯集中,穩(wěn)定性較高。30艘船舶仿真實驗下算法運行時間隨種群規(guī)模和迭代次數(shù)的變化情況如圖7和圖8所示,可以看出,當?shù)螖?shù)和種群規(guī)模較小時兩種算法運行時間差距不大,原因是NSGA-II為單線程串行式運算,沒有啟動時間,而SK-NSGA-II下的Spark運行程序時首先要提交Spark應用程序任務,并初始化集群入口函數(shù),分配節(jié)點資源,此外還涉及節(jié)點間網(wǎng)絡通信問題,因此在算法執(zhí)行的開始階段Spark無法體現(xiàn)出其優(yōu)勢。然而隨著迭代次數(shù)和種群規(guī)模的增加,SK-NSGA-II運行效率遠高于NSGA-II，原因為此時程序運行的大部分時間都是程序計算,且SK-NSGA-II會將增加的數(shù)據(jù)分散到各個節(jié)點并行計算,從而大量節(jié)省算法計算的時間。

表2 實驗結果統(tǒng)計情況

圖6 SK-NSGA-II和NSGA-II運行結果

圖7 算法運行時間與迭代次數(shù)變化

圖8 算法運行時間與種群規(guī)模變化

(2) 模型有效性分析。為驗證模型求解方案的有效性,將SK-NSGA-II求解出的最優(yōu)方案與港口船舶交通組織相關部門常采用的FCFS方法(First Come First Served)和FoLi方法(First out Last in)進行對比,其中,船舶進出港序列如下：SK-NSGA-II(0,13,19,3,28,12,21,7,15,27,5,2,29,1,26,20,10,4,24,14,9,16,18,23,22,8,17,6,25,11)、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)。經(jīng)計算,FCFS方法所得調(diào)度序列的總船舶調(diào)度時間最優(yōu)解為6 813.8 min,單船最大調(diào)度時間238.8 min；FoLi方法所得調(diào)度序列的船舶總調(diào)度時間最優(yōu)解為6 353.0 min,單船最大調(diào)度時間為382.4 min,通過比較,SK-NSGA-II下總船舶調(diào)度時間最優(yōu)解較FCFS及FoLi方法分別下降33.5%和28.7%,因此無論是總船舶調(diào)度時間還是單船最大調(diào)度時間,SK-NSGA-II求解出的優(yōu)化方案均有較大提升。

(3) 模型有效性驗證。對模型有效性驗證主要分析其求解出的最優(yōu)船舶交通組織方案(表3為前10條船舶信息)是否滿足模型約束條件要求。單向/混合通航模式轉化驗證,12號出港船載重噸大于5萬噸,被安排為單向通航,下一艘21號出港船載重噸小于5萬噸,被安排為混合通航模式,此時單向通航轉化為混合通航模式,兩船在航道關鍵點4保持了預設的至少8 min港池同向安全時隙。21號出港船和7號進港船載重噸小于5萬噸,均被安排為混合通航模式,下一艘15號進港船載重噸大于5萬噸,被安排為單向通航,此時混合通航轉化為單向通航,且15號船與21號和7號船在關鍵航路風險點1位置保持了預設的至少8 min港池異向安全時隙。最后,經(jīng)驗證其他船的通航模式轉換約束也均得到保證。其他模型約束驗證：21號出港和7號進港船載重噸小于5萬噸,均被安排為混合通航模式,且兩船開始被調(diào)度時間均晚于其完全就緒時間,同時兩船在關鍵點2、5分別保持了至少30 min、20 min的安全時隙,從而保證了兩異向混合通航船在駛入混合航道單向子航道(Key 1和Key 3之間)后的整個航行過程只能保持單向通航,且避免了兩異向船在港池連水域(Key 4和Key 6之間)的會遇沖突。15號和27號進港船載重噸大于5萬噸,均被安排單向通航,兩船開始被調(diào)度時間均晚于其完全就緒時間,且兩船各自被調(diào)度總時間等于其在航道各關鍵點和港池航行時間的總和,同時兩船在航道關鍵點1-6位置保持了至少8 min同向安全時隙,從而保證船舶在航行過程中的時間安全性和連續(xù)性。最后,經(jīng)驗證其他模型約束也均得到保證。

表3 船舶交通組織方案

4 結 語

本文針對國內(nèi)外港口混合類型航道特點,抽象出一種串行式簡單混合類型航道作為研究對象,構建了以單向/混合通航模式轉化、混合航道異類子航道間通航模式切換、港池連接水域船舶交通沖突消解等為約束的串行式混合類型航道船舶交通組織優(yōu)化模型。提出一種Spark分布式多目標遺傳算法,將全部種群分散在了多節(jié)點上并行執(zhí)行算法的遺傳操作,快速高效地求取出了船舶進出港優(yōu)化方案。實驗結果表明提出的串行式簡單混合類型航道船舶交通組織優(yōu)化方法合理、有效,能夠保證船舶安全航行的前提下有效提高船舶進出港作業(yè)效率。然而實際混合類型航道常因港口自然地理等條件限制而具有多樣性和特殊性等特點,本文主要針對一種串行式簡單混合航道類型進行初步理論研究,相應成果可為下一步構建更貼近實際的復雜混合類型航道船舶交通組織優(yōu)化模型奠定基礎。