自动化集装箱码头动态堆场堆存策略研究

梁承姬 刘 浩 张 悦

(上海海事大学物流研究中心 上海 201306)

0 引 言

由于人工成本的快速增长和大型化船舶的发展，码头的堆场面积却相对有限，越来越不能满足日益增长的集装箱装卸的需求，这就需要提高堆场的堆存效率，堆场的自动化就成为越来越多的学者开始研究的重点领域。本文以2017年开始运营的上海洋山港四期全自动化集装箱码头为研究背景，探索自动化集装箱码头堆场堆存问题。

目前国内外对堆场堆存计划的研究大多数是针对传统集装箱码头的。文献[1]将出口箱的堆存问题分为两个阶段：第一阶段是根据堆场不同箱区贝位的数量来分派出口箱的位置；第二阶段是确定每个箱区的容量来决定出口箱的堆存位置。王璐玺[2]采取群智能算法求解集装箱堆场中场桥的路径优划问题。文献[3]提出了堆场堆存中同时考虑空间分配和堆场起重机调度的综合优化模型。文献[4]对堆场运营操作进行了深入的综述，提出了堆场作业分类方案。李坤等[5]研究卸载集装箱堆场空间分配与车辆调度的集成作业问题，通过将禁忌搜索算法的结果同CPLEX所求得的最优解进行比较。魏航[6]构建了码头方补助金函数与车辆方的成本函数，建立了取箱时间窗优化模型，并设计了求解的遗传算法。邵乾虔[7]将场桥资源配置与集卡预约系统进行集成优化，旨在提升堆场作业效率的同时平衡码头作业分布。武慧荣等[8]以箱区作业量均衡为目标对集装箱海铁联运港口混堆堆场的箱区分配问题进行研究。文献[9]引入一种新的集装箱堆放/储存创新手段，作为克服集装箱堆场空间不足的潜在解决方案。文献[10]建立基于0-1混合整数规划的堆场集装箱堆场多目标优化模型，提高其效率。文献[11]研究一种集装箱堆场的配置，提出了集装箱堆场详细模拟系统的方法。郑红星等[12]考虑问题自身的特点并设计了基于任务排序的染色体结构,用融入禁忌搜索的混合遗传算法进行求解。

对自动化集装箱码头堆场的研究还比较少。罗勋杰等[13]对国外典型自动化集装箱码头堆场在平面布置、设备选型和功能规划等方面分析的基础上，提出洋山四期全自动化集装箱码头堆场布局新模式。魏晨等[14]考虑双起重机时空同步约束条件，以最小化任务完工时间为最优目标，构建双起重机混合调度整数规划模型。梁承姬等[15]把堆存计划作为一个具有时间和空间维度的网络优化问题来研究，提出一种基于网络流的自动化集装箱码头堆场空间动态分配模型，并采用禁忌搜索算法来求解。

自动化码头的箱区比传统码头的箱区大，一般一个大箱区包含若干各个子箱区，每个箱区一般堆存大约6 000个TEU，而传统码头箱区一般只堆存了大约2 000个TEU，再加上考虑混堆等因素，如果箱区间的箱量不平衡，势必会影响场桥的衔接调度的任务量的不平衡，因此自动化码头的堆存策略对提高堆场整体装卸效率起到关键的作用。本文基于效率较高的混堆模式，全面考虑进出口箱的四种类型，提出混堆模式下自动化集装箱码头堆场空间资源优化配置的方法。在考虑箱区平衡的前提下，以最小化泊位和堆场的运输距离为目标函数，构建整数规划数学模型，采用遗传算法进行计算，并将求解后的结果和粒子群算法求得的结果进行对比分析。结果表明，两者都能够求出最优解，两者的最大误差不超过5%，但是采用遗传算法求解的时间更短，具有更好的收敛性。自动化集装箱码头堆场布局示意图如图1所示。

图1 自动化集装箱码头堆场布局示意图

1 问题描述

堆场空间动态分配问题是指为随机进入堆场的进口箱和出口箱分配相应的箱区位置。动态是指各时刻各箱区的可用空间会随着集装箱装卸船作业和进出场作业等持续变化。所以，堆场空间的动态分配问题是一个复杂而且持续的过程。根据以往对堆场空间动态分配的研究来看：大多数以滚动计划法为主，在考虑堆场分配计划时，不但要考虑当天的进出场箱，而且要考虑未来几天甚至一周堆场内的进出箱数量。

在集装箱港口生产调度中，最重要的是作业路调度，其次是集卡调度和场桥调度，后两个由第一个引发。这里的作业路是指港口为船开通的岸桥。本文根据集装箱的作业状态，将集装箱大致分为4大类，如图2所示。其中，D型箱和G型箱是本文研究的重点。在本文中，D型箱和G型箱的堆存方法都考虑了“作业路”的影响，并且是阶段性连续制定，即前一时段提前考虑好下一时段D型箱和G型箱的堆存计划。

图2 集装箱分类

由于目前航运市场的慢慢回暖，船舶大型化越来越普及，同时运输的集装箱数量也在不断增长，同样给船舶服务的各作业路的集装箱任务量也在不断倍增，所以在制定堆存策略时需要考虑尽量平衡集装箱在堆场中的堆放位置，避免过于分散和集中。

自动化码头堆场箱区比较大，箱区海侧与陆侧的距离很远，为了提高研究的准确性，需要继续划分为若干个子箱区。本文的堆场堆存计划主要考虑多条作业路多条船舶的集装箱任务分配，按照同一船舶的不同作业路的集装箱分配到不同箱区的规则，并且让集装箱分配的箱区保持均衡，即“既集中又分散”，这样可以减少装卸集装箱的AGV过于拥挤，又避免太分散而消耗成本。本文已知的输入数据包括各阶段各船舶装卸作业路的任务量，各阶段各子箱区的可用容量和各阶段离开各子箱区的进出口箱数量等。根据这些已知数据来决策各阶段各船舶作业路的集装箱任务量，以及分配到各子箱区的集装箱数量。

2 模型建立

针对上述问题，本文模型的建立实现了箱区和箱区之间总作业量平衡优化，均衡分配各箱区中4种箱型的任务量，目标是最小化各个集装箱在泊位与堆场箱区之间运输距离，从而间接提高堆场装卸效率。

2.1 模型假设

(1) 船舶进港预靠泊位和分配的作业路数已知。

(2)决策期内计划时段t进出场的集装箱必须在该时段内完成堆存任务。

(3)船舶各时间段各作业路内要完成的进口箱组数量和出口箱组数量已知。

(4)所有进出口集装箱统一尺寸定为20英尺。

2.2 模型参数定义

T决策期为1天，每个决策期内所有的计划时段数，每个计划时段用t表示，每8个小时作为一个计划时段，则T=3(t=1,2,3);

B堆场内要均衡的箱区总数;

S决策期内进口箱所属的船舶数量;

V决策期内出口箱所在的船舶数量;

P作业路数，即岸桥数;

O子箱区数量;

i箱区编号，i=1,2,…,B;

h子箱区编号，h=1,2,…,O;

r作业路，r=1,2,…,P;

Cih箱区i中子箱区h的可用容量;

M一个尽可能大的数;

Gihtk计划时段t卸到箱区i子箱区h，t+k时段装船的出口箱任务数量，其中k≥t,t=1,2,3;

Dihtk计划时段t内卸到箱区i子箱区h，t+k时段运走的进口箱任务数量，其中k≥t,t=1,2,3;

Dihjt计划时段t从船舶j卸载至箱区i子箱区h的进口箱任务箱量;

棉织物以良好的吸湿性，透气性和穿着的舒适性，深受大众喜欢。为了追求时尚，生产商会制造出各种独特风格的棉产品，这就需要对棉织物染色。传统的染色工艺流程先纺纱接着织布再染色，新型的染色工艺流程为先染棉条接着纺纱再织布[1]。两者相比，后者色差小，节约水电，污染小，同时可以缩短生产周期。纺纱时可以采用有几种颜色棉不同比例混配，满足消费者对色彩多元化的需求。

Gihlt计划时段t进场至箱区i子箱区h船舶l的出口箱任务箱量;

Lihjt计划时段t内，箱区i子箱区h内所有的L型箱任务数量;

Pihjt计划时段t内，箱区i子箱区h内所有的P型箱任务数量;

Gihj(t-k)决策期开始时已分配到箱区i子箱区h并在计划时段t被运走的出口箱任务数量;

Dihj(t-k)决策期开始时已分配在箱区i子箱区h并在计划时段t被装船的进口箱任务数量;

Wiht计划时段t内，箱区i子箱区h的集装箱装卸任务作业量;

Vihjt计划时段t结束后，箱区i子箱区h内所有箱型总数量;

Mihjt决策期开始前已卸载到箱区i子箱区h并在计划时段t被运走的出口箱任务数量;

Nihjt决策期开始前已装载在箱区i子箱区h并在计划时段t被装船的进口箱任务数量;

Xij船舶j预靠泊位与箱区i海侧的距离;

Xihj船舶j经箱区i海侧与箱区i子箱区h的距离;

Xil船舶l预靠泊位与箱区i海侧的距离;

Xihl船舶l经箱区i海侧与箱区i子箱区h的距离;

Dihjrt计划时段t从船舶j第r条作业路卸载到箱区i子箱区h的进口箱任务数量,其中t=1,2,3;

Gihltk计划时段t进场至箱区i子箱区h,计划时段k装载到船舶l的出口箱任务数量,其中t=1,2,3;

Ejrt计划时段t出场，从船舶j第r条作业路的进口箱最多堆存的箱区数量;

Elt计划时段t进场，船舶l的出口箱最多堆存的箱区数量。

2.3 决策变量

Dihjrtk计划时段t从船舶j第r条作业路卸载至箱区i子箱区h，计划时段k被取走的进口箱数量;

Gihltk计划时段t进场至箱区i子箱区h，计划时段k装载到船舶l的出口箱数量;

aihjrt计划时段t从船舶j第r条作业路卸载至箱区i子箱区h，决策期外被取走的进口箱数量;

bihlt计划时段t进场至箱区i子箱区h，决策期外装载到船舶l的出口箱数量;

S1ihjrt=1，表示计划时段t从船舶j第r条作业路卸载的进口箱堆存在箱区i子箱区h中，否则为0;

S2ihlt=1，表示计划时段t从船舶l进场的出口箱堆存在箱区i子箱区h中,否则为0。

2.4 模型构建

目标函数：

(1)

约束条件：

(2)

(3)

(4)

(5)

(7)

Vihj(t+1)=Vihjt+[(Gihjt+Dihjt)-(Pihjt+Lihjt)]

i=1,…,B;t=1,…,T;j=1,…,S

(8)

Vihjt≤ηCihi=1,2…B;h=1,…,O;

t=1,…,T;j=1,…,S

(9)

(10)

Dihjrt≤M·S1ihjrt∀i,h,j,r,t

(11)

(12)

Gihlt≤M·S2ihlt∀i,h,l,t

(13)

(14)

S1ihjrt、S2ihlt为0,1变量，Dihjrtk、Gihltk、aihjrt、

bihlt为非负整数

(15)

在模型中，式(1)是目标函数，由两部分之和组成，第一部分是进口箱到堆存箱区海侧的距离和箱区海侧到堆存箱区子箱区的距离之和，第二部分是出口箱箱区海侧到泊位的距离和出口箱箱区海侧到子箱区的距离之和。

约束式(2)表示在t时段卸下的集装箱在t+k时段被取走的D型箱的数量等于分派到各箱区的D型箱的数量总和。约束式(3)表示在t时段到堆场在t+k时段被取走的G型箱的数量等于分派到各箱区G型箱的数量总和。约束式(4)表示在t期内分派到箱区i子箱区h第r条作业路卸载的D型箱的数量等于在t期内分派到同一箱区，在T期内被取走的第r条作业路卸载的D型箱数量与计划期外取走的数量之和。约束式(5)表示在t时期到堆场分配到箱区i子箱区h的G型箱的箱量等于在t时期内分配到同一箱区，在T期内被取走的G型箱量与计划期外取走的箱量之和。约束式(6)表示在箱区i子箱区h在t时期装船的L型箱量由两部分组成：(1)在t时期开始时已经分派好的出口箱；(2)由在t期前已经到达的出口箱，在t期装载至船舶的G型箱转化而来的。约束式(7)表示在箱区i子箱区h中在t时期提走的P型箱数量由两部分组成：(1)在t时期开始时已经分派好的进口箱数量；(2)由在t时期前到达的进口箱数量，在t期卸载至船舶的D型箱转化而来的。约束式(8)表示箱区中4种类型总箱量的更新。约束式(9)表示箱区中四种箱型的总箱量不能超过其能容纳的最大容量。约束式(10)表示计算箱区i子箱区h在每个时间段内作业的进口箱和出口箱数量。约束式(11)是判断船舶j计划时段t第r条作业路卸载的进口箱是否堆存在箱区i子箱区h，若堆存则为1，否则为0。约束式(12)表示计划时段t船舶j第r条作业路卸载的进口箱所需箱区总数不大于该时段堆场能给的最多箱区数。约束式(13)是判断计划时段t进场的船舶l的出口箱是否堆存箱区i子箱区h，若堆存则为1，否则为 0。约束式(14)表示计划时段t进场的船舶l的出口箱所需的箱区总数不大于该时段堆场能给的最多箱区数。约束式(15)是整数条件约束。

3 遗传算法求解

文中提出的堆存问题涉及船舶和作业路，其中作业路在问题描述中有提到，把经过一台岸桥处理的装卸集装箱称为一条作业路。在这里利用矩阵式编码的方式表示自动化码头堆场堆存问题。假设有两艘船舶，当前有5个(Y1，Y2，Y3，Y4，Y5)可用子箱区，用3条(r1,r2,r3)作业路去进行装卸集装箱任务。各时段作业路任务量和各子箱区容量变化分别如表1和表2所示，染色体编码如表3所示。染色体中的每个基因表示船舶在每一时段内经过每条作业路处理后的集装箱堆存在各个子箱区的数量，每一行的基因之和表示各艘船舶各时段内在各条作业路处理后的集装箱堆存到堆场的数量总和。而各个子箱区堆存的集装箱数量不能超过各时段内各个子箱区的最大可用容量。根据子箱区数量对染色体进行编码，把分派给各个子箱区集装箱数量进行适应度值计算，然后对计算后的适应度值进行不断比较，最后取最大的适应度值为目标函数。

表1 各时段作业路任务量

续表1

表2 各子箱区容量变化

表3 染色体示例

因为各条作业路可以处理任意一个装卸箱任务，为了提高计算的有效性和最优值，交叉操作遵循单点交叉原则，起初生成一个随机列，按照得到的不同序列，将序列中相邻编号的基因值进行两两交叉。变异操作的方法是将染色体中第i行中任意两行的基因值进行互相交换。

交叉操作的具体做法是：选择2条父代染色体，随机产生任意1个切点，交换切点位置的子箱区编号，得到子代染色体。如图3所示。

图3 交叉操作示意图

因为染色体编码的特殊性，同时考虑到子箱区容量的限制，交叉变异后的染色体必须进行修复，具体方法如下:

(1) 判断各子箱区是否满足只堆放船舶的一条作业路或不堆放船舶任一条作业路的集装箱这一条件，若满足，则跳到(2)；若不满足，把船舶所有作业路r中在该子箱区中除最大基因值以外的其他基因值随机分派到其他的箱区。

(2) 将染色体中第i行的基因相加，若满足船舶作业路在该时段装卸船的集装箱数量总和与基因值之和的差值小于0这一条件，跳到(3)；若不满足条件，跳到(4)。

(3) 若将第j列加上差值后的基因之和仍然不大于船舶作业路在该时段装卸的集装箱数量，那么该位置的基因值再加上一次差值；若还是不满足条件，令第i行中最下面的基因值那一列加上0到差值之间任意值。

(4) 若第j列减去差值后的基因之和大于0，那么该基因值需要减去差值。若不符合条件，把第i行中基因值最大的那一列基因值减去0到差值之间的任意值，直到符合条件。

(5) 将染色体中各个子箱区各个时段堆存的集装箱数量进行相加，如果集装箱数量之和大于该时段子箱区的可用容量，跳到(6)；若不满足条件，结束修复。

(6) 若第j列大于子箱区可用容量，把该时段中最大基因值所在列的基因值全部减去差值，并把该行其他列中的最小基因值全部加上差值。

4 算例分析

在进行模型求解时，将模型中的相关约束和目标函数用遗传算法进行编码，求解得出结果。由于上海洋山港四期全自动化集装箱码头还处于刚开始运营的状态，各项数据还不是特别齐全，因此算例的数据主要来自实际项目研究的结果。因为自动化集装箱堆场箱区比较大，箱区海侧与箱区陆侧之间的距离很长，因此需要划分若干个子箱区，分别考虑泊位到海侧的距离和每个箱区海侧到子箱区的距离，数据规模为：船舶数量为10条船，装卸作业路数量为36条，其中4条船有出口箱任务，箱区数量为3，子箱区数量为9。

具体的输入数据，船舶出口箱的作业信息如表4所示，船舶进口箱的作业信息如表5所示，初始计划阶段各子箱区可用容量如表6所示，泊位与各箱区海侧的距离如表7所示，各箱区海侧与子箱区的距离如表8所示。在一台装有Window 7的64位操作系统的个人电脑进行处理。

表4 船舶出口箱作业信息

表5 船舶进口箱作业信息

表6 初始计划阶段各子箱区可用容量 TEU

表7 泊位与各箱区海侧的距离 m

表8 各箱区海侧与子箱区的距离 m

4.1 模型求解

具体的计算结果如表9、表10、图4和图5所示。

表9 出口箱船分配结果

表10 各船舶在各时段分配到各子箱区的箱量

续表10

图4 各阶段的子箱区工作量分布图

图5 GA的收敛图

为了验证遗传算法的有效性，本文设计了10个案例，船舶数量从2到20艘，箱区从4到22个，作业路从3到7条的码头布局，分别使用PSO算法和遗传算法计算不同的案例，并通过对不同规模数量的案例结果进行比较，GA和PSO的计算结果如表11所示。

表11 不同案例的PSO和GA计算结果的比较

4.2 结果分析

从图4可以看出，在同个时间段内作业的进口箱和出口箱能够均衡地分配到堆场的各子箱区中，各个时间段内各个子箱区的作业量差距比较平缓，并且各个箱区能够满足同一时间段内进口箱和出口箱的差值最小，符合自动化集装箱码头堆场的“重进重出”。从表11可以看出，通过GA和PSO对模型进行算例求解，并且通过对不同规模数据的算例分析，采用GA和 PSO对比的方法，两者求出的目标函数值非常接近，而且随着数据规模的扩大，两者的目标函数值越来越接近。然而 GA的求解时间更短，具有更好的收敛性，更快速地得到最优解，进一步验证了GA在较大数据规模上有显着的效果。同时对相同规模案例计算结果的对比，观察通过 GA和 PSO计算，两者平均有3%左右的误差。研究表明，本文中提出的模型，通过遗传算法的求解，可以满足较大作业量的自动化集装箱码头堆场装卸要求，有效地改善堆场空间分配问题。

5 结 语

自动化码头堆场装卸调度问题越来越成为国内外研究的热点问题，合理的堆存策略有利于提高码头的装卸效率，节约码头的日常作业资源，提高码头竞争力。文中研究基于平衡各子箱区工作量的堆场堆存问题，不仅考虑了相邻子箱区之间的工作量平衡，还考虑了整个堆场箱区总的作业量。根据各子箱区容量的实时变化来安排作业调度计划，并通过遗传算法来进行算例求解。最后对实际案例进行比较分析，证明了本文模型和算法的高效性和实用性。该模型可以显著提高堆场资源的利用率，有效地为进出口集装箱分配堆场空间，提高堆场工作效率，降低码头作业成本，对于建设绿色智能高效的自动化港口具有重要意义。