考虑时间窗的集装箱港口场桥全局调度优化

梁承姬，黄 帅

上海海事大学 物流科学与工程研究院，上海201306

1 引言

随着经济全球化以及信息技术的不断发展，特别是中国持续推进对外开放以及“一带一路”倡议使得货物贸易需求迅速提升，中国港口得到了快速发展。但伴随着激烈的市场竞争，高效率运作对于港口的作用越来越突显。场桥作为港口的昂贵资源，对堆场物流系统甚至是整个港口物流系统都起着推动作用[1]。高效的场桥调度计划能够使得场桥与其他机械设备资源更好地协调工作，在满足实际约束的情况下尽可能地缩短船舶的在港装卸时间，加快货物的运转周期。

在前期研究中，为了简化问题难度，大多数学者针对单个场桥进行调度优化研究。Ng W C等[2]考虑集装箱任务准备时间不同情况下的场桥调度问题，通过分支界定法对模型求解。Huang等[3]针对单场桥调度问题提出了两种改进最小成本的启发式算法。韩晓龙等[4]分别运用启发式算法和模拟退火算法对单箱区单场桥调度问题进行研究，通过结果对比分析得出模拟退火算法在运算时间和路径优化方面都优于启发式算法。

随着航运业的发展以及信息化技术水平的提高，专家学者开始研究多场桥并行调度问题，考虑了场桥同时作业的安全距离等限制条件。Li Wenkai 等[5]利用滚动时域算法研究单个箱区内多场桥调度问题。Wu Yong等[6]则在文献[5]的基础上，将提箱延迟任务数考虑到目标函数中并用启发式算法进行求解。刘志雄等[7]设计了一种三维坐标表示方法来确定场桥移动过程中的位置，从而利用混合演化算法求解得到最优的场桥转场次数及作业完工时间。梁承姬等[8]研究单个箱区中多台场桥在干扰情况下基于混堆模式的存取箱同时进行的调度问题。邵乾虔等[9]将进口箱场桥作业调度问题分解成场桥路径优化问题和贝内翻箱作业优化问题，建立动态优化模型。Speer等[10]通过仿真模型详细讨论了场桥移动干涉等约束，并提出用分支定界法求解场桥的实时调度问题。初良勇等[11]研究在外集卡预约模式下的多箱区多场桥调度，利用模拟退火算法进行求解，并与实际人工操作对比，从而验证算法的有效性。曹朋亮等[12]考虑了集卡作业面模式下的场桥与集卡联合调度，利用改进遗传算法确定场桥作业量，进而得到优化后的场桥最短行驶路径。初良勇等[13]在文献[11]的基础上设计了基于遗传算法的模型，并与文献[11]的结果对比，验证该方法可以大幅度降低成本。

综上，现有关于场桥调度的文献大部分都是以场桥路径最短或者场桥完工时间最小化为目标。但随着港口信息化水平的不断提高，集装箱港口开始采用外集卡预约模式，这也意味着可以提前确定集卡运输集装箱任务的到达时间和总任务量，集卡与场桥之间的匹配度可以进一步优化，从而提高场桥的作业效率。但是当前很少有文献考虑到了这一因素。因此本文针对多箱区多场桥调度问题，考虑到场桥在箱区内与箱区间作业的干涉约束，根据集卡到达时间（即准备时间），提出了计划时间段和基于集装箱任务组的时间窗，并采用遗传算法求解以场桥移动成本及延误成本最小化为目标的模型。

2 问题描述

后方堆场作为存储或者中转集装箱的场地，在整个码头中处于核心地位。而场桥是堆场中进行集装箱堆取作业的机械设备，其工作效率的高低直接影响到堆场乃至整个港口的服务水平。由于堆场内集装箱装卸任务工作量分布不均匀，场桥需要在箱区间频繁进行移动。而场桥在箱区间的移动和转弯会占用大量的时间和空间，容易导致堆场通道堵塞，进而增加场桥与集装箱任务组之间的相互等待时间。

因此本文提出了计划时间段和时间窗的概念，在考虑场桥移动成本最小的基础上最小化两者相互等待成本，同时考虑到多箱区多场桥作业过程中不可跨越和保持安全距离等现实约束。根据上海某集装箱港口的实际数据，研究在某一个计划时间域内（本文选取4 h）按照各个集装箱任务组的准备时间划分成四个计划时间段：0～60，60～120，120～180，180～240，各个任务组要在其对应的计划时间段内分开完成调度。在每个计划时间段再按各个集装箱任务组的准备时间设计一个时间范围（即时间窗），若场桥在这个时间窗外作业则给予一定的单位时间成本处罚。如图1所示，集装箱任务组最早能被服务的时刻即为其准备时间，最晚被服务时刻是任务组等待时间上限。但集装箱任务组实际开始操作时间则为任务组最早能被服务时刻与场桥到达时刻两者之间的较大值。

图1 集装箱任务组时间窗示意图

3 模型的建立

3.1 模型假设

（1）本文研究的堆场区域如图2所示。

（2）堆场上场桥操作的集装箱都是20 英尺标准集装箱，且按照不同类型不同目的地将同一箱区同一贝位的集装箱作为一个任务组来处理。

（3）所有场桥的工作参数都是相同的，包括移动速度，进行转场作业时的转弯时间，操作集装箱的时间都是固定值。

（4）不考虑由于设备新旧程度不同而可能导致的能耗不同，每台场桥的移动成本相同。

图2 集装箱港口堆场示意图

（5）规定每台场桥初始时刻位于要操作的第一个集装箱任务组贝位，结束所有分配任务后位于最后一个集装箱任务组贝位。

（6）场桥操作完集装箱任务组i 后随即按最短路径移动到下一个任务组j 所处的贝位。

（7）设定场桥在水平方向箱区间的移动距离按贝位差进行计算，在垂直方向箱区间的移动距离按箱区通道和箱区宽度计算。

（8）集装箱任务组的准备时间根据集卡预约时间转变而来，假定其在堆场所处位置都是已知且固定不变的。

（9）本文不考虑每个计划时间段内有未完成的任务情况，即在每个时间段结束时场桥必须完成当前时间段内的所有任务。

（10）每个计划时间段被分配的集装箱数量不能超过任一场桥在该时间段的总工作能力（即每小时场桥最多可处理20个集装箱任务的装卸）。

3.2 集合、参数及决策变量的定义

（1）参数

c,c′：场桥，c,c′∈C；

b：箱区，b ∈B；

k：计划时间段，k ∈K ；

i,j,o：集装箱任务组，i,j,o ∈M ；

pi：集装箱任务组i 包含的集装箱数；

TGk：k 计划时间段内集装箱任务组总数；

Bp：垂直方向中间通道宽度；

Bw：单个箱区的宽度；

l：单个贝位的长度；

u：单个箱区的贝位数；

mi：集装箱任务组i 所对应的贝位；

ni：集装箱任务组i 所对应的箱区；

Tturn：场桥转场作业时2次转弯90°的总时间；

q：场桥操作单个集装箱的时间；

v：场桥移动速度；

W1：场桥移动成本；

W2：场桥到达时间早于集装箱任务组准备时间的单位时间惩罚金额；

W3：超过集装箱任务组等待时间上限的单位时间惩罚金额；

ETi：集装箱任务组i 的准备时间（即集装箱任务组i 最早被服务时刻）；

LTi：集装箱任务组i 最晚被服务的时间上限；

Sic：场桥c 操作集装箱任务组i 的开始时刻；

OTi：集装箱任务组i 的操作时间；

FTi：集装箱任务组i 的操作完成时刻；

MTij：场桥从集装箱任务组i 移动到任务组j 的时间；

dij：场桥从集装箱任务组i 移动到任务组j 的距离；

（2）集合

C：堆场箱区内可工作的场桥集合；

B：堆场箱区集合；

K ：计划域内计划时间段集合；

M ：集装箱任务组集合；

Mk：k 计划时间段内集装箱任务组集合；

Mkb：k 计划时间段内b 箱区的集装箱任务组集合；

Nc：场桥c 操作的集装箱任务组集合；

（3）决策变量

Vcibk：0-1，若在b 箱区k 计划时间段内场桥c 操作集装箱任务组i 则为1，否则为0；

Uijbk：0-1，判断在b 箱区k 计划时间段内的集装箱任务组i,j 是否同时被处理，当FTj≥FTi-OTi且FTi≥FTj-OTi时则为0，否则为1；

xijc：0-1，若场桥c 操作集装箱任务组i,j 且操作顺序为i →j 时则为1，否则为0。

ωic：0-1，若场桥c 操作集装箱任务组i 时则为1，否则为0。

3.3 目标函数和约束条件

其中：

其中：

式（1）借鉴了文献[11]的目标函数，其中第1部分表示最小化场桥的移动成本，第2 部分在第1 部分基础上最小化场桥与集装箱任务组之间的相互等待成本。

本文将集装箱任务组按计划时间段分批次分批量进行作业从而减少场桥在箱区间频繁进行转场作业：约束条件（2）表示在任一时间段内场桥处理的集装箱任务组数；约束条件（3）保证在任一计划时间段内任意一个集装箱任务组只能分配给一台场桥进行作业；约束条件（4）保证任一计划时间段内一台场桥只能同时操作一个集装箱任务组；约束条件（5）保证在任意时刻不同场桥间须保持一定的安全作业距离；约束条件（6）保证任一计划时间段内每个箱区至多有2 台场桥同时工作。在每个计划时间段内再采用时间窗对场桥作业进行约束：约束条件（7）和（8）表示任一场桥进行作业时至多有一个紧前作业和紧后作业；约束条件（9）表示任一场桥进行作业时至少有一个紧前作业或紧后作业；约束条件（10）定义了相关变量之间的关系；约束条件（11）定义了同一场桥处理前后两个集装箱任务组的作业时间关系；约束条件（12）保证任一集装箱任务组等待被操作的时间不能超过等待上限。

4 遗传算法的实现

由于场桥全局调度问题是一个NP 难的问题，在以往的研究中通常采用智能优化算法求解。而针对本文模型特点，遗传算法不仅能将约束条件嵌入算法结构中，解决其高复杂度性，而且能提高在解的空间中的搜索次数，增加搜索到最优解的概率，缩短优化时间。并且根据参考文献[13]有专家学者采用遗传算法进行求解并获得了较好的结果。因此本文考虑使用遗传算法来解决这个问题。

4.1 染色体编码

首先对集装箱任务组和场桥进行编号，根据不同计划时间段划分集装箱任务组，然后将不同时间段的任务组分配给相应的场桥并按照一定的顺序进行场桥调度作业。如图3 所示，本文采用二维整数形式编码，分别用来表示集装箱任务组以及场桥的作业顺序。其中染色体中非0的基因值表示集装箱任务组和场桥的编号，而染色体中的间隔符“0”则将染色体分为4 个部分，从左往右分别表示第1～4 个计划时间段的场桥调度计划。例如第一段染色体表示在第一个计划时间段内场桥1 做任务组9，场桥2 做任务组3，场桥3 做任务组16和5，场桥4 做任务组13，其中场桥3 先做任务组16，再做任务组5。

图3 染色体编码示意图

4.2 生成初始种群

初始种群的产生和选择对算法的实现有很大的影响。通常会采取两种方式生成初始种群：（1）启发式方法；（2）随机生成法。前者虽然能生成更高质量的初始个体，但是容易陷入局部最优解，而后者则有利于初始种群的多样性。因此本文采用随机生成法在满足基本约束条件的情况下生成初始种群，并且规定可行解只是初始种群的一部分，具体规则如下：

（1）对于染色体中集装箱任务组的优先级部分，首先根据每个计划时间段划分集装箱任务组数确定间隔符号“0”的基因位，然后在每个时间段内随机排列被分配的集装箱任务组编号，并且要满足约束条件（3）。

（2）场桥部分则按照各个时间段内的集装箱任务组随机产生可工作的场桥编号，但要保证在该计划时间段内分配给场桥的任务数不能超过场桥的工作能力。

4.3 适应度计算

遗传算法中适应度函数值来评价一个个体（解）的好坏，其直接关系到最终解的质量和搜索效率。本文选取目标函数的值作为适应度值，在计算适应度值时，需要判断是否满足模型中的约束条件：（1）通过设定时间步长，每隔一定的时间间隔确定堆场内场桥所处的贝位，再计算场桥之间是否处于同一箱区以及是否保持一定的安全距离；（2）利用拉格朗日松弛法引入一个很大的正数作为惩罚项来限制每个计划时间段结束时场桥必须完成该时间段内的所有任务组，而对于场桥提前到达或者延误的情况，则分别设置相应的单位时间惩罚金额。

4.4 遗传操作

4.4.1 选择操作

本文采用轮盘赌法进行选择运算，其主要思想是根据每个染色体的适值比例确定该个体的选择概率或者生存概率[14]，将父代染色体和子代染色体按适应度值大小进行排序，从中选择适应度好的个体组成新的种群。

4.4.2 交叉操作

本文采用双切点交叉法，具体步骤如图4所示。其中未交换的染色体片段按映射关系恢复合法性时只针对集装箱任务组，而场桥部分不变更。

4.4.3 变异操作

图4 交叉操作示意图

变异运算是产生新个体的辅助方法，它有助于提高局部搜素能力，同时保持种群的多样性，防止发生早熟现象。本文采用逆转变异法[15]，即在染色体场桥部分中随机选择两点，将其基因值进行对换，这也用于解决染色体中出现场桥之间相互跨越现象。如图5所示，场桥3在去往任务组16作业的移动过程中会与场桥1前往任务组9的途中发生场桥跨越，此时若在保证在该计划时间段内完成所有任务组的前提下，将其换成其他可工作的场桥4，则可把上面的不可行解转化成可行解，从而在一定程度上保持了种群的多样性。但由于染色体中的间隔符“0”没有实际意义，所以规定在变异操作中不能选择“0”基因位进行交换。

图5 变异操作示意图

4.4.4 基因修复

在经过交叉和变异操作以后，可能会产生一些不符合约束条件的染色体，因此需要进行基因修复：

步骤1 在交叉后，若交换的染色体片段正好是“0”基因位，则意味着交叉无意义。因此需要重新生成新的切点。同理在变异操作中若交换的两基因位值相等，也需要重新随机生成交换点。若不存在这种情况则转到步骤2。

步骤2 在交叉变异后，需要判断相邻两个“0”基因位之间的染色体片段中是否满足假设条件（10）。若不满足，则需要将超出场桥工作能力的集装箱任务分配给这个时间段相对任务最少的场桥。

4.5 结束规则

通过以上操作产生的新个体将会替代原先种群中适应度较差的染色体，这个迭代过程持续到最大迭代次数时停止。

5 算例与结果分析

本文采用上海某集装箱港口的实际运营数据进行研究，通过与实际作业情况以及其他算法的优化结果进行对比进而验证上述所提模型和算法的有效性和适用性。运行环境为Intel®CoreTMi5处理器、内存8 GB、硬盘128 GB的个人计算机，使用Matlab2016a运行本文的遗传算法来求解算例。

5.1 输入数据

本文选取该港口堆场中某块区域的6 个箱区进行研究，数据规模为：每个箱区由60 个贝位组成，每个贝位又由6 列组成。为了便于后续计算场桥在箱区间作业的移动距离，本文设定水平方向的中间过道为3个贝位距离，垂直方向的中间过道为2个贝位距离。在计划时间4 小时内处理200 个集装箱任务数量，可用的场桥数量为4 台，每台场桥处理单个集装箱的操作时间为3 min，假定集装箱任务组要在其准备时间后的30 min内被服务[13]，场桥移动成本、场桥与任务组相互等待的惩罚金额等数据在算法主程序中给出，其他输入数据见表1～6。

表1 箱区1任务量数据

表2 箱区2任务量数据

表3 箱区3任务量数据

表4 箱区4任务量数据

表5 箱区5任务量数据

表6 箱区6任务量数据

5.2 结果分析

针对本文模型，在算法中设置了相应的参数：种群大小N=300，迭代次数G=500，交叉概率PC=0.85，变异概率PM=0.2。通过Matlab运行求解，得到遗传算法的结果收敛图，如图6所示。由算法收敛图中可以看到，大约迭代到130 代时得到最终的收敛结果，避免了前期陷入局部解。

图6 GA收敛图

根据本文模型和所设计的算法得到计划时间域内的作业任务分配以及场桥的作业顺序。如图7 是各个计划时间段内场桥调度甘特图，可以看出该结果既满足模型中分配给场桥的任务数不超过其工作能力的要求，也满足每个集装箱任务组在计划时间段结束的约束。

为了更加清楚直观地看到场桥的作业任务顺序，如图8～11所示为各个计划时间段内分配给各个场桥作业的集装箱任务组及其开始时刻和结束时刻，图中的数字分别对应算例中的任务组编号，灰色空白部分则为场桥与集装箱任务组之间的相互等待时间。其中选取集装箱任务组准备时间和场桥到达任务组对应贝位时间这两者中较大的值作为每个任务组开始操作的时间，从而得到每个集装箱任务组的开始时刻，再根据表格里任务组对应的数量得到场桥操作时间和结束时刻。

图7 计划时间域内场桥调度甘特图

图8 计划时间段1内各场桥调度方案图

图9 计划时间段2内各场桥调度方案图

图10 计划时间段3内各场桥调度方案图

图11 计划时间段4内各场桥调方案图

为了进一步验证本文所提模型与算法的有效性，将遗传算法所得结果与实际运营操作进行对比，结果见表7所示。从表7 中可以看出不论是在作业时间还是目标函数值方面，本文采用的遗传算法都使得结果更优化，不仅缩短了场桥作业时间，而且大幅度降低了运营成本。

表7 运算结果对比表

为了验证模型与算法的适用性和稳定性，选取了8个试验脚本，采用遗传算法和粒子群算法分别针对不同规模大小的算例进行试验对比，每个脚本下的目标函数值均采取试验10 次取最优值的方法，CPU 时间取值则为10 次试验结果的平均值，具体结果如表8 所示，其中S 为箱区数，Y 为场桥数，T 为总集装箱任务数。

表8 GA与PSO试验结果对比

从表8 中可以看到，对于场桥全局调度问题，结果表明这两种算法的结果几乎一致。在这八组试验脚本中，每组遗传算法求解得到的解和粒子群算法的解都相差不大，但遗传算法的运行时间相对较快些，并且其收敛速度更快，从而验证了遗传算法在求解本文所提出的场桥全局调度模型时的稳定性和有效性。

6 结语

本文针对某计划时间域内集装箱港口的全局场桥调度问题进行了研究。考虑到场桥作业过程的不可相互跨越和保持一定的安全距离等约束，引入计划时间段和时间窗的概念，以场桥移动成本和场桥与集装箱任务组之间相互等待成本最小化为目标建立了优化模型，并设计遗传算法进行求解，结果表明该模型和算法可以有效解决多箱区多场桥调度中场桥相互干扰和安全距离等问题，并且有效减少了不必要的等待时间，为解决大规模的场桥调度问题提供了科学合理的决策依据。但在实际操作中，场桥的工作效率还受众多不确定因素的影响，例如机械设备故障或者船舶提前进港等情况，因此未来可以考虑不确定因素影响下的集卡与场桥联合调度，从而更加优化集装箱港口的堆场操作。