考虑实时预倒箱的出口箱堆场多场桥调度优化
2018-10-16郑红星刘保利匡海波
郑红星，刘保利，匡海波，闫 叙
(大连海事大学交通运输管理学院，辽宁 大连 116026)
1 引言
由于我国大多数集装箱港口是进口箱和出口箱分开堆放的，在现有岸边作业系统和水平运输系统一定的情况下，出口箱堆场的作业效率直接影响着整个码头的服务水平，研究该类堆场的效率提升策略是当前集装箱港口研究的热点。作为堆场中重要的作业设备—场桥，对其如何科学有效地安排调度来提高装船效率，是出口箱堆场亟需解决的问题。
目前，针对出口箱堆场场桥调度问题，国内外有很多学者进行了深入的研究。鉴于倒箱因素直接影响场桥作业的时长，本文将已有文献按处理该因素的方法不同，分为以下三类：A类——不考虑倒箱影响，只考虑场桥在作业过程中抓取待提箱的时长；B类——固定倒箱次序，在作业过程中场桥抓取某个待提箱的时长等于单独提该箱的时间加上其倒箱时间，倒箱时间或直接给出，或按单箱翻倒时间与压箱数乘积计算；C类——提前控制倒箱，在船舶装船作业开始之前或按配载图提前倒箱，或通过箱位优化确定最少倒箱数的堆存方案。
在A类文献中，Kim等[1]以出口集装箱作业序列为研究对象，以场桥在各箱区间总移动时间最小为目标，构建了单台场桥作业调度的混合整数规划模型。Mak等[2]研究了混堆堆场内的多场桥调度问题，考虑了集装箱的提箱准备时间、提箱作业时间、场桥移动时间及因场桥间干扰引起的等待时间，以多台场桥作业完成时刻之和最小为目标，构建了混合整数规划模型，设计了一种遗传算法与禁忌搜索算法相结合的混合优化算法。Chang Daofang等[3]研究了单个箱区内的双场桥调度问题，建立了以最小化延迟任务数为目标的整数规划模型，并设计了基于滚动时域的启发式算法。乐美龙等[4]针对出口箱堆场，考虑场桥不可跨越与保持安全距离等现实约束，以多场桥完成所有装卸任务的总时间最短为目标，并设计了两阶段算法，最终给出了一个任务分配和排序方案。Li Wenkai等[5]研究了单个箱区内的多场桥调度问题，以最小所有集装箱的提箱提前时间、提箱延迟时间及存箱延迟时间的加权和为优化目标，构建了连续型混合整数线性规划模型，并设计了滚动时域算法，实验表明所提出的算法可有效求解大规模算例。Wu Yong等[6]针对与Li Wenkai等[5]相同的问题，将提箱延迟任务数引入至目标函数中，提出了一种基于集群-重新分配思想的启发式算法。韩晓龙等[7]研究了集装箱码头装船作业中的场桥调度问题，结合配载计划，建立了提箱作业总完成时间最短为目标的场桥调度模型。范厚明等[8]提出了出口箱箱位分配和场桥调度的分区域平衡策划方法，考虑了场桥间相互干涉的现实约束，对场桥非装卸时间进行了优化，并均衡了各场桥的作业任务量。
在B类文献中，Chen Lu等[9]研究了出口箱堆场内的多场桥调度问题，同时考虑了场桥间作业干扰、场桥在多个箱区内的转场情况和场桥于单个箱区内的排序情况等，以所有集装箱的最迟提箱完成时刻最小为优化目标，构建了混合整数规划模型，并分别提出了遗传算法和禁忌搜索算法两种启发式算法用于求解。郑红星等[10]研究了混堆箱区某时段内的多场桥调度问题，考虑了内外集卡的优先级、场桥间不可跨越和保持安全距离等因素，构建了多场桥调度模型，并设计了混合遗传算法用于求解，文中各任务箱的提取操作时间不尽相同。梁承姬等[11]研究了混堆堆场内某箱区的场桥调度问题，建立了以场桥装卸完工时间最小为目标的优化模型，并设计了相应的优化算法，该文中将各任务箱的提取时间视为已知，但各不相同。虽然上述文献考虑的是混堆，但没有外集卡的装船阶段可看成出口箱堆场。郑红星等[12]为解决混堆装船箱区内的多场桥调度问题开发了一种滚动时域算法，重点考虑内外集卡的不同优先级别和倒箱因素对场桥调度问题的影响，在减少集卡等待成本的同时降低了倒箱量；且该文中倒箱的处理方法属于按单箱翻倒时间与压数乘积计算。张笑菊等[13]针对混堆堆场的集装箱码头装船顺序优化问题，考虑船舶一个贝位集装箱的同贝同步装卸作业，以单台场桥在单个箱区内移动时间和翻箱时间最小为目标，构建了出口集装箱装船顺序优化模型并设计了启发式算法，提高了场桥与岸桥的作业效率。Jin Jiangang等[14]以场桥作业成本和移动成本之和最小为目标，对场桥空间分配和场桥配置整合优化问题进行了研究，构建了整数线性规划模型，明确了各时段内场桥的工作区域。
在C类文献中，Lee等[15]将装船前的出口集装箱翻箱问题定义为预翻箱问题，并提出整数规划模型和近邻搜索算法，有效地解决了以翻箱次数最少为目标的堆场翻箱问题。朱明华等[16]基于给定出口箱堆场集装箱的堆存状态和装船顺序，建立了以倒箱量最少和场桥代价最低为目标的数学模型，提出了定向搜索算法进行求解。周鹏飞等[17]针对交箱序列的动态不确定性，建立了出口箱堆场中具体箱位分配模型，在优化翻箱量的同时缩短了场桥大车行走距离。邵乾虔等[18]结合出口箱堆场作业时间，建立了以最小化预翻箱量和场桥堆存作业移动距离为目标的数学模型，并给出了求解算法。
同时，鉴于出口箱堆场的核心作业是内集卡提箱装船，研究该类堆场的场桥调度需着重考虑内集卡作业效率对其的影响。有关集卡的研究一直是国内外学者研究的热点，其中Amini等[19]为优化集装箱码头集卡拥堵问题，针对集装箱交叉堆放的情况下，构建了多目标线性规划模型并结合三种启发式算法进行求解。张芳芳等[20]考虑了堆场可存储位置动态变化的因素，以内集卡完成任务的总时间最小为目标，构建了集卡调度模型并采用四种不同的改进 PSO 算法进行求解。赵金楼等[21]分别以集卡行驶距离和集卡任务间空载距离最小为目标，提出了集卡两阶段路径优化模型，在考虑集卡数量和作业顺序的影响下提高堆场作业效能。
综上，已有关于场桥调度的文献大都以场桥行走路径最短、场桥作业完成时间最短为优化目标，其中忽略倒箱的文献较多，直接将倒箱时间加入场桥作业过程的文献较少，而考虑提前控制倒箱的文献近年来逐渐增加。但在实际作业中限于集港时出口箱抵达时机同配载计划的不匹配，倒箱对场桥作业的时长影响很大，必须在调度过程中加以考虑；同时由于提前倒箱作业场桥数量的不足、场地和时间的限制、装船的时限要求等因素，提前控制倒箱和箱位分配很难实现，因此需考虑在场桥作业过程中的实时预倒箱。在有关集卡调度的文献中，大都以集卡行驶距离最短和总作业时间最短等为目标，少有考虑内集卡等待时间上限和由于场桥倒箱而产生的延误时间，而在出口箱堆场伴有倒箱的装船作业中，为尽可能减少岸桥等待内集卡的时间，需重点考虑如何采用实时预倒箱来加快内集卡的周转。
区别已有文献，本文在现有研究的基础上，针对出口箱堆场的场桥调度优化问题，从降低内集卡等待时间的角度出发，兼顾内集卡提箱的等待容忍限度，重点考虑基于配载计划中待提箱上压箱翻倒的时机和分配，视倒箱为作业过程的另一类别的任务，将倒箱任务和提箱任务集成优化，最终给出优化的场桥作业调度计划，其中包括多台场桥的行走路径和实时预倒箱方案。
2 调度模型及下界
2.1 问题描述
一般而言，预先获知船舶的抵港计划、船期和配载计划后，码头会为其配备合理数量的岸桥，并分配合适的泊位。从作业重要性上来看，泊位和岸桥是最重要的资源。因此，就出口箱堆场而言，如何高效地进行提箱作业，使得船舶的在泊时间最小，同时实现岸桥利用率的最大化，是出口箱堆场中多场桥调度的核心目的。
本文的问题可描述为：在固定的计划期内，某船拟从出口箱堆场某箱区提箱的配载计划已知，考虑待提箱的提箱次序固定、多台场桥作业过程中不可跨越和保持一定安全距离等现实约束，侧重作业过程中的实时预倒箱，兼顾内集卡的等待上限，使得带有惩罚因子的内集卡总提箱等待时间最少。
2.2 模型假设
本文将待提箱称为主计划箱，将主计划箱上的压箱称为该箱的子计划箱。
模型假设如下：(1)计划期内主计划箱对应内集卡就绪时刻均由往返规律预知；(2)只考虑20英尺单一箱型；(3)场桥间不可跨越且须留有安全距离；(4)箱区内主计划箱的箱位分布、配积载图及场桥作业能力等均已知；(5)提箱作业须在对应内集卡就绪后进行；(6)倒箱原则是不压计划期内的主计划箱。
2.3 调度模型
以某箱区为例，其贝位展开图见图1示，原问题转化为图论问题见图2示。
考虑转化过程中涉及的多主计划箱位于同贝同栈的情况，图2右侧即为Bay4转化情况(假设C3箱计划提箱时刻早于C5箱)，可见C3箱虽为主计划箱，但对其的作业可能不为提箱作业，而是提取其他箱时所需的倒箱作业。
图1 贝位展开图
图2 原调度的图论问题
本文将原调度问题转化为图论问题如图2所示，其中实线框内计划箱节点代表原问题中多主计划箱位于同贝同栈的转化情况，虚线框内计划箱节点代表原问题中多主计划箱位于同贝异栈的转化情况(若两种情况都存在则仍用实线框表示)；1、2号节点为起点，代表原问题中场桥；3号节点为终点，代表原问题中场桥作业完成；4至46号节点为各贝位计划箱转化后所对应的节点。本文调度问题转化为由起点出发，遍历全部中间节点最终汇集至终点的图论问题；同时在图论问题基础上，引入原问题各箱间作业约束、场桥现实约束等。
参数定义为：M充分大的正数；QTi为i箱对应集卡就绪时刻，不为主计划箱节点时取M；Dij节点(i,j)间的距离，以移动时间衡量；Bj为j箱的作业时间，不为箱节点时取0；C内集卡惩罚因子；ξ内集卡等待上限；n计划箱总数；D场桥间安全距离；Dt场桥行走距离D所用时长；BWi为i箱所在贝位，不为箱节点时取0；Q实线框外的所有计划箱集合；Rh第h个实线框内的所有节点集合(节点集合同转化情况相对应)；F所有节点集合；P场桥节点集合；R子计划箱节点集合；R′主计划箱节点集合；FZ虚拟终点集合；Pk第k号场桥为保持场桥间现实作业约束而无法到达的点集；m场桥数；L实线框数；Yhv第h个实线框内第v个节点集合；Shv第h个实线框第v个节点集合所对应到达边总数；Zi若第i号节点为主计划箱节点则取1，否则取0。
变量定义为：FTik第k号场桥作业i箱的完成时刻，若不为箱节点则取非负；Xijk若第k号场桥由节点i移至节点j则取1，否则取0；Aik若第k号场桥作业i箱的等待时间小于ξ则取1，否则取0；Cijkk′若满足FTik′≥FTjk则取1，否则取0；Eijkk′若场桥k′作业i箱同场桥k作业j箱的作业时间发生冲突则取1，否则取0；Gijkk′在场桥k′作业i箱同场桥k作业j箱作业时间发生冲突的条件下，若这两个场桥间不满足安全距离约束则取1，否则取0；Pijkk′在场桥k′作业i箱同场桥k作业j箱时作业时间发生冲突且不满足安全距离约束的条件下，若场桥k′先于场桥k作业则取1，否则取0；Whv第h个实线框第v个节点集合被遍历则取1，否则取0；TTi为i箱对应内集卡带有惩罚因子的等待时间。
(1)
s.t.:FTjk≥Dij*Xijk+FTik-(1-Xijk)*M+Bj,i,j∈F;k∈P
(2)
(3)
Xiik=0,i∈F;k∈P
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
FTjk≥FTik′-Cijkk′*M,i,j∈F;k,k′∈P
(21)
FTik′≥FTjk-(1-Cijkk′)*M,i,j∈F;k,k′∈P
(22)
FTjk≥FTik′+Bj-Cijkk′*M-Eijkk′*M,i,j∈F;k,k′∈P
(23)
FTik′≥FTjk-Bj-Cijkk′*M-(1-Eijkk′)*M,i,j∈F;k,k′∈P
(24)
BWi≤BWj+D+(1-Gijkk′)*M+(1-Eijkk′)*M,i,j∈F;k,k′∈P
(25)
BWi≥BWj+D-Gijkk′*M-(1-Eijkk′)*M,i,j∈F;k,k′∈P
(26)
FTjk≥FTik′-Bi+Bj-(1-Pijkk′)*M-(1-Gijkk′)*M,i,j∈F;k,k′∈P
(27)
FTjk≤FTik′-Bi+Bj+Pijkk′*M+(1-Gijkk′)*M,i,j∈F;k,k′∈P
(28)
(29)
(30)
Xijk=0,i∈F;j∈Pk;k∈P
(31)
FTik-QTi-ξ≤(1-Aik)*M,i∈F;k∈P
(32)
FTik-QTi-ξ≥-Aik*M,i∈F;k∈P
(33)
TTi≥FTik-QTi-(1-Aik)*M,i∈F;k∈P
(34)
TTi≥(FTik-QTi)*C-Aik*M,i∈F;k∈P
(35)
TTi≥0,FTik≥0,i∈F;k∈P
(36)
式(1)目标函数为带有惩罚因子的内集卡总等待时间；式(2)～(4)保证各场桥顺次作业各计划箱的完成时刻大小关系，且场桥对主计划箱的提箱作业在对应集卡就绪后进行；式(5)～(7)保证实线框外的所有计划箱均被某一场桥作业一次；式(8)～(9)表示变量Whv为1时实线框h中节点集合v的到达边大于1，否则其到达边为0；式(10)～(13)保证各实线框内仅有一个节点集合被遍历，且该节点集合内的所有计划箱均被某一场桥作业一次；式(14)～(16)保证各场桥均以对应的场桥节点作为起点，并满足起点的图论约束；式(17)～(18)保证终点满足图论约束；式(19)保证各栈位的计划箱由场桥从上至下依次作业；式(20)保证主计划箱按集卡到达顺序由场桥依次完成提箱作业；式(21)～(22)表示场桥间作业完成时刻大小同变量Cijkk′间的对应关系；式(23)～(24)表示场桥间作业时间是否发生冲突同变量Eijkk′间的对应关系；式(25)～(26)表示场桥间是否作业时间发生冲突且不满足安全距离同变量Gijkk′间的对应关系；式(27)～(28)表示在不满足现实约束的条件下，场桥作业先后次序同变量Pijkk′间的对应关系；式(29)～(30)保证各计划箱作业完成时刻的取值；式(31)保证各场桥的作业范围；式(32)～(35)保证不同内集卡等待时间下，带有惩罚因子的等待时间取值；式(36)保证变量范围。
2.4 下界
本文首先给出近似衡量算法有效性的下界1，即考虑主计划箱均可在集卡就绪后直接进行提箱作业(不考虑压箱)。下界1存在的必要是：无论何种规模均可给出下界。考虑到下界1的精确性，本文在原问题基础上松弛场桥间保持安全距离及不可跨越约束，并将同贝同栈情况合理转化，原图论问题转化为新图论问题(下界2)如图3所示。
图3 下界2图论问题
对本文提出的下界2做简要说明。本文在原问题基础上松弛了场桥间保持安全距离及不可跨越的因素，将解空间进行放大，下界2解空间是原问题解空间的子集，使得下界2最优解必位于原问题最优解之下或与之相同；同时，同贝同栈情况被合理转化，保证转化后作业全部箱所需的总时间变少或不变，因此本文给出下界2最优解一定是原问题最优解的下界。
参数定义为：QTi为i箱对应集卡就绪时刻，不为主计划箱节点时取M；Dij节点(i,j)间距离；Bj为i箱作业时间，不为箱节点时取0；M充分大正数；C内集卡惩罚因子；ξ内集卡等待上限；n计划箱数；Q计划箱节点集合；F所有节点集合；P场桥节点集合；R子计划箱节点集合；m场桥数；Zi若第i号节点为主计划箱节点取1，否则取0。
变量定义为：FTi第i箱完成时刻，若非箱节点则取非负；Xij由节点i移至节点j时取1，否则取0；Ahi衡量节点i惩罚因子取值，h取1或2分别对应两种惩罚情况；TTi为i箱对应内集卡带有惩罚因子的等待时间。
(37)
s.t.FTj≥Dij*Xij+FTi-(1-Xij)*M+Bj,i,j∈F
(38)
FTj≥QTj+Bj-(1-Zj)*M,j∈F
(39)
FTk=0,k∈P
(40)
Xii=0,i∈F
(41)
(42)
(43)
(44)
(45)
(46)
FTi≤FTi+1,i∈R
(47)
(48)
FTi-QTi-ξ≤(1-A1i)*M,i∈F
(49)
A1i+A2i=1,i∈F
(50)
TTi≥FTi-QTi-(1-A1i)*M,i∈F
(51)
TTi≥(FTi-QTi)*C-(1-A2i)*M,i∈F
(52)
TTi≥0,FTi≥0,i∈F
(53)
式(37)目标函数为带有惩罚因子的内集卡总等待时间；式(38)～(41)保证场桥作业连续性，且内集卡提箱作业在其就绪后进行；式(42)～(44)保证各起点及箱节点的图论约束；式(45)～(46)保证终点的图论约束；式(47)～(48)保证各箱节点间的作业约束；式(49)～(52)保证不同集卡等待时间下，带有惩罚因子的等待时间取值；式(53)保证变量的取值范围。
3 混合和声模拟退火算法
考虑到CPLEX仅可在小规模算例时对调度模型进行求解，本文设计了混合和声模拟退火算法(简称HAS算法)，即以SA算法为基本框架，融入HS算法中记忆库(HM)及群体操作思想。同进口箱堆场相比，由于船舶配积载图事先已知，出口箱堆场内的主计划箱提箱次序固定，鉴于此本文设计了和声修复策略；同时，为有效提升算法性能，设计了随温度而变化的动态参数。
3.1 HAS算法流程
本文HAS算法流程如图4所示，HM中包括M个个体，且每次迭代产生M-1个个体，同HM中M-1个非最优个体按Metropolis接受准则取舍，并记录全局最优解。
图4 算法流程图
3.2 解的编码
本文解的编码采用浮点与整数编码结合策略，具体解的编码片段如图5所示。其中前段和声为主、子计划箱被分配作业的顺序(各箱按主计划箱及其子计划箱所在层位从上至下依次标号，如1.1、1.2、1.3 等)，后段和声为各箱作业时所对应场桥的序号。
以图5的某个体片段为例对解的编码做简要说明，首先，本文中每个标号均对应一个集装箱，但一个集装箱可能具有多个标号(如多主计划箱位于同贝同栈)。其次，本文解的编码中各标号(集装箱)的排序按其开始作业顺序先后排序，如图5中的3.1一定在1.2之前作业。最后，前段和声同后段和声长度相同。
3.3 初始化HM及随机生成
本文初始化HM及随机生成策略相同，为保证产生个体的可行性，设计了产生M个个体的步骤如下：
步骤1初始化，个体数k=1，主计划箱的次序数i=1；
步骤2依次生成第1个作业次序i.j，其中j=1,2,…,G(i)+1，G(i)为i箱的压箱数；
步骤3令i=i+1，依次生成第i个作业次序i.j，其中j=1,2,…,G(i)，并将第i个作业次序随机插入至第1个作业次序中；之后，将i.j置于第1个作业次序的最后，其中j=G(i)+1，
图5 解的编码示意图
步骤4若i小于主计划箱数，则转至步骤3；否则，转至步骤5；
步骤5将更新后的第1个作业次序作为第k个个体的前段和声序列；同时，第k个个体后段和声的场桥序列随机生成，转至步骤6；
步骤6令k=k+1，若k≤M，则令i=1，转至步骤2；否则，结束。
3.4 和声微调
本文新个体产生涉及三种方案，分别为和声微调、最优微调(对全局最优和声微调)以及随机生成和声。本文和声微调采用四种单亲变换策略，分别是两点互换策略、正向移位策略、反向移位策略以及逆序变换策略。考虑到前段和声同后段和声的微调策略是分开进行的，本文以某前段和声片段为例对四种策略做简要说明如图6所示。
从图6可以看出和声微调的四种策略均可能使原个体变为不可行，需引入和声修复策略。其次，前、后段和声有某种联系，如各箱因其所在位置不同，而仅可由特定场桥作业，因此仅由前段和声进行四种策略，会降低最优解产生的概率。综上，考虑到迭代初期和声前后段的关联度较低，而在后期和声的前后段关系基本形成。本文在算法后期引入“最优微调”策略，包括上述图6中前三种策略，且“最优微调”均为前、后段和声同时进行变换策略。
图6 和声微调策略示意
3.5 和声修复
针对各主计划箱及其子计划箱间作业顺序约束、各主计划箱间作业顺序约束，本文设计了和声修复1；考虑场桥间保持安全距离以及不可跨越因素，本文设计了和声修复2(注：在算法中适应度计算部分也会考虑场桥间现实约束，和声修复2起辅助作用)。
3.5.1 和声修复1
考虑到各箱间的作业约束同场桥序号无关，和声修复1仅针对前段和声而进行。以某一新个体为例，具体和声修复1(包括两部分)的步骤如下：
(1)和声修复1的第一部分
步骤1初始化，令i=1，j=1；
步骤2提取个体前段和声第j位箱；
步骤3若其为第i个主计划箱或其子计划箱，则将第j位箱记录到临时信息矩阵中，对应其位置j记录到临时位置矩阵中；否则不记录；令j=j+1；
步骤4若j大于前段和声长度，则转至步骤5；否则转至步骤2；
步骤5将临时信息矩阵中的信息升序排序后，依次按临时位置矩阵的原位置替换到原和声中；清空临时信息矩阵、临时位置矩阵；
步骤6令i=i+1，若i大于主计划箱数n，则结束；否则，令j=1，转至步骤2。
(2)和声修复1的第二部分(对第一部分修复后的个体进行再次修复)
注：临时“前段和声”为零向量。
步骤1初始化，令j=L，m=L，k=n(其中L为前段和声长度，n为主计划箱数)；
步骤2提取个体第j位的箱，若该箱是子计划箱，则转至步骤3；否则转至步骤4；
步骤3令临时“前段和声”的第m位等于个体前段和声第j位的箱，m=m-1，j=j-1，若j<1，则转至步骤7；否则转至步骤2；
步骤4若该箱是第k个主计划箱，则令k=k-1转至步骤3；否则转至步骤5；
步骤5若k大于第j位箱对应的主计划箱号，则转至步骤6；否则，令j=j-1，若j<1，则转至步骤7；若j≥1，转至步骤2；
步骤6记录X为第j位箱所对应的主计划箱序号与k的差值，依次产生第k个至第k-X个主计划箱，并依次放入临时“前段和声”中，令k=k-X-1，m=m-X-1，j=j-1，若j<1，则转至步骤7；否则，转至步骤2；
步骤7将个体的前段和声更新为临时“前段和声”。
3.5.2 和声修复2
本文的场桥相关约束，需在和声修复中进行有效的限制，具体和声修复2步骤如下：
步骤1初始化，令p=1，j=1+L(其中L为前段和声长度)；
步骤2提取第p个和声第j位场桥序号，记录场桥序号z；
步骤3若第p个和声第j-L位箱所在的贝位，属于第z号场桥作业范围，则转到步骤5；否则，转到步骤4；
步骤4将第p个和声的第j位场桥序号随机更新为可服务此计划箱的场桥序号；
步骤5令j=j+1，若j>2×L，则转到步骤6；否则，转到步骤2；
步骤6令p=p+1，若p大于和声总个数，则结束；否则，转到步骤2；
3.6 动态参数的设定
本文对HMCR、PAR两个参数进行了改进，引入了随温度而变化的动态参数，使算法在不同的搜索时期发挥出不同的搜索性能。通过多次实验对比后，对参数HMCR采用反比例曲线Y=k/(x+b)+a,(k>0,b>0)进行改进，使HMCR由0.6向0.9快速收敛，以增加算法初期的全局搜索能力，和算法中、后期的局部搜索能力。对参数PAR采用Logistic曲线：Y=1/(K+a*bx),(a>0,0
HMCR=179.982/(Tk+199.97)
(54)
(55)
3.7 适应度评价
适应度评价见公式(56)～(57)示。
(56)
(57)
公式(56)～(57)中，QWi为惩罚因子的取值；FTi为第i个内集卡提箱完成时刻；QTi为第i个内集卡计划提箱时刻；ξ为内集卡等待上限；C为等待时间超过等待上限的惩罚值；Xk为第k个个体；Fitness(Xk)为第k个个体的适应度；n为主计划箱数。
4 数值实验
4.1 方案有效性实验
(1)算例原始数据
在出口箱堆场某箱区中，已知计划期内(据天津港等地的实地调查数据可知，场桥作业计划约1h滚动一次，故本文取计划期为1h)内集卡的提箱信息如表1中原始数据一栏所示。场桥相关信息如下：跨距6栈，堆垛高度5层，移动时间0.1分/贝，装载任务3分，倒箱需2分，作业安全距离3贝。结合港口实地调查数据以及适应度评价公式的特点，取内集卡等待上限ξ为10分、惩罚因子C为10。
(2)算例求解
文中算法的相关参数取值如下：(降温系数，内循环次数，初温，终温，记忆库大小)=(0.96，30，100，0.01，5)，所有的实验都运行在3.10GHz Intel Core 2 CPU 和4GB内存的双核计算机上，采用MATLAB R2014a编码。经计算，本文提出的HAS算法搜索过程如图7所示，搜索到5800代左右时，目标收敛于45.5分，求解耗时121.29秒；场桥实时行走路径如图8所示，可以看出，场桥路径无交叉点且始终保持安全距离。
图7 收敛图
图8 场桥实时行走路径
表1 方案对比表
任务原始数据HAS方案RHA方案FCFS方案到达时刻贝栈层压箱数完成时刻等待时长完成时刻等待时长完成时刻等待时长1224215.23.275752664119312.46.4115391231012312314.65.64148440173173173517543220.33.324724.37.361914541223245245723942126329.46.429.56.58271552230334737.110.19321051135337537510381344141343543511434441463485485124713321503525525135172325435875871455923158363.48.463.28.21557342060361.44.466.89.8目标值
为验证本文方法得到场桥作业方案的有效性，分别同采用先到先服务方案和不考虑实时预倒箱的郑红星等[22]中的方案(在该文中，目标函数基本一致，不涉及内集卡时同本文问题相同)进行对比分析，如表1所示。可以看出，FCFS方案的目标值最大，内集卡作业总等待时间最长，且有一个内集卡超过等待上限；不考虑实时预倒箱的RHA方案效果居中，无内集卡超限，较FCFS方案好，但是改进有限；本文给出的HAS方案效果最好，总等待时间较RHA方案降低44.92%，同下界1的相对偏差为1.11%。
表2 调度模型的CPLEX求解结果
4.2 算例求解
本文通过CPLEX Studio IDE 12.5对原调度模型进行编码求解，随机生成了30个算例，考虑小规模下2、4、6、8、10个主计划箱和5个压箱以及大规模下12、14、16、18、20个主计划箱和10个压箱(考虑出口箱堆场作业实际，在1h内单台场桥最大作业箱量应少于20)。其中，各主计划箱的位置均随机生成，对应贝号、栈号和层高分别为区间[1,16]、[1,6]和[1,5]内的随机整数；同时，各主计划箱的就绪时刻按经验分布给出，其上的压箱数为[1,4]内的随机整数，得到的结果如表2所示。
从表2可以看出，CPLEX的求解时间随着问题规模的增大呈指数型增长，且当规模为Ins6_5_2时出现求解时间超过1小时的情况。这主要是由于原调度问题出现了多主计划箱位于同贝同栈的情况，由图论转化规则可知，转化后的图论点数呈跳跃式增长，无法在合理的时间内给出最优解，故针对6个主计划箱及以上的情况应采用启发式算法进行求解。
4.3 算法的有效性实验
(1)不同规模下的算例比较实验
为验证HAS算法的有效性，结合4.2中的实际算例，给出算法对比如表3所示。针对每一算例，将本文HAS算法目标值同下界进行对比分析。从表3中可以看出，在小规模算例下，目标值同下界1的平均相对偏差为4.88%，同下界2的平均相对偏差为0.35%，说明本文提出的HAS算法在小规模算例下具有优良的计算效果。在大规模算例下，目标值同下界1的平均相对偏差为9.13%，同下界2的平均相对偏差为4.16%；而在最后6个算例下，目标值同下界1的平均相对偏差依然控制在10.1%，说明本文提出的HAS算法在大规模算例下依然可以找到近似最优的满意解，验证了算法的有效性。从求解耗时来看，在个别算例中存在突变点，这主要是由于算例中出现了多主计划箱位于同贝同栈的情况，增加了算法的求解耗时，求解耗时整体上呈线性趋势增长，说明算法在不同规模下仍具有较好的稳定性。
表3 算法对比表
(2)不同压箱量的算例实验
针对每组算例，采用本文提出的算法进行求解，对比求解耗时和目标值的增长速度。
从表4可以看出，在15个算例中，目标函数值和求解耗时都随着压箱量的增加而增加。目标值于压箱量从20到25时有一个拐点，这是由于在压箱量为25时，随着主计划箱及提箱时刻分布的不同，内集卡可用于预倒箱的空闲时间逐渐减少，导致个别内集卡超限。而求解耗时增加较为平缓，表明算法求解时间相对稳定，没有随压箱量的增加而成指数型增长。
5 结语
考虑现实约束，侧重作业过程中的实时预倒箱，本文构建了集装箱码头出口箱堆场多场桥调度的混合整数规划模型，揭示了实时预倒箱对堆场系统作业效率的巨大影响。针对CPLEX求解调度模型时存在的问题，本文设计了融入多种改进策略的HAS算法对模型进行求解。为验证算法的有效性，文中给出了调度问题的两个下界。数值实验表明，此方法可较好地解决集装箱码头出口箱堆场的多场桥调度问题。
表4 不同压箱量对比表
未来研究可拓展为内集卡、场桥和岸桥集成调度中的实时预倒箱问题。
