用改进萤火虫算法求解岸桥调度模型

董良才　孙思韵

摘要：

针对集装箱码头岸桥调度问题，以集装箱箱组为切入点，综合考虑岸桥干扰约束及作业单元优先顺序约束，以最小化船舶作业时间以及岸桥作业时间为目标，建立混合整数规划模型.利用多种算法进行求解对比，并针对新颖的萤火虫算法进行研究，提出两种改进的萤火虫算法以克服其运行时间较长及易陷入局部最优的缺陷.实例分析表明，两种改进后的萤火虫算法能有效解决岸桥调度问题，其相关理论对提高岸桥的作业效率以及集装箱码头服务水平具有一定借鉴意义.

关键词：

岸桥调度； 萤火虫算法； 遗传算法； 模拟退火算法； 岸桥干扰

中图分类号： U691.5

文献标志码： A

0 引 言

岸桥是在码头前沿装卸集装箱的主要设备，其运作效率直接关系到整个集装箱港口的运作效率.岸桥调度问题就是给岸桥分配作业单元并确定作业单元的先后顺序，使集装箱船舶能够尽快完成装卸作业.

DAGANZO[1]首次提出装卸多艘集装箱船舶的岸桥调度问题，将每艘集装箱船舶划分为多个船区，要求在任何时刻某一船区最多只能容纳一台岸桥进行作业，以最小化所有集装箱船舶的累计延误成本为目标函数.PETERKOFSKY等[2]利用分支定界法求解上述问题.这两篇文献的目标函数都是最小化船舶的延迟成本，但没有考虑岸桥之间的互相干扰以及作业单元间的先后顺序.

对岸桥调度模型的研究综述如下.

KIM等[3]研究单船岸桥调度问题，以最小化岸桥完工时间以及岸桥总完工时间为目标，以集装箱箱组作为作业单元，利用分支定界法进行求解.MOCCIA等[4]考虑岸桥在同一条轨道上运行，岸桥不能交叉，且需要留有安全间隔，由此构建了新的岸桥调度模型，并利用CPLEX求解.孙俊清等[5]对KIM等[3]的模型进行修改，考虑不同岸桥装卸能力的差异，以所有到港船舶的等候服务时间最短为目标，利用模拟退火算法（Simulated Annealing Algorithm， SAA）对其求解.LEE等[6]建立了考虑岸桥干扰约束的岸桥调度模型，并利用遗传算法（Genetic Algorithm， GA）对其求解.韩笑乐等[7]考虑

岸桥作业调度问题的其他约束，建立了考虑优先顺序约束和岸桥碰撞约束的数学模型，并利用启发式算法进行求解.董良才等[8]提出基于时间窗的岸桥调度模型，并考虑舱盖板的约束，将一个贝位的装卸单元分为6个大类，并利用GA进行求解.LEGATO等[9]提出包含各种实际约束的模型，并利用分支定界法以及Petri网进行求解.范志强等[10]分析了岸桥支援对船舶装卸作业效率的影响，发现减少岸桥的等待时间有利于岸桥支援，建立了双目标混合模型，设计了GA进行求解，并求出问题的下界.

对岸桥调度算法的研究综述如下.

王辉球[11]对岸桥调度问题的复杂度进行讨论，并证明了此问题为NP难问题，利用GA对考虑安全间隔的岸桥调度模型进行求解.MARCELLO等[12]运用禁忌搜索算法对考虑岸桥互相干扰的岸桥调度模型进行求解.李晨等[13]考虑岸桥不可交叉、安全距离以及甲板开闭的约束，推导出岸桥的总完工时间，采用GA进行求解.MEISEL等[14]用JAVA平台对不同案例求解得出基准值，对不同的模型进行评价.杨明珠[15]对单船岸桥调度问题进行研究，利用改进的贪婪算法求解.CHUNG等[16]利用改进的GA对KIM等[3]的模型进行求解，利用次序杂交的方式对两部分编码进行交叉操作.KAVESHGAR等[17]利用GA对KIM等[3]的模型进行求解，改善初始种群规则以提高运行速度，提出一种新的编码方式，使得维数减少.范志强等[18]考虑了不同岸桥的效率差异，并利用GA对其求解.董良才等[19]对全岸线岸桥的调度问题进行研究，建立模型，采用基于段的编码方式对模型进行求解.NGUYEN等[20]将GA与遗传规划结合对岸桥调度问题进行求解.

目前岸桥调度问题是集装箱码头研究的一大热点，但对岸桥在实际作业中的安全距离以及作业单元由舱盖板划分而导致的作业单元优先顺序的考虑并不充分.而YANG[21]提出的萤火虫算法（Firefly Algorithm，FA）在其他领域的应用结果表明，FA能较好地解决NP难问题，并且能较好地与其他算法结合，在解决离散编码问题上具有独特的方法，但至今仍未见将其应用到岸桥调度问题上.故本文拟在充分考虑岸桥调度各实际因素的基础上建立更完备的岸桥调度模型，并引入新型FA，通过结合其他启发式算法的优良特征，设计符合岸桥调度模型的算法，为岸桥调度问题提供更切合实际的解决方案.

1 数学模型

集装箱船舶停靠码头后，码头安排一定数量岸桥对其进行装卸作业.岸桥调度就是合理安排每台岸桥作业单元顺序使得船舶与岸桥的作业时间最短.集装箱装卸作业单元的划分方式有基于贝位区域、基于独立贝位以及基于集装箱箱组的划分方式，其中基于集装箱箱组划分方式的岸桥调度问题最具复杂性.本文基于集装箱箱组进行研究.

由于船舶甲板与船舱以舱盖板划分，将一个大贝内的集装箱根据甲板卸箱、舱内卸箱、舱内装箱、甲板装箱进行划分，将划分后的集装箱箱组作为一个作业单元.同一个大贝内的作业顺序要符合先卸船、后装船、卸船先卸甲板箱、装船先装舱内箱的约束.岸桥作业时必须防止互相干扰，主要包括：①岸桥不能相互交叉；②岸桥间必须留有一定的安全距离.

数学模型的建立将基于假设条件：

（1）每台岸桥有且仅有一个作业单元为初始与终了作业单元；

（2）在任何时刻，一个作业单元只能容纳一台岸桥对其进行作业；

（3）岸桥一旦开始一个作业单元，就要先完成该作业单元所有任务才能移至下一作业单元继续作业.

1.1 符号定义

i，j为作业单元编号，随贝位变大而变大；k为岸桥编号，随贝位变大而变大；n为作业单元总数量；m为岸桥的总数量；t为相邻两个作业单元间的岸桥移动时间；M为一个足够大的正数；li为第i个作业单元所在贝位；lk，0为岸桥k的起始贝位；lk，T为岸桥k的终了贝位；pi为第i个作业单元的处理时间；rk为岸桥k的最早可用时间；α1为岸桥最长完工时间的权重；α2为岸桥总完工时间的权重；Ω为所有作业单元的集合；ψ为不可同时进行的作业单元集合；φ为具有优先作业顺序的作业单元集合；

1.2 决策变量

1.3 模型描述

式（1）为岸桥调度问题的目标函数，以最小化岸桥最长完工时间和岸桥总完工时间为目标.式（2）确保岸桥的最长完工时间必须大于等于所有岸桥的最长完工时间.式（3）和（4）表示每台岸桥都有且仅有一个作业单元作为其初始与终了作业单元.式（5）表示每个作业单元都必须由一台岸桥独立完成.式（6）表示同一时刻一台岸桥只能为一个作业单元服务，直到完成该作业单元后才可继续下一作业单元.式（7）为对每台岸桥完工时间的约束，每台岸桥完工时间应大于等于其终了作业单元的完工时间.式（8）为每台岸桥的最早可用时间约束，每台岸桥的初始作业单元开始时间应该大于等于其最早可用时间.式（9）表示在同一台岸桥上两个相邻作业单元之间的时间约束.式（10）为作业单元先后作业时间约束.式（11）表示岸桥在作业过程中不能交叉.式（12）表示由于岸桥干扰约束，作业单元i与作业单元j不能同时进行作业.式（13）为岸桥间安全距离的约束.式（14）表示具有优先作业约束的作业单元.式（15）为01变量约束.式（16）表示对任意作业单元与岸桥，其作业时间均大于等于0.

该模型在KAVESHGAR等[17]于2012年提出的岸桥调度模型基础上进行修改，并加入约束式（13），充分考虑岸桥间安全距离约束.

2 算法设计

分别对3种基本算法（GA，SAA和FA）进行算法设计（其中GA与SAA不在本文进行赘述），主要针对FA的不足，将多种群GA和模拟退火机制与其结合，设计出一种融合模拟退火机制和遗传算子的多种群萤火虫算法（简称为HFA），并根据FA易陷入局部最优的缺点设计出多种群自适应萤火虫算法（简称为SFA）.

2.1 萤火虫算法

FA是由剑桥大学的YANG[21]提出的，根据萤火虫成虫发光原理产生的.萤火虫彼此吸引的原因取决于两个要素，即自身亮度和吸引度.萤火虫的发光亮度取决于目标函数值，发光亮度越高表示越优，相对发光亮度则体现了萤火虫所处位置的好坏并决定了萤火虫的移动方向.吸引度决定了萤火虫的移动距离.如果发光亮度相同，则萤火虫会随机移动.

萤火虫相对发光亮度为

式中：

I0为萤火虫最大发光亮度，即自身（rij=0处）发光亮度；γ为光强吸收系数；rij为萤火虫i，j之间的距离；β0为最大吸引度，即rij=0处的吸引度，吸引度与距离成反比；xi，xj分别为萤火虫i，j的空间位置；α为步长因子，是区间[0，1]之间的常数；λ为[0，1]上服从均匀分布的随机数.岸桥调度问题的FA步骤如下.

步骤1

初始化基本参数：n（萤火虫数目），β0，γ，α，最大迭代次数.

步骤2 初始化萤火虫位置.计算萤火虫目标函数值并以此作为其自身亮度，将不符合岸桥干扰约束的解的目标函数值设为一个极大值.

步骤3 判断是否符合作业单元优先顺序约束，若符合则执行步骤4，否则对解的编码进行调整.

步骤4 根据式（17）和（18）计算I和β.

步骤5 每个萤火虫与其他萤火虫比较I，决定萤火虫的移动方向.若存在具有更高发光亮度的萤火虫，则按式（19）向其移动.若不存在更优解，则随机移动.

步骤6 满足终止条件后结束，输出最优解，否则，重复步骤2～5.

2.2 结合GA和模拟退火机制的萤火虫算法（HFA）

考虑到FA两两比较造成求解时间成倍增加，将种群分为多子群；各子群采用并行GA，且交叉变异参数各不相同，加大搜索区域；在GA交叉变异环节加入模拟退火机制（Metropolis抽样），增强其局部寻优能力；将各子群中的最优解放入主群中，在主群中利用FA求解.在协作寻优时分别采用移民算子及人工选择算子.HFA的主要步骤如下.

步骤1 设定控制参数：子种群个数

L，子种群规模N，各子种群交叉概率Pc，变异概率Pm，温度冷却系数q，初始温度T0和结束温度Tend.

步骤2 随机产生L个初始种群.各种群按照各自的交叉、变异概率进行寻优，分别计算个体适应度函数值并判断是否符合约束条件，并按基本GA进行寻优.

步骤3 执行协作寻优，从各子种群中找出最优个体和最差个体，将最优个体放入主群中，并将前一种群中最优个体代替当前种群中最差个体.

步骤4 在主群中按2.1节进行FA寻优，对I进行两两比较，若有更优的萤火虫，则萤火虫按式（19）移动，否则保留当前解.

步骤5 判断主群中的解是否满足作业单元优先顺序，若满足则执行步骤6，否则对编码进行调整.

步骤6 判断是否满足终止条件，若满足则输出结果，否则重复步骤2～5.

2.3 多种群自适应萤火虫算法（SFA）

将种群分为多个子群，并对各子群采用不同的

α，β0，γ，提高搜索区域，将各子群的最优解放到主群中并利用FA进行求解.最初求解时采用一个较大的α，使算法能更好地完成全局搜索，随迭代次数增加，α逐渐减小，使算法能快速收敛.为防止陷入局部最优，设定一个迭代次数间隔，若在迭代次数间隔内没有更新最优解，则认为其可能陷入局部最优，进而将α设为一个较大值，使其跳出局部最优.SFA的寻优步骤如下.

步骤1 初始化算法的基本参数：

L，n（各子种群中的萤火虫数目），β0，γ，α，最大迭代次数，判定是否陷入局部收敛的迭代次数t′.

步骤2 分别对各子种群分配β0，γ，α.各子种群分别按各自的参数进行并行FA寻优.

步骤3 判断各子种群在t′内有没有更新最优解，若没有，则判定其陷入局部最优，此时将α设为一个较大的值，使其尽快跳出局部最优.

步骤4 进行协作寻优，使用移民算子将前一子种群中的最优值替换后一子种群中的最差值.使用人工选择算子将各子种群中的最优值放入主群中.

步骤5 对主群进行FA寻优.

步骤6 判断在tn次数内有没有更新最优解，若没有，则判定其陷入局部最优，此时将α设为一个较大的值，使其尽快跳出局部最优.

步骤7 满足终止条件后结束，输出最优解，否则，重复步骤2～6.

3 算例分析

分别对两个算例进行分析，算例来自文献[14]，目前单船岸桥调度问题主要采用该案例进行方法比较.采用小规模算例对3种基本算法进行对比，采用大规模算例对两种改进FA进行对比.目标函数权重采用α1=0.9，α2=0.1，且岸桥在相邻大贝的移动时间为1 min，两台岸桥的安全距离为1个大贝.

3.1 小规模算例

小规模算例为2台岸桥对一艘具有10个大贝和10个集装箱箱组的船舶进行装卸作业，采用3种基本算法对其求解，并对比算法性能，挖掘各自特点.表1为算例数据.作业单元间存在先后顺序，第4个作业单元必须优先于第5个作业单元进行处理，第9个作业单元必须优先于第10个作业单元进行处理.岸桥准备时间不考虑，岸桥初始位置分别在02贝和06贝.

由表2和图1可知，GA最优，SAA最差，而FA运行时间远大于另两种算法的运行时间.

3.2 大规模算例

大规模算例为3台岸桥对1艘具有10个大贝和20个集装箱箱组的船舶进行装卸作业，利用两种改进的FA对其求解，将模型中所提出的约束条件在结果中体现，并对算法性能进行分析.表3为算例数据.岸桥3由于需要先完成其他任务，在装卸作业开始30 min后加入作业，

4 结 论

本文在现有文献基础上对岸桥作业调度进行分

析，建立符合实际情况的岸桥调度问题模型，考虑岸桥不可交叉及安全距离约束，首次加入由舱盖板划分的作业单元优先顺序约束，使结果更具有应用性.

在算法设计上，利用遗传算法（GA）、模拟退火算法（SAA）、萤火虫算法（FA）分别对岸桥调度问题进行求解，并对结果进行比较分析，得到两种改进的FA.HFA将多种群遗传算法和模拟退火机制加入FA中，极大地改善了FA收敛速度慢的缺陷.SFA改善了FA易陷入局部最优的缺陷.本文为FA在岸桥调度问题中的使用奠定了基础，并且成功将FA与成熟算法结合得到更优的结果，也验证了FA在NP难问题中的适用性.

参考文献：

[1]

DAGANZO C F. The crane scheduling problem[J]. Transportation Research Part B Methodological， 1989， 23（3）： 159175.

[2]PETERKOFSKY R I， DAGANZO C F. A branch and bound solution method for the crane scheduling problem[J]. Transportation Research Part B Methodological， 1990， 24（3）： 159172.

[3]KIM K H， PARK Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research， 2004， 156（3）： 752768.

[4]MOCCIA L， CORDEAU J F， GAUDIOSO M， et al. A branchandcut algorithm for the quay crane scheduling problem in a container terminal[J]. Naval Research Logistics， 2005， 53（1）： 4549.

[5]孙俊清， 李平， 韩梅. 装卸桥调度问题及其混合智能优化算法GASA[C]//第26届中国控制会议论文集.北京： 北京航空航天大学出版社， 2007： 9296.

[6]LEE D H， WANG H Q， MIAO L X. Quay crane scheduling with noninterference constraints in port container terminals[J].Transportation Research Part E Logistics & Transportation Review， 2008， 44（1）： 124135.

[7]韩笑乐， 梁亮， 陆志强， 等. 集装箱码头岸吊作业调度建模及调度策略研究[J]. 工业工程与管理， 2009， 14（5）： 2026.

[8]董良才， 丁以中， 宓为建. 基于时间窗的集装箱装卸桥调度[J]. 上海海事大学学报， 2011， 32（1）： 17.

[9]LEGATO P， TRUNFIO R， MEISEL F. Modeling and solving rich quay crane scheduling problems[J]. Computers & Operations Research， 2012， 39（4）： 20632078.

[10]范志强， 乐美龙. 最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法[J]. 系统管理学报， 2013， 22（1）：120127.

[11]王辉球. 集装箱岸吊的调度模型和算法研究[D]. 北京： 清华大学， 2006.

[12]MARCELLO S， CORDEAU J F， LAPORTE G， et al. A tabu search heuristic for the quay crane scheduling problem[J]. Journal of Scheduling， 2007， 10（4）： 327336.