进口集装箱堆存和翻箱策略两阶段规划模型

游鑫梦 梁承姬 张悦

摘要：为提高进口集装箱提取作业效率，制定合理的堆存策略和翻箱策略，考虑集装箱堆存作业与提取作业的关联性建立两阶段规划模型。从降低期望翻箱率的角度，优化进口集装箱的箱位分配，构建第一阶段箱区贝位分配模型，并采用遗传算法求解。基于第一阶段的箱区贝位分配结果，在提箱顺序已知的情况下，优化障碍箱的落箱位，构建第二阶段提箱优化模型，并设计启发式算法求解。通过算例将该算法与已有算法进行对比，结果表明设计的算法在降低贝内二次翻箱率的效果上更显著，进而表明提出的两阶段规划模型能有效降低翻箱率，提升进口集装箱提取作业效率。

关键词： 进口集装箱; 堆存策略; 翻箱策略; 启发式算法

Abstract： In order to enhance the efficiency of import container picking-up operation and formulate reasonable storage and re-handling strategies， a two-stage programming model is established with the consideration of the relationship between storage and picking-up operations of containers. From the point of view of reducing the expected re-handling rate， the position allocation of import containers is optimized， and the bay-in-block allocation model of the first stage is constructed and solved by the genetic algorithm. Based on the bay-in-block allocation results of the first stage and the known picking-up order of containers， the positions of obstacle containers are optimized， and an optimization model of container picking-up operation of the second stage is constructed and solved by the designed heuristic algorithm. The algorithm is compared with the existing algorithms through examples. The results show that the designed algorithm is more effective in reducing the double re-handling rate， which shows that the proposed two-stage programming model can effectively reduce the re-handling rate and improve the efficiency of import container picking-up operation.

Key words： import container; storage strategy; re-handling strategy; heuristic algorithm

0 引 言

近年來，我国水路运输业发展迅速，码头吞吐量急速上升，导致堆场堆放的集装箱越来越多，堆场翻箱率居高不下。进口集装箱（以下简称进口箱）进场堆存和提取过程均涉及翻箱问题，而翻箱作业制约了集装箱作业效率，因此本文目的是制定合理的进口箱堆存和翻箱策略，从降低翻箱率的角度提升进口箱提取效率。

对于集装箱堆存过程中的箱位分配问题：BAZZAZI等[1]在考虑集装箱类型的条件下研究了每个时段箱区的集装箱分配问题，并采用遗传算法求解;YU等[2]提出非隔离、单周期隔离和多周期隔离3种堆存策略，并对这3种策略进行了对比分析;周鹏飞等[3]提出通过统计箱组堆存时间获取提箱优先级的方法，对卸船箱组的箱位分配进行优化，并设计了启发式算法进行求解;严伟等[4]基于聚类算法设置出口集装箱集港堆存规则，并通过仿真进行了验证;周思方等[5]通过预估箱组提取时间范围建立了箱位指派模型;梁承姬等[6]基于网络流方法对箱区分配进行了动态研究，并采用禁忌搜索算法进行求解;武慧荣等[7]以海铁联运集装箱码头进出口集装箱为研究对象，构建了堆场箱区分配模型，并采用模拟退火算法进行求解。

对于集装箱提取过程中的翻箱问题：文献[2]借鉴KIM[8]提出的计算期望翻箱量的方法，研究了箱区贝位堆存箱量和栈高与翻箱量之间的关系;LEE等[9]提出一种改进模型来预估编组集装箱的箱位，并设计了启发式算法进行求解;徐亚等[10]提出一种启发式算法及其改进算法，对提箱过程中的翻箱问题进行了优化;PETERING等[11]采用一种新的混合整数规划模型研究了箱区集装箱的重定位问题，并采用扩展性的启发式算法求解;郑斯斯等[12]通过对多种翻箱规则下的优先级进行排序建立了倒箱路径优化模型，并采用启发式算法求解;郭瑞智等[13]考虑提箱过程中场桥作业时间构建了整数规划模型，并设计了启发式算法求解。

本文在前人研究的基础上，从降低堆场翻箱率的角度对进口箱的堆存策略和翻箱策略进行研究。首先，以场桥期望提箱完工时间最短为优化目标，建立第一阶段箱区贝位分配模型。其次，基于第一阶段进口箱分配优化结果，以翻箱总次数最少为目标，构建第二阶段提箱优化模型。通过设计启发式算法减少对障碍箱的二次操作。最后，借助算例将启发式算法求解的结果与已有算法求解的结果进行对比，验证本文提出算法的有效性。

1 问题描述

进口箱从待卸船舶被卸载，并被送入堆场进行堆存。根据文献[8]的研究结论，箱区贝位堆存箱量和栈高与翻箱量之间存在定量关系，而且可以预估进口箱在提取过程中的期望翻箱量。因此，进口箱的堆存优化需要在箱区贝位合理分配集装箱堆存量，降低箱区首次翻箱率。

在上述研究的基础上获取贝内集装箱的堆存量。将每个阶段需取走的集装箱记作目标箱，将目标箱上方的集装箱记作障碍箱，则优化障碍箱的落箱位置是降低贝内二次翻箱率的关键。

针对障碍箱的落箱位置选择问题，设计提箱作业启发式算法。设障碍箱的提箱优先级为p0，障碍箱落箱候选堆栈的优先级选择顺序如下：（1）若某堆栈内堆放的集装箱的最高优先级低于p0，则该堆栈为障碍箱落箱最优堆栈;（2）空栈为障碍箱落箱次优堆栈;（3）比较每个堆栈现有集装箱的最高优先级，选择集装箱最高优先级值最低的堆栈为障碍箱落箱末优堆栈。若以上每种类型的堆栈存在多个，则优先考虑邻近堆栈上的空箱位为障碍箱落箱位置。本文中提箱优先级指提箱先后次序，依该次序为集装箱编号。

综上所述，进口箱堆存和提取均涉及翻箱问题，且两个过程相互关联。本文从堆存和提取方面进行两阶段研究。第一阶段以单箱区为研究对象，确定在初步降低箱区期望首次翻箱率的同时，优化箱区各贝位的进口箱量分配。第二阶段在箱区各贝位集装箱堆存状态和提取顺序已知的情况下研究贝内翻箱问题。通过优化障碍箱的落箱位置进一步降低贝内二次翻箱率。本文建立进口箱堆存和提取两阶段规划模型来实现上述过程。

2 进口箱堆存和提取两阶段规划模型

2.1 第一阶段箱区贝位分配模型

2.1.1 模型假设

某时段被分配到箱区的集装箱量已知;集装箱进入堆场时，分配到箱区各贝位的概率相同;贝位堆栈的最大层数为H时，为满足所有情况下障碍箱的落箱需求，贝内需留有H-1个空箱位;在无悬臂轨道吊的箱区布局中，只有一台场桥进行作业。

2.1.2 模型参数与变量

已知参数：Cu表示在某时段内分配到箱区的卸船箱总量;n表示箱区的贝位总数;i表示贝位编号（i=1，2，…，n）;S表示贝位最大堆栈数（s=1，2，…，S）;H表示贝内堆栈最大层数（h=1，2，…，H）;C表示贝位堆放集装箱的最大容量;Coi表示贝位i的初始集装箱堆存量;to表示场桥单位翻箱作业时间;tc表示场桥单位提放箱作业时间;tm表示场桥单贝位移动时间;R（C）表示当贝内集装箱堆存量为C时，提取所有集装箱的预估期望翻箱量。

决策变量：Ci表示从船舶卸载的集装箱分配到箱区贝位i的箱量。

2.1.3 贝位期望翻箱量估计

借鉴文献[8]估计贝位期望翻箱量的方法，研究得出箱区每个贝位期望翻箱量与堆存箱量和栈高有关。当贝位最大堆栈数S已确定时，根据贝位的堆存箱量C计算提箱过程中产生的平均翻箱量R（C）。

2.1.4 箱区贝位分配模型

以场桥期望提箱完工时间最短为目标，建立箱区贝位分配模型如下：

式（2）为目标函数，表示目标是箱区场桥期望提箱完工时间（由场桥期望翻箱作业时间、移动时间和提放箱作业时间组成）最短，第一项中R（Coi+Ci）-RCoi表示贝位i新增的期望翻箱量;式（3）保证分配到各贝位的箱量之和等于卸船进口箱总量;式（4）表示当堆栈最底层的集装箱出现翻箱作业时，确保贝内有充足的空箱位提供，即限制贝内集装箱的分配数量不超过其最大容量;式（5）是对决策变量的取整约束。

2.2 第二阶段提箱优化模型

2.2.1 模型假设

贝内堆存的集装箱均为20英尺（1英尺≈0.304 8 m）的标准箱;考虑场桥作业的安全性，翻箱限制在同一贝内进行;贝内集装箱初始堆存状态和提取顺序已知;进行提箱作业时，不考虑新的集装箱入贝堆存。

2.2.2 模型参数与变量

已知参数：根据上述箱区贝位分配模型，可得到贝内集装箱堆存量C。在本阶段研究中，共同参数部分与第一阶段模型中的一致，其他具体参数有：集装箱的提箱优先级p（p=1，2，…，P）、障碍箱的提箱优先级p0、提箱阶段l（l=1，2，…，L）、贝内集装箱的初始堆存状态Ipsh（表示提箱优先级为p的集装箱堆存在堆栈s的第h层）。

决策变量：xlpsh，若第l阶段提箱优先级为p的集装箱堆存在堆栈s的第h层，则其值取1，否则为0;ylpshab，若第l阶段提箱优先级为p的集装箱从堆栈s的第h层被翻至堆栈a的第b层，则其值取1，否则为0;zlpsh，若第l阶段提箱优先级为p的集装箱被从堆栈s的第h层提走，则其值取1，否则为0。

2.2.3 提箱优化模型

基于上述参数和决策变量，以贝内翻箱总次数最少为目标，建立进口箱提箱优化模型：

式（7）表示贝内集装箱初始堆存情况与第0阶段的堆存情况一致;式（8）表示每次操作只作业一个集装箱，且该集装箱只能被提取或被翻倒至其他堆栈[14];式（9）表示若某个阶段产生翻箱作业，则为障碍箱选择的落箱位必须是空箱位;式（10）等号右边第2项和第3项表示提箱过程中翻箱操作对位置变量xlpsh的影響，第4项表示提箱操作对xlpsh的影响[15];式（11）表示在堆存集装箱或翻箱过程中不能出现悬空位置;式（12）确保贝内所有集装箱最终被提取完毕;式（13）表示任一提箱优先级为p的集装箱在贝内均有确定的箱位，或已被提取离场，或仍堆存在贝内;式（14）表示贝内任一箱位最多只能堆放一个集装箱;式（15）表示按照既定的提箱顺序依次提箱;式（16）表示决策变量的取值范围。

3 模型求解

根据模型的特点，对第一阶段箱区贝位分配模型采用遗传算法进行求解，对第二阶段提箱优化模型设计启发式算法来求解。两种求解方法均在MATLAB平台上操作运行。

3.1 遗传算法主要求解步骤

（1）初始种群。在进行编码时采用整数编码的形式，假设箱区贝位数为n，需要生成n个贝位的分配量，即染色体可以表示为：C1，C2，C3，…，Cn。其中，基因值C1，C2，C3，…，Cn分别对应箱区各贝位进口箱的箱量分配。图1为染色体编码示例。

（2）适应度函数和选择策略。目标为场桥期望提箱完工时间最短，因此取目标函数的倒数作为适应度函数。

采取精英保留策略，即在父代种群中选择适应性强的个体插入子代种群中，从而保证子代中一定存在优于上一代的个体。

（3）交叉。对每代种群以一定的交叉率pc进行染色体交叉。由于染色体设计的特殊性，参考文献[1]中的线性组合交叉策略，线性组合系数为k，在两个个体P1，g、P2，g之间进行算术交叉，产生新的个体。计算方式如下：

图2为父代（第g代）染色体交叉示例：箱区设置10个贝位，分配到箱区的进口箱总量为100 TEU，P1，g和P2，g为两条父代染色体。当k=0.85时，子代P1，g+1在1号贝位的数值为：0.85×9+0.15×8=8.85。按照此方法计算其余位置数值从而得到子代P1，g+1。子代P2，g+1在1号贝位的数值为：0.85×8+0.15×9=8.15。采取相同的方式得到子代P2，g+1。为满足染色体的基因值为正整数，线性交叉后子代个体采用奇数贝位对应的基因值向负无穷方向取整，偶数贝位对应的基因值向正无穷方向取整的方式进行保留。基因修复后子代P1，g+1在1号贝位的数值为8，子代P2，g+1在1号贝位的数值为8。若基因总值不等于100，则在超过或小于额定值的染色体中寻找最大或最小的基因值，并进行相应的删减或增加，从而使得染色体满足条件。

（4）变异。对每代种群以一定的变异率pm进行染色体变异。变异方式采用将两个父代染色体上相同基因位置的进箱量相互置换，同时重新获得箱区各贝位所对应的进口箱分配量。

（5）结束规则。当算法迭代到设定的最大次数时，结束并输出结果。

3.2 提箱作业启发式算法

贝内集装箱在被提取之前均有确定且唯一的优先级别。视一个优先级别的集装箱为一个提箱阶段。当提箱过程中出现翻箱操作时，需寻找其余未满额定层数的堆栈，作为翻出障碍箱的可落堆栈集。为障碍箱选择合适的落箱堆栈是降低二次翻箱率的关键，而可落堆栈集中包含以下6种堆存情形：（1）仅有一个堆栈内现有集装箱最高优先级低于p0，且无空栈;（2）与情形1的类似，但有多个满足条件的合适堆栈;（3）存在某堆栈内现有集装箱最高优先级低于p0的情况，也存在空栈;（4）存在空栈且唯一，而不存在某堆栈内现有集装箱最高优先级低于p0的情况;（5）存在多个空栈，而不存在某堆栈内现有集装箱最高优先级低于p0的情况;（6）除以上5种情形之外的其他堆存情况。

确定贝内每个提箱阶段目标箱所存箱位，将可落堆栈集中包含的6种堆存情形设置成相应的落箱规则，并将其嵌套至提箱作业过程中;外集卡依次到港，提取已经获得优先级的集装箱。嵌套落箱规则的提箱作业启发式算法流程见图3。

4 算 例

4.1 第一阶段箱区贝位分配模型求解

以自动化码头单箱区为研究对象，参数设置见表1。箱区每个贝位初始集装箱堆存量已知，见表2。遗传算法中：最大迭代次数设为1 000;种群规模设为100（100条染色体）;交叉系数pc设为0.85;变异系数pm设为0.15;交叉线性组合系数k设为0.8。应用MATLAB R2018a编程环境，使用遗传算法计算10次，取最优的收敛效果，见图4。当算法迭代至第550次时，目標函数值趋向收敛，用时约54 638 s，场桥期望提箱完工时间达到最短。当目标函数值最小时，对应决策变量的最优结果见表2，例如，1号贝位所分配的进口箱最优箱量为16 TEU，总堆存量最优结果为20 TEU。

4.2 第二阶段提箱优化模型求解

在提箱优化问题上，为验证所设计的启发式算法的有效性，采用MATLAB R2018a编程将本文提出的启发式算法与KH算法[16]、IH算法[10]和OH算法[14]的运行结果进行对比。选取10种不同的贝位规模，并在每种规模下随机生成100个算例实验，最后以平均翻箱量和平均运行时间这两个指标评比算法的性能，见表3。第二阶段进一步落实到在提箱过程中对贝内集装箱的翻箱问题，基于第一阶段箱区贝位分配模型的求解结果，取其中优化的进箱量为28 TEU的贝位进行研究，应用翻箱策略提取集装箱的示例见图5。集装箱上的编号表示提箱优先级，0表示空箱位。当场桥提取1号集装箱时，存在压箱现象，需依次将24号和22号箱翻倒至同贝的其他堆栈。根据提箱作业启发式算法，结合当前阶段贝内集装箱的堆存状态，直接将24号和22号集装箱分别移至堆栈5和3的顶部。

当目标箱上的障碍箱全部翻倒后，场桥可提取1号箱离场。同理，应用设计的启发式算法，依次提取每个提箱阶段的目标箱，最终将贝内集装箱提取完毕。

4.3 结果分析

第一阶段优化以单箱区为研究对象，目标是降低箱区首次翻箱率。当场桥的期望提箱完工时间最短时，从船舶卸载的集装箱分配到箱区的箱量在每个贝位内大致呈现均衡性。而由于场桥的单位翻箱作业时间远大于其在单位贝位内的移动时间，故箱区内邻近陆侧贝位的进箱量比海侧端口的多。

第一阶段仅仅从研究堆存策略的角度，初步使堆场箱区首次翻箱率得到降低。在进行第二阶段提箱优化后，通过合理设计障碍箱倒箱落位的启发式算法，并结合算例表明，即使扩大贝位规模，本文设计的启发式算法在翻箱量和程序运行时间上也优于已有算法，验证了本文算法的有效性。因此，可将设计的算法应用于提箱过程中，进一步降低堆场二次翻箱率。

5 结 论

本文为制定合理的堆存与翻箱策略，对进口箱堆存与提取过程进行了优化研究，并考虑两个过程的关联性，构建了两阶段规划模型。第一阶段以场桥期望提箱完工时间最短为目标，在初步降低箱区期望首次翻箱率的情况下，建立箱区贝位分配模型进行堆存优化。将第一阶段求解的贝位进箱分配结果作为输入，并在集装箱堆存状态和提箱顺序已知的条件下，优化障碍箱的落箱位，建立第二阶段提箱优化模型，并设计启发式算法进行求解。该算法与已有算法的对比结果表明，应用该算法降低贝内二次翻箱率的效果更显著，从而表明提出的两阶段模型能够降低堆场翻箱率，使进口箱提箱作业效率得到提升。

参考文献：

[1]BAZZAZI M， SAFAEI N， JAVADIAN N， et al. A genetic algorithm to solve the storage space allocation problem in a container terminal[J]. Computers & Industrial Engineering， 2009， 56： 44-52. DOI： 10.1016/j.cie.2008.03.012.

[2]YU Mingzhu， QI Xiangtong. Storage space allocation models for inbound containers in an automatic container terminal[J]. European Journal of Operational Research， 2013， 226： 32-45. DOI： 10.1016/j.ejor.2012.10.045.

[3]周鵬飞， 李丕安. 集装箱堆场不确定提箱次序与卸船箱位分配[J]. 哈尔滨工程大学学报， 2013， 34（9）： 1119-1123. DOI： 10.3969 /j.issn.1006-7043.201301022.

[4]严伟， 朱夷诗， 黄有方， 等. 基于聚类分析的集装箱码头堆场策略[J]. 上海海事大学学报， 2014， 35（1）： 35-40， 59. DOI： 10.13340 /j.jsmu.2014.01.008.

[5]周思方， 张庆年. 基于提箱同步的进口箱堆存策略研究[J]. 交通运输系统工程与信息， 2018， 18（5）： 151-157. DOI： 10.16097/j.cnki.1009-6744.2018.05.022.

[6]梁承姬， 贾茹， 盛扬. 基于网络流的自动化集装箱码头堆场空间分配[J]. 计算机应用与软件， 2018， 35（1）： 77-84. DOI： 10.3969 /j.issn.1000-386x.2018.01.013.

[7]武慧荣， 朱晓宁， 邓红星. 集装箱海铁联运港口混堆堆场箱区均衡分配模型[J]. 重庆交通大学学报（自然科学版）， 2018， 37（4）： 109-115. DOI： 10.3969 /j.issn.1674-0696.2018.04.17.

[8]KIM K H. Evaluation of the number of rehandles in container yards[J]. Computers & Industrial Engineering， 1997， 32（4）： 701-711.

[9]LEE Yusin， CHAO Shih-Liang. A neighborhood search heuristic for pre-marshalling export containers[J]. European Journal of Operational Research， 2009， 196： 468-475. DOI： 10.1016/j.ejor.2008.03.011.

[10]徐亚， 陈秋双， 龙磊， 等. 集装箱倒箱问题的启发式算法研究[J]. 系统仿真学报， 2008， 20（14）： 3666-3669， 3674. DOI： 10.16182/j.cnki.joss.2008.14.006.

[11]PETERING M E H， HUSSEIN M I. A new mixed integer program and extended look-ahead heuristic algorithm for the block relocation problem[J]. European Journal of Operational Research， 2013， 231： 120-130. DOI： 10.1016/j.ejor.2013.05.037.

[12]郑斯斯， 王爱虎. 路径优化算法求解集装箱码头堆场翻箱问题[J]. 工业工程与管理， 2017， 22（3）： 31-40. DOI： 10.19495/j.cnki.1007-5429.2017.03.005.

[13]郭瑞智， 史玛君， 林昊堃. 集装箱倒箱问题的模型与启发式算法研究[J]. 数学杂志， 2017， 37（4）： 805-810. DOI： 10.13548/j.sxzz.2017.04.005.

[14]KIM K H， HONG G-P. A heuristic rule for relocating blocks[J]. Computers & Operations Research， 2006， 33（4）： 940-954. DOI： 10.1016/j.cor.2004.08.005.

[15]朱明华， 程奂翀， 范秀敏. 基于定向搜索算法的集装箱堆场翻箱问题[J]. 计算机集成制造系统， 2012， 18（3）： 639-644. DOI： 10.13196/j.cims.2012.03.193.zhumh.013.

[16]KIM K H， KIM H B. Segregating space allocation models for container inventories in port container terminals[J]. International Journal of Production Economics， 1999， 59： 415-423.

（编辑 贾裙平）