張延珍 蘭培真

摘要：為提高引航排班作業(yè)效率，以最小化引航任務(wù)間隔時間、引航員等待時間、引航作業(yè)時間、引航交通費(fèi)為目標(biāo)，以引航任務(wù)開始與完成時間、到離港泊位等為約束條件建立引航任務(wù)組適應(yīng)度模型。將遺傳算法的交叉與變異機(jī)制引入基本蝙蝠算法，構(gòu)建基于遺傳蝙蝠算法的引航排班方法，并利用MATLAB予以實現(xiàn)。結(jié)果表明：這種引航排班方法的日均效率比基本蝙蝠算法提升了48.1%，比手工排班方法提升了75.8%;這種引航排班方法的單個引航任務(wù)組構(gòu)建效率較基本蝙蝠算法提升了50.7%，比手工排班方法提升了77.2%。結(jié)果驗證了該引航排班方法的優(yōu)越性。

關(guān)鍵詞：

引航任務(wù)組構(gòu)建; 遺傳蝙蝠算法; 適應(yīng)度模型; 效率提升

中圖分類號：? U692.4+3

文獻(xiàn)標(biāo)志碼：? A

Pilotage scheduling method based on genetic bat algorithm

ZHANG Yanzhen， LAN Peizhen

（

Navigation College， Jimei University， Xiamen 361021， Fujian， China）

Abstract：

In order to improve the operation efficiency of pilotage scheduling， the pilotage task group fitness model is constructed under the constraints of starting and finishing time of pilotage tasks， arrival and departure berths， etc， with the objectives of minimizing the pilotage task interval time， the pilot waiting time， the pilotage operation time and the pilotage traffic cost. The crossover and mutation mechanism of the genetic algorithm is introduced into the basic bat algorithm， and the pilotage scheduling method based on the genetic bat algorithm is constructed and implemented by MATLAB. The results show that： the average daily efficiency of the proposed pilotage scheduling method is 48.1% higher than that of the basic bat algorithm and 75.8% higher than that of the manual scheduling method; the construction efficiency of a single pilotage task group of the proposed pilotage scheduling method is 50.7% higher than that of the basic bat algorithm and 77.2% higher than that of the manual scheduling method. The results verify the superiority of the pilotage scheduling method.

Key words：

pilotage task group construction; genetic bat algorithm; fitness model; efficiency promotion

收稿日期： 2020-09-17

修回日期： 2020-12-11

作者簡介：

張延珍（1994—），女，陜西延安人，碩士研究生，研究方向為交通運(yùn)輸規(guī)劃與管理，（E-mail）1102682696@qq.com;

蘭培真（1962—），女，福建古田人，教授，博士，研究方向為交通信息工程及控制、交通運(yùn)輸規(guī)劃與管理、海上交通安全保障，

（E-mail）peizlan@163.com

0 引 言

據(jù)廈門港引航站資料統(tǒng)計，近年來廈門港平均年引領(lǐng)船舶在11 300艘次左右，其中包括集裝箱船、危險品船、散雜貨船等多種內(nèi)外貿(mào)船舶。面對繁重的引航任務(wù)，廈門港引航站目前仍采用手工排班方式，具體步驟為：第一步，引航站領(lǐng)導(dǎo)對當(dāng)天需引航船舶的類型、船長、抵離港時間以及吃水等情況進(jìn)行安全審核。第二步，將合規(guī)的需引航船舶按時間段分為4組并對引航員進(jìn)行編號，依據(jù)引航員編號和等級依次安排引航任務(wù)，通常以每位引航員每日完成兩艘船的引航任務(wù)為原則進(jìn)行排班。若當(dāng)日需引航船舶較少，引航員有剩余，隔日排班將從當(dāng)日沒有排到的引航員開始，不必從頭開始;若當(dāng)日需引航船舶較多，則對引航員循環(huán)排班。第三步，公布預(yù)排班結(jié)果，若在結(jié)果公布后計劃有變，則進(jìn)行臨時調(diào)整。第四步，調(diào)度員于當(dāng)日晚9時對剩余需引航船舶進(jìn)行排班調(diào)整，以方便實際操作。引航環(huán)境復(fù)雜多變，船舶種類多，相關(guān)人員多，使得引航排班的不確定性較高，手工排班耗時多且效率較低。因此，對引航自動排班系統(tǒng)的研究極為重要。

引航排班問題可分為引航任務(wù)組構(gòu)建和引航員分配兩部分。為更好地設(shè)計引航排班系統(tǒng)，本文先對引航任務(wù)組構(gòu)建問題進(jìn)行研究分析。引航任務(wù)組構(gòu)建問題的求解屬于典型的NP難問題，目前國內(nèi)外已有學(xué)者對引航調(diào)度領(lǐng)域進(jìn)行研究，但多以優(yōu)化船舶航線為主，關(guān)于引航排班的研究甚少。國內(nèi)學(xué)者吳祖新[1]運(yùn)用模擬退火算法建立引航自動排班系統(tǒng)提高排班效率;劉冰[2]以寧波港為例構(gòu)建引航排班模型，運(yùn)用遺傳算法（genetic algorithm，GA）進(jìn)行優(yōu)化，排班效率較手工排班方式有所提升;謝哲學(xué)[3]將引航排班相關(guān)因素作為參數(shù)構(gòu)建數(shù)學(xué)模型并用匈牙利法求解，推動引航調(diào)度發(fā)展。國外學(xué)者UIUSCU等[4]對伊斯坦布爾海峽過境船舶調(diào)度路線進(jìn)行研究;TROTTIER等[5]對加拿大海運(yùn)公司船舶航線調(diào)度問題進(jìn)行優(yōu)化。除此之外，也有學(xué)者[6]用粒子群優(yōu)化算法等啟發(fā)式智能優(yōu)化算法對引航調(diào)度問題進(jìn)行研究，通過對常用方法的比較分析，發(fā)現(xiàn)基于啟發(fā)式智能優(yōu)化算法求解此問題具有一定的優(yōu)越性。蝙蝠算法（bat algorithm，BA）在此類問題的應(yīng)用中較現(xiàn)有研究方法具有操作簡單、速度快、調(diào)整參數(shù)較少等優(yōu)點[7]，但目前為止幾乎沒有應(yīng)用BA研究引航任務(wù)組構(gòu)建問題的文獻(xiàn)。本文通過建立引航任務(wù)組模型，提出將GA的交叉與變異機(jī)制引入傳統(tǒng)BA中對模型進(jìn)行優(yōu)化，通過實例驗證該算法可有效提升引航排班效率。

1 引航排班問題描述及引航任務(wù)組模型構(gòu)建

1.1 引航排班問題描述

引航排班問題一般描述為：

編號為1，2，…，n的n艘船（分別稱為S1，S2，…，Sn），由p個引航員r1，r2，…，rp進(jìn)行引航，所需引航時間分別為t1，t2，…，tn，這n艘船分別在編號為1，2，…，m的m個泊位進(jìn)行靠離泊作業(yè)，同一引航員在同一時刻只能完成單個引航作業(yè)，根據(jù)上述條件求解最優(yōu)引航計劃。圖1以15艘船、7個泊位為例建立引航船舶時空模型，其中橫坐標(biāo)表示引航時間，縱坐標(biāo)代表泊位編號。

圖1中：三角形所在位置的橫坐標(biāo)和縱坐標(biāo)分別代表Si的引航開始時刻和地點;圓所在位置的橫坐標(biāo)和縱坐標(biāo)分別代表Si的引航結(jié)束時刻和地點;帶箭頭的虛線表示船舶航行方向。不同時刻位于同一平行于橫坐標(biāo)的直線附近的船，引航開始或結(jié)束地點相近。引航任務(wù)組的構(gòu)建需同時滿足引航時間、地點相近，船舶等級匹配等原則。圖1中的S6長100.17 m，吃水4.0 m，于2019年9月17日8：10從1號泊位出發(fā)，13：10到達(dá)6號泊位。此時鄰近泊位待引船舶有S9、S13、S14。這種情況下的任務(wù)組構(gòu)建原則為：首先，選取出發(fā)時間與S6到達(dá)時間間隔最短的船，即S9。其次，計算引航員從S6引航結(jié)束的地點到S9引航開始的地點所需時間，若該時間大于間隔時間t96（排班表上從S6引航結(jié)束到S9引航開始的時間），則返回上一步，重新選取除S9以外間隔時間最短的船舶;若該時間小于間隔時間，則進(jìn)行下一步。最后，判斷所選船舶等級與S6的引航員等級是否匹配，匹配則進(jìn)行下一步，否則返回上一步重新進(jìn)行選擇。

1.2 引航任務(wù)組模型構(gòu)建

變量定義：

N為所有待引航船舶的編號集合，i，j∈N，i≠j;ti和tj分別表示Si和Sj所需要的引航時間;cij為引航員從Si引航結(jié)束地點到Sj引航開始地點乘坐交通艇的費(fèi)用，與航程dij成正比;sj表示Sj引航開始時刻，ei表示Si引航結(jié)束時刻;tji表示排班表上Sj引航開始時刻與Si引航結(jié)束時刻之間的時間差;trij表示引航員從Si引航結(jié)束地點到Sj引航開始地點實際所需時間。決策變量引航任務(wù)組uij含義如下：

uij=0， Si與Sj組合失敗

1， Si與Sj組合成功 （i≠j）

（1）

數(shù)學(xué)模型：在暫不考慮臺風(fēng)等惡劣天氣以及其他不確定影響因素的條件下，以引航時間、地點、狀態(tài)、船舶等級4個主要影響因素為約束條件，以最小化引航任務(wù)組總交通費(fèi)、引航作業(yè)總時間、引航任務(wù)間隔總時間、引航員等待總時間為目標(biāo)構(gòu)建引航任務(wù)組模型：

g1=i

jcijuij

（2）

g2=i

j（ti+tj）uij

（3）

g3=i

j（sj-ei）uij

（4）

g4=i

j（tji-trij）uij

（5）

式（2）表示各引航任務(wù)組總交通費(fèi);式（3）表示各引航任務(wù)組引航作業(yè)總時間;式（4）表示各引航任務(wù)組引航任務(wù)間隔總時間;式（5）表示各引航任務(wù)組引航員等待總時間。

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

g=min（θ1g1+θ2g2+θ3g3+θ4g4）

（6）

約束條件：

dij≤20 n mile

（7）

0

（8）

0

（9）

0

（10）

式（6）中θ1、θ2、θ3、θ4分別為g1、g2、g3、g4的權(quán)重系數(shù);式（7）對前后兩艘引航船之間的距離進(jìn)行約束，表示Si引航結(jié)束地點與Sj引航開始地點相近;式（8）對引航任務(wù)間隔時間進(jìn)行約束，表示Si引航結(jié)束時刻與Sj引航開

始時刻的差值必須為正且不大于2 h;式（9）對引航員等待時間進(jìn)行約束，引航員等待時間不超過0.5 h;式（10）對單個引航任務(wù)組引航作業(yè)總時間進(jìn)行約束，表示各引航員單日工作總時間不超過10 h，以防止引航員疲勞作業(yè)。此外各引航任務(wù)組中的船舶類型需滿足引航要求，當(dāng)Si由高級引航員引航時，與Si組合的Sj類型不限;當(dāng)Si由中級引航員引航時，與Si組合的Sj為除一級船舶以外的任意等級船舶;當(dāng)Si由低級引航員引航時，與Si組合的Sj僅為三級船舶。

2 基于改進(jìn)BA的引航排班方法

BA將優(yōu)化搜索過程模擬為種群個體移動搜尋獵物的過程，利用適應(yīng)度函數(shù)衡量蝙蝠目前所處位置的優(yōu)劣，將個體優(yōu)勝劣汰的過程類比成優(yōu)化搜索過程，是一種用較優(yōu)可行解代替較差可行解的算法。[8]為計算方便，在BA中設(shè)定以下理想化蝙蝠探測定位規(guī)則[9]：

（1）所有蝙蝠都采用回聲定位方法檢測距離，并用特殊方式區(qū)分獵物與障礙物。

（2）每只蝙蝠都可以自動調(diào)整發(fā)射脈沖的頻率和波長，

蝙蝠i發(fā)射脈沖的頻率fi∈[fmin，fmax]，fmin和fmax分別表示當(dāng)前發(fā)射脈沖頻率的最小值和最大值[10]，脈沖發(fā)生率ri∈[0，1]。假設(shè)在D維搜索空間中，蝙蝠i在第t次迭代時的速度為vi，t，位置為xi，t，則蝙蝠i發(fā)射脈沖的頻率及其在第t+1次迭代時的速度和位置表達(dá)式為

fi=fmin+（fmax-fmin）β

（11）

vi，t+1=vi，t+（xi，t+1-x）fi

（12）

xi，t+1=xi，t+vi，t+1

（13）

式中：β為均勻分布在[0，1]內(nèi)的隨機(jī)數(shù);x表示當(dāng)生成的第一個隨機(jī)數(shù)w>ri時，在當(dāng)前蝙蝠群體中隨機(jī)擾動產(chǎn)生的全局最優(yōu)解。

當(dāng)產(chǎn)生的第二個隨機(jī)數(shù)q

xnew=xold+εAt

（14）

ri，t+1=ri，0（1-exp（-γt））xold

（15）

Ai，t+1=αAi，t

（16）

式中：ε是[-1，1]內(nèi)的隨機(jī)數(shù);ri，0為蝙蝠i的初始脈沖發(fā)生率;α和γ均為常數(shù)，0<α<1，γ>0。

BA雖優(yōu)點較多，但在優(yōu)化過程中也極易陷入局部極值，導(dǎo)致種群更新停滯，出現(xiàn)收斂早熟等問題[11]。因此，本文將GA的交叉與變異機(jī)制引入BA中，構(gòu)建遺傳蝙蝠算法（genetic bat algorithm，GBA）：在合適的位置引入交叉與變異因子產(chǎn)生代表新的解集的種群，在基本位置信息更新后得到種群更新交變概率pgb，利用后代蝙蝠交變后所得的新的位置信息取代原雙親蝙蝠的位置信息。采用GBA可以充分繼承BA中原蝙蝠位置信息的諸多優(yōu)點，加強(qiáng)對周圍區(qū)域的搜索能力[12]，進(jìn)一步提高算法的搜索效率和收斂性能，增強(qiáng)種群在迭代優(yōu)化過程中的多樣性?；贕BA的引航任務(wù)組構(gòu)建流程見圖2。

3 實例驗證

3.1 實驗數(shù)據(jù)

通過對廈門引航站30名調(diào)度員和引航員進(jìn)行問卷調(diào)查，確定權(quán)重系數(shù)θ1、θ2、θ3、θ4均為0.25。以廈門引航站2019年9月11—17日引航208艘船為例進(jìn)行計算，運(yùn)用MATLAB 2018b編寫程序并將各算法分別運(yùn)行40次。將船舶依據(jù)船長和吃水劃分為3個等級：船長大于300 m、吃水大于10.0 m的船舶的等級為一級，船長小于160 m、吃水小于5.0 m的船舶的等級為三級，其他船舶的等級均為二級。

3.2 參數(shù)設(shè)定

進(jìn)行多組實驗驗證，參數(shù)設(shè)置為：種

群規(guī)模為80，最大迭代次數(shù)為200。BA參數(shù)為：初始脈沖發(fā)生率r0∈[0，0.4]，初始響度A0∈[0.6，1]，蝙蝠發(fā)射脈沖的頻率f∈[0，1]，常數(shù)α=γ=0.95。在GBA中：交叉概率pc=0.5，變異概率pm=0.8，交變概率pgb=0.9，其他參數(shù)與BA的相同。

3.3 結(jié)果分析

運(yùn)用GBA和BA分別對目標(biāo)函數(shù)進(jìn)行運(yùn)算，結(jié)果見表1。由表1可知，在種群規(guī)模相同時，GBA適應(yīng)度函數(shù)的最優(yōu)值和平均值均比BA的更優(yōu)，且GBA的迭代次數(shù)遠(yuǎn)遠(yuǎn)比BA的少，說明GBA比BA的解的整體質(zhì)量高，且收斂速度更快，收斂性能更好。

為驗證GBA排班結(jié)果的合理性，將GBA和BA對引航任務(wù)的分組數(shù)與廈門港引航站手工排班（MS）結(jié)果進(jìn)行對比，見圖3。由圖3可知，BA對引航任務(wù)的分組數(shù)較GBA和MS的多，而GBA對引航任務(wù)的分組數(shù)與MS的幾乎完全一致（除9月12日和14日的相差一組外，其余日期的均相同）。

GBA、BA和MS排班耗時結(jié)果見表2。由表2數(shù)據(jù)計算可知：BA的日平均排班效率較MS的提升了53.3%，BA對單個引航任務(wù)組的構(gòu)建效率較MS的提升了53.8%;GBA的日平均排班效率較MS的提升了75.8%，GBA對單個引航任務(wù)組的構(gòu)建效率較MS的提升了77.2%;GBA的日平均排班效率較BA的提升了48.1%，GBA對單個引航任務(wù)組的構(gòu)建效率較BA的提升了50.7%。這是因為：隨著迭代次數(shù)的不斷增加，BA因個體缺乏種群多樣性而陷入局部極值，收斂性能較差;GBA在傳統(tǒng)BA中引入遺傳交叉與變異機(jī)制后增強(qiáng)了種群的多樣性，從而能夠以較快的收斂速度得到最優(yōu)解。

為進(jìn)一步驗證GBA的優(yōu)越性，取種群規(guī)模分別為40、80、120、160、200，設(shè)定最大迭代次數(shù)為200次，比較GBA與BA適應(yīng)度函數(shù)的最優(yōu)值和平均值，結(jié)果見表3。由表3可知：隨著種群規(guī)模的增大，GBA與BA均能得到接近最優(yōu)值的平均值，但GBA在不

同種群規(guī)模下均能得到最優(yōu)值;隨著種群規(guī)模的增大，GBA適應(yīng)度函數(shù)的平均值逐步向平均值靠攏，表明GBA在整體尋優(yōu)過程中盲目性小，整體搜索結(jié)果較好。

4 結(jié) 論

在基本蝙蝠算法（BA）的種群更新迭代過程中引入遺傳算法的交叉與變異機(jī)制，提出一種基于遺傳蝙蝠算法（GBA）的引航任務(wù)組構(gòu)建方法。在綜合考慮引航任務(wù)間隔時間、引航員等待時間等實際情況的基礎(chǔ)上引入引航交通費(fèi)目標(biāo)構(gòu)建模型。將GBA與BA所得結(jié)果進(jìn)行比較，發(fā)現(xiàn)GBA不僅能夠避免算法過早陷入局部最優(yōu)解，求解精度也顯著提高，完成任務(wù)的時間明顯減少。隨著國內(nèi)各大港口的引航排班工作日益復(fù)雜，本文所提出的基于GBA的引航排班方法有利于提升引航排班效率，減輕調(diào)度員工作強(qiáng)度，可作為國內(nèi)各大港口引航自動排班系統(tǒng)建立的參考依據(jù)。在面對突發(fā)狀況（如天氣驟變、引航員身體不適）時本文方法存在一定的局限性，因此，如何有效降低不確定因素對引航排班的影響將是下一步研究的重點。

參考文獻(xiàn)：

[1]

吳祖新. 基于模擬退火算法的引航排班系統(tǒng)的研究[D]. 大連： 大連海事大學(xué)， 2011.

[2]劉冰. 遺傳算法及其在引航排班中的應(yīng)用研究[D]. 大連： 大連海事大學(xué)， 2007.

[3]謝哲學(xué). 基于匈牙利法的引航員任務(wù)指派研究[D]. 寧波： 寧波大學(xué)， 2017.

[4]UIUSCUS， ZBAS B， AlTIOK T， et al. Transit vessel scheduling in the strait of Istanbul[J]. The Journal of Navigation， 2009， 62（1）： 59-77. DOI： 10.1017/S037 3463308005092.

[5]TROTTIER L P， CORDEAU J F. Solving the vessel routing and scheduling problem at a Canadian maritime transportation company[J]. INFOR： Information Systems and Operational Research， 2019， 57（2）： 260-285. DOI： 10.1080/03155986.2018.1533213.

[6]蘇淑霞. 粒子群算法在云計算任務(wù)調(diào)度中的應(yīng)用[J]. 南京師大學(xué)報（自然科學(xué)版）， 2014， 37（4）： 145-149.

[7]KAUR N， SINGH S. A budget-constrained time and reliability optimization bat algorithm for scheduling workflow applications in clouds[J]. Procedia Computer Science， 2016， 98： 199-204. DOI： 10.1016/j.procs.2016.09.032.

[8]黎成. 新型元啟發(fā)式蝙蝠算法[J]. 電腦知識與技術(shù)， 2010， 6（23）： 6569-6572.

[9]尹進(jìn)田， 劉云連， 劉麗， 等. 一種高效的混合蝙蝠算法[J]. 計算機(jī)工程與應(yīng)用， 2014， 50（7）： 62-66. DOI： 10.3778/j.issn.1002-8331.1308-0334.

[10]黃光球， 趙魏娟， 陸秋琴. 求解大規(guī)模優(yōu)化問題的可全局收斂蝙蝠算法[J]. 計算機(jī)應(yīng)用研究， 2013， 30（5）： 1323-1328. DOI： 10.3969/j.issn.1001-3695.2013.05.011.

[11]郜振華， 吳昊. 一種改進(jìn)的混合蝙蝠算法[J]. 南華大學(xué)學(xué)報（自然科學(xué)版）， 2019， 33（1）： 62-66. DOI： 10.19431/j.cnki.1673-0062.2019.01.012.

[12]彭泓， 丁玉成. 基于遺傳交叉因子的蝙蝠算法的改進(jìn)[J]. 激光雜志， 2015， 36（2）： 23-26. DOI： 10.14016/j.cnki.jgzz.2015.02.023.

（編輯 賈裙平）