论文部分内容阅读
摘要：为提高引航排班作业效率，以最小化引航任务间隔时间、引航员等待时间、引航作业时间、引航交通费为目标，以引航任务开始与完成时间、到离港泊位等为约束条件建立引航任务组适应度模型。将遗传算法的交叉与变异机制引入基本蝙蝠算法，构建基于遗传蝙蝠算法的引航排班方法，并利用MATLAB予以实现。结果表明：这种引航排班方法的日均效率比基本蝙蝠算法提升了48.1%，比手工排班方法提升了75.8%;这种引航排班方法的单个引航任务组构建效率较基本蝙蝠算法提升了50.7%，比手工排班方法提升了77.2%。结果验证了该引航排班方法的优越性。
关键词：
引航任务组构建; 遗传蝙蝠算法; 适应度模型; 效率提升
中图分类号： U692.4+3
文献标志码： 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—），女，陕西延安人，硕士研究生，研究方向为交通运输规划与管理，（E-mail）[email protected];
兰培真（1962—），女，福建古田人，教授，博士，研究方向为交通信息工程及控制、交通运输规划与管理、海上交通安全保障，
（E-mail）[email protected]
0 引 言
据厦门港引航站资料统计，近年来厦门港平均年引领船舶在11 300艘次左右，其中包括集装箱船、危险品船、散杂货船等多种内外贸船舶。面对繁重的引航任务，厦门港引航站目前仍采用手工排班方式，具体步骤为：第一步，引航站领导对当天需引航船舶的类型、船长、抵离港时间以及吃水等情况进行安全审核。第二步，将合规的需引航船舶按时间段分为4组并对引航员进行编号，依据引航员编号和等级依次安排引航任务，通常以每位引航员每日完成两艘船的引航任务为原则进行排班。若当日需引航船舶较少，引航员有剩余，隔日排班将从当日没有排到的引航员开始，不必从头开始;若当日需引航船舶较多，则对引航员循环排班。第三步，公布预排班结果，若在结果公布后计划有变，则进行临时调整。第四步，调度员于当日晚9時对剩余需引航船舶进行排班调整，以方便实际操作。引航环境复杂多变，船舶种类多，相关人员多，使得引航排班的不确定性较高，手工排班耗时多且效率较低。因此，对引航自动排班系统的研究极为重要。
引航排班问题可分为引航任务组构建和引航员分配两部分。为更好地设计引航排班系统，本文先对引航任务组构建问题进行研究分析。引航任务组构建问题的求解属于典型的NP难问题，目前国内外已有学者对引航调度领域进行研究，但多以优化船舶航线为主，关于引航排班的研究甚少。国内学者吴祖新[1]运用模拟退火算法建立引航自动排班系统提高排班效率;刘冰[2]以宁波港为例构建引航排班模型，运用遗传算法（genetic algorithm，GA）进行优化，排班效率较手工排班方式有所提升;谢哲学[3]将引航排班相关因素作为参数构建数学模型并用匈牙利法求解，推动引航调度发展。国外学者UIUSCU等[4]对伊斯坦布尔海峡过境船舶调度路线进行研究;TROTTIER等[5]对加拿大海运公司船舶航线调度问题进行优化。除此之外，也有学者[6]用粒子群优化算法等启发式智能优化算法对引航调度问题进行研究，通过对常用方法的比较分析，发现基于启发式智能优化算法求解此问题具有一定的优越性。蝙蝠算法（bat algorithm，BA）在此类问题的应用中较现有研究方法具有操作简单、速度快、调整参数较少等优点[7]，但目前为止几乎没有应用BA研究引航任务组构建问题的文献。本文通过建立引航任务组模型，提出将GA的交叉与变异机制引入传统BA中对模型进行优化，通过实例验证该算法可有效提升引航排班效率。 1 引航排班问题描述及引航任务组模型构建
1.1 引航排班问题描述
引航排班问题一般描述为：
编号为1，2，…，n的n艘船（分别称为S1，S2，…，Sn），由p个引航员r1，r2，…，rp进行引航，所需引航时间分别为t1，t2，…，tn，这n艘船分别在编号为1，2，…，m的m个泊位进行靠离泊作业，同一引航员在同一时刻只能完成单个引航作业，根据上述条件求解最优引航计划。图1以15艘船、7个泊位为例建立引航船舶时空模型，其中横坐标表示引航时间，纵坐标代表泊位编号。
图1中：三角形所在位置的横坐标和纵坐标分别代表Si的引航开始时刻和地点;圆所在位置的横坐标和纵坐标分别代表Si的引航结束时刻和地点;带箭头的虚线表示船舶航行方向。不同时刻位于同一平行于横坐标的直线附近的船，引航开始或结束地点相近。引航任务组的构建需同时满足引航时间、地点相近，船舶等级匹配等原则。图1中的S6长100.17 m，吃水4.0 m，于2019年9月17日8：10从1号泊位出发，13：10到达6号泊位。此时邻近泊位待引船舶有S9、S13、S14。这种情况下的任务组构建原则为：首先，选取出发时间与S6到达时间间隔最短的船，即S9。其次，计算引航员从S6引航结束的地点到S9引航开始的地点所需时间，若该时间大于间隔时间t96（排班表上从S6引航结束到S9引航开始的时间），则返回上一步，重新选取除S9以外间隔时间最短的船舶;若该时间小于间隔时间，则进行下一步。最后，判断所选船舶等级与S6的引航员等级是否匹配，匹配则进行下一步，否则返回上一步重新进行选择。
1.2 引航任务组模型构建
变量定义：
N为所有待引航船舶的编号集合，i，j∈N，i≠j;ti和tj分别表示Si和Sj所需要的引航时间;cij为引航员从Si引航结束地点到Sj引航开始地点乘坐交通艇的费用，与航程dij成正比;sj表示Sj引航开始时刻，ei表示Si引航结束时刻;tji表示排班表上Sj引航开始时刻与Si引航结束时刻之间的时间差;trij表示引航员从Si引航结束地点到Sj引航开始地点实际所需时间。决策变量引航任务组uij含义如下：
uij=0， Si与Sj组合失败
1， Si与Sj组合成功 （i≠j）
（1）
数学模型：在暂不考虑台风等恶劣天气以及其他不确定影响因素的条件下，以引航时间、地点、状态、船舶等级4个主要影响因素为约束条件，以最小化引航任务组总交通费、引航作业总时间、引航任务间隔总时间、引航员等待总时间为目标构建引航任务组模型：
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）表示各引航任务组总交通费;式（3）表示各引航任务组引航作业总时间;式（4）表示各引航任务组引航任务间隔总时间;式（5）表示各引航任务组引航员等待总时间。
目标函数：
g=min（θ1g1+θ2g2+θ3g3+θ4g4）
（6）
约束条件：
dij≤20 n mile
（7）
0<tji<2 h， tji=ei-sj
（8）
0<tji-trij≤0.5 h
（9）
0<ti+tj<10 h
（10）
式（6）中θ1、θ2、θ3、θ4分别为g1、g2、g3、g4的权重系数;式（7）对前后两艘引航船之间的距离进行约束，表示Si引航结束地点与Sj引航开始地点相近;式（8）对引航任务间隔时间进行约束，表示Si引航结束时刻与Sj引航开
始时刻的差值必须为正且不大于2 h;式（9）对引航员等待时间进行约束，引航员等待时间不超过0.5 h;式（10）对单个引航任务组引航作业总时间进行约束，表示各引航员单日工作总时间不超过10 h，以防止引航员疲劳作业。此外各引航任务组中的船舶类型需满足引航要求，当Si由高级引航员引航时，与Si组合的Sj类型不限;当Si由中级引航员引航時，与Si组合的Sj为除一级船舶以外的任意等级船舶;当Si由低级引航员引航时，与Si组合的Sj仅为三级船舶。
2 基于改进BA的引航排班方法
BA将优化搜索过程模拟为种群个体移动搜寻猎物的过程，利用适应度函数衡量蝙蝠目前所处位置的优劣，将个体优胜劣汰的过程类比成优化搜索过程，是一种用较优可行解代替较差可行解的算法。[8]为计算方便，在BA中设定以下理想化蝙蝠探测定位规则[9]：
（1）所有蝙蝠都采用回声定位方法检测距离，并用特殊方式区分猎物与障碍物。
（2）每只蝙蝠都可以自动调整发射脉冲的频率和波长，
蝙蝠i发射脉冲的频率fi∈[fmin，fmax]，fmin和fmax分别表示当前发射脉冲频率的最小值和最大值[10]，脉冲发生率ri∈[0，1]。假设在D维搜索空间中，蝙蝠i在第t次迭代时的速度为vi，t，位置为xi，t，则蝙蝠i发射脉冲的频率及其在第t+1次迭代时的速度和位置表达式为
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]内的随机数;x表示当生成的第一个随机数w>ri时，在当前蝙蝠群体中随机扰动产生的全局最优解。
当产生的第二个随机数q<Ai（Ai为蝙蝠i发射脉冲的响度，Ai∈[Amin，A0]）且适应度值f（xi）<f（x）时，需进行局部搜索，即利用式（14）在最优解附近产生局部新解，其位置、脉冲发生率、响度按以下公式进行更新：
xnew=xold+εAt
（14）
ri，t+1=ri，0（1-exp（-γt））xold
（15）
Ai，t+1=αAi，t
（16）
式中：ε是[-1，1]内的随机数;ri，0为蝙蝠i的初始脉冲发生率;α和γ均为常数，0<α<1，γ>0。
BA虽优点较多，但在优化过程中也极易陷入局部极值，导致种群更新停滞，出现收敛早熟等问题[11]。因此，本文将GA的交叉与变异机制引入BA中，构建遗传蝙蝠算法（genetic bat algorithm，GBA）：在合适的位置引入交叉与变异因子产生代表新的解集的种群，在基本位置信息更新后得到种群更新交变概率pgb，利用后代蝙蝠交变后所得的新的位置信息取代原双亲蝙蝠的位置信息。采用GBA可以充分继承BA中原蝙蝠位置信息的诸多优点，加强对周围区域的搜索能力[12]，进一步提高算法的搜索效率和收敛性能，增强种群在迭代优化过程中的多样性。基于GBA的引航任务组构建流程见图2。
3 实例验证
3.1 实验数据
通过对厦门引航站30名调度员和引航员进行问卷调查，确定权重系数θ1、θ2、θ3、θ4均为0.25。以厦门引航站2019年9月11—17日引航208艘船为例进行计算，运用MATLAB 2018b编写程序并将各算法分别运行40次。将船舶依据船长和吃水划分为3个等级：船长大于300 m、吃水大于10.0 m的船舶的等级为一级，船长小于160 m、吃水小于5.0 m的船舶的等级为三级，其他船舶的等级均为二级。
3.2 参数设定
进行多组实验验证，参数设置为：种
群规模为80，最大迭代次数为200。BA参数为：初始脉冲发生率r0∈[0，0.4]，初始响度A0∈[0.6，1]，蝙蝠发射脉冲的频率f∈[0，1]，常数α=γ=0.95。在GBA中：交叉概率pc=0.5，变异概率pm=0.8，交变概率pgb=0.9，其他参数与BA的相同。
3.3 结果分析
运用GBA和BA分别对目标函数进行运算，结果见表1。由表1可知，在种群规模相同时，GBA适应度函数的最优值和平均值均比BA的更优，且GBA的迭代次数远远比BA的少，说明GBA比BA的解的整体质量高，且收敛速度更快，收敛性能更好。
为验证GBA排班结果的合理性，将GBA和BA对引航任务的分组数与厦门港引航站手工排班（MS）结果进行对比，见图3。由图3可知，BA对引航任务的分组数较GBA和MS的多，而GBA对引航任务的分组数与MS的几乎完全一致（除9月12日和14日的相差一组外，其余日期的均相同）。
GBA、BA和MS排班耗时结果见表2。由表2数据计算可知：BA的日平均排班效率较MS的提升了53.3%，BA对单个引航任务组的构建效率较MS的提升了53.8%;GBA的日平均排班效率较MS的提升了75.8%，GBA对单个引航任务组的构建效率较MS的提升了77.2%;GBA的日平均排班效率较BA的提升了48.1%，GBA对单个引航任务组的构建效率较BA的提升了50.7%。这是因为：随着迭代次数的不断增加，BA因个体缺乏种群多样性而陷入局部极值，收敛性能较差;GBA在传统BA中引入遗传交叉与变异机制后增强了种群的多样性，从而能够以较快的收敛速度得到最优解。
为进一步验证GBA的优越性，取种群规模分别为40、80、120、160、200，设定最大迭代次数为200次，比较GBA与BA适应度函数的最优值和平均值，结果见表3。由表3可知：随着种群规模的增大，GBA与BA均能得到接近最优值的平均值，但GBA在不
同种群规模下均能得到最优值;随着种群规模的增大，GBA适应度函数的平均值逐步向平均值靠拢，表明GBA在整体寻优过程中盲目性小，整体搜索结果较好。
4 结 论
在基本蝙蝠算法（BA）的种群更新迭代过程中引入遗传算法的交叉与变异机制，提出一种基于遗传蝙蝠算法（GBA）的引航任务组构建方法。在综合考虑引航任务间隔时间、引航员等待时间等实际情况的基础上引入引航交通费目标构建模型。将GBA与BA所得结果进行比较，发现GBA不仅能够避免算法过早陷入局部最优解，求解精度也显著提高，完成任务的时间明显减少。随着国内各大港口的引航排班工作日益复杂，本文所提出的基于GBA的引航排班方法有利于提升引航排班效率，减轻调度员工作强度，可作为国内各大港口引航自动排班系统建立的参考依据。在面对突发状况（如天气骤变、引航员身体不适）时本文方法存在一定的局限性，因此，如何有效降低不确定因素对引航排班的影响将是下一步研究的重点。
参考文献：
[1]
吴祖新. 基于模拟退火算法的引航排班系统的研究[D]. 大连： 大连海事大学， 2011.
[2]刘冰. 遗传算法及其在引航排班中的应用研究[D]. 大连： 大连海事大学， 2007.
[3]谢哲学. 基于匈牙利法的引航员任务指派研究[D]. 宁波： 宁波大学， 2017.
[4]UIUSCU S， 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]. 南京师大学报（自然科学版）， 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]黎成. 新型元启发式蝙蝠算法[J]. 电脑知识与技术， 2010， 6（23）： 6569-6572.
[9]尹进田， 刘云连， 刘丽， 等. 一种高效的混合蝙蝠算法[J]. 计算机工程与应用， 2014， 50（7）： 62-66. DOI： 10.3778/j.issn.1002-8331.1308-0334.
[10]黄光球， 赵魏娟， 陆秋琴. 求解大规模优化问题的可全局收敛蝙蝠算法[J]. 计算机应用研究， 2013， 30（5）： 1323-1328. DOI： 10.3969/j.issn.1001-3695.2013.05.011.
[11]郜振华， 吴昊. 一种改进的混合蝙蝠算法[J]. 南华大学学报（自然科学版）， 2019， 33（1）： 62-66. DOI： 10.19431/j.cnki.1673-0062.2019.01.012.
[12]彭泓， 丁玉成. 基于遗传交叉因子的蝙蝠算法的改进[J]. 激光杂志， 2015， 36（2）： 23-26. DOI： 10.14016/j.cnki.jgzz.2015.02.023.
（編辑 贾裙平）
关键词：
引航任务组构建; 遗传蝙蝠算法; 适应度模型; 效率提升
中图分类号： U692.4+3
文献标志码： 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—），女，陕西延安人，硕士研究生，研究方向为交通运输规划与管理，（E-mail）[email protected];
兰培真（1962—），女，福建古田人，教授，博士，研究方向为交通信息工程及控制、交通运输规划与管理、海上交通安全保障，
（E-mail）[email protected]
0 引 言
据厦门港引航站资料统计，近年来厦门港平均年引领船舶在11 300艘次左右，其中包括集装箱船、危险品船、散杂货船等多种内外贸船舶。面对繁重的引航任务，厦门港引航站目前仍采用手工排班方式，具体步骤为：第一步，引航站领导对当天需引航船舶的类型、船长、抵离港时间以及吃水等情况进行安全审核。第二步，将合规的需引航船舶按时间段分为4组并对引航员进行编号，依据引航员编号和等级依次安排引航任务，通常以每位引航员每日完成两艘船的引航任务为原则进行排班。若当日需引航船舶较少，引航员有剩余，隔日排班将从当日没有排到的引航员开始，不必从头开始;若当日需引航船舶较多，则对引航员循环排班。第三步，公布预排班结果，若在结果公布后计划有变，则进行临时调整。第四步，调度员于当日晚9時对剩余需引航船舶进行排班调整，以方便实际操作。引航环境复杂多变，船舶种类多，相关人员多，使得引航排班的不确定性较高，手工排班耗时多且效率较低。因此，对引航自动排班系统的研究极为重要。
引航排班问题可分为引航任务组构建和引航员分配两部分。为更好地设计引航排班系统，本文先对引航任务组构建问题进行研究分析。引航任务组构建问题的求解属于典型的NP难问题，目前国内外已有学者对引航调度领域进行研究，但多以优化船舶航线为主，关于引航排班的研究甚少。国内学者吴祖新[1]运用模拟退火算法建立引航自动排班系统提高排班效率;刘冰[2]以宁波港为例构建引航排班模型，运用遗传算法（genetic algorithm，GA）进行优化，排班效率较手工排班方式有所提升;谢哲学[3]将引航排班相关因素作为参数构建数学模型并用匈牙利法求解，推动引航调度发展。国外学者UIUSCU等[4]对伊斯坦布尔海峡过境船舶调度路线进行研究;TROTTIER等[5]对加拿大海运公司船舶航线调度问题进行优化。除此之外，也有学者[6]用粒子群优化算法等启发式智能优化算法对引航调度问题进行研究，通过对常用方法的比较分析，发现基于启发式智能优化算法求解此问题具有一定的优越性。蝙蝠算法（bat algorithm，BA）在此类问题的应用中较现有研究方法具有操作简单、速度快、调整参数较少等优点[7]，但目前为止几乎没有应用BA研究引航任务组构建问题的文献。本文通过建立引航任务组模型，提出将GA的交叉与变异机制引入传统BA中对模型进行优化，通过实例验证该算法可有效提升引航排班效率。 1 引航排班问题描述及引航任务组模型构建
1.1 引航排班问题描述
引航排班问题一般描述为：
编号为1，2，…，n的n艘船（分别称为S1，S2，…，Sn），由p个引航员r1，r2，…，rp进行引航，所需引航时间分别为t1，t2，…，tn，这n艘船分别在编号为1，2，…，m的m个泊位进行靠离泊作业，同一引航员在同一时刻只能完成单个引航作业，根据上述条件求解最优引航计划。图1以15艘船、7个泊位为例建立引航船舶时空模型，其中横坐标表示引航时间，纵坐标代表泊位编号。
图1中：三角形所在位置的横坐标和纵坐标分别代表Si的引航开始时刻和地点;圆所在位置的横坐标和纵坐标分别代表Si的引航结束时刻和地点;带箭头的虚线表示船舶航行方向。不同时刻位于同一平行于横坐标的直线附近的船，引航开始或结束地点相近。引航任务组的构建需同时满足引航时间、地点相近，船舶等级匹配等原则。图1中的S6长100.17 m，吃水4.0 m，于2019年9月17日8：10从1号泊位出发，13：10到达6号泊位。此时邻近泊位待引船舶有S9、S13、S14。这种情况下的任务组构建原则为：首先，选取出发时间与S6到达时间间隔最短的船，即S9。其次，计算引航员从S6引航结束的地点到S9引航开始的地点所需时间，若该时间大于间隔时间t96（排班表上从S6引航结束到S9引航开始的时间），则返回上一步，重新选取除S9以外间隔时间最短的船舶;若该时间小于间隔时间，则进行下一步。最后，判断所选船舶等级与S6的引航员等级是否匹配，匹配则进行下一步，否则返回上一步重新进行选择。
1.2 引航任务组模型构建
变量定义：
N为所有待引航船舶的编号集合，i，j∈N，i≠j;ti和tj分别表示Si和Sj所需要的引航时间;cij为引航员从Si引航结束地点到Sj引航开始地点乘坐交通艇的费用，与航程dij成正比;sj表示Sj引航开始时刻，ei表示Si引航结束时刻;tji表示排班表上Sj引航开始时刻与Si引航结束时刻之间的时间差;trij表示引航员从Si引航结束地点到Sj引航开始地点实际所需时间。决策变量引航任务组uij含义如下：
uij=0， Si与Sj组合失败
1， Si与Sj组合成功 （i≠j）
（1）
数学模型：在暂不考虑台风等恶劣天气以及其他不确定影响因素的条件下，以引航时间、地点、状态、船舶等级4个主要影响因素为约束条件，以最小化引航任务组总交通费、引航作业总时间、引航任务间隔总时间、引航员等待总时间为目标构建引航任务组模型：
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）表示各引航任务组总交通费;式（3）表示各引航任务组引航作业总时间;式（4）表示各引航任务组引航任务间隔总时间;式（5）表示各引航任务组引航员等待总时间。
目标函数：
g=min（θ1g1+θ2g2+θ3g3+θ4g4）
（6）
约束条件：
dij≤20 n mile
（7）
0<tji<2 h， tji=ei-sj
（8）
0<tji-trij≤0.5 h
（9）
0<ti+tj<10 h
（10）
式（6）中θ1、θ2、θ3、θ4分别为g1、g2、g3、g4的权重系数;式（7）对前后两艘引航船之间的距离进行约束，表示Si引航结束地点与Sj引航开始地点相近;式（8）对引航任务间隔时间进行约束，表示Si引航结束时刻与Sj引航开
始时刻的差值必须为正且不大于2 h;式（9）对引航员等待时间进行约束，引航员等待时间不超过0.5 h;式（10）对单个引航任务组引航作业总时间进行约束，表示各引航员单日工作总时间不超过10 h，以防止引航员疲劳作业。此外各引航任务组中的船舶类型需满足引航要求，当Si由高级引航员引航时，与Si组合的Sj类型不限;当Si由中级引航员引航時，与Si组合的Sj为除一级船舶以外的任意等级船舶;当Si由低级引航员引航时，与Si组合的Sj仅为三级船舶。
2 基于改进BA的引航排班方法
BA将优化搜索过程模拟为种群个体移动搜寻猎物的过程，利用适应度函数衡量蝙蝠目前所处位置的优劣，将个体优胜劣汰的过程类比成优化搜索过程，是一种用较优可行解代替较差可行解的算法。[8]为计算方便，在BA中设定以下理想化蝙蝠探测定位规则[9]：
（1）所有蝙蝠都采用回声定位方法检测距离，并用特殊方式区分猎物与障碍物。
（2）每只蝙蝠都可以自动调整发射脉冲的频率和波长，
蝙蝠i发射脉冲的频率fi∈[fmin，fmax]，fmin和fmax分别表示当前发射脉冲频率的最小值和最大值[10]，脉冲发生率ri∈[0，1]。假设在D维搜索空间中，蝙蝠i在第t次迭代时的速度为vi，t，位置为xi，t，则蝙蝠i发射脉冲的频率及其在第t+1次迭代时的速度和位置表达式为
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]内的随机数;x表示当生成的第一个随机数w>ri时，在当前蝙蝠群体中随机扰动产生的全局最优解。
当产生的第二个随机数q<Ai（Ai为蝙蝠i发射脉冲的响度，Ai∈[Amin，A0]）且适应度值f（xi）<f（x）时，需进行局部搜索，即利用式（14）在最优解附近产生局部新解，其位置、脉冲发生率、响度按以下公式进行更新：
xnew=xold+εAt
（14）
ri，t+1=ri，0（1-exp（-γt））xold
（15）
Ai，t+1=αAi，t
（16）
式中：ε是[-1，1]内的随机数;ri，0为蝙蝠i的初始脉冲发生率;α和γ均为常数，0<α<1，γ>0。
BA虽优点较多，但在优化过程中也极易陷入局部极值，导致种群更新停滞，出现收敛早熟等问题[11]。因此，本文将GA的交叉与变异机制引入BA中，构建遗传蝙蝠算法（genetic bat algorithm，GBA）：在合适的位置引入交叉与变异因子产生代表新的解集的种群，在基本位置信息更新后得到种群更新交变概率pgb，利用后代蝙蝠交变后所得的新的位置信息取代原双亲蝙蝠的位置信息。采用GBA可以充分继承BA中原蝙蝠位置信息的诸多优点，加强对周围区域的搜索能力[12]，进一步提高算法的搜索效率和收敛性能，增强种群在迭代优化过程中的多样性。基于GBA的引航任务组构建流程见图2。
3 实例验证
3.1 实验数据
通过对厦门引航站30名调度员和引航员进行问卷调查，确定权重系数θ1、θ2、θ3、θ4均为0.25。以厦门引航站2019年9月11—17日引航208艘船为例进行计算，运用MATLAB 2018b编写程序并将各算法分别运行40次。将船舶依据船长和吃水划分为3个等级：船长大于300 m、吃水大于10.0 m的船舶的等级为一级，船长小于160 m、吃水小于5.0 m的船舶的等级为三级，其他船舶的等级均为二级。
3.2 参数设定
进行多组实验验证，参数设置为：种
群规模为80，最大迭代次数为200。BA参数为：初始脉冲发生率r0∈[0，0.4]，初始响度A0∈[0.6，1]，蝙蝠发射脉冲的频率f∈[0，1]，常数α=γ=0.95。在GBA中：交叉概率pc=0.5，变异概率pm=0.8，交变概率pgb=0.9，其他参数与BA的相同。
3.3 结果分析
运用GBA和BA分别对目标函数进行运算，结果见表1。由表1可知，在种群规模相同时，GBA适应度函数的最优值和平均值均比BA的更优，且GBA的迭代次数远远比BA的少，说明GBA比BA的解的整体质量高，且收敛速度更快，收敛性能更好。
为验证GBA排班结果的合理性，将GBA和BA对引航任务的分组数与厦门港引航站手工排班（MS）结果进行对比，见图3。由图3可知，BA对引航任务的分组数较GBA和MS的多，而GBA对引航任务的分组数与MS的几乎完全一致（除9月12日和14日的相差一组外，其余日期的均相同）。
GBA、BA和MS排班耗时结果见表2。由表2数据计算可知：BA的日平均排班效率较MS的提升了53.3%，BA对单个引航任务组的构建效率较MS的提升了53.8%;GBA的日平均排班效率较MS的提升了75.8%，GBA对单个引航任务组的构建效率较MS的提升了77.2%;GBA的日平均排班效率较BA的提升了48.1%，GBA对单个引航任务组的构建效率较BA的提升了50.7%。这是因为：随着迭代次数的不断增加，BA因个体缺乏种群多样性而陷入局部极值，收敛性能较差;GBA在传统BA中引入遗传交叉与变异机制后增强了种群的多样性，从而能够以较快的收敛速度得到最优解。
为进一步验证GBA的优越性，取种群规模分别为40、80、120、160、200，设定最大迭代次数为200次，比较GBA与BA适应度函数的最优值和平均值，结果见表3。由表3可知：随着种群规模的增大，GBA与BA均能得到接近最优值的平均值，但GBA在不
同种群规模下均能得到最优值;随着种群规模的增大，GBA适应度函数的平均值逐步向平均值靠拢，表明GBA在整体寻优过程中盲目性小，整体搜索结果较好。
4 结 论
在基本蝙蝠算法（BA）的种群更新迭代过程中引入遗传算法的交叉与变异机制，提出一种基于遗传蝙蝠算法（GBA）的引航任务组构建方法。在综合考虑引航任务间隔时间、引航员等待时间等实际情况的基础上引入引航交通费目标构建模型。将GBA与BA所得结果进行比较，发现GBA不仅能够避免算法过早陷入局部最优解，求解精度也显著提高，完成任务的时间明显减少。随着国内各大港口的引航排班工作日益复杂，本文所提出的基于GBA的引航排班方法有利于提升引航排班效率，减轻调度员工作强度，可作为国内各大港口引航自动排班系统建立的参考依据。在面对突发状况（如天气骤变、引航员身体不适）时本文方法存在一定的局限性，因此，如何有效降低不确定因素对引航排班的影响将是下一步研究的重点。
参考文献：
[1]
吴祖新. 基于模拟退火算法的引航排班系统的研究[D]. 大连： 大连海事大学， 2011.
[2]刘冰. 遗传算法及其在引航排班中的应用研究[D]. 大连： 大连海事大学， 2007.
[3]谢哲学. 基于匈牙利法的引航员任务指派研究[D]. 宁波： 宁波大学， 2017.
[4]UIUSCU S， 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]. 南京师大学报（自然科学版）， 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]黎成. 新型元启发式蝙蝠算法[J]. 电脑知识与技术， 2010， 6（23）： 6569-6572.
[9]尹进田， 刘云连， 刘丽， 等. 一种高效的混合蝙蝠算法[J]. 计算机工程与应用， 2014， 50（7）： 62-66. DOI： 10.3778/j.issn.1002-8331.1308-0334.
[10]黄光球， 赵魏娟， 陆秋琴. 求解大规模优化问题的可全局收敛蝙蝠算法[J]. 计算机应用研究， 2013， 30（5）： 1323-1328. DOI： 10.3969/j.issn.1001-3695.2013.05.011.
[11]郜振华， 吴昊. 一种改进的混合蝙蝠算法[J]. 南华大学学报（自然科学版）， 2019， 33（1）： 62-66. DOI： 10.19431/j.cnki.1673-0062.2019.01.012.
[12]彭泓， 丁玉成. 基于遗传交叉因子的蝙蝠算法的改进[J]. 激光杂志， 2015， 36（2）： 23-26. DOI： 10.14016/j.cnki.jgzz.2015.02.023.
（編辑 贾裙平）