自动化码头起重机和自带提升功能的AGV的集成调度
添玉 +王建彬 +范会方
摘要：为深入研究新工艺带来的自动化码头设备集成调度问题，针对自动化码头的一种自带提升功能的自动导引小车（LAGV）和缓冲支架系统，提出新的设备集成调度框架。考虑不同设备之间的相互关联和制约的协同关系，将岸桥分配调度与LAGV、场桥调度分开，合理定义两种任务（两个问题）的划分方式，建立两个多目标混合整数规划模型。设计一种具有内外层关联的适应度函数的双层遗传算法。相对传统联合调度算法，该算法平衡了计算复杂性与调度均衡性。最后的数值试验证明了模型和算法的有效性。从岸桥数量、任务规模、AGV数量和调度策略等对岸桥等待时间的影响上，对采用LAGV的系统和采用传统AGV的系统进行比较，为自动化码头装卸作业调度提供决策支持。
关键词：
自动化码头； 自动导引小车（AGV）； 集成调度； 遗传算法（GA）； 启发式策略
中图分类号： U691.3
文献标志码： A
Integrated scheduling of cranes and AGVs with lifting function in automated container terminals
TIAN Yu1， WANG Jianbin1， FANG Huifang2
（1. Logistics Engineering College， Shanghai Maritime University， Shanghai 201306， China；
2. Software Automation Department， ZPMC Electric， Shanghai 200125， China）
Abstract：
In order to further study the issue of integrated equipment scheduling caused by new techniques in automated terminals for automated guided vehicles with lifting platforms （called LAGV） and buffer support system in automated terminal， a new integrated scheduling framework is proposed. Considering the interrelated and constrained cooperativeness relations among different equipments， it is divided into two problems， the quay crane allocation/scheduling problem and the LAGV and yard crane scheduling problem. By reasonably defining the division of two tasks （two problems）， two multiobjective mixedinteger programming models are established sequentially. A twolayer genetic algorithm is developed， where a fitness function is proposed to interlink two layers. The algorithm leads to the tradeoff between the computational complexity and the scheduling equilibrium compared with traditional joint scheduling algorithms. A numerical test is carried out in order to evaluate the performance of the model and algorithm. The system adopting LAGVs is compared with the system adopting traditional AGVs through investigating the influence of the number of quay cranes， the scale of tasks and the number & scheduling strategies of AGVs on the waiting time of quay cranes. The results provide decision support for automated terminal handling operations.
Key words：
automated terminal； Automated Guided Vehicle （AGV）； integrated scheduling； Genetic Algorithm （GA）； heuristic strategy
0引言
在新的全球經济格局下，如何提高集装箱码头运作效率成为当前码头发展亟待解决的问题。而在码头实际作业过程中，码头整体作业效率的提升依赖于岸桥、水平运输车辆、场桥等主要设备的密切协作与合理调度。因此，码头设备调度问题成为当前研究的热点。
目前，国内外专家对集装箱码头优化调度问题已经做了大量的研究。文献[13]仅研究码头单个环节调度，通过模型构建、算法设计及案例分析研究码头设备调度问题，但未考虑码头多个环节之间的相互影响。文献[49]在研究集装箱码头设备调度问题时，考虑了多环节作业之间的相互作用和制约，建立了多类型设备集成调度模型。码头新工艺的出现对调度问题产生了很大影响，文献[1012]针对码头新工艺下的设备调度问题，采用构建模型、仿真模型及实验分析等方法进行研究。
当前的研究主要针对码头一种或两种设备的联合调度，且大多数集中在传统码头领域，缺乏将不同新工艺用于码头设备集成调度的深入研究。本文建立岸桥（QC）、自带提升功能的自动导引小车（LAGV）和支架、自动化场桥（AYC）集成调度混合整数规划模型，并设计双层遗传算法对问题进行求解。
1问题描述
图1展示了自动化码头的一种新工艺布局，其装卸运输系统由4部分组成：QC，LAGV，缓冲支架以及AYC。QC负责船舶装卸，LAGV负责水平运输，AYC负责场区的存/取操作。作为连接水平运输和堆场操作的柔性机制，缓冲支架减少水平运输设备和自动化轨道吊相互等待时间，缓解水平运输能力与自动化轨道吊装卸堆放能力之间的矛盾，提高系统作业效率，但也增加了设备调度复杂性。
考虑任务执行过程中各装卸环节的衔接以及各装卸设备之间存在时空非同步性影响，分析码头装卸作业调度系统，可知各子环节调度存在目标冲突、
装卸资源请求冲突、响应结果冲突。因此，QC调度问题、水平运输调度问题、AYC调度问题相互影响、紧密关联，必须在有效解决上述冲突的情况下合理协调各种调度决策才能达到最优的整体运作效果。
2集成调度模型
2.1调度框架
对于集装箱装卸任务的划分，BIERWIRTH等[13]将其分为5种：①基于贝位区域；②基于单个贝位；③基于堆垛的任务；④基于集装箱簇；⑤基于单个集装箱。
定义两层调度子问题的不同任务划分方式：上层采用集装箱簇作为任务定义，既避免由于基于单个集装箱任务定义导致的QC各种十分复杂的干扰约束的出现，和任务量的庞大造成求解时间和空间复杂度指数性增加，又不会因任务定义太大而导致QC作业难以均衡；下层是AGV和场桥的调度，采用基于单个集装箱的任务定义，有利于AGV运输的灵活性和场桥重进重出的高效率，也便于与上层进行任务单位的衔接。
如图2所示，设备集成调度框架是在已知船舶配载计划、QC属性、任务属性的情况下，通过基于簇任务的QC分配与调度模型求解各QC的箱任务序列，为基于箱任务序列的自动化设备集成调度模型提供一定的输入条件，而将后者求解出的箱任务结束时刻反馈给前者，作为QC调度的评估，不断重复该逻辑，最后得到各设备的最優任务序列。
2.2基于簇任务的QC分配与调度模型
2.2.1假设条件
（1）计划期内船舶泊位计划已知，船舶上贝位连续分布，且每个贝位在岸线方向上的长度相同；
（2）每个集装箱簇任务所在贝位、作业类型、最短理想作业时间、先后作业顺序、簇内集装箱的作业顺序均已知；
（3）单船设有同时作业最多和最少QC数；
（4）所有QC在同一轨道上水平匀速移动且不能跨越作业，相邻QC之间满足安全距离要求。
2.2.2符号说明
K为QC的集合，K={1，2，…，k，…，C}；T为计划期内时间段的集合，T={1，2，…，t，…，P}；Ω为所有簇任务集合，Ω={1，2，…，n，…，N}，用m表示同台QC上任务n的前任务；ψ为不能同时作业的簇任务集合；Φ为有作业先后顺序要求的簇任务集合；Rmin和Rmax分别表示为船舶分配的最少和最多QC数；Ta为船舶到达时刻；Tb为船舶靠泊时刻；Tn为簇任务n的理想最短作业时间；ln为簇任务n的位置，用贝位编号表示；Δl为相邻QC的安全距离，用间隔贝位数表示，通常为一个贝位；vk为第k台QC的水平移动速度，m/min，k∈K；M为一个充分大的正整数；Ts和Te分别表示船舶开始作业和结束作业时刻；Tsn，Ten分别为簇任务n的真实开始时刻和结束时刻，Tsn为簇任务n的允许作业时刻；ckn为第k台QC服务簇任务n后的空闲时刻，每次任务完成后立即更新；lkn为第k台QC完成簇任务n时位于码头岸线上的位置，每次任务完成后立即更新；δkn为第k台QC为完成簇任务n移动到合适位置所需的时间；xtk为01变量，若第t时段有第k台QC为船舶进行装卸作业，则为1，否则为0；ztkn为01变量，若第t时段有第k台QC为簇任务n作业，则为1，否则为0；fn1n2为01变量，若簇任务n2开始作业时，簇任务n1已经完成，则为1，否则为0，n1，n2∈Ω。
2.2.3目标函数
（1）最小化船舶在港时间
S1=min（Te-Ta）=min（（Te-Ts）+（Ts-Ta））
其中：Te-Ts表示船舶的装卸作业时间；Ts-Ta表示船舶的等待作业时间，包含等待泊位时间和等待岸桥时间。
（2）最小化QC移动距离
S2=min knztkn·vk·δkn=
min knT（ztkn（|lkn-lkn′|+
k′|ln-（k-k′）Δl-l′k′n′|））
当进行装卸作业时，QC的状态是不断变化的，当第k台QC对船舶上的簇任务n进行作业时，其位置和再次空闲时刻需要更新：
lkn=ztknln
ckn=ztknTen
由于QC不能跨越作业，某QC k′可能会因为其他作业需要而被迫移动，其位置和空闲时间更新如下：
l′kn=ztkn（ln-（k-k′）Δl）
c′kn=ztkn（c′kn′+ln-（k-k′）Δl-l′k′n′/vk）
2.2.4约束条件
Ts≥Tb （1）
Te≥max（Ten），n∈Ω （2）
Rmin≤kxtk≤Rmax，t∈T （3）
nztkn=xtk，t∈T；k∈K；n∈Ω （4）
tkztkn≥Tn，n∈Ω （5）
zt1k1n+zt2k2n=1，t1，t2∈{Tsn，…，Ten}；
k1，k2∈K，k1≠k2； n∈Ω （6）
Tsn≥max{（ckm+δkn）ztkn，Tsn}，
t∈T；k∈K；m，n∈Ω （7）
Ten≥Tsn+Tn，n∈Ω （8）
fn1n2+fn2n1=1，（n1，n2）∈ψ （9）
Ten1-Tsn2≤0，（n1，n2）∈Φ （10）
Ten1≤Tsn2+M（1-zt1kn1zt2kn2fn1n2），
t1，t2∈T； k∈K； n1，n2∈Ω （11）
（lk2n2-lk1n1）（ln2-ln1）ztk1n1ztk2n2≥0 （12）
xt，k-1+xt，k+1-xt，k={-1，0，1}，
t∈T； k-1，k，k+1∈K （13）
式（1）表示船舶的开始作业时刻必须大于其靠泊时刻。式（2）表示所有簇任务作业完成时间即为船舶结束作业的时间。式（3）表示每个时刻为船舶服务的船舶数量在一定范围内。式（4）表示在单位时间内一台QC只能为一个任务服务。式（5）表示每个簇任务都配置了相应的QC作业，并且QC作业时间应满足簇任务所需的装卸作业时间要求。式（6）表示有且仅有一台QC为簇任务n服务。式（7）表示簇任务n的开始作业时刻。式（8）表示簇任务n的作业结束时刻。式（9）表示对不能同时作业的簇任务的限定。式（10）表示有先后顺序的簇任务在时间上的关系。式（11）表示两个簇任务由同一台QC服务时，其作业时间需要满足的关系。式（12）表示QC不能在同一船舶的两个作业之间交叉作业。式（13）表示任意时间若有多台QC为该船舶服务，则QC必须连续，即满足QC不能跨越原则。
2.3基于箱任务序列的自动化设备集成调度模型
2.3.1假设条件
（1）集港在装卸船作业过程之前已经完成，疏港在装卸船作业过程之后进行。
（2）通过QC调度模型得到每台QC所负责的簇任务和箱任务序列。
（3）调度计划期内，已知每个箱任务操作类型（装/卸），在船上和堆场的装卸位置。
（4）QC，LAGV和AYC的可用数量已知，且每个设备一次只處理一个集装箱。
（5）LAGV，AYC空/重载和QC的速度以及各个设备的装卸效率。
（6）每个堆场箱区仅岸侧AYC负责装卸船；不考虑LAGV堵塞情况；已知LAGV和AYC在任何两个操作节点位置之间的距离。
2.3.2符号变量说明
ve和vd分别表示提供AYC初始和结束虚拟任务的虚拟岸桥。vs和vf分别表示提供LAGV初始和结束虚拟任务的虚拟岸桥。Q为AYC的集合。V为LAGV的集合。P为堆场岸侧交换区的集合。mk为第k台QC执行的任务数量，k∈K。eki为QC在作业区开始作业箱任务（k，i）事件，当箱任务（k，i）为卸船任务时，表示QC开始放箱到LAGV；当箱任务（k，i）为装船任务时，表示QC开始从LAGV上抓箱；（k，i）为箱任务编号，代表第k台QC的第i个箱任务，k∈K，i=1，…，mk。Eaki为LAGV在堆场岸侧交换区开始作业箱任务（k，i）事件，当箱任务（k，i）为卸船任务时，表示LAGV开始将其顶升到支架；当箱任务（k，i）为装船任务时，表示LAGV开始从支架处接箱，k∈K。Ebki为AYC在堆场岸侧交换区开始作业箱任务（k，i）事件，当箱任务（k，i）为卸船任务时，表示AYC开始从支架上抓箱；当箱任务（k，i）为装船任务时，表示AYC开始放箱到支架，k∈K。TL为装船任务的事件eki的集合，k∈K，即eki∈TL。TD为卸船任务的事件eki的集合，k∈K，即eki∈TD。TC为事件eki集合中有先后顺序要求的任务集合，k∈K，即eki∈TC。Nq为第q台AYC执行Ebki的集合，k∈K，q∈Q。Np为第p个堆场岸侧交换区事件Eaki的集合，k∈K，p∈P。ski为第k台QC执行事件eki的实际准备就绪时刻，k∈K。Hkik（i-1）为第k台QC完成ek（i-1）后执行eki的全部准备时间，k∈K，i≠1。yki为事件eki的实际发生时刻，k∈K。Yaki为事件Eaki的发生时刻，k∈K。Ybki为事件Ebki的发生时刻，k∈K。Tljki为从Ebki发生的位置到Eblj发生的位置之间AYC的纯移动时间，k∈{ve}∪K，l∈{vd}∪K，j=1，…，ml，mve=mvd=|Q|。Gljki表示AYC完成Ebki后执行Eblj需要调整的时间，k∈{ve}∪K，l∈{vd}∪K。 tljki为从eki发生的位置到elj发生的位置LAGV的纯运行时间，k∈{vs}∪K，l∈{vf}∪K，mvs=mvf=|V|。cljki为LAGV完成eki后去完成elj的调整时间，k∈{vs}∪K，l∈{vf}∪K。Sljki为eki与Ealj两个事件间的调整时间，k∈{vs}∪K，l∈{vf}∪K。Ski为eki与Eaki两个事件间的调整时间，k∈K。ΔSki为Eaki与Ebki两个事件间的间隔时间，k∈K。ljki为01变量，若同一辆LAGV完成eki后紧接着完成elj，则其值为1，否则为0，k∈{vs}∪K，l∈{vf}∪K。φljki为01变量，若同一台AYC完成Ebki后紧接着完成Eblj，则其值为1，否则为0，k∈{ve}∪K，l∈{vd}∪K。
2.3.3目标函数及约束
i=1，…，mk；j=1，…，ml
S3=min k∈Kmki=1（yki-ski）+ （14）
S4=min k∈{ve}∪Kmki=1l∈K∪{vd}mlj=1Tljkiφljki （15）
S5=min k∈{vs}∪Kmki=1l∈K∪{vf}mlj=1tljkiljki （16）
l∈{vf}∪Kmlj=1ljki=1，k∈{vs}∪K
（17）
k∈{vs}∪Kmki=1ljki=1，l∈{vf}∪K
（18）
l∈{vd}∪Kmlj=1φljki=1，k∈{ve}∪K
（19）
k∈{ve}∪Kmki=1φljki=1，l∈{vd}∪K
（20）
ylj-max（yki+cljki，slj）≥M（ljki-1），
k∈{vs}∪K；l∈K
（21）
Yblj-（Ybki+Gljki）≥M（φljki-1），
k∈{ve}∪K；l∈K
Yalj-（yki+Sljki）≥M（ljki-1），
（22）
k∈{vs}∪K；l∈K （23）
yki-yk（i-1）≥ski-sk（i-1），k∈K；i≠1 （24）
yki≥ski，k∈K （25）
ski≥yk（i-1）+Hkik（i-1），k∈K；i≠1 （26）
yki≥Yaki+Ski，eki∈TL；k∈K （27）
Yaki≥Ybki+ΔSki，eki∈TL；k∈K （28）
Yaki≥yki+Ski，eki∈TD；k∈K （29）
Ybki≥Yaki+ΔSki，eki∈TD；k∈K （30）
Ybki-Ybkj≥0，
Ebki，Ebkj∈Nq；k∈K；
i>j；q∈Q （31）
Ybki-Yblj≥0，Ebki，Eblj∈Nq；k，l∈K；
eki，elj∈TC；yki>ylj；q∈Q （32）
式（14）～（16）为目标函数，分别表示最小化QC延迟时间、最小化AYC总移动时间、最小化LAGV的总运行时间。式（17）～（20）表示LAGV或AYC一次只能执行一个任务，一个任务一旦由某个AYC或LAGV执行就不能中断，且每个任务都要被执行。式（21）和（22）表示由同一装卸运输设备执行的相邻任务的时间逻辑关系，式（21）表示同一辆LAGV完成eki后去执行elj需要有时间cljki准备及岸桥时间准备，式（22）表示同一台AYC完成Ebki后去执行Eblj需要有时间tljki准备。式（23）表示作业不同环节的时间逻辑关系，如果任务（k，i）和（l，j）是同一辆LAGV的两个相邻任务，那么LAGV完成eki后需要时间Sljki调整去完成Eblj。式（24）表示同一台QC执行相邻任务的调整时间应满足QC执行所需作业的时间。式（25）表示eki的实际发生时刻最小为最早可能发生时刻。式（26）表示QC执行ek（i-1）后需时间Hkik（i-1）准备才能执行任务eki。式（27）和（28）表示对于同一装船任务（k，i），作业相邻环节的时间逻辑关系，此类任务的设备操作顺序是：AYC→LAGV→QC，因此AYC完成Ebki时刻与Eaki和Ebki的调整时间之和不会超过LAGV完成Eaki的时刻，LAGV完成Eaki的时刻与Eaki和eki的调整时间之和不会超過QC完成eki的时刻。同理，式（29）和（30）表示对于同一卸船任务（k，i），其作业相邻环节的时间逻辑关系。此类任务的设备操作顺序是：QC→LAGV→AYC。式（31）表示每台AYC的任务执行顺序需要符合QC任务序列中的顺序。式（32） 表示每台AYC执行具有约束关系的任务必须符合它们的先后顺序。
3双层多目标遗传算法设计
上述模型中的调度子问题均为NP难问题，本文设计双层多目标遗传算法求解：外层优化QC簇任务作业序列；内层基于外层的QC箱任务序列优化LAGV和AYC的任务序列，然后计算相关的评价指标值并将其反馈到外层，作为外层染色体的评价准则；通过内外层遗传算法的协调确定最优的集成调度方案。其算法流程见图3。
3.1染色体编码
主要考虑两个位串编码，外层位串表示QC分配调度的簇任务序列， 内层位串表示LAGV和AYC调度中的箱任务序列；内外层均采用自然数对染色体编码，每个染色体代表所有任务的一个随机排列，每个自然数代表任务编号，染色体长度等于任务数量。
3.2不可行和重复序列的修正策略
随机生成或迭代更新的染色体可能存在不可行或重复个体的情况，因此需进行修正。
针对不可行序列的修正策略：外层簇任务序列根据不同时、有先后关系的簇任务约束进行染色体的修正；而内层遗传算法是在外层遗传算法获得的可行QC的作业序列的基础上进行的，因此内层箱任务序列需要与外层所得的QC作业箱任务序列一致。
步骤1按外层算法所得的每个QC作业箱任务序列修正随机产生的箱任务序列，得到符合每个QC作业序列的箱任务序列。
步骤2按簇任务约束关系来修正箱任务顺序。根据QC调度序列，不同时、有先后关系的簇任务若由同一台QC完成，那么已经在步骤1中修正。若它们不由同一台QC完成，则应修正编码使其满足约束关系。采取下列方式修正：
①对先后顺序关系簇任务集合，直接按先后顺序展开组成箱任务序列，找到其箱序列编码中的位置直接替换；
②对不同时的簇任务集合，先找出其在簇序列中的先后位置，并按位置先后展开组成箱任务序列，再找其在箱序列编码中的位置并替换。
步骤3重复上述两步修复策略，直到新的箱任务序列不再变化为止。
对种群中重复序列的修正策略：由于算法内外层任务均采取统一编码方式，在种群中会不可避免地产生重复的个体，不利于算法收敛精度，因此搜寻每代的重复个体，并采用部分逆反变异操作生成新的个体替换原染色体，得到新的种群作为下一代。这样不仅能降低重复个体存在的概率，而且能保持种群多样性。
3.3集成调度的启发式策略
本文算法设计思想是将遗传算法与有效的启发式策略相结合，将由内外层编码得到的可行序列作为任务选择QC或AGV，AYC的顺序，依此顺序采用下面的QC调度策略和AGV，AYC调度策略，逐一为当前任务分配合适的设备，直到所有任务完成分配。
QC调度策略见图4。
QC调度策略的具体步骤如下：
步骤1初始化船舶开始作业时刻（即靠泊时刻），QC的位置和可用时间，簇任务在船上的贝位、任务量和相关约束。
步骤2若可用QC数大于或等于船舶作业QC最小数，则随机选择一组连续的QC分配给船舶，转步骤3；否则推迟船舶开始作业时刻。
步骤3考虑QC和任务属性，逐一为簇任务n分配作业QC。首先检查簇任务n左右两侧距其最近的QC，若需要等待时间相同则优先选择距离更近的QC，若需要等待时间不同则选择等待时间较短的QC，并更新簇任务n的开始作业和结束作业时刻以及QC位置和再次空闲时刻。
步骤4如此循环执行步骤3，为簇任务n+1分配QC，直到为所有簇任务分配QC完毕，得到QC分配和调度簇任务序列。
AYC调度策略：在给定QC作业箱任务顺序后，AYC的作业序列与QC作业序列一致。
LAGV调度策略：根据箱任务序列对LAGV进行运输任务指派，采用以下启发式规则对LAGV进行调度：①遵循QC作业顺序优先原则；②先到先指派。
3.4适应值函数选择
适应值函数由目标函数加权和的倒数确定。外层为船舶在港时间（箱任务最大完成时刻）与QC移动距离的归一化加权和倒数；内层为箱任务最迟结束时刻、每台QC的箱任务均衡程度、QC总延迟时间、LAGV的总运行时间和AYC总移动时间的归一化加权和倒数。
3.5选择、交叉、变异
采用轮盘赌方法对染色体进行选择；采用部分匹配交叉（图5）和部分逆反变异（图6）的方法对染色体进行操作。
4算例分析
4.1案例说明
以采用新工艺的青岛某自动化码头为例。该码头总岸线长2 088 m，每个40英尺集装箱贝位在岸线上跨度为12 m，码头共有7台QC可供分配，假定QC初始位置均匀分布于码头岸线上。堆场采用垂直岸线布置，本案例涉及8个箱区，每个箱区配备两台AYC，岸侧场桥负责装卸船的存取箱，陆侧场桥负责配合外部集卡集疏港，各箱区岸侧均设置一组支架的交换区。设置支架数量为5条，并预留一条无支架装卸车道。水平交通组织中的各类车道数量和宽度是根据QC后伸距以及LAGV参数设定的，车道布局见图7。QC下装卸车道为单行道，行车方向是依据船头朝向和装卸箱量的比例设定的，以减少倒箱门现象对车辆和道路的干扰。缓冲车道允许双向行驶，以缩短车辆在岸边与堆场之间的运行距离；高速相邻车道行驶方向相反，便于车辆在箱区岸侧交换区的进出，水平交通规则见图7。
假设各AYC和LAGV初始位置均设置在各箱区支架交换区。各设备完成其所有作业后回到初始位置，各装卸运输设备参数见表1。QC平均作业效率每小时不低于36个循环，假设QC抓/放箱操作时间均为10 s，QC小车在QC交换区与船舶之间的平均水平运行时间为40 s。某艘船停靠在距岸线100 m处，靠泊时刻为计划期的第60 min，随机生成该船需要裝卸作业的簇任务以及箱任务，包括任务数量、在船上和堆场中的位置、各任务之间不同时、
有先后顺序等的约束关系。
4.2试验分析
本文算法采用MATLAB R2012b编程实现，并在Intel（R） Core（TM） 2Quad CPU Q9500 @2.83 GHz处理器，RAM 2GB电脑上运行。通过多次初步试验确定有关的参数：（1）外层。种群大小50；最大遗传代数100；交叉概率0.85；变异概率0.10。（2）内层。种群大小50；最大遗传代数100；交叉概率0.80；变异概率0.05。
为了评估新工艺的集成调度模型和算法，首先设计8组中等规模仿真算例验证所提算法的性能。为实现建模与算法的分离，将模型的非线性约束转换成线性约束，采用MATLAB中的YALMIP工具箱结合CPLEX12.2求解器，求解QC调度模型，其中计划期的时间单位设置成所有簇任务的装卸时间需求最小值，再根据QC调度结果求解自动化设备集成调度模型。表2最后一列显示了本文算法的加权目标函数值与最优值之间的偏差。试验发现，CPLEX的计算耗时随着任务数的增加快速上升，30个以上箱任务的问题无法在有效的时间内得到结果（最后两组算例的时间都超过了4 h），而双层遗传算法尽管不能获得最优解，但在大规模任务的计算效率上具有优势。
为分析系统的灵敏性，选取LAGV数和计划期长度（任务数）作为变化因素，试验结果见图8。可以看出，在给定LAGV数的条件下，加权目标函数值随着计划期长度的增加而增加，但任务的平均值在下降。这表明，计划期越长，系统越能获得更好的性能。然而计算更多任务数将花费更多时间。在实际中，由于码头各种中断事件的发生，如起重机或AGV等设备故障，会不可避免地需要进行再调度。因此，可以结合实际情况，选取一个适当的计划期以权衡计算量和系统性能的损失。此外，在给定计划期的条件下，LAGV数会影响系统性能，特别是对某具体算例，存在最优的数量配置。决定加权目标函数值变化的因素除LAGV数外，还包括任务的信息及其在QC上的序列。
为分析集成调度的效果，采用双层遗传算法，模拟3台QC，8辆LAGV，8台AYC，10个簇任务，44个装卸箱任务条件下各设备作业序列的优化。图9呈现了QC理想调度（QC无等待）与集成调度得到的各QC任务的开始和结束时刻（图9a）中矩形块为簇任务编号，图9b）中矩形块为箱任务编号）。
图9a）显示在集成调度的情况下，各QC作业比较均衡并均存在等待，说明LAGV和AYC的调度影响了QC调度结果；较单环节调度，集成调度协调了各环节之间的冲突，对码头资源整合有重要借鉴作用。图9b）显示QC累积等待时间在各QC之间分
配的非均衡性，因为LAGV和AYC的调度目标之一是在最小化船舶在港时间的情况下使各QC任务完成时间尽量均衡，减少任务多的QC的作业延迟。
选择3种变化因素对比在新工艺“LAGV+支架”与传统AGV工艺下集成调度的结果。第1个因素是QC数量，设定为2，3，4；第2个因素是簇任务规模，设定为3，5，7，10；第3个因素是水平运输设备的数量，设定为4，8，12，18，24，44。此外，比较了两种常见LAGV调度策略的影响。每种组合试验次数为10次，试验结果见图10。
a）QC
b）任务
c）水平运输设备
d）调度策略
由图10a）可知：当QC和（L）AGV的配置比例增大时，采用“LAGV+支架”工艺较采用AGV可明显降低QC等待时间；当该比例减少时，“LAGV+支架”工艺的缓冲作用发挥不明显，QC等待时间差别不大。
由图10b）可知：两种工艺下的QC等待时间均随着任务规模增大而增加，采用“LAGV+支架”工艺较采用AGV的QC等待时间短；在设备配置一定的情况下，当任务规模为中等时，采用“LAGV+支架”工艺较AGV工艺的优势更明显。
由图10c）可知：当水平運输设备不够充足时，两种工艺下的QC等待时间均随着（L）AGV数量的增加而减少；“LAGV+支架”工艺下的QC等待时间比相应的AGV工艺下的QC等待时间短。但是，随着（L）AGV数量继续增加，QC等待时间趋于稳定。在水平运输设备不充足的情况下，采用“LAGV+支架”工艺较AGV工艺有更明显的优势。
由图10d）可知：在缩短QC等待时间上，本文算法采用的策略a（选择最早空闲的最近的一辆LAGV完成待作业任务）较策略b（选择最近两辆LAGV中最早到达的一辆LAGV完成待作业任务）具有明显优势。分析可知，采用策略b一方面会导致紧急任务得不到及时作业，另一方面会导致某些LAGV处于闲置状态，水平运输设备任务量不均衡，进而导致QC等待时间过长。
5结束语
考虑码头装卸作业各环节和缓冲系统的调度，以最小化船舶在港时间为整体目标，建立了自动化设备集成调度框架和相关模型。设计了双层遗传算法结合启发式策略对模型进行求解。结果表明：设备协同调度较单环节独立调度能改善岸桥（QC）调度均衡性；“支架+自带提升功能的自动导引小车（LAGV）”工艺在中等任务规模、QC与车辆配比较大条件下，具有明显的优势。研究结果可为码头设备的调度提供重要的决策支持。下一步的研究工作中将会考虑LAGV路径规划和能量约束的影响。
参考文献：
[1]KIM Jeongmin， CHOE Ri， RYU Kwang Ryel. Multiobjective optimization of dispatching strategies for situationadaptive AGV operation in an automated container terminal[C]//Research in Adaptive and Convergent Systems. ACM， 2013： 16.
[2]乐美龙， 赵彦营， 刘秀玲. 时间窗下单船岸桥调度[J]. 计算机工程与应用， 2014， 50（9）： 242248.
[3]HE Junliang， HUANG Youfang， YAN Wei. Yard crane scheduling in a container terminal for the tradeoff between efficiency and energy consumption[J]. Advanced Engineering Informatics， 2015， 29（1）： 5975.
[4]秦天保， 彭嘉瑶， 沙梅. 带任务顺序约束的岸桥集卡集成调度约束规划模型[J]. 上海海事大学学报， 2013， 34（3）： 17.
[5]马超， 梁承姬. 集装箱码头岸桥分配与集卡调度整合问题研究[J]. 广西大学学报（自然科学版）， 2015， 40（3）： 643650.
[6]CHEN Lu， LANGEVIN Andre， 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.
[7]钱继锋. 集装箱码头“岸桥集卡堆场”作业计划的优化[D]. 北京： 北京交通大学， 2014.
[8]DKHIL Hamdi， YASSINE Adnan， CHABCHOUB Habib. Optimization and simulation of container handling systems in automated maritime terminal[J]. Studies in Computational Intelligence， 2013， 457： 301312.
[9]乐美龙， 张清波. 自动化码头桥吊、自动引导车以及龙门吊的联合调度[J]. 青岛科技大学学报（自然科学版）， 2015， 36（5）： 569574.
[10]宓为建， 李央央， 胡鸿韬. 集装箱堆场分配与自动化装载小车路径联合优化[J]. 上海海事大学学报， 2015， 36（4）： 1621.
[11]汤鹏飞， 梁承姬， 丁一， 等. 考虑岸桥缓存区的ALV调度优化问题研究[J]. 广西大学学报（自然科学版）， 2015， 40（6）： 15401550.
[12]余孟齐， 韩晓龙. 有限缓冲空间下岸桥和自动升降车的集成调度[J]. 武汉理工大学学报（信息与管理工程版）， 2016， 38（1）： 101105.
[13]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.
（编辑贾裙平）
摘要：为深入研究新工艺带来的自动化码头设备集成调度问题，针对自动化码头的一种自带提升功能的自动导引小车（LAGV）和缓冲支架系统，提出新的设备集成调度框架。考虑不同设备之间的相互关联和制约的协同关系，将岸桥分配调度与LAGV、场桥调度分开，合理定义两种任务（两个问题）的划分方式，建立两个多目标混合整数规划模型。设计一种具有内外层关联的适应度函数的双层遗传算法。相对传统联合调度算法，该算法平衡了计算复杂性与调度均衡性。最后的数值试验证明了模型和算法的有效性。从岸桥数量、任务规模、AGV数量和调度策略等对岸桥等待时间的影响上，对采用LAGV的系统和采用传统AGV的系统进行比较，为自动化码头装卸作业调度提供决策支持。
关键词：
自动化码头； 自动导引小车（AGV）； 集成调度； 遗传算法（GA）； 启发式策略
中图分类号： U691.3
文献标志码： A
Integrated scheduling of cranes and AGVs with lifting function in automated container terminals
TIAN Yu1， WANG Jianbin1， FANG Huifang2
（1. Logistics Engineering College， Shanghai Maritime University， Shanghai 201306， China；
2. Software Automation Department， ZPMC Electric， Shanghai 200125， China）
Abstract：
In order to further study the issue of integrated equipment scheduling caused by new techniques in automated terminals for automated guided vehicles with lifting platforms （called LAGV） and buffer support system in automated terminal， a new integrated scheduling framework is proposed. Considering the interrelated and constrained cooperativeness relations among different equipments， it is divided into two problems， the quay crane allocation/scheduling problem and the LAGV and yard crane scheduling problem. By reasonably defining the division of two tasks （two problems）， two multiobjective mixedinteger programming models are established sequentially. A twolayer genetic algorithm is developed， where a fitness function is proposed to interlink two layers. The algorithm leads to the tradeoff between the computational complexity and the scheduling equilibrium compared with traditional joint scheduling algorithms. A numerical test is carried out in order to evaluate the performance of the model and algorithm. The system adopting LAGVs is compared with the system adopting traditional AGVs through investigating the influence of the number of quay cranes， the scale of tasks and the number & scheduling strategies of AGVs on the waiting time of quay cranes. The results provide decision support for automated terminal handling operations.
Key words：
automated terminal； Automated Guided Vehicle （AGV）； integrated scheduling； Genetic Algorithm （GA）； heuristic strategy
0引言
在新的全球經济格局下，如何提高集装箱码头运作效率成为当前码头发展亟待解决的问题。而在码头实际作业过程中，码头整体作业效率的提升依赖于岸桥、水平运输车辆、场桥等主要设备的密切协作与合理调度。因此，码头设备调度问题成为当前研究的热点。
目前，国内外专家对集装箱码头优化调度问题已经做了大量的研究。文献[13]仅研究码头单个环节调度，通过模型构建、算法设计及案例分析研究码头设备调度问题，但未考虑码头多个环节之间的相互影响。文献[49]在研究集装箱码头设备调度问题时，考虑了多环节作业之间的相互作用和制约，建立了多类型设备集成调度模型。码头新工艺的出现对调度问题产生了很大影响，文献[1012]针对码头新工艺下的设备调度问题，采用构建模型、仿真模型及实验分析等方法进行研究。
当前的研究主要针对码头一种或两种设备的联合调度，且大多数集中在传统码头领域，缺乏将不同新工艺用于码头设备集成调度的深入研究。本文建立岸桥（QC）、自带提升功能的自动导引小车（LAGV）和支架、自动化场桥（AYC）集成调度混合整数规划模型，并设计双层遗传算法对问题进行求解。
1问题描述
图1展示了自动化码头的一种新工艺布局，其装卸运输系统由4部分组成：QC，LAGV，缓冲支架以及AYC。QC负责船舶装卸，LAGV负责水平运输，AYC负责场区的存/取操作。作为连接水平运输和堆场操作的柔性机制，缓冲支架减少水平运输设备和自动化轨道吊相互等待时间，缓解水平运输能力与自动化轨道吊装卸堆放能力之间的矛盾，提高系统作业效率，但也增加了设备调度复杂性。
考虑任务执行过程中各装卸环节的衔接以及各装卸设备之间存在时空非同步性影响，分析码头装卸作业调度系统，可知各子环节调度存在目标冲突、
装卸资源请求冲突、响应结果冲突。因此，QC调度问题、水平运输调度问题、AYC调度问题相互影响、紧密关联，必须在有效解决上述冲突的情况下合理协调各种调度决策才能达到最优的整体运作效果。
2集成调度模型
2.1调度框架
对于集装箱装卸任务的划分，BIERWIRTH等[13]将其分为5种：①基于贝位区域；②基于单个贝位；③基于堆垛的任务；④基于集装箱簇；⑤基于单个集装箱。
定义两层调度子问题的不同任务划分方式：上层采用集装箱簇作为任务定义，既避免由于基于单个集装箱任务定义导致的QC各种十分复杂的干扰约束的出现，和任务量的庞大造成求解时间和空间复杂度指数性增加，又不会因任务定义太大而导致QC作业难以均衡；下层是AGV和场桥的调度，采用基于单个集装箱的任务定义，有利于AGV运输的灵活性和场桥重进重出的高效率，也便于与上层进行任务单位的衔接。
如图2所示，设备集成调度框架是在已知船舶配载计划、QC属性、任务属性的情况下，通过基于簇任务的QC分配与调度模型求解各QC的箱任务序列，为基于箱任务序列的自动化设备集成调度模型提供一定的输入条件，而将后者求解出的箱任务结束时刻反馈给前者，作为QC调度的评估，不断重复该逻辑，最后得到各设备的最優任务序列。
2.2基于簇任务的QC分配与调度模型
2.2.1假设条件
（1）计划期内船舶泊位计划已知，船舶上贝位连续分布，且每个贝位在岸线方向上的长度相同；
（2）每个集装箱簇任务所在贝位、作业类型、最短理想作业时间、先后作业顺序、簇内集装箱的作业顺序均已知；
（3）单船设有同时作业最多和最少QC数；
（4）所有QC在同一轨道上水平匀速移动且不能跨越作业，相邻QC之间满足安全距离要求。
2.2.2符号说明
K为QC的集合，K={1，2，…，k，…，C}；T为计划期内时间段的集合，T={1，2，…，t，…，P}；Ω为所有簇任务集合，Ω={1，2，…，n，…，N}，用m表示同台QC上任务n的前任务；ψ为不能同时作业的簇任务集合；Φ为有作业先后顺序要求的簇任务集合；Rmin和Rmax分别表示为船舶分配的最少和最多QC数；Ta为船舶到达时刻；Tb为船舶靠泊时刻；Tn为簇任务n的理想最短作业时间；ln为簇任务n的位置，用贝位编号表示；Δl为相邻QC的安全距离，用间隔贝位数表示，通常为一个贝位；vk为第k台QC的水平移动速度，m/min，k∈K；M为一个充分大的正整数；Ts和Te分别表示船舶开始作业和结束作业时刻；Tsn，Ten分别为簇任务n的真实开始时刻和结束时刻，Tsn为簇任务n的允许作业时刻；ckn为第k台QC服务簇任务n后的空闲时刻，每次任务完成后立即更新；lkn为第k台QC完成簇任务n时位于码头岸线上的位置，每次任务完成后立即更新；δkn为第k台QC为完成簇任务n移动到合适位置所需的时间；xtk为01变量，若第t时段有第k台QC为船舶进行装卸作业，则为1，否则为0；ztkn为01变量，若第t时段有第k台QC为簇任务n作业，则为1，否则为0；fn1n2为01变量，若簇任务n2开始作业时，簇任务n1已经完成，则为1，否则为0，n1，n2∈Ω。
2.2.3目标函数
（1）最小化船舶在港时间
S1=min（Te-Ta）=min（（Te-Ts）+（Ts-Ta））
其中：Te-Ts表示船舶的装卸作业时间；Ts-Ta表示船舶的等待作业时间，包含等待泊位时间和等待岸桥时间。
（2）最小化QC移动距离
S2=min knztkn·vk·δkn=
min knT（ztkn（|lkn-lkn′|+
k′|ln-（k-k′）Δl-l′k′n′|））
当进行装卸作业时，QC的状态是不断变化的，当第k台QC对船舶上的簇任务n进行作业时，其位置和再次空闲时刻需要更新：
lkn=ztknln
ckn=ztknTen
由于QC不能跨越作业，某QC k′可能会因为其他作业需要而被迫移动，其位置和空闲时间更新如下：
l′kn=ztkn（ln-（k-k′）Δl）
c′kn=ztkn（c′kn′+ln-（k-k′）Δl-l′k′n′/vk）
2.2.4约束条件
Ts≥Tb （1）
Te≥max（Ten），n∈Ω （2）
Rmin≤kxtk≤Rmax，t∈T （3）
nztkn=xtk，t∈T；k∈K；n∈Ω （4）
tkztkn≥Tn，n∈Ω （5）
zt1k1n+zt2k2n=1，t1，t2∈{Tsn，…，Ten}；
k1，k2∈K，k1≠k2； n∈Ω （6）
Tsn≥max{（ckm+δkn）ztkn，Tsn}，
t∈T；k∈K；m，n∈Ω （7）
Ten≥Tsn+Tn，n∈Ω （8）
fn1n2+fn2n1=1，（n1，n2）∈ψ （9）
Ten1-Tsn2≤0，（n1，n2）∈Φ （10）
Ten1≤Tsn2+M（1-zt1kn1zt2kn2fn1n2），
t1，t2∈T； k∈K； n1，n2∈Ω （11）
（lk2n2-lk1n1）（ln2-ln1）ztk1n1ztk2n2≥0 （12）
xt，k-1+xt，k+1-xt，k={-1，0，1}，
t∈T； k-1，k，k+1∈K （13）
式（1）表示船舶的开始作业时刻必须大于其靠泊时刻。式（2）表示所有簇任务作业完成时间即为船舶结束作业的时间。式（3）表示每个时刻为船舶服务的船舶数量在一定范围内。式（4）表示在单位时间内一台QC只能为一个任务服务。式（5）表示每个簇任务都配置了相应的QC作业，并且QC作业时间应满足簇任务所需的装卸作业时间要求。式（6）表示有且仅有一台QC为簇任务n服务。式（7）表示簇任务n的开始作业时刻。式（8）表示簇任务n的作业结束时刻。式（9）表示对不能同时作业的簇任务的限定。式（10）表示有先后顺序的簇任务在时间上的关系。式（11）表示两个簇任务由同一台QC服务时，其作业时间需要满足的关系。式（12）表示QC不能在同一船舶的两个作业之间交叉作业。式（13）表示任意时间若有多台QC为该船舶服务，则QC必须连续，即满足QC不能跨越原则。
2.3基于箱任务序列的自动化设备集成调度模型
2.3.1假设条件
（1）集港在装卸船作业过程之前已经完成，疏港在装卸船作业过程之后进行。
（2）通过QC调度模型得到每台QC所负责的簇任务和箱任务序列。
（3）调度计划期内，已知每个箱任务操作类型（装/卸），在船上和堆场的装卸位置。
（4）QC，LAGV和AYC的可用数量已知，且每个设备一次只處理一个集装箱。
（5）LAGV，AYC空/重载和QC的速度以及各个设备的装卸效率。
（6）每个堆场箱区仅岸侧AYC负责装卸船；不考虑LAGV堵塞情况；已知LAGV和AYC在任何两个操作节点位置之间的距离。
2.3.2符号变量说明
ve和vd分别表示提供AYC初始和结束虚拟任务的虚拟岸桥。vs和vf分别表示提供LAGV初始和结束虚拟任务的虚拟岸桥。Q为AYC的集合。V为LAGV的集合。P为堆场岸侧交换区的集合。mk为第k台QC执行的任务数量，k∈K。eki为QC在作业区开始作业箱任务（k，i）事件，当箱任务（k，i）为卸船任务时，表示QC开始放箱到LAGV；当箱任务（k，i）为装船任务时，表示QC开始从LAGV上抓箱；（k，i）为箱任务编号，代表第k台QC的第i个箱任务，k∈K，i=1，…，mk。Eaki为LAGV在堆场岸侧交换区开始作业箱任务（k，i）事件，当箱任务（k，i）为卸船任务时，表示LAGV开始将其顶升到支架；当箱任务（k，i）为装船任务时，表示LAGV开始从支架处接箱，k∈K。Ebki为AYC在堆场岸侧交换区开始作业箱任务（k，i）事件，当箱任务（k，i）为卸船任务时，表示AYC开始从支架上抓箱；当箱任务（k，i）为装船任务时，表示AYC开始放箱到支架，k∈K。TL为装船任务的事件eki的集合，k∈K，即eki∈TL。TD为卸船任务的事件eki的集合，k∈K，即eki∈TD。TC为事件eki集合中有先后顺序要求的任务集合，k∈K，即eki∈TC。Nq为第q台AYC执行Ebki的集合，k∈K，q∈Q。Np为第p个堆场岸侧交换区事件Eaki的集合，k∈K，p∈P。ski为第k台QC执行事件eki的实际准备就绪时刻，k∈K。Hkik（i-1）为第k台QC完成ek（i-1）后执行eki的全部准备时间，k∈K，i≠1。yki为事件eki的实际发生时刻，k∈K。Yaki为事件Eaki的发生时刻，k∈K。Ybki为事件Ebki的发生时刻，k∈K。Tljki为从Ebki发生的位置到Eblj发生的位置之间AYC的纯移动时间，k∈{ve}∪K，l∈{vd}∪K，j=1，…，ml，mve=mvd=|Q|。Gljki表示AYC完成Ebki后执行Eblj需要调整的时间，k∈{ve}∪K，l∈{vd}∪K。 tljki为从eki发生的位置到elj发生的位置LAGV的纯运行时间，k∈{vs}∪K，l∈{vf}∪K，mvs=mvf=|V|。cljki为LAGV完成eki后去完成elj的调整时间，k∈{vs}∪K，l∈{vf}∪K。Sljki为eki与Ealj两个事件间的调整时间，k∈{vs}∪K，l∈{vf}∪K。Ski为eki与Eaki两个事件间的调整时间，k∈K。ΔSki为Eaki与Ebki两个事件间的间隔时间，k∈K。ljki为01变量，若同一辆LAGV完成eki后紧接着完成elj，则其值为1，否则为0，k∈{vs}∪K，l∈{vf}∪K。φljki为01变量，若同一台AYC完成Ebki后紧接着完成Eblj，则其值为1，否则为0，k∈{ve}∪K，l∈{vd}∪K。
2.3.3目标函数及约束
i=1，…，mk；j=1，…，ml
S3=min k∈Kmki=1（yki-ski）+ （14）
S4=min k∈{ve}∪Kmki=1l∈K∪{vd}mlj=1Tljkiφljki （15）
S5=min k∈{vs}∪Kmki=1l∈K∪{vf}mlj=1tljkiljki （16）
l∈{vf}∪Kmlj=1ljki=1，k∈{vs}∪K
（17）
k∈{vs}∪Kmki=1ljki=1，l∈{vf}∪K
（18）
l∈{vd}∪Kmlj=1φljki=1，k∈{ve}∪K
（19）
k∈{ve}∪Kmki=1φljki=1，l∈{vd}∪K
（20）
ylj-max（yki+cljki，slj）≥M（ljki-1），
k∈{vs}∪K；l∈K
（21）
Yblj-（Ybki+Gljki）≥M（φljki-1），
k∈{ve}∪K；l∈K
Yalj-（yki+Sljki）≥M（ljki-1），
（22）
k∈{vs}∪K；l∈K （23）
yki-yk（i-1）≥ski-sk（i-1），k∈K；i≠1 （24）
yki≥ski，k∈K （25）
ski≥yk（i-1）+Hkik（i-1），k∈K；i≠1 （26）
yki≥Yaki+Ski，eki∈TL；k∈K （27）
Yaki≥Ybki+ΔSki，eki∈TL；k∈K （28）
Yaki≥yki+Ski，eki∈TD；k∈K （29）
Ybki≥Yaki+ΔSki，eki∈TD；k∈K （30）
Ybki-Ybkj≥0，
Ebki，Ebkj∈Nq；k∈K；
i>j；q∈Q （31）
Ybki-Yblj≥0，Ebki，Eblj∈Nq；k，l∈K；
eki，elj∈TC；yki>ylj；q∈Q （32）
式（14）～（16）为目标函数，分别表示最小化QC延迟时间、最小化AYC总移动时间、最小化LAGV的总运行时间。式（17）～（20）表示LAGV或AYC一次只能执行一个任务，一个任务一旦由某个AYC或LAGV执行就不能中断，且每个任务都要被执行。式（21）和（22）表示由同一装卸运输设备执行的相邻任务的时间逻辑关系，式（21）表示同一辆LAGV完成eki后去执行elj需要有时间cljki准备及岸桥时间准备，式（22）表示同一台AYC完成Ebki后去执行Eblj需要有时间tljki准备。式（23）表示作业不同环节的时间逻辑关系，如果任务（k，i）和（l，j）是同一辆LAGV的两个相邻任务，那么LAGV完成eki后需要时间Sljki调整去完成Eblj。式（24）表示同一台QC执行相邻任务的调整时间应满足QC执行所需作业的时间。式（25）表示eki的实际发生时刻最小为最早可能发生时刻。式（26）表示QC执行ek（i-1）后需时间Hkik（i-1）准备才能执行任务eki。式（27）和（28）表示对于同一装船任务（k，i），作业相邻环节的时间逻辑关系，此类任务的设备操作顺序是：AYC→LAGV→QC，因此AYC完成Ebki时刻与Eaki和Ebki的调整时间之和不会超过LAGV完成Eaki的时刻，LAGV完成Eaki的时刻与Eaki和eki的调整时间之和不会超過QC完成eki的时刻。同理，式（29）和（30）表示对于同一卸船任务（k，i），其作业相邻环节的时间逻辑关系。此类任务的设备操作顺序是：QC→LAGV→AYC。式（31）表示每台AYC的任务执行顺序需要符合QC任务序列中的顺序。式（32） 表示每台AYC执行具有约束关系的任务必须符合它们的先后顺序。
3双层多目标遗传算法设计
上述模型中的调度子问题均为NP难问题，本文设计双层多目标遗传算法求解：外层优化QC簇任务作业序列；内层基于外层的QC箱任务序列优化LAGV和AYC的任务序列，然后计算相关的评价指标值并将其反馈到外层，作为外层染色体的评价准则；通过内外层遗传算法的协调确定最优的集成调度方案。其算法流程见图3。
3.1染色体编码
主要考虑两个位串编码，外层位串表示QC分配调度的簇任务序列， 内层位串表示LAGV和AYC调度中的箱任务序列；内外层均采用自然数对染色体编码，每个染色体代表所有任务的一个随机排列，每个自然数代表任务编号，染色体长度等于任务数量。
3.2不可行和重复序列的修正策略
随机生成或迭代更新的染色体可能存在不可行或重复个体的情况，因此需进行修正。
针对不可行序列的修正策略：外层簇任务序列根据不同时、有先后关系的簇任务约束进行染色体的修正；而内层遗传算法是在外层遗传算法获得的可行QC的作业序列的基础上进行的，因此内层箱任务序列需要与外层所得的QC作业箱任务序列一致。
步骤1按外层算法所得的每个QC作业箱任务序列修正随机产生的箱任务序列，得到符合每个QC作业序列的箱任务序列。
步骤2按簇任务约束关系来修正箱任务顺序。根据QC调度序列，不同时、有先后关系的簇任务若由同一台QC完成，那么已经在步骤1中修正。若它们不由同一台QC完成，则应修正编码使其满足约束关系。采取下列方式修正：
①对先后顺序关系簇任务集合，直接按先后顺序展开组成箱任务序列，找到其箱序列编码中的位置直接替换；
②对不同时的簇任务集合，先找出其在簇序列中的先后位置，并按位置先后展开组成箱任务序列，再找其在箱序列编码中的位置并替换。
步骤3重复上述两步修复策略，直到新的箱任务序列不再变化为止。
对种群中重复序列的修正策略：由于算法内外层任务均采取统一编码方式，在种群中会不可避免地产生重复的个体，不利于算法收敛精度，因此搜寻每代的重复个体，并采用部分逆反变异操作生成新的个体替换原染色体，得到新的种群作为下一代。这样不仅能降低重复个体存在的概率，而且能保持种群多样性。
3.3集成调度的启发式策略
本文算法设计思想是将遗传算法与有效的启发式策略相结合，将由内外层编码得到的可行序列作为任务选择QC或AGV，AYC的顺序，依此顺序采用下面的QC调度策略和AGV，AYC调度策略，逐一为当前任务分配合适的设备，直到所有任务完成分配。
QC调度策略见图4。
QC调度策略的具体步骤如下：
步骤1初始化船舶开始作业时刻（即靠泊时刻），QC的位置和可用时间，簇任务在船上的贝位、任务量和相关约束。
步骤2若可用QC数大于或等于船舶作业QC最小数，则随机选择一组连续的QC分配给船舶，转步骤3；否则推迟船舶开始作业时刻。
步骤3考虑QC和任务属性，逐一为簇任务n分配作业QC。首先检查簇任务n左右两侧距其最近的QC，若需要等待时间相同则优先选择距离更近的QC，若需要等待时间不同则选择等待时间较短的QC，并更新簇任务n的开始作业和结束作业时刻以及QC位置和再次空闲时刻。
步骤4如此循环执行步骤3，为簇任务n+1分配QC，直到为所有簇任务分配QC完毕，得到QC分配和调度簇任务序列。
AYC调度策略：在给定QC作业箱任务顺序后，AYC的作业序列与QC作业序列一致。
LAGV调度策略：根据箱任务序列对LAGV进行运输任务指派，采用以下启发式规则对LAGV进行调度：①遵循QC作业顺序优先原则；②先到先指派。
3.4适应值函数选择
适应值函数由目标函数加权和的倒数确定。外层为船舶在港时间（箱任务最大完成时刻）与QC移动距离的归一化加权和倒数；内层为箱任务最迟结束时刻、每台QC的箱任务均衡程度、QC总延迟时间、LAGV的总运行时间和AYC总移动时间的归一化加权和倒数。
3.5选择、交叉、变异
采用轮盘赌方法对染色体进行选择；采用部分匹配交叉（图5）和部分逆反变异（图6）的方法对染色体进行操作。
4算例分析
4.1案例说明
以采用新工艺的青岛某自动化码头为例。该码头总岸线长2 088 m，每个40英尺集装箱贝位在岸线上跨度为12 m，码头共有7台QC可供分配，假定QC初始位置均匀分布于码头岸线上。堆场采用垂直岸线布置，本案例涉及8个箱区，每个箱区配备两台AYC，岸侧场桥负责装卸船的存取箱，陆侧场桥负责配合外部集卡集疏港，各箱区岸侧均设置一组支架的交换区。设置支架数量为5条，并预留一条无支架装卸车道。水平交通组织中的各类车道数量和宽度是根据QC后伸距以及LAGV参数设定的，车道布局见图7。QC下装卸车道为单行道，行车方向是依据船头朝向和装卸箱量的比例设定的，以减少倒箱门现象对车辆和道路的干扰。缓冲车道允许双向行驶，以缩短车辆在岸边与堆场之间的运行距离；高速相邻车道行驶方向相反，便于车辆在箱区岸侧交换区的进出，水平交通规则见图7。
假设各AYC和LAGV初始位置均设置在各箱区支架交换区。各设备完成其所有作业后回到初始位置，各装卸运输设备参数见表1。QC平均作业效率每小时不低于36个循环，假设QC抓/放箱操作时间均为10 s，QC小车在QC交换区与船舶之间的平均水平运行时间为40 s。某艘船停靠在距岸线100 m处，靠泊时刻为计划期的第60 min，随机生成该船需要裝卸作业的簇任务以及箱任务，包括任务数量、在船上和堆场中的位置、各任务之间不同时、
有先后顺序等的约束关系。
4.2试验分析
本文算法采用MATLAB R2012b编程实现，并在Intel（R） Core（TM） 2Quad CPU Q9500 @2.83 GHz处理器，RAM 2GB电脑上运行。通过多次初步试验确定有关的参数：（1）外层。种群大小50；最大遗传代数100；交叉概率0.85；变异概率0.10。（2）内层。种群大小50；最大遗传代数100；交叉概率0.80；变异概率0.05。
为了评估新工艺的集成调度模型和算法，首先设计8组中等规模仿真算例验证所提算法的性能。为实现建模与算法的分离，将模型的非线性约束转换成线性约束，采用MATLAB中的YALMIP工具箱结合CPLEX12.2求解器，求解QC调度模型，其中计划期的时间单位设置成所有簇任务的装卸时间需求最小值，再根据QC调度结果求解自动化设备集成调度模型。表2最后一列显示了本文算法的加权目标函数值与最优值之间的偏差。试验发现，CPLEX的计算耗时随着任务数的增加快速上升，30个以上箱任务的问题无法在有效的时间内得到结果（最后两组算例的时间都超过了4 h），而双层遗传算法尽管不能获得最优解，但在大规模任务的计算效率上具有优势。
为分析系统的灵敏性，选取LAGV数和计划期长度（任务数）作为变化因素，试验结果见图8。可以看出，在给定LAGV数的条件下，加权目标函数值随着计划期长度的增加而增加，但任务的平均值在下降。这表明，计划期越长，系统越能获得更好的性能。然而计算更多任务数将花费更多时间。在实际中，由于码头各种中断事件的发生，如起重机或AGV等设备故障，会不可避免地需要进行再调度。因此，可以结合实际情况，选取一个适当的计划期以权衡计算量和系统性能的损失。此外，在给定计划期的条件下，LAGV数会影响系统性能，特别是对某具体算例，存在最优的数量配置。决定加权目标函数值变化的因素除LAGV数外，还包括任务的信息及其在QC上的序列。
为分析集成调度的效果，采用双层遗传算法，模拟3台QC，8辆LAGV，8台AYC，10个簇任务，44个装卸箱任务条件下各设备作业序列的优化。图9呈现了QC理想调度（QC无等待）与集成调度得到的各QC任务的开始和结束时刻（图9a）中矩形块为簇任务编号，图9b）中矩形块为箱任务编号）。
图9a）显示在集成调度的情况下，各QC作业比较均衡并均存在等待，说明LAGV和AYC的调度影响了QC调度结果；较单环节调度，集成调度协调了各环节之间的冲突，对码头资源整合有重要借鉴作用。图9b）显示QC累积等待时间在各QC之间分
配的非均衡性，因为LAGV和AYC的调度目标之一是在最小化船舶在港时间的情况下使各QC任务完成时间尽量均衡，减少任务多的QC的作业延迟。
选择3种变化因素对比在新工艺“LAGV+支架”与传统AGV工艺下集成调度的结果。第1个因素是QC数量，设定为2，3，4；第2个因素是簇任务规模，设定为3，5，7，10；第3个因素是水平运输设备的数量，设定为4，8，12，18，24，44。此外，比较了两种常见LAGV调度策略的影响。每种组合试验次数为10次，试验结果见图10。
a）QC
b）任务
c）水平运输设备
d）调度策略
由图10a）可知：当QC和（L）AGV的配置比例增大时，采用“LAGV+支架”工艺较采用AGV可明显降低QC等待时间；当该比例减少时，“LAGV+支架”工艺的缓冲作用发挥不明显，QC等待时间差别不大。
由图10b）可知：两种工艺下的QC等待时间均随着任务规模增大而增加，采用“LAGV+支架”工艺较采用AGV的QC等待时间短；在设备配置一定的情况下，当任务规模为中等时，采用“LAGV+支架”工艺较AGV工艺的优势更明显。
由图10c）可知：当水平運输设备不够充足时，两种工艺下的QC等待时间均随着（L）AGV数量的增加而减少；“LAGV+支架”工艺下的QC等待时间比相应的AGV工艺下的QC等待时间短。但是，随着（L）AGV数量继续增加，QC等待时间趋于稳定。在水平运输设备不充足的情况下，采用“LAGV+支架”工艺较AGV工艺有更明显的优势。
由图10d）可知：在缩短QC等待时间上，本文算法采用的策略a（选择最早空闲的最近的一辆LAGV完成待作业任务）较策略b（选择最近两辆LAGV中最早到达的一辆LAGV完成待作业任务）具有明显优势。分析可知，采用策略b一方面会导致紧急任务得不到及时作业，另一方面会导致某些LAGV处于闲置状态，水平运输设备任务量不均衡，进而导致QC等待时间过长。
5结束语
考虑码头装卸作业各环节和缓冲系统的调度，以最小化船舶在港时间为整体目标，建立了自动化设备集成调度框架和相关模型。设计了双层遗传算法结合启发式策略对模型进行求解。结果表明：设备协同调度较单环节独立调度能改善岸桥（QC）调度均衡性；“支架+自带提升功能的自动导引小车（LAGV）”工艺在中等任务规模、QC与车辆配比较大条件下，具有明显的优势。研究结果可为码头设备的调度提供重要的决策支持。下一步的研究工作中将会考虑LAGV路径规划和能量约束的影响。
参考文献：
[1]KIM Jeongmin， CHOE Ri， RYU Kwang Ryel. Multiobjective optimization of dispatching strategies for situationadaptive AGV operation in an automated container terminal[C]//Research in Adaptive and Convergent Systems. ACM， 2013： 16.
[2]乐美龙， 赵彦营， 刘秀玲. 时间窗下单船岸桥调度[J]. 计算机工程与应用， 2014， 50（9）： 242248.
[3]HE Junliang， HUANG Youfang， YAN Wei. Yard crane scheduling in a container terminal for the tradeoff between efficiency and energy consumption[J]. Advanced Engineering Informatics， 2015， 29（1）： 5975.
[4]秦天保， 彭嘉瑶， 沙梅. 带任务顺序约束的岸桥集卡集成调度约束规划模型[J]. 上海海事大学学报， 2013， 34（3）： 17.
[5]马超， 梁承姬. 集装箱码头岸桥分配与集卡调度整合问题研究[J]. 广西大学学报（自然科学版）， 2015， 40（3）： 643650.
[6]CHEN Lu， LANGEVIN Andre， 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.
[7]钱继锋. 集装箱码头“岸桥集卡堆场”作业计划的优化[D]. 北京： 北京交通大学， 2014.
[8]DKHIL Hamdi， YASSINE Adnan， CHABCHOUB Habib. Optimization and simulation of container handling systems in automated maritime terminal[J]. Studies in Computational Intelligence， 2013， 457： 301312.
[9]乐美龙， 张清波. 自动化码头桥吊、自动引导车以及龙门吊的联合调度[J]. 青岛科技大学学报（自然科学版）， 2015， 36（5）： 569574.
[10]宓为建， 李央央， 胡鸿韬. 集装箱堆场分配与自动化装载小车路径联合优化[J]. 上海海事大学学报， 2015， 36（4）： 1621.
[11]汤鹏飞， 梁承姬， 丁一， 等. 考虑岸桥缓存区的ALV调度优化问题研究[J]. 广西大学学报（自然科学版）， 2015， 40（6）： 15401550.
[12]余孟齐， 韩晓龙. 有限缓冲空间下岸桥和自动升降车的集成调度[J]. 武汉理工大学学报（信息与管理工程版）， 2016， 38（1）： 101105.
[13]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.
（编辑贾裙平）
