自动化码头装卸混合模式下QC、LAGV及ARMG协同调度方法
添玉 王建彬,陈晶晶 范会方
摘要：
为解决复杂的自动化码头设备协同调度问题，考虑码头各作业间的相互作用和制约，以最小化船舶在港时间和主要设备作业成本为目标，构建新的装卸混合模式下岸桥（quay crane， QC）、顶升式自动引导车（lifting automated guided vehicle， LAGV）及自动化轨道吊（automated rail mounted gantry crane， ARMG）协同调度的混合整数非线性规划模型。提出一种遗传算法与启发式策略结合的协同调度方法，实现在系统整体性能最优情况下的设备作业序列优化。该模型能充分保障QC、LAGV、ARMG之间的协同性，并引入QC调度的主要约束，更利于与QC调度模型进一步集成。数值试验证明了该方法的有效性，可为码头装卸作业调度提供决策支持。
关键词：
自动化码头； 自动引导车（AGV）； 自动化轨道吊； 协同调度； 遗传算法（GA）
中图分类号： U691.3
文献标志码： A
Abstract：
In order to solve the complex collaborative scheduling problem of automated terminal equipments， considering the interaction and restriction among various operations in terminals， a new mixed integer nonlinear programming model is constructed for quay cranes （QCs）， lifting automated guided vehicles （LAGVs） and automated rail mounted gantry cranes （ARMGs） collaborative scheduling under the mixed loading and unloading mode. The model objectives are to minimize the ship turnround time at a port and to minimize the operation cost of key equipments. A collaborative scheduling method based on the genetic algorithm and the heuristic strategy is proposed to obtain an optimized operation sequence of equipments under the condition of the optimal overall performance of the system. The model fully guarantees the cooperativity of QCs， LAGVs and ARMGs， and the main constraints of QC scheduling are introduced， which is more conducive to the further integration with QC scheduling model. A numerical test is taken to demonstrate the effectiveness of the method. It can provide decision support for loading and unloading operations of automated terminals.
Key words：
automated terminal； automated guided vehicle （AGV）； automated rail mounted gantry crane； collaborative scheduling； genetic algorithm （GA）
0引言
由于集装箱码头装卸工藝、作业空间和设备配置等限制，优化各环节调度成为提高码头整体效率的重要途径。目前，已有学者对包括水平运输设备在内的集装箱码头集成调度问题进行了研究。CAO等[12]针对出口集装箱分别建立了解决单个岸桥（quay crane， QC）与多辆集卡协调分配的混合整数模型和集卡与龙门吊集成调度模型，前者设计了遗传算法和改进约翰逊规则的启发式算法来提高求解速率，后者基于Benders变异对问题进行求解。秦天保等[3]针对集装箱QC与集卡集成调度问题，以卸船完工时间最小为目标，采用约束规划技术建模求解。CHEN等[4]研究了集装箱码头QC与集卡集成调度问题，建立了带约束的规划模型，并设计了一个三阶段算法。韩晓龙等[5]考虑集卡作业时间不确定和动态性到达的情况，建立了集卡与QC协同调度模型并设计了改进的遗传算法进行求解。TANG等[6]建立了QC与集卡联合调度模型，并用改进的粒子群算法解决进出口箱装卸作业问题。HE等[7]建立了传统集装箱码头QC、场桥和集卡的集成调度模型，提出了基于仿真的遗传算法与粒子群算法结合的优化方法。
MEERSMANS等[8]最早研究了自动化码头多类型设备的集成调度问题，提出了分支定界法及启发式算法，但仅考虑了装船作业情形。LAU等[9]分析了码头核心设备之间的协调关系，提出了设备集成调度模型，设计分层遗传算法并结合启发式策略进行求解。HOMAYOUNI等[10]提出自动化码头自动引导车（automated guided vehicle， AGV）和QC同时调度的混合整数规划模型，并设计了两阶段启发式遗传算法进行求解。DKHIL等[11]考虑码头多种资源之间的相互作用与制约，提出了QCAGVASC（automated stacking crane）集成模型。LUO等[1213]分别考虑了装卸同时进行的情形和单卸的情形，研究了自动化码头AGV调度规则和确定集装箱堆放位置的新方法，通过数值试验评估算法的有效性。
集装箱码头运作由众多环节相互合作完成，且各环节相互影响和制约，但当前绝大多数关于调度的研究集中在传统码头领域，缺乏多类型设备的深度集成，鲜有考虑边装边卸作业模式及工艺革新造成的调度复杂性。少数研究集成调度的文献存在的不足有：（1）忽略了QC调度中任务约束的影响；（2）假设场桥作业序列完全遵从QC装卸序列。因此，本文将以顶升式自动引导车（lifting automated guided vehicle，LAGV）为水平运输设备的自动化码头装卸系统作为对象，引入QC调度的主要约束，提出新的QC、LAGV和自动化轨道吊（automated rail mounted gantry crane，ARMG）协同调度模型和算法，实现系统性能的改善。
1问题描述
码头设备资源的调度受码头工艺的制约和影响，而码头工艺创新为码头作业效率的提升提供了重要的途径。这里研究双车QC、LAGV和ARMG组成的新型自动化集装箱码头工艺，其布局见图1。LAGV所在的QC作业区位于QC后伸距下方，各车道为单向行驶，行车方向依据船头朝向和装、卸箱量的比例设定，以减少倒箱门现象对车辆和道路的干扰。堆场采用垂直于岸线的布局，堆场海侧行驶区采用双向车道，相邻车道行驶方向相反，便于车辆在堆场海侧交换区的进出。缓冲车道位于QC作业区与堆场海侧交换区之间，既作为LAGV的临时等待区，又作为岸边与堆场之间的连接通道，以缩短水平运输距离。
与传统工艺相比，LAGV负责水平运输，堆场每个箱区海侧布置由一组支架组成的交换区，作为集装箱的临时缓冲存放点，以缓解水平运输能力与堆场装卸能力的矛盾，提高系统作业效率。然而，交接方式的灵活性增加了设备调度的复杂性，这对调度方法提出了更高要求。
码头装卸系统是一个复杂的、动态的并行工作系统，其作业类型包括将进口集装箱运输到堆场侧和将出口集装箱运输到船侧。以装船作业为例简述运作决策过程：首先，船舶进港后，码头根据船舶配载图、堆场分配计划等，制定QC分配和调度计划；然后，由ARMG从堆场指定位置提取集装箱，经缓冲支架交给指定LAGV；最后，由指定LAGV运输集装箱到指定QC。若LAGV晚到则会造成QC等待，增加船舶的在港时间。卸船过程相反。
显然，QC装卸作业、水平运输作业与堆场设备作业相互关联，必须制定统筹全局的设备协同调度计划。以往大多研究仅考虑单独装箱或卸箱作业，即使涉及QC同时装卸，也未考虑在堆场箱区混合堆存情况下如何提高调度协同性问题。这样的简化会极大地降低全局性能。因此，本文研究更一般的情形：在装卸混合模式下，船舶的进出口集装箱混合堆存在不同箱区，QC边装边卸，LAGV灵活服务多台QC且可双循环运输，同时箱区的ARMG边存边取。调度方案的优劣由两方面因素评价：（1）LAGV自身效率。为降低空驶率，将LAGV总行驶时间作为评价指标。（2）QC和ARMG的效率。集装箱船在港时间越长，其花费成本就越大，故将船舶在港时间和ARMG移动时间作为评价指标。
2自动化设备集成调度模型
2.1假设条件
（1）集港在装卸船作业之前已经完成，疏港在装卸船作业之后才进行；（2）计划期内的船舶配载计划、泊位计划、堆场箱位计划和QC调度计划已知，这里QC调度的任务以簇[14]形式定义，且簇任务内集装箱装卸顺序和簇之间的约束关系确定；（3）QC、LAGV和ARMG数量已知，且每个设备一次只处理一个集装箱；（4）LAGV、ARMG（空/重载）和QC的行驶速度及其装卸效率已知；（5）进、出口集装箱允许堆存在堆场同一箱区，每个箱区的集装箱仅由海侧ARMG负责装卸，已知LAGV与任意两个操作节点之间的距离，忽略LAGV和ARMG在堆场交换区等待支架空闲的时间。
2.2符号变量说明
常量符号如下。
K表示QC的集合，Q表示ARMG的集合，V表示LAGV的集合。ve和vd分别表示为ARMG提供初始和结束虚拟任务的虚拟QC，vs和vf分别表示为LAGV提供初始和结束虚拟任务的虛拟QC。mk表示第k台QC执行的任务数量，k∈K。（k，i）为箱任务编号，表示第k台QC 的第i个箱任务，k∈K，i=1，2，…，mk。eki和dki分别为QC在其作业区开始和结束箱任务（k，i）的事件，当箱任务（k，i）为卸船任务时其分别表示QC开始落箱到LAGV上的事件和结束落箱到LAGV上的事件，当箱任务（k，i）为装船任务时其分别表示QC从LAGV上开始提箱的事件和结束落箱到船上的事件，k∈K，i=1，2，…，mk。 Eaki表示LAGV在堆场海侧交换区开始作业箱任务（k，i）的事件，当箱任务（k，i）为卸船任务时其表示LAGV开始将箱顶升到支架的事件，当箱任务（k，i）为装船任务时其表示LAGV开始从支架处接箱的事件，k∈K，i=1，2，…，mk。Ebki表示ARMG在堆场海侧交换区开始作业箱任务（k，i）的事件，当箱任务（k，i）为卸船任务时其表示ARMG开始从支架上抓箱的事件，当箱任务（k，i）为装船任务时其表示ARMG开始放箱到支架上的事件，k∈K，i=1，2，…，mk。TC表示有先后顺序要求的事件eki的集合，TD表示卸船任务对应的事件eki的集合，TL表示装船任务对应的事件eki的集合，Nq表示第q台ARMG执行的Ebki的集合，k∈K，i=1，2，…，mk，q∈Q。
变量符号如下。ski表示第k台QC执行eki的实际准备就绪时刻，Hk（i-1）i表示第k台QC完成ek（i-1）后执行eki的全部准备时间，yki表示eki的实际发生时刻，ψki表示dki的实际发生时刻，Δwki表示eki与dki发生时刻的间隔时间，Yaki表示Eaki的发生时刻，Ybki表示Ebki的发生时刻，Ski表示eki与Eaki之间的间隔时间，ΔSki表示Eaki与Ebki之间的间隔时间，k∈K，i=1，2，…，mk。Tki，lj表示
ARMG从
Ebki发生的位置到Eblj发生的位置的纯移动时间，Rki，lj表示ARMG完成Ebki后执行Eblj需要的调整时间，k∈{ve}∪K，l∈{vd}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mve=Q。tki，lj表示LAGV从eki发生的位置到elj发生的位置耗费的时间，cki，lj表示LAGV完成eki后去执行elj需要的调整时间，rki，lj表示eki与Ealj之间LAGV的调整时间，k∈{vs}∪K，l∈{vf}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mvs=V。
决策变量如下。ki，lj为01变量，若同一辆LAGV完成eki后紧接着完成elj则其值为1，否则为0，k∈{vs}∪K，l∈{vf}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mvs=mvf=V。φki，lj为01变量，若同一台ARMG完成Ebki后紧接着完成Eblj则其值为1，否则为0，k∈{ve}∪K，l∈{vd}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mve=mvd=Q。
2.3目标函数及约束
下式中，除有特殊限定外：
k，l∈K；i=1，2，…，mk；j=1，2，…，ml。
S1=min（maxk∈K ψkmk）
（1）
S2=min k∈{ve}∪K
i
l∈K∪{vd}
j（Tki，ljφki，lj）
（2）
S3=min k∈{vs}∪K i
l∈K∪{vf}
j（tki，ljφki，lj）
（3）
l∈{vf}∪K
jki，lj=1，k∈{vs}∪K
（4）
k∈{vs}∪K
iki，lj=1，l∈{vf}∪K
（5）
l∈{vd}∪K
jφki，lj=1，k∈{ve}∪K
（6）
k∈{ve}∪K
iφki，lj=1，l∈{vd}∪K
（7）
ylj-max（yki+cki，lj，slj）≥M（ki，lj-1），
k∈{vs}∪K
（8）
Yblj-（Ybki+Rki，lj）≥M（φki，lj-1），
k∈{ve}∪K
（9）
Yalj-（yki+rki，lj）≥M（ki，lj-1），
k∈{vs}∪K
（10）
yki≥ski
（11）
ski≥yk（i-1）+Hk（i-1）i， i=2，3，…，mk
（12）
yki≥Yaki+Ski，eki∈TL
（13）
Yaki≥Ybki+ΔSki，eki∈TL
（14）
Yaki≥yki+Ski，eki∈TD
（15）
Ybki≥Yaki+ΔSki，eki∈TD
（16）
Ybki-Yblj≥0，Ebki，Eblj∈Nq；yki>ylj；
eki∈TD；elj∈TL； q∈Q；
若k≠l則eki，elj∈TC
（17）
ψki-yki≥Δwki
（18）
式（1）～（3）为目标函数，分别表示最小化所有QC中最大完工时刻、最小化ARMG总移动时间、最小化LAGV的总行驶时间。式（4）～（7）表示LAGV或ARMG一次只能执行一个任务，一个任务一旦由某一ARMG或LAGV执行就不能中断，且每个任务都要被执行。式（8）和（9）表示由同一装卸运输设备执行的相邻任务的时间逻辑关系，式（8）表示同一辆LAGV完成
eki后去执行elj需要有时间cki，lj准备，以及只有LAGV到达和QC自身准备就绪，QC才能开始装卸集装箱。式（9）表示同一台ARMG完成Ebki后去执行Eblj需要有时间Rki，lj准备。式（10）表示不同作业环节的时间逻辑关系，如果任务（k，i）和（l，j）是同一辆LAGV的两个相邻任务，那么LAGV完成eki后需要时间rki，lj调整才能执行Ealj。式（11）表示eki的实际发生时刻最小为最早可能发生时刻。式（12）表示QC执行ek（i-1）后需时间Hk（i-1）i准备才能执行任务eki。式（13）和（14）表示某装船任务（k，i）的相邻作业环节间的时间逻辑关系，此类任务的设备操作顺序是ARMG—LAGV—QC，因此LAGV完成Eaki的时刻与Eaki和eki的调整时间之和不会超过QC完成eki的时刻，ARMG完成Ebki时刻与Eaki和Ebki的调整时间之和不会超过LAGV完成Eaki的时刻。同理，式（15）和（16）表示某卸船任务（k，i）的相邻作业环节间的时间逻辑关系，此类任务的设备操作顺序是QC—LAGV—ARMG。式（17）表示每一台ARMG执行QC的任务时其作业顺序在先装后卸情形下需要符合QC作业顺序和其任务约束关系。式（18）表示QC装卸每个集装箱需要时间Δwki。
值得注意的是，上述模型与已有文献相比，主要有3点不同。（1）LAU等[9]的研究将ARMG调度序列归结为QC调度序列的子序列，意味着ARMG调度必须遵从QC调度，由式（19）约束：
Yki-Ykj≥0，Ebki∈Nq；i>j；q∈Q
（19）
而本文模型考虑船舶集装箱装卸混合作业时ARMG与 QC调度的协同性，体现在将式（19）放松为式（17），表明ARMG除先装后卸情形外，可以按照灵活作业顺序操作，无须遵从QC调度序列。（2）所有类似文献均研究传统AGV工艺，在堆场箱区只有AGV与 ARMG刚性衔接，而本文针对缓冲支架系统，特别定义了Yaki和Ybki两个状态变量，增加LAGV、ARMG和支架三者之间衔接的灵活性。（3）考虑QC调度任务约束关系，由式（17）体现，以利于与QC调度模型进一步集成。
3协同调度方法及算法设计
3.1协同调度思想
传统调度方法[9]规定水平运输设备和场桥的作业序列必须遵从QC作业顺序。该方法一般适用于单装/单卸模式，而在装卸混合模式下虽然能够降低集成调度的复杂性，缩小问题解空间，但会忽略设备作业协同性，甚至会将最优解排除。
本文提出的协同调度策略的特点在于，要求水平运输设备必须遵从QC或约束关系的任务顺序，而放松ARMG与QC作业的一致性约束，除QC先装后卸作业情形外，允许ARMG自主灵活地确定作业序列，见图2。
3.2结合启发式策略的遗传算法设计
在QC作业序列的基础上，基于遗传算法，采用协同调度策略优化ARMG作业序列，并采用启发式LAGV指派策略优化车辆运输任务，见图3。
3.2.1染色体编码和解码
基于QC调度计划对箱任务采用自然数编码，每个染色体代表所有箱任务的一种随机排列，每个自然数代表箱任务编号，染色体长度等于箱任务数量。染色体序列需结合LAGV指派和ARMG调度的启发式策略进行解码，确定各ARMG及LAGV的任务顺序。
在上述编码基础上，设计ARMG调度序列的启发式策略的步骤如下：（1）从编码序列中抽取每台ARMG的任务序列，获得各台ARMG的随机箱序列；（2）针对ARMG随机任务序列中的任意两个任务，判断两个任务是否属于同一辆QC，若是则转步骤（3），否则继续寻找，直到所有的两个任务组合都寻找过一次为止；（3）判断两个任务是否是同一任务类型，若是则转步骤（2），否则判断这两个任务在QC作业序列中的作业顺序是否是先装后卸，若是则将ARMG中这两个任务的顺序调整成QC作业顺序，然后转步骤（2）。最终获得符合QC先装后卸作业约束的ARMG箱任务序列。
若在装卸混合模式下存在同箱区且在同一QC序列中先卸后装两个附近的任务，则采用上述启发式策略有利于避免各设备的串行完成，实现并行协同调度，降低过多等待，提高码头效率。
码头常以船舶在港时间最短为首要目标，因此采用如下3种基于时间型启发式规则的LAGV指派策略，逐一为任意箱任务序列中的集装箱指派合适的LAGV。LAGV完成当前运输任务后随即去执行后续任务；LAGV卸船箱任务的起始位置在QC作业区；LAGV装船箱任务的起始位置在堆场海侧交换区。（1）先到先指派策略：针对某一运输任务，选择最快完成前项任务抵达该任务起始位置的LAGV。（2）适合装箱位置就绪策略：针对某一运输任务，以起重设备作业该任务的准备就绪时刻（若装船，则是ARMG准备就绪时刻；若卸船，则是QC准备就绪时刻）为基准，从所有车辆中选择完成前项任务后最早抵达该任务起始位置的LAGV。（3）适合QC就绪策略：针对某一运输任务，以QC就绪时刻为基准，从所有车辆中选择完成前项任务后最早空驶（卸船箱）或提箱（装船箱）至QC作业区的LAGV。
3.2.2不可行和重复序列的修正策略
随机生成或迭代更新的染色体可能存在不可行或重復个体的情况，故需进行修正。针对不可行序列的修正策略：将箱任务序列满足已知QC作业箱任务顺序及簇任务约束关系。针对种群中重复序列的修正策略：搜寻每代的重复个体，并采用部分逆反变异操作生成新的个体替换原染色体，得到新的种群作为下一代。这样不仅降低重复个体存在的概率，而且保持了种群多样性。
3.2.3染色体选择、交叉、变异操作
采用轮盘赌的方法对染色体进行选择；采用部分匹配交叉（图4）和部分逆反变异（图5）的方法对染色体进行交叉、变异操作。
3.2.4适应度函数设置
以最小化箱任务最大结束时刻为首要目标，并通过设置加权系数，将适应度函数设计为一种组合函数，其由箱任务最大结束时刻、QC累计等待时间、每台QC的箱任务均衡程度、LAGV的总行驶时间和ARMG总移动时间组成。鉴于最小化问题，将适应度函数设为上述组合函数的倒数，具体计算取决于箱任务的LAGV指派以及各设备之间的交接时刻，状态更新流程图见图6。
4案例验证与结果分析
4.1案例说明
以采用“双车QC+ LAGV+ ARMG”工艺系统的青岛某自动化集装箱码头为例，码头整体布局和水平运输交通规则见图1。LAGV所在的QC作业区共7条行车道，每条车道宽4 m，其中4条为装卸车道，3条为穿越车道，装卸车道成对布置，并与穿越车道相间隔。堆场海侧行驶区共有6条双向车道，且相邻车道行驶方向相反。各装卸运输设备的速度见表1。
某船需要装卸的进出口集装箱在船上的位置及簇任务划分和约束关系可通过船舶配载计划获得。假设QC调度计划已知，QC抓/放箱操作时间均为10 s，QC小车在QC作业区与船之间的水平行驶时间为40 s，且在QC作业区车道上的行驶方向为逆时针方向；ARMG初始位置在堆场海侧交换区（包含4个缓冲支架和1个空车道），堆场数量为10个，每个堆场仅海侧ARMG工作；LAGV初始位置在缓冲车道，各设备完成各自所有任务后必须回到初始位置。
考虑算法运算效率，通过多次组合试验确定算法相关参数。初始种群大小为50，最大遗传代数为100，交叉概率为0.85，变异概率为0.1。本文试验均采用MATLAB R2014a编程实现算法，并在Intel（R） Core（TM） i76700HQ CPU @2.6 GHz处理器、8 GB内存的电脑上运行得到试验结果。
4.2协同调度求解结果分析
4.2.1算法的优化性能分析及鲁棒性分析
设计7组中等规模仿真算例，从计算时间和结果进行比较，验证所提算法的优化性能。采用CPLEX 12.2求解器和遗传算法分别求解算例。在CPLEX求解过程中，将模型的非线性约束式（8）划分成2个线性约束，结果见表2。表2中最后一列显示了采用本文算法得到的加权目标函数值与最优值之间的偏差。试验发现，计算耗时随着任务数的增加快速上升，对30个以上的箱任务问题无法在有效时间内得到结果，而用遗传算法尽管不能获得最优解，但其解与最优解的偏差在适当范围内，且在大规模任务的计算效率上具有优势。
不同任务规模和LAGV数量下算法的鲁棒性变化如图7所示：鲁棒性指标在适当范围（0～4%）内波动，其最大值为3.90%，平均值为2.47%，说明算法有较好的鲁棒性。
4.2.2结果比较分析
根据设置的案例数据，采用结合启发
式策略的遗传算法对自动化设备协同调度模型进行求解。试验选择2个因素作为变量：LAGV数量，设置在8与24之间；每个计划期内的任务规模，设置成40、50、60、70和80。所需其他数据（如LAGV初始位置、集装箱类型及其在堆场中的位置）均采用随机模拟方式产生。因此，不同变量因素下有多种组合，每种组合随机产生10组数据，每组数据重复试验操作5次，取其平均值来减少算法误差。
4.2.2.1协同调度方法的比较分析
為分析系统性能的灵敏性，将LAGV数量和每个计划期内的任务规模作为变化因素，得到不同调度方法的结果，见图8。在给定LAGV数量的情况下，2种调度方法的加权目标函数值均随着任务规模的增加而增加，但平均每个任务的加权目标函数值在下降。这表明任务规模变大时系统将获得更好的性能。但实际上，由于码头各种中断事件的发生，如起重机或LAGV等设备故障，不可避免地需要进行再调度。因此，可结合实际情况，选取一个适当的任务规模以权衡计算量和系统性能的损失。在给定任务规模和LAGV数量的情况下，本文提出的协同调度方法的加权目标函数值小于传统调度方法的加权目标函数值。这表明，在码头实际管理中，充分优化ARMG作业序列有助于提高其与QC和LAGV之间的协调性，达到系统整体性能平均8.7%的提升。
4.2.2.2不同LAGV指派策略比较分析
图9为不同LAGV指派策略对整体调度结果的影响。在3种LAGV指派策略下，随着LAGV数量的增多平均每个任务的加权目标函数值均在下降。图9中的数据表明，不同的LAGV指派策略无绝对的优劣，不同的策略适合不同的设备配置比例。由此可见，在码头实际管理中，根据设备配置比例合理利用不同LAGV指派策略比利用单一LAGV指派策略效果更好，更有助于码头整体效率的提升。
图10为不同LAGV指派策略对QC等待时间的影响。在LAGV和QC配置比例较小时：LAGV本属于瓶颈资源，采用先到先指派策略更易造成无效等待，从而加剧水平运输设备的紧缺性，最终导致其他QC过多等待；采用适合QC就绪策略，即始终选择适合的QC，有助于减少QC等待时间。因此，在此情形下采用适合QC就绪策略的效果优于采用适合装箱位置就绪策略的效果。在LAGV和QC配置比例较大时，这两种策略对QC等待时间的影响无明显差异。
图11为不同LAGV指派策略对ARMG移动时间的影响。在LAGV和QC配置比例较小时，LAGV本属于瓶颈资源，采用先到先指派策略和适合装箱位置就绪策略更易导致LAGV等待发生，从而加剧水平运输运力的紧张，导致其他ARMG过多等待，进而影响到ARMG的调度序列，使得重进重出比例下降，因此此时采用适合QC就绪策略效果较好。在LAGV与QC配置比例较大时，QC和ARMG效率成为关键，而采用先到先指派策略有助于减少LAGV空驶率，从而提升运力，最终配合ARMG优
化作业序列，降低移动时间，因此此时先到先指派策略优于适合装箱位置就绪策略。
图12为不同LAGV指派策略对LAGV行驶时间的影响。采用先到先指派策略，即选择最早到达的、最近的LAGV有利于减少空驶率，从而更有利于降低LAGV行驶成本。相对于适合装箱位置就绪策略，适合QC就绪策略的目的在于减少无效等待时间，故空驶率不会太高；相对于先到先指派策略，适合QC就绪策略用在卸箱任务时容易产生较高空驶率，且用于装船任务时更倾向于选择无效时间最短的车辆，故空驶率较高。总之，从车辆行驶成本看，适合QC就绪策略是3种指派策略中的一个折中策略，其目的在于优化QC等待时间。因此，如图12所示，该策略下的曲线变化平缓，且位于其他两种策
略对应的曲线之间。
5结束语
码头设备的协同调度有利于减少船舶在港时间，提高码头整体作业效率。本文在以往研究的基础上构建新的协同调度模型并设计改进的遗传算法进行求解，其创新之处在于：考虑了LAGV结合具有有限堆场缓存空间的自动化集装箱码头装卸新工艺的作业特点；考虑了装卸混合模式下设备调度的协同性；引入了QC调度的主要约束。最终通过数值试验与传统调度方法的对比验证了本文模型和算法的有效性。
参考文献：
[1]
CAO Jinxin， SHI Qixin， LEE DerHorng. Integrated quay crane and yard truck schedule problem in container terminals[J]. Tsinghua Science & Technology， 2010， 15（4）： 467474.
[2]CAO Jinxin， LEE DerHorng， CHEN Jianghang， et al. The integrated yard truck and yard crane scheduling problem： Benders decompositionbased methods[J]. Transportation Research Part E： Logistic & Transportation Review， 2010， 46（3）： 344353.
[3]秦天保， 彭嘉瑶， 沙梅. 带任务顺序约束的岸桥集卡集成调度约束规划模型[J]. 上海海事大学学报， 2013， 34（3）： 17.
[4]CHEN Lu， LANGEVIN A， LU Zhiqiang. Integrated scheduling of crane handling and truck transportation in a maritime container terminal[J]. European Journal of Operational Research， 2013， 225（1）： 142152.
[5]韩晓龙， 牟少莉. 基于CHC算法的集卡与岸桥协调调度优化问题[J]. 武汉理工大学学报（信息与管理工程版）， 2014， 36（2）： 233236.
[6]TANG Lixin， ZHAO Jiao， LIU Jiyin. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research， 2014， 236（3）： 978990.
[7]HE Junliang， HUANG Youfang， YAN Wei， et al. Integrated internal truck， yard crane and quay crane scheduling in a container terminal considering energy consumption[J]. Expert Systems with Applications， 2015， 42（5）： 24642487.
[8]MEERSMANS P J M， WAGELMANS A P M. Effective algorithms for integrated scheduling of handling equipment at automated container terminals[R]. Rotterdam： Erasmus University， 2001.
[9]LAU H Y K， ZHAO Ying. Integrated scheduling of handling equipment at automated container terminals[J]. Annals of Operations Research， 2008， 112（2）： 665682.
[10]HOMAYOUNI S M， HONG T S， ISMAIL N， et al. A genetic algorithm for optimization of simultaneous scheduling of AGVs and QCs in container terminals[C/OL]//11th Asia Pacific Industrial Engineering and Management System. Melaka， Malaysia， December 710， 2010. http：//www.apiems.org/archive/apiems2010/paper.php.
[11]DKHIL H， YASSINE A， CHABCHOUB H. Optimization of container handling systems in automated maritime terminal[J]. Studies in Computational Intelligence， 2013， 457： 301312.
[12]LUO Jiabin， WU Yue. Modelling of dualcycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E： Logistics & Transportation Review， 2015， 79： 4964.
[13]LUO Jiabin， WU Yue， MENDES A B. Modelling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal[J]. Computers & Industrial Engineering， 2016， 94： 3244.
[14]BIERWIRTH C， MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research， 2010， 202（3）： 615627.
（編辑赵勉）
摘要：
为解决复杂的自动化码头设备协同调度问题，考虑码头各作业间的相互作用和制约，以最小化船舶在港时间和主要设备作业成本为目标，构建新的装卸混合模式下岸桥（quay crane， QC）、顶升式自动引导车（lifting automated guided vehicle， LAGV）及自动化轨道吊（automated rail mounted gantry crane， ARMG）协同调度的混合整数非线性规划模型。提出一种遗传算法与启发式策略结合的协同调度方法，实现在系统整体性能最优情况下的设备作业序列优化。该模型能充分保障QC、LAGV、ARMG之间的协同性，并引入QC调度的主要约束，更利于与QC调度模型进一步集成。数值试验证明了该方法的有效性，可为码头装卸作业调度提供决策支持。
关键词：
自动化码头； 自动引导车（AGV）； 自动化轨道吊； 协同调度； 遗传算法（GA）
中图分类号： U691.3
文献标志码： A
Abstract：
In order to solve the complex collaborative scheduling problem of automated terminal equipments， considering the interaction and restriction among various operations in terminals， a new mixed integer nonlinear programming model is constructed for quay cranes （QCs）， lifting automated guided vehicles （LAGVs） and automated rail mounted gantry cranes （ARMGs） collaborative scheduling under the mixed loading and unloading mode. The model objectives are to minimize the ship turnround time at a port and to minimize the operation cost of key equipments. A collaborative scheduling method based on the genetic algorithm and the heuristic strategy is proposed to obtain an optimized operation sequence of equipments under the condition of the optimal overall performance of the system. The model fully guarantees the cooperativity of QCs， LAGVs and ARMGs， and the main constraints of QC scheduling are introduced， which is more conducive to the further integration with QC scheduling model. A numerical test is taken to demonstrate the effectiveness of the method. It can provide decision support for loading and unloading operations of automated terminals.
Key words：
automated terminal； automated guided vehicle （AGV）； automated rail mounted gantry crane； collaborative scheduling； genetic algorithm （GA）
0引言
由于集装箱码头装卸工藝、作业空间和设备配置等限制，优化各环节调度成为提高码头整体效率的重要途径。目前，已有学者对包括水平运输设备在内的集装箱码头集成调度问题进行了研究。CAO等[12]针对出口集装箱分别建立了解决单个岸桥（quay crane， QC）与多辆集卡协调分配的混合整数模型和集卡与龙门吊集成调度模型，前者设计了遗传算法和改进约翰逊规则的启发式算法来提高求解速率，后者基于Benders变异对问题进行求解。秦天保等[3]针对集装箱QC与集卡集成调度问题，以卸船完工时间最小为目标，采用约束规划技术建模求解。CHEN等[4]研究了集装箱码头QC与集卡集成调度问题，建立了带约束的规划模型，并设计了一个三阶段算法。韩晓龙等[5]考虑集卡作业时间不确定和动态性到达的情况，建立了集卡与QC协同调度模型并设计了改进的遗传算法进行求解。TANG等[6]建立了QC与集卡联合调度模型，并用改进的粒子群算法解决进出口箱装卸作业问题。HE等[7]建立了传统集装箱码头QC、场桥和集卡的集成调度模型，提出了基于仿真的遗传算法与粒子群算法结合的优化方法。
MEERSMANS等[8]最早研究了自动化码头多类型设备的集成调度问题，提出了分支定界法及启发式算法，但仅考虑了装船作业情形。LAU等[9]分析了码头核心设备之间的协调关系，提出了设备集成调度模型，设计分层遗传算法并结合启发式策略进行求解。HOMAYOUNI等[10]提出自动化码头自动引导车（automated guided vehicle， AGV）和QC同时调度的混合整数规划模型，并设计了两阶段启发式遗传算法进行求解。DKHIL等[11]考虑码头多种资源之间的相互作用与制约，提出了QCAGVASC（automated stacking crane）集成模型。LUO等[1213]分别考虑了装卸同时进行的情形和单卸的情形，研究了自动化码头AGV调度规则和确定集装箱堆放位置的新方法，通过数值试验评估算法的有效性。
集装箱码头运作由众多环节相互合作完成，且各环节相互影响和制约，但当前绝大多数关于调度的研究集中在传统码头领域，缺乏多类型设备的深度集成，鲜有考虑边装边卸作业模式及工艺革新造成的调度复杂性。少数研究集成调度的文献存在的不足有：（1）忽略了QC调度中任务约束的影响；（2）假设场桥作业序列完全遵从QC装卸序列。因此，本文将以顶升式自动引导车（lifting automated guided vehicle，LAGV）为水平运输设备的自动化码头装卸系统作为对象，引入QC调度的主要约束，提出新的QC、LAGV和自动化轨道吊（automated rail mounted gantry crane，ARMG）协同调度模型和算法，实现系统性能的改善。
1问题描述
码头设备资源的调度受码头工艺的制约和影响，而码头工艺创新为码头作业效率的提升提供了重要的途径。这里研究双车QC、LAGV和ARMG组成的新型自动化集装箱码头工艺，其布局见图1。LAGV所在的QC作业区位于QC后伸距下方，各车道为单向行驶，行车方向依据船头朝向和装、卸箱量的比例设定，以减少倒箱门现象对车辆和道路的干扰。堆场采用垂直于岸线的布局，堆场海侧行驶区采用双向车道，相邻车道行驶方向相反，便于车辆在堆场海侧交换区的进出。缓冲车道位于QC作业区与堆场海侧交换区之间，既作为LAGV的临时等待区，又作为岸边与堆场之间的连接通道，以缩短水平运输距离。
与传统工艺相比，LAGV负责水平运输，堆场每个箱区海侧布置由一组支架组成的交换区，作为集装箱的临时缓冲存放点，以缓解水平运输能力与堆场装卸能力的矛盾，提高系统作业效率。然而，交接方式的灵活性增加了设备调度的复杂性，这对调度方法提出了更高要求。
码头装卸系统是一个复杂的、动态的并行工作系统，其作业类型包括将进口集装箱运输到堆场侧和将出口集装箱运输到船侧。以装船作业为例简述运作决策过程：首先，船舶进港后，码头根据船舶配载图、堆场分配计划等，制定QC分配和调度计划；然后，由ARMG从堆场指定位置提取集装箱，经缓冲支架交给指定LAGV；最后，由指定LAGV运输集装箱到指定QC。若LAGV晚到则会造成QC等待，增加船舶的在港时间。卸船过程相反。
显然，QC装卸作业、水平运输作业与堆场设备作业相互关联，必须制定统筹全局的设备协同调度计划。以往大多研究仅考虑单独装箱或卸箱作业，即使涉及QC同时装卸，也未考虑在堆场箱区混合堆存情况下如何提高调度协同性问题。这样的简化会极大地降低全局性能。因此，本文研究更一般的情形：在装卸混合模式下，船舶的进出口集装箱混合堆存在不同箱区，QC边装边卸，LAGV灵活服务多台QC且可双循环运输，同时箱区的ARMG边存边取。调度方案的优劣由两方面因素评价：（1）LAGV自身效率。为降低空驶率，将LAGV总行驶时间作为评价指标。（2）QC和ARMG的效率。集装箱船在港时间越长，其花费成本就越大，故将船舶在港时间和ARMG移动时间作为评价指标。
2自动化设备集成调度模型
2.1假设条件
（1）集港在装卸船作业之前已经完成，疏港在装卸船作业之后才进行；（2）计划期内的船舶配载计划、泊位计划、堆场箱位计划和QC调度计划已知，这里QC调度的任务以簇[14]形式定义，且簇任务内集装箱装卸顺序和簇之间的约束关系确定；（3）QC、LAGV和ARMG数量已知，且每个设备一次只处理一个集装箱；（4）LAGV、ARMG（空/重载）和QC的行驶速度及其装卸效率已知；（5）进、出口集装箱允许堆存在堆场同一箱区，每个箱区的集装箱仅由海侧ARMG负责装卸，已知LAGV与任意两个操作节点之间的距离，忽略LAGV和ARMG在堆场交换区等待支架空闲的时间。
2.2符号变量说明
常量符号如下。
K表示QC的集合，Q表示ARMG的集合，V表示LAGV的集合。ve和vd分别表示为ARMG提供初始和结束虚拟任务的虚拟QC，vs和vf分别表示为LAGV提供初始和结束虚拟任务的虛拟QC。mk表示第k台QC执行的任务数量，k∈K。（k，i）为箱任务编号，表示第k台QC 的第i个箱任务，k∈K，i=1，2，…，mk。eki和dki分别为QC在其作业区开始和结束箱任务（k，i）的事件，当箱任务（k，i）为卸船任务时其分别表示QC开始落箱到LAGV上的事件和结束落箱到LAGV上的事件，当箱任务（k，i）为装船任务时其分别表示QC从LAGV上开始提箱的事件和结束落箱到船上的事件，k∈K，i=1，2，…，mk。 Eaki表示LAGV在堆场海侧交换区开始作业箱任务（k，i）的事件，当箱任务（k，i）为卸船任务时其表示LAGV开始将箱顶升到支架的事件，当箱任务（k，i）为装船任务时其表示LAGV开始从支架处接箱的事件，k∈K，i=1，2，…，mk。Ebki表示ARMG在堆场海侧交换区开始作业箱任务（k，i）的事件，当箱任务（k，i）为卸船任务时其表示ARMG开始从支架上抓箱的事件，当箱任务（k，i）为装船任务时其表示ARMG开始放箱到支架上的事件，k∈K，i=1，2，…，mk。TC表示有先后顺序要求的事件eki的集合，TD表示卸船任务对应的事件eki的集合，TL表示装船任务对应的事件eki的集合，Nq表示第q台ARMG执行的Ebki的集合，k∈K，i=1，2，…，mk，q∈Q。
变量符号如下。ski表示第k台QC执行eki的实际准备就绪时刻，Hk（i-1）i表示第k台QC完成ek（i-1）后执行eki的全部准备时间，yki表示eki的实际发生时刻，ψki表示dki的实际发生时刻，Δwki表示eki与dki发生时刻的间隔时间，Yaki表示Eaki的发生时刻，Ybki表示Ebki的发生时刻，Ski表示eki与Eaki之间的间隔时间，ΔSki表示Eaki与Ebki之间的间隔时间，k∈K，i=1，2，…，mk。Tki，lj表示
ARMG从
Ebki发生的位置到Eblj发生的位置的纯移动时间，Rki，lj表示ARMG完成Ebki后执行Eblj需要的调整时间，k∈{ve}∪K，l∈{vd}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mve=Q。tki，lj表示LAGV从eki发生的位置到elj发生的位置耗费的时间，cki，lj表示LAGV完成eki后去执行elj需要的调整时间，rki，lj表示eki与Ealj之间LAGV的调整时间，k∈{vs}∪K，l∈{vf}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mvs=V。
决策变量如下。ki，lj为01变量，若同一辆LAGV完成eki后紧接着完成elj则其值为1，否则为0，k∈{vs}∪K，l∈{vf}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mvs=mvf=V。φki，lj为01变量，若同一台ARMG完成Ebki后紧接着完成Eblj则其值为1，否则为0，k∈{ve}∪K，l∈{vd}∪K，i∈{1，2，…，mk}，j∈{1，2，…，ml}，mve=mvd=Q。
2.3目标函数及约束
下式中，除有特殊限定外：
k，l∈K；i=1，2，…，mk；j=1，2，…，ml。
S1=min（maxk∈K ψkmk）
（1）
S2=min k∈{ve}∪K
i
l∈K∪{vd}
j（Tki，ljφki，lj）
（2）
S3=min k∈{vs}∪K i
l∈K∪{vf}
j（tki，ljφki，lj）
（3）
l∈{vf}∪K
jki，lj=1，k∈{vs}∪K
（4）
k∈{vs}∪K
iki，lj=1，l∈{vf}∪K
（5）
l∈{vd}∪K
jφki，lj=1，k∈{ve}∪K
（6）
k∈{ve}∪K
iφki，lj=1，l∈{vd}∪K
（7）
ylj-max（yki+cki，lj，slj）≥M（ki，lj-1），
k∈{vs}∪K
（8）
Yblj-（Ybki+Rki，lj）≥M（φki，lj-1），
k∈{ve}∪K
（9）
Yalj-（yki+rki，lj）≥M（ki，lj-1），
k∈{vs}∪K
（10）
yki≥ski
（11）
ski≥yk（i-1）+Hk（i-1）i， i=2，3，…，mk
（12）
yki≥Yaki+Ski，eki∈TL
（13）
Yaki≥Ybki+ΔSki，eki∈TL
（14）
Yaki≥yki+Ski，eki∈TD
（15）
Ybki≥Yaki+ΔSki，eki∈TD
（16）
Ybki-Yblj≥0，Ebki，Eblj∈Nq；yki>ylj；
eki∈TD；elj∈TL； q∈Q；
若k≠l則eki，elj∈TC
（17）
ψki-yki≥Δwki
（18）
式（1）～（3）为目标函数，分别表示最小化所有QC中最大完工时刻、最小化ARMG总移动时间、最小化LAGV的总行驶时间。式（4）～（7）表示LAGV或ARMG一次只能执行一个任务，一个任务一旦由某一ARMG或LAGV执行就不能中断，且每个任务都要被执行。式（8）和（9）表示由同一装卸运输设备执行的相邻任务的时间逻辑关系，式（8）表示同一辆LAGV完成
eki后去执行elj需要有时间cki，lj准备，以及只有LAGV到达和QC自身准备就绪，QC才能开始装卸集装箱。式（9）表示同一台ARMG完成Ebki后去执行Eblj需要有时间Rki，lj准备。式（10）表示不同作业环节的时间逻辑关系，如果任务（k，i）和（l，j）是同一辆LAGV的两个相邻任务，那么LAGV完成eki后需要时间rki，lj调整才能执行Ealj。式（11）表示eki的实际发生时刻最小为最早可能发生时刻。式（12）表示QC执行ek（i-1）后需时间Hk（i-1）i准备才能执行任务eki。式（13）和（14）表示某装船任务（k，i）的相邻作业环节间的时间逻辑关系，此类任务的设备操作顺序是ARMG—LAGV—QC，因此LAGV完成Eaki的时刻与Eaki和eki的调整时间之和不会超过QC完成eki的时刻，ARMG完成Ebki时刻与Eaki和Ebki的调整时间之和不会超过LAGV完成Eaki的时刻。同理，式（15）和（16）表示某卸船任务（k，i）的相邻作业环节间的时间逻辑关系，此类任务的设备操作顺序是QC—LAGV—ARMG。式（17）表示每一台ARMG执行QC的任务时其作业顺序在先装后卸情形下需要符合QC作业顺序和其任务约束关系。式（18）表示QC装卸每个集装箱需要时间Δwki。
值得注意的是，上述模型与已有文献相比，主要有3点不同。（1）LAU等[9]的研究将ARMG调度序列归结为QC调度序列的子序列，意味着ARMG调度必须遵从QC调度，由式（19）约束：
Yki-Ykj≥0，Ebki∈Nq；i>j；q∈Q
（19）
而本文模型考虑船舶集装箱装卸混合作业时ARMG与 QC调度的协同性，体现在将式（19）放松为式（17），表明ARMG除先装后卸情形外，可以按照灵活作业顺序操作，无须遵从QC调度序列。（2）所有类似文献均研究传统AGV工艺，在堆场箱区只有AGV与 ARMG刚性衔接，而本文针对缓冲支架系统，特别定义了Yaki和Ybki两个状态变量，增加LAGV、ARMG和支架三者之间衔接的灵活性。（3）考虑QC调度任务约束关系，由式（17）体现，以利于与QC调度模型进一步集成。
3协同调度方法及算法设计
3.1协同调度思想
传统调度方法[9]规定水平运输设备和场桥的作业序列必须遵从QC作业顺序。该方法一般适用于单装/单卸模式，而在装卸混合模式下虽然能够降低集成调度的复杂性，缩小问题解空间，但会忽略设备作业协同性，甚至会将最优解排除。
本文提出的协同调度策略的特点在于，要求水平运输设备必须遵从QC或约束关系的任务顺序，而放松ARMG与QC作业的一致性约束，除QC先装后卸作业情形外，允许ARMG自主灵活地确定作业序列，见图2。
3.2结合启发式策略的遗传算法设计
在QC作业序列的基础上，基于遗传算法，采用协同调度策略优化ARMG作业序列，并采用启发式LAGV指派策略优化车辆运输任务，见图3。
3.2.1染色体编码和解码
基于QC调度计划对箱任务采用自然数编码，每个染色体代表所有箱任务的一种随机排列，每个自然数代表箱任务编号，染色体长度等于箱任务数量。染色体序列需结合LAGV指派和ARMG调度的启发式策略进行解码，确定各ARMG及LAGV的任务顺序。
在上述编码基础上，设计ARMG调度序列的启发式策略的步骤如下：（1）从编码序列中抽取每台ARMG的任务序列，获得各台ARMG的随机箱序列；（2）针对ARMG随机任务序列中的任意两个任务，判断两个任务是否属于同一辆QC，若是则转步骤（3），否则继续寻找，直到所有的两个任务组合都寻找过一次为止；（3）判断两个任务是否是同一任务类型，若是则转步骤（2），否则判断这两个任务在QC作业序列中的作业顺序是否是先装后卸，若是则将ARMG中这两个任务的顺序调整成QC作业顺序，然后转步骤（2）。最终获得符合QC先装后卸作业约束的ARMG箱任务序列。
若在装卸混合模式下存在同箱区且在同一QC序列中先卸后装两个附近的任务，则采用上述启发式策略有利于避免各设备的串行完成，实现并行协同调度，降低过多等待，提高码头效率。
码头常以船舶在港时间最短为首要目标，因此采用如下3种基于时间型启发式规则的LAGV指派策略，逐一为任意箱任务序列中的集装箱指派合适的LAGV。LAGV完成当前运输任务后随即去执行后续任务；LAGV卸船箱任务的起始位置在QC作业区；LAGV装船箱任务的起始位置在堆场海侧交换区。（1）先到先指派策略：针对某一运输任务，选择最快完成前项任务抵达该任务起始位置的LAGV。（2）适合装箱位置就绪策略：针对某一运输任务，以起重设备作业该任务的准备就绪时刻（若装船，则是ARMG准备就绪时刻；若卸船，则是QC准备就绪时刻）为基准，从所有车辆中选择完成前项任务后最早抵达该任务起始位置的LAGV。（3）适合QC就绪策略：针对某一运输任务，以QC就绪时刻为基准，从所有车辆中选择完成前项任务后最早空驶（卸船箱）或提箱（装船箱）至QC作业区的LAGV。
3.2.2不可行和重复序列的修正策略
随机生成或迭代更新的染色体可能存在不可行或重復个体的情况，故需进行修正。针对不可行序列的修正策略：将箱任务序列满足已知QC作业箱任务顺序及簇任务约束关系。针对种群中重复序列的修正策略：搜寻每代的重复个体，并采用部分逆反变异操作生成新的个体替换原染色体，得到新的种群作为下一代。这样不仅降低重复个体存在的概率，而且保持了种群多样性。
3.2.3染色体选择、交叉、变异操作
采用轮盘赌的方法对染色体进行选择；采用部分匹配交叉（图4）和部分逆反变异（图5）的方法对染色体进行交叉、变异操作。
3.2.4适应度函数设置
以最小化箱任务最大结束时刻为首要目标，并通过设置加权系数，将适应度函数设计为一种组合函数，其由箱任务最大结束时刻、QC累计等待时间、每台QC的箱任务均衡程度、LAGV的总行驶时间和ARMG总移动时间组成。鉴于最小化问题，将适应度函数设为上述组合函数的倒数，具体计算取决于箱任务的LAGV指派以及各设备之间的交接时刻，状态更新流程图见图6。
4案例验证与结果分析
4.1案例说明
以采用“双车QC+ LAGV+ ARMG”工艺系统的青岛某自动化集装箱码头为例，码头整体布局和水平运输交通规则见图1。LAGV所在的QC作业区共7条行车道，每条车道宽4 m，其中4条为装卸车道，3条为穿越车道，装卸车道成对布置，并与穿越车道相间隔。堆场海侧行驶区共有6条双向车道，且相邻车道行驶方向相反。各装卸运输设备的速度见表1。
某船需要装卸的进出口集装箱在船上的位置及簇任务划分和约束关系可通过船舶配载计划获得。假设QC调度计划已知，QC抓/放箱操作时间均为10 s，QC小车在QC作业区与船之间的水平行驶时间为40 s，且在QC作业区车道上的行驶方向为逆时针方向；ARMG初始位置在堆场海侧交换区（包含4个缓冲支架和1个空车道），堆场数量为10个，每个堆场仅海侧ARMG工作；LAGV初始位置在缓冲车道，各设备完成各自所有任务后必须回到初始位置。
考虑算法运算效率，通过多次组合试验确定算法相关参数。初始种群大小为50，最大遗传代数为100，交叉概率为0.85，变异概率为0.1。本文试验均采用MATLAB R2014a编程实现算法，并在Intel（R） Core（TM） i76700HQ CPU @2.6 GHz处理器、8 GB内存的电脑上运行得到试验结果。
4.2协同调度求解结果分析
4.2.1算法的优化性能分析及鲁棒性分析
设计7组中等规模仿真算例，从计算时间和结果进行比较，验证所提算法的优化性能。采用CPLEX 12.2求解器和遗传算法分别求解算例。在CPLEX求解过程中，将模型的非线性约束式（8）划分成2个线性约束，结果见表2。表2中最后一列显示了采用本文算法得到的加权目标函数值与最优值之间的偏差。试验发现，计算耗时随着任务数的增加快速上升，对30个以上的箱任务问题无法在有效时间内得到结果，而用遗传算法尽管不能获得最优解，但其解与最优解的偏差在适当范围内，且在大规模任务的计算效率上具有优势。
不同任务规模和LAGV数量下算法的鲁棒性变化如图7所示：鲁棒性指标在适当范围（0～4%）内波动，其最大值为3.90%，平均值为2.47%，说明算法有较好的鲁棒性。
4.2.2结果比较分析
根据设置的案例数据，采用结合启发
式策略的遗传算法对自动化设备协同调度模型进行求解。试验选择2个因素作为变量：LAGV数量，设置在8与24之间；每个计划期内的任务规模，设置成40、50、60、70和80。所需其他数据（如LAGV初始位置、集装箱类型及其在堆场中的位置）均采用随机模拟方式产生。因此，不同变量因素下有多种组合，每种组合随机产生10组数据，每组数据重复试验操作5次，取其平均值来减少算法误差。
4.2.2.1协同调度方法的比较分析
為分析系统性能的灵敏性，将LAGV数量和每个计划期内的任务规模作为变化因素，得到不同调度方法的结果，见图8。在给定LAGV数量的情况下，2种调度方法的加权目标函数值均随着任务规模的增加而增加，但平均每个任务的加权目标函数值在下降。这表明任务规模变大时系统将获得更好的性能。但实际上，由于码头各种中断事件的发生，如起重机或LAGV等设备故障，不可避免地需要进行再调度。因此，可结合实际情况，选取一个适当的任务规模以权衡计算量和系统性能的损失。在给定任务规模和LAGV数量的情况下，本文提出的协同调度方法的加权目标函数值小于传统调度方法的加权目标函数值。这表明，在码头实际管理中，充分优化ARMG作业序列有助于提高其与QC和LAGV之间的协调性，达到系统整体性能平均8.7%的提升。
4.2.2.2不同LAGV指派策略比较分析
图9为不同LAGV指派策略对整体调度结果的影响。在3种LAGV指派策略下，随着LAGV数量的增多平均每个任务的加权目标函数值均在下降。图9中的数据表明，不同的LAGV指派策略无绝对的优劣，不同的策略适合不同的设备配置比例。由此可见，在码头实际管理中，根据设备配置比例合理利用不同LAGV指派策略比利用单一LAGV指派策略效果更好，更有助于码头整体效率的提升。
图10为不同LAGV指派策略对QC等待时间的影响。在LAGV和QC配置比例较小时：LAGV本属于瓶颈资源，采用先到先指派策略更易造成无效等待，从而加剧水平运输设备的紧缺性，最终导致其他QC过多等待；采用适合QC就绪策略，即始终选择适合的QC，有助于减少QC等待时间。因此，在此情形下采用适合QC就绪策略的效果优于采用适合装箱位置就绪策略的效果。在LAGV和QC配置比例较大时，这两种策略对QC等待时间的影响无明显差异。
图11为不同LAGV指派策略对ARMG移动时间的影响。在LAGV和QC配置比例较小时，LAGV本属于瓶颈资源，采用先到先指派策略和适合装箱位置就绪策略更易导致LAGV等待发生，从而加剧水平运输运力的紧张，导致其他ARMG过多等待，进而影响到ARMG的调度序列，使得重进重出比例下降，因此此时采用适合QC就绪策略效果较好。在LAGV与QC配置比例较大时，QC和ARMG效率成为关键，而采用先到先指派策略有助于减少LAGV空驶率，从而提升运力，最终配合ARMG优
化作业序列，降低移动时间，因此此时先到先指派策略优于适合装箱位置就绪策略。
图12为不同LAGV指派策略对LAGV行驶时间的影响。采用先到先指派策略，即选择最早到达的、最近的LAGV有利于减少空驶率，从而更有利于降低LAGV行驶成本。相对于适合装箱位置就绪策略，适合QC就绪策略的目的在于减少无效等待时间，故空驶率不会太高；相对于先到先指派策略，适合QC就绪策略用在卸箱任务时容易产生较高空驶率，且用于装船任务时更倾向于选择无效时间最短的车辆，故空驶率较高。总之，从车辆行驶成本看，适合QC就绪策略是3种指派策略中的一个折中策略，其目的在于优化QC等待时间。因此，如图12所示，该策略下的曲线变化平缓，且位于其他两种策
略对应的曲线之间。
5结束语
码头设备的协同调度有利于减少船舶在港时间，提高码头整体作业效率。本文在以往研究的基础上构建新的协同调度模型并设计改进的遗传算法进行求解，其创新之处在于：考虑了LAGV结合具有有限堆场缓存空间的自动化集装箱码头装卸新工艺的作业特点；考虑了装卸混合模式下设备调度的协同性；引入了QC调度的主要约束。最终通过数值试验与传统调度方法的对比验证了本文模型和算法的有效性。
参考文献：
[1]
CAO Jinxin， SHI Qixin， LEE DerHorng. Integrated quay crane and yard truck schedule problem in container terminals[J]. Tsinghua Science & Technology， 2010， 15（4）： 467474.
[2]CAO Jinxin， LEE DerHorng， CHEN Jianghang， et al. The integrated yard truck and yard crane scheduling problem： Benders decompositionbased methods[J]. Transportation Research Part E： Logistic & Transportation Review， 2010， 46（3）： 344353.
[3]秦天保， 彭嘉瑶， 沙梅. 带任务顺序约束的岸桥集卡集成调度约束规划模型[J]. 上海海事大学学报， 2013， 34（3）： 17.
[4]CHEN Lu， LANGEVIN A， LU Zhiqiang. Integrated scheduling of crane handling and truck transportation in a maritime container terminal[J]. European Journal of Operational Research， 2013， 225（1）： 142152.
[5]韩晓龙， 牟少莉. 基于CHC算法的集卡与岸桥协调调度优化问题[J]. 武汉理工大学学报（信息与管理工程版）， 2014， 36（2）： 233236.
[6]TANG Lixin， ZHAO Jiao， LIU Jiyin. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research， 2014， 236（3）： 978990.
[7]HE Junliang， HUANG Youfang， YAN Wei， et al. Integrated internal truck， yard crane and quay crane scheduling in a container terminal considering energy consumption[J]. Expert Systems with Applications， 2015， 42（5）： 24642487.
[8]MEERSMANS P J M， WAGELMANS A P M. Effective algorithms for integrated scheduling of handling equipment at automated container terminals[R]. Rotterdam： Erasmus University， 2001.
[9]LAU H Y K， ZHAO Ying. Integrated scheduling of handling equipment at automated container terminals[J]. Annals of Operations Research， 2008， 112（2）： 665682.
[10]HOMAYOUNI S M， HONG T S， ISMAIL N， et al. A genetic algorithm for optimization of simultaneous scheduling of AGVs and QCs in container terminals[C/OL]//11th Asia Pacific Industrial Engineering and Management System. Melaka， Malaysia， December 710， 2010. http：//www.apiems.org/archive/apiems2010/paper.php.
[11]DKHIL H， YASSINE A， CHABCHOUB H. Optimization of container handling systems in automated maritime terminal[J]. Studies in Computational Intelligence， 2013， 457： 301312.
[12]LUO Jiabin， WU Yue. Modelling of dualcycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E： Logistics & Transportation Review， 2015， 79： 4964.
[13]LUO Jiabin， WU Yue， MENDES A B. Modelling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal[J]. Computers & Industrial Engineering， 2016， 94： 3244.
[14]BIERWIRTH C， MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research， 2010， 202（3）： 615627.
（編辑赵勉）
