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

張明,任鴻翔,徐富權(quán)*,劉國威,周毅

1.福建船政交通職業(yè)學(xué)院航海學(xué)院,福建 福州 350007;2.大連海事大學(xué)航海學(xué)院,遼寧 大連 116026;3.中海油能源發(fā)展股份有限公司采油服務(wù)分公司,天津 300452

0 引言

隨中國航運(yùn)業(yè)的蓬勃發(fā)展,進(jìn)出港口的船舶增多,噸位增大,港口業(yè)務(wù)日漸繁忙,航道資源日趨緊張。港口航道主要包括單向、雙向和復(fù)式航道等模式。為提高航道的通過能力,可拓寬航道,由單向航道改為雙向航道。雙向航道的通航效率相對較高,但在船舶吃水受限,或雙向通航需改為單向通航等情況下,船舶的調(diào)度優(yōu)化受到較大影響。通常由港口調(diào)度中心和港口船舶交通管理中心2個部門制定港口的泊位分配和船舶進(jìn)出港次序,在調(diào)度過程中,若能從整體上協(xié)調(diào)泊位資源和航道資源,可提高港口的調(diào)度效率和運(yùn)營效率。

在雙向航道的通航能力方面,王更等[1]建立深圳港銅鼓航道的仿真模型,驗證其雙向航行的通過能力;司文靜等[2]分析雙向通航水域的潮流、風(fēng)、駕駛員等船舶操縱因素,基于排隊論方法建立航道通過能力模型,計算航道的通過能力,通過實例驗證模型精度;戴林偉[3]研究可變道航道,建立雙向交通流元胞自動機(jī)模型,仿真研究允許和禁止變道情況下的船舶交通流,分析船舶到達(dá)率、船舶流量和平均航速間的關(guān)系。

在雙向航道船舶調(diào)度方面,Sluiman[4]提出過境船舶雙向航行的交通調(diào)度算法,限制船舶間的安全距離;鄭紅星等[5]研究雙向通航的水域調(diào)度,考慮服務(wù)規(guī)則和夜航約束,建立混合整數(shù)調(diào)度模型,采用分支切割算法求解調(diào)度方案,滿足調(diào)度需求;何春華[6]通過網(wǎng)格分割法規(guī)劃雙向通航水域,建立進(jìn)出港船舶的大數(shù)據(jù)信息傳遞調(diào)度模型,依據(jù)數(shù)據(jù)特征調(diào)度并設(shè)計自適應(yīng)融合算法;王亞輝等[7]船舶進(jìn)出港大數(shù)據(jù),仿真分析雙向航道的通航能力,設(shè)計自適應(yīng)算法,得到航道調(diào)度新策略;張新宇等[8]研究黃驊港雙向航道交通問題,分割大型船舶的乘潮位置,構(gòu)建船舶乘潮時間窗計算模型,提高大型船舶進(jìn)港效率。

在港口泊位資源方面,Zhang等[9]對單向航道和泊位資源進(jìn)行聯(lián)合優(yōu)化,建立多目標(biāo)綜合優(yōu)化模型,提高船舶調(diào)度效率;Al-Refaie等[10]分析采用不同模型處理定期到達(dá)和緊急到達(dá)工況,得到船舶調(diào)度和泊位分配方案,明顯減少延誤成本;Liu等[11]針對單向航道港口提出混合整數(shù)線性規(guī)劃模型,減少所有船舶的總等待時間(調(diào)度開始時刻減去船舶申請時刻的時間),設(shè)計自適應(yīng)大鄰域搜索算法,并通過京唐港數(shù)據(jù)進(jìn)行驗證;Zhang等[12]研究散貨港碼頭作業(yè)和船舶調(diào)度的集成優(yōu)化,考慮裝卸作業(yè)、航行沖突等特殊情況,建立協(xié)同優(yōu)化模型,通過改進(jìn)的算法求解復(fù)雜模型,采用黃驊港數(shù)據(jù)驗證模型的合理性;邰世文等[13]研究煤炭碼頭船舶和泊位的聯(lián)合優(yōu)化問題,仿真碼頭作業(yè)模式,以作業(yè)效率最高和在港時間最短為目標(biāo)建立聯(lián)合優(yōu)化多目標(biāo)模型,采用遺傳算法求解;鄭紅星等[14-15]研究船舶進(jìn)出港次序與泊位分配的協(xié)同優(yōu)化問題,分別考慮單向航道、減載移泊和潮汐等影響,建立協(xié)調(diào)調(diào)度優(yōu)化模型并設(shè)計相應(yīng)的算法求解。

現(xiàn)有研究多以船舶在港總等待時間最短為目標(biāo),但影響港口船舶調(diào)度的因素較多,采用多目標(biāo)優(yōu)化更符合多方利益。隨船舶大型化的發(fā)展,大船多需乘潮進(jìn)港,泊位分配計劃對船舶調(diào)度也有影響。從整體上集成優(yōu)化港口資源可得到更高效的運(yùn)營方案,提高港口業(yè)務(wù)能力?？紤]單向航道的協(xié)調(diào)調(diào)度研究較多,對通航規(guī)則相對復(fù)雜的雙向航道水域的協(xié)調(diào)調(diào)度研究較少。本文研究雙向航道與泊位資源的協(xié)調(diào)優(yōu)化問題,考慮雙向通航限制、泊位類型和潮汐等影響因素,建立多目標(biāo)集成優(yōu)化模型,并設(shè)計智能優(yōu)化算法求解調(diào)度方案,以期提高港口的運(yùn)營效率。

1 問題描述與模型構(gòu)建

1.1 問題描述

在雙向航道港口調(diào)度中需考慮船舶類型、船舶吃水和船舶寬度等限制條件,確定航道通航規(guī)則。船舶進(jìn)出港過程示意圖如圖1所示。滿足雙向通航規(guī)則的船舶,經(jīng)船舶交通服務(wù)中心審批后可同時進(jìn)入航道;若未通過審批,進(jìn)港船舶需在錨地等待調(diào)度,出港船舶需在泊位等待調(diào)度;遇到航行限制時,需考慮將雙向航道改為單向航道。頻繁改變通航模式將延誤港口運(yùn)營,需制定合理高效的調(diào)度方案。根據(jù)碼頭布局,主要有離散型和連續(xù)型2種泊位,采用離散型泊位的港口較多[16],均已固定港池水深和岸線長度,泊位有明確的服務(wù)船舶類型,制定船舶進(jìn)出港計劃時應(yīng)提前完成泊位資源分配。制定調(diào)度方案時,減少船舶等待時間可提高港口業(yè)務(wù)量,減少船舶調(diào)度時間可提高航道利用率。

圖1 船舶進(jìn)出港過程示意圖

雙向航道和泊位資源的協(xié)調(diào)優(yōu)化問題可描述為:具有離散型泊位的港口,在己知船舶類型、船舶預(yù)計到港和離港時刻等相關(guān)信息的前提下,考慮大船乘潮進(jìn)出港、通航規(guī)則轉(zhuǎn)換等現(xiàn)實條件,兼顧進(jìn)出港船舶的服務(wù)時間、航行安全的時空間約束,以船舶總調(diào)度時間、總等待時間最短為目標(biāo),建立協(xié)調(diào)調(diào)度模型,得到更高效的船舶進(jìn)出港調(diào)度方案。

1.2 雙向航道與泊位資源協(xié)調(diào)優(yōu)化模型

對模型設(shè)置假設(shè):1)港口水域氣象條件,港口拖輪、泊位和錨地等資源均符合雙向航道調(diào)度要求;2)已知各船舶進(jìn)出港申請時間,船舶在泊位或錨地等待調(diào)度;3)港池內(nèi)為離散型泊位,且泊位有對應(yīng)服務(wù)船舶類型;4)分配泊位時需考慮船舶吃水、船舶類型和船舶長度等基本屬性;5)船舶以恒定速度在航道航行,禁止在航道中追越其他船舶。

建立雙向航道與泊位資源協(xié)調(diào)優(yōu)化模型的目標(biāo)函數(shù)為:

min [Z1,Z2],

式中:Z1為船舶總調(diào)度時間,Z2為船舶總等待時間。其中,

Z1=Te,max-Ts,min,Te,max≥Te,i,Ts,min≤Ts,i,?i∈I,

(1)

(2)

式中:Te,max為所有船舶調(diào)度結(jié)束的最晚時刻;Ts,min為所有船舶調(diào)度開始的最早時刻;Te,i為船舶i調(diào)度的結(jié)束時刻,i為船舶編號,i∈I={1,2,…,n},其中I為進(jìn)出港的船舶集合,n為當(dāng)前調(diào)度階段的船舶總數(shù);Ts,i為船舶i調(diào)度的開始時刻;Ta,i為船舶i申請進(jìn)出港的時刻。

模型約束條件中,所有船舶都有泊位可靠泊,可表示為:

式中:Xi為船舶i是否存在類型匹配的空閑泊位,Xi=0為無可用泊位,Xi=1為存在可用泊位。

船舶的調(diào)度開始時刻不得早于船舶申請時刻,可表示為:

Ts,i-Ta,i≥0,?i∈I。

船舶調(diào)度結(jié)束時刻限制為:

Te,i-Ts,i-Tb,ij-d1/vi≥0,?i∈I,j∈J,

式中:J為可用的泊位集合,j為泊位編號,j∈J={1,2,…,m},m為港內(nèi)泊位數(shù);Tb,ij為船舶i從泊位j到航道入口的航行時間;d1為航道長;vi為船舶i在港內(nèi)的平均航速。

受雙向航道航行規(guī)則約束,當(dāng)視程不佳時,轉(zhuǎn)換為單向通航模式,可表示為:

式中:NM,i為船舶i的通航模式,NM,i=0為單向通航,NM,i=1為雙向通航;V為能見度;V0為航道雙向通航時限制視程。

受雙向航道航行規(guī)則約束,當(dāng)風(fēng)力較大時,轉(zhuǎn)換至單向通航模式,可表示為:

式中:W為風(fēng)力等級,W0為航道雙向通航時限制風(fēng)力。

受雙向航道航行規(guī)則約束,當(dāng)船寬較大時,轉(zhuǎn)換至單向通航模式,可表示為:

式中:Ws,i為船舶i的寬度,B1為航道雙向通航時單船限制船寬。

受雙向航道航行規(guī)則約束,當(dāng)兩船寬之和較大時,轉(zhuǎn)換至單向通航模式,可表示為:

式中:B2為雙向通航時相對航行的兩船船寬之和限值;i′為除i以外任意船舶編號,i≠i′,且i,i′∈I={1,2,…,n}。

所有需乘潮進(jìn)出港船舶須選擇乘潮時間段,乘潮船舶應(yīng)在理論乘潮時間段內(nèi)占用航道,公式為:

Nts,i-Sp-M(1-Ni,p)≥0,?i∈I,?p∈Tp,

Nte,i-Ep-M(1-Ni,p)≤0,?i∈I,?p∈Tp,

式中:Cs,i為船舶i是否需乘潮進(jìn)出港,Cs,i=0時無需乘潮,Cs,i=1時需乘潮;Ni,p為船舶i是否選擇乘潮時間段,Ni,p=0為船舶i未選擇乘潮時間段p進(jìn)出港,Ni,p=1為船舶i選擇乘潮時間段p進(jìn)出港;M為極大的正數(shù);Nts,i為大型船舶i在安全的乘潮航行時間窗內(nèi)的開始時刻;Nte,i為大型船舶i在安全的乘潮航行時間窗內(nèi)的結(jié)束時刻;Tp為所有乘潮時間段的集合,p為乘潮時間段的編號;Sp為大型船舶乘潮時間段p的開始時刻;Ep為大型船舶乘潮時間段p的結(jié)束時刻。

受船舶調(diào)度開始時刻的約束,按次序計算船舶調(diào)度時刻,若相鄰兩艘船舶均為進(jìn)港船,可表示為:

Ts,i′=max(Ta,i′,Ts,i+d2/vi+Tf,i′-d2/vi′),Aii′=1,?i,i′∈I,

式中:Aii′為船舶i與船舶i′的調(diào)度前后次序,Aii′=0時船舶i在船舶i′后進(jìn)入航道,Aii′=1時船舶i在船舶i′前進(jìn)入航道;Tf,i為船舶i與同向行駛船舶的安全間隔時間;d2為錨地至航道入口的距離。

若相鄰兩艘船舶均為出港船,可表示為:

Ts,i′=max(Ta,i′,Ts,i+Tb,ij+Tf,i′-Tb,i′j′),Aii′=1,?i,i′∈I,j,j′∈J,

式中j′為除j以外的任意泊位編號,j≠j′且j,j′∈J={1,2,…,m}。

若相鄰兩艘船舶異向航行,后船為出港船,可表示為:

Ts,i′=max(Ta,i′,Te,i-Tb,ij+Tf,i′-Tb,i′j′),Aii′=1,NMi=0,?i,i′∈I,j,j′∈J。

若相鄰兩艘船舶異向航行,后船為進(jìn)港船,可表示為:

Ts,i′=max(Ta,i′,Te,i+Tf,i′-d2/vi′),Aii′=1,?i,i′∈I。

受航道上禁止追越限制,可表示為:

vc,i-vc,i′≥0,Aii′=1,?i,i′∈I,

式中:vc,i為船舶i在航道的航速,vc,i′為船舶i′在航道的航速。

受泊位分配約束,依照泊位類型、泊位長度和泊位水深進(jìn)行約束,可表示為:

M(Kb,j-Ks,i)=0,?i∈I,j∈J,

Io,i(Lb,j-Ls,i)M>0,?i∈I,j∈J,

Io,i(Db,j-Ds,i)M>0,?i∈I,j∈J,

式中:Kb,j為泊位j的類型;Ks,i為船舶i的類型;Io,i為船舶i的進(jìn)出港航行方向,Io,i=0時為出港,Io,i=1時為進(jìn)港;Lb,j為泊位j的長度;Ls,i為船舶i的長度;Db,j為泊位j的水深;Ds,i為船舶i的吃水深度。

選擇同一泊位的出港船舶調(diào)度應(yīng)早于靠泊該泊位的進(jìn)港船舶,可表示為:

Aii′-MIo,i>0,?i∈I,j∈J。

在調(diào)度前,進(jìn)港船靠泊的泊位應(yīng)為空閑狀態(tài),可表示為:

Io,i-MBo,j>0,?i∈I,j∈J,

式中:Bo,j為泊位j是否空閑,Bo,j=0時泊位空閑,Bo,j=1時泊位已被使用。

決策變量取值范圍為NMi,Cs,i,Ni,p,Io,i,Bo,j,Aii′,Xi∈{0,1},?i,i′∈I,j∈J。

2 算法設(shè)計

船舶進(jìn)出港調(diào)度優(yōu)化問題屬于非確定性多項式問題,雙向航道與泊位資源協(xié)調(diào)優(yōu)化模型包含多個復(fù)雜約束,難以通過精確算法或?qū)I(yè)求解器求解,可采用智能優(yōu)化算法進(jìn)行求解。NSGA-II算法常用于求解多目標(biāo)優(yōu)化問題,運(yùn)行速度較快、結(jié)果收斂性較好,但解集隨機(jī)性較高,解的質(zhì)量較差,直接應(yīng)用于模型求解效果不佳。根據(jù)雙向航道和泊位資源協(xié)調(diào)調(diào)度問題的特點,改進(jìn)NSGA-II算法,設(shè)計種群初始化策略、新個體生產(chǎn)策略,并引入自適應(yīng)交叉及變異概率,改進(jìn)后的算法流程如圖2所示,分為9步。

圖2 改進(jìn)后NSGA-II算法流程圖

1)根據(jù)航道、船舶和泊位等數(shù)據(jù)設(shè)置初始化參數(shù)。

2)將船舶調(diào)度次序和泊位分配編碼分別置于2層循環(huán)中,在內(nèi)部循環(huán)中制定進(jìn)港船舶和出港船舶的調(diào)度順序,考慮船舶出港后有泊位空閑,在外部循環(huán)中接收更新后的空閑泊位信息,制定泊位分配方案,產(chǎn)生大小為2N的初代種群,N為種群規(guī)模。

3)對初代種群進(jìn)行編碼,見圖3。

圖3 編碼示意圖

由圖3可知:有3層染色體結(jié)構(gòu)層,第1層為船舶出港次序,4號出港船調(diào)度次序在3號出港船前;第2層為船舶進(jìn)港次序,2號進(jìn)港船調(diào)度次序位于5號船舶后;第3層為對應(yīng)船舶泊位,8號進(jìn)港船舶對應(yīng)5號泊位。滿足雙向通航條件時,3號和5號船舶同時進(jìn)出港作業(yè),否則需等待上艘船舶航行結(jié)束后,3號船舶再進(jìn)入航道。計算適應(yīng)度,適應(yīng)度函數(shù)分別取式(1)(2)的倒數(shù)。

4)對初代種群進(jìn)行非支配排序和擁擠距離計算。

5)采用精英策略選擇N個優(yōu)秀個體組成新種群。

6)采用單親交叉、兩點交叉和局部變異產(chǎn)生N個新個體,單親交叉過程、兩點交叉過程和局部變異過程如圖4～6所示。

圖4 單親交叉示意圖

圖5 兩點交叉示意圖

圖6 局部變異過程示意圖

7)通過遺傳操作產(chǎn)生的新種群與每次迭代保存的父代種群合并,得到新一代種群。

8)對新一代種群進(jìn)行非支配排序和擁擠距離計算。

9)若滿足算法終止條件,輸出所有非支配排序?qū)訛?的解;若不滿足終止條件,進(jìn)化代數(shù)加1后,轉(zhuǎn)至步驟5進(jìn)行循環(huán)。

為避免算法陷入局部最優(yōu),引入自適應(yīng)交叉和變異概率,隨種群發(fā)展變異概率P改變。若出現(xiàn)個體向同一方向發(fā)展,此時需增大P;反之需減小P,保證優(yōu)等個體生存。自適應(yīng)交叉與變異概率

式中:Pmax為最大交叉概率,Pmin為最小交叉概率,f為當(dāng)前個體的適應(yīng)度,favg為種群平均適應(yīng)度,fmax為最大適應(yīng)度。

3 算例分析

以我國北方某港口為例,驗證第2節(jié)的多目標(biāo)求解算法在解決雙向航道與泊位資源協(xié)調(diào)優(yōu)化問題的有效性和優(yōu)越性。該港口有一、二、三號港外錨地,3個錨地距航道口分別為3、7、9 n mile,雙向通航,航道長d1=8 n mile,規(guī)定若單船寬度大于45 m或相向航行的船舶寬度之和大于75 m,需實行單向通航。航道水深有限,超大型船舶需乘潮進(jìn)出港。港口共有20個離散型泊位,具體泊位信息如表1所示。進(jìn)出港船舶信息如表2所示,該階段需完成調(diào)度20艘船舶,包含12艘進(jìn)港船舶和8艘出港船舶,2號和12號船舶需乘潮進(jìn)出港。

表1 港口泊位信息

表2 進(jìn)出港口船舶信息

3.1 有效性分析

采用MATLAB 2020a運(yùn)行算法,設(shè)置最大遺傳代數(shù)為200,種群規(guī)模為200,交叉和變異概率分別為0.9、0.1,得到的Pareto前沿解集如圖7所示。其中圖中加黑圓圈點解的調(diào)度計劃為:該階段所有船舶Z1=382.2 min,Z2=893.4 min;12艘進(jìn)港船舶調(diào)度次序、時間節(jié)點和泊位分配計劃如表3所示。12號船舶使用航道時間窗為[140.0, 199.3],滿足其理論需乘潮汐的時間窗[140.0,280.0]。8艘出港船舶調(diào)度次序和時間節(jié)點如表4所示。2號船舶需乘潮汐的時間窗為[150.0,270.0],使用航道時間窗為[206.7, 266.0],可安全進(jìn)出航道。由表3、4可知:泊位分配計劃滿足船舶自身條件,需保持安全會遇形勢的2號、12號、14號船舶(船寬較大,單向通航)均采用單向通航模式,調(diào)整其他船舶在航道中的航速,未出現(xiàn)追越局面。因此,多目標(biāo)求解算法適用于雙向航道與泊位資源協(xié)調(diào)優(yōu)化問題,可得到有效最優(yōu)解。

表3 進(jìn)港船舶調(diào)度計劃

表4 出港船舶調(diào)度計劃

圖7 Pareto前沿解集

3.2 算法優(yōu)越性分析

多目標(biāo)優(yōu)化模型的Z1收斂過程如圖8a)所示,Z2收斂過程如圖8b)所示。由圖8可知,在200次迭代尋優(yōu)過程中改進(jìn)的NSGA-II算法穩(wěn)定性較好。

a)Z1 b)Z2 圖8 優(yōu)化目標(biāo)收斂曲線

為驗證改進(jìn)后NSGA-II算法的優(yōu)越性,設(shè)置不同規(guī)模的算例分別求解,結(jié)果如表5所示。由表5可知:隨船舶數(shù)n、泊位數(shù)m及單向通航船舶數(shù)的變化,改進(jìn)后NSGA-II算法在Z1和Z2的尋優(yōu)效果和算法運(yùn)行時間方面均優(yōu)于NSGA-II算法。

表5 不同算例和2種算法下2個目標(biāo)的優(yōu)化對比

通常以人工方式進(jìn)行港口的船舶調(diào)度,遵循先到先服務(wù)規(guī)則或大船優(yōu)先服務(wù)規(guī)則,實時制定調(diào)度方案,受外在因素干擾較多,調(diào)度效率較低。對北方某港口遵循先到先服務(wù)規(guī)則進(jìn)行調(diào)度,基于表1、2的信息,Z1=539.5 min,Z2=2 836.8 min。采用改進(jìn)后NSGA-II算法求解的調(diào)度方案Z1=382.2 min,Z2=893.4 min,分別縮短了29.2%和68.5%,船舶進(jìn)出港調(diào)度效率顯著提升。

4 結(jié)束語

研究具有離散型泊位的雙向航道港口船舶的進(jìn)出港調(diào)度優(yōu)化問題,建立雙向航道與泊位資源協(xié)調(diào)的多目標(biāo)優(yōu)化模型,采用改進(jìn)后NSGA-II算法優(yōu)化協(xié)調(diào)雙向航道與泊位資源,在目標(biāo)尋優(yōu)和求解時間方面均優(yōu)于NSGA-II算法。與先到先服務(wù)調(diào)度方案相比,多目標(biāo)優(yōu)化模型求解得到的調(diào)度方案大幅度提高港口船舶調(diào)度效率。

但多目標(biāo)優(yōu)化模型未考慮拖輪、岸橋等資源整合,下一步研究可同時整合港內(nèi)資源。調(diào)度模型亦可融入泊位作業(yè)效率、船舶油耗等經(jīng)濟(jì)因素,以期得到全面高效的調(diào)度方案。