基于遺傳蝙蝠算法的引航排班方法

張延珍 蘭培真

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

關(guān)鍵詞：

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

中圖分類號(hào)：? 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

作者簡(jiǎn)介：

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

蘭培真（1962—），女，福建古田人，教授，博士，研究方向?yàn)榻煌ㄐ畔⒐こ碳翱刂啤⒔煌ㄟ\(yùn)輸規(guī)劃與管理、海上交通安全保障，

（E-mail）peizlan@163.com

0 引 言

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

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

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

1.1 引航排班問(wèn)題描述

引航排班問(wèn)題一般描述為：

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

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

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

變量定義：

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

uij=0， Si與Sj組合失敗

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

（1）

數(shù)學(xué)模型：在暫不考慮臺(tái)風(fēng)等惡劣天氣以及其他不確定影響因素的條件下，以引航時(shí)間、地點(diǎn)、狀態(tài)、船舶等級(jí)4個(gè)主要影響因素為約束條件，以最小化引航任務(wù)組總交通費(fèi)、引航作業(yè)總時(shí)間、引航任務(wù)間隔總時(shí)間、引航員等待總時(shí)間為目標(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è)總時(shí)間;式（4）表示各引航任務(wù)組引航任務(wù)間隔總時(shí)間;式（5）表示各引航任務(wù)組引航員等待總時(shí)間。

目標(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）對(duì)前后兩艘引航船之間的距離進(jìn)行約束，表示Si引航結(jié)束地點(diǎn)與Sj引航開(kāi)始地點(diǎn)相近;式（8）對(duì)引航任務(wù)間隔時(shí)間進(jìn)行約束，表示Si引航結(jié)束時(shí)刻與Sj引航開(kāi)

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

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

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

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

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

蝙蝠i發(fā)射脈沖的頻率fi∈[fmin，fmax]，fmin和fmax分別表示當(dāng)前發(fā)射脈沖頻率的最小值和最大值[10]，脈沖發(fā)生率ri∈[0，1]。假設(shè)在D維搜索空間中，蝙蝠i在第t次迭代時(shí)的速度為vi，t，位置為xi，t，則蝙蝠i發(fā)射脈沖的頻率及其在第t+1次迭代時(shí)的速度和位置表達(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)生成的第一個(gè)隨機(jī)數(shù)w>ri時(shí)，在當(dāng)前蝙蝠群體中隨機(jī)擾動(dòng)產(chǎn)生的全局最優(yōu)解。

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

3 實(shí)例驗(yàn)證

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻(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]蘇淑霞. 粒子群算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用[J]. 南京師大學(xué)報(bào)（自然科學(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í)與技術(shù)， 2010， 6（23）： 6569-6572.

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

[10]黃光球， 趙魏娟， 陸秋琴. 求解大規(guī)模優(yōu)化問(wèn)題的可全局收斂蝙蝠算法[J]. 計(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é)報(bào)（自然科學(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.

（編輯 賈裙平）