自动化集装箱码头卸船箱动态选位问题研究*

柴佳祺 张清波 边志成

上海振华重工（集团）股份有限公司 上海 200125

0 引言

近年来，劳动力成本逐年攀高，随着集装箱码头整体装备设计制造水平的不断提升以及新工艺新技术的不断完善，国内外自动化集装箱码头（Automated Container Terminal，ACT）已掀起新一波建设热潮。然而，自动化集装箱码头生产组织的信息化、智能化等软实力的发展必须与装备制造等硬实力的发展相适应，二者缺一不可。因此，国内自动化码头生产作业管理相关理论与方法正面临着迫切需求，关于自动化码头智能计划及动态调度等一系列智能协同作业成套问题已成为该领域研究的核心与热点。本文所研究的自动化集装箱码头卸船箱动态选位问题正是ACT智能协同作业成套问题中的重要研究方向之一。

自20世纪70年代以来，越来越多的业界学者和专家针对箱区选位问题从不同角度进行分析，运用各种方法解决实际问题。Bazzazi M等[1]建议使用有效的遗传算法（GA）来解决扩展储存空间分配问题（SSAP），该问题考虑了集装箱码头现存的大量等式约束；Yu M等[2]在不同策略下的进站集装箱的存储空间分别设计了最优舱位分配模型，从而缩短跨运车等待时间。谢尘等[3]采用分布式遗传算法和启发式算法相结合的混合算法求解选位模型，提出基于混堆模式的出口箱进场选位优化策略，从而降低了船舶压箱总数和在港时间；Zhang C等[4]采用滚动时域的方法，对每个计划周期，缩短集装箱从堆存区到船停泊位置的运输距离，减少了工作量的不平衡，避免了站点可能出现的障碍；王志明等[5]以实例利用遗传算法求解到场箱的分配箱位，研究了集装箱后方堆场堆存策略，实现了对一次卸船或进港的一批箱子进行集装箱堆场作业的全局优化；Kim K H等[6]讨论了动态分配方法，建立混合整数规划模型，基于集装箱在港停留时间和梯度下降优化，分别提出2个启发式算法，使堆场具有较高的装船作业效率和空间利用率；Kang J等[7]对箱重信息不确定条件下的进口箱箱位分配问题进行研究，整个优化过程运用模拟退火算法和仿真技术相结合的手段；Kim K H等[8]利用动态规划模型多阶段逆向求解的特征，建立基于动态规划的进口箱箱位分配模型；杨淑芹等[9]根据进口集装箱先到港以及尽量轻箱在下、重箱在上的原则，采用启发式方法合理安排进口集装箱堆场箱位，以达到装船作业时堆场机械的翻箱率最低。

1 问题描述

卸船箱动态选位问题属于自动化集装箱码头的资源分配问题，选位算法的方法和原则与卸船箱堆存计划有关。常用的卸船堆存计划模式可分为一对一计划和模糊计划2种，随着码头吞吐量和运营水平的不断变化，这2种计划实用性渐弱。为此，需要通过实时的自动选位和任务捕捉来增加箱位分配的灵活性、实时性和有效性，即需要智能选位算法来支撑堆场动态选位模式。

卸船进场选位算法由集装箱码头营运系统数据库服务器来执行，其功能是动态监测场地内任务中已被卸船落箱在水平运输设备上但尚未分配具体场地位置的卸船落位任务，一旦发现目标便根据相关数据流信息由卸船进场选位算法计算出最合理的场地位置，并将该计算结果写入卸船箱落箱任务中。

动态选位模式是指卸船箱进场前不做任何场地堆存计划，而是通过算法对箱子进行检测，判断其类型、尺寸、货特、货主、持箱人等信息自动选择最优箱区，且自动进入最优箱区的最优倍位，从而实现现场无人工操作的智能化模式。目前，越来越多的自动化集装箱码头将卸船计划模块从计划部转移到中控室，很大程度上提高了卸船计划的动态性。

卸船箱进场自动选位是指管理系统自动为完成岸边集装箱起重机卸船作业的箱子选择具体的场地位置并生成可供轮胎式集装箱起重机终端看到的落位任务过程。集装箱码头卸箱进场自动选位可分3个主要步骤：

1）服务器索箱 即服务器检索进口箱选位任务，若检测到该箱子，即进入下一步；

2）最优箱位确定 最优箱位确定是指给检测到的箱子制定一个最佳落箱位置，该步骤可分为对检测到的箱子进行类别判断、根据箱子类别进一步确定该类箱子应该堆存到场地哪些区域（卸船箱堆存计划）、在既定区域内选择距离场地机械最近的位置、从该倍位上满足卸箱要求的位置上选择最优落箱位置等环节；

3）落箱任务发送 将选好的最优箱位发送到该任务记录的水平运输设备接收终端上，以指导运输方位。

基于合同网的自动化集装箱码头智能选位过程是通过招标－投标－中标的市场竞争机制进行任务分配（见图1）。当集装箱从岸边卸下等待进场选位时，每个集装箱会发出招标请求，每个箱区则会投标，通过算法模型可得到每个箱区给该集装箱打的分数，最终得到分数的总和为目标函数，分数最高的则为最优落箱位置。这种方法考虑了投标商之间的负载均衡，综合考虑与衡量投标商的负载、能力和信任度等方面因素，从而使系统以较低代价、较高质量完成任务分配的合同关系。

图1 合同网选位过程示意图

2 模型构建

2.1 模型的约束条件

卸船箱选位的约束条件有均衡性约束、合理性约束和有效性约束。模型中使用符号及其表示的意义为：i为等待选位的集装箱序号，1≤i≤I；I为等待选位的集装箱总数；j为箱区序号，1≤j≤J；J为箱区总数；Mij为第i个箱子进入第j个箱区所获得的分数；Dij为第i个箱子到第j个箱区的距离分数；Tj为箱区j内已有任务数量；Nj为箱区j内最大任务数量；Xij（0,1）矩阵为第i个集装箱是否进入第j个箱区；Z为总目标函数。

1）均衡性约束

如图2所示，每个箱区的贝位都有最大任务数量的限制，并需要留有一定数量的翻箱位。已知每个区块的容量由已知参数N表示，进入同一区位的任务数量不能超过该区位的最大任务数量，该约束可表示为

图2 均衡性约束示意图

2）合理性约束

如图3所示，一个集装箱只能进入一个箱区，目标箱位唯一，该约束可表示为

图3 合理性约束示意图

3）有效性约束

如图4所示，一个集装箱不能进入分数为0的箱区，该约束可表示为

图4 有效性约束示意图

2.2 目标函数

该模型所表示的是单目标规划问题，其目标函数可表示为

该目标函数等于决策变量乘以已知的二维矩阵所有元素之和，趋向于求最大值，即距离分数以及箱子进入箱区所得分数相加之和的最大化。其中，α、β为平衡两者分数的权重系数，该模型取α和β分别平衡两者，意味着先考虑Mij即箱子进入箱区所得的分数为主，而其次考虑距离分数。

3 算例分析

为了证明本文所建立的单目标规划模型的有效性和可行性，采用Aimms软件的CPLEX算法库进行求解。按如下步骤即可得到最优解：

步骤1：录入待整理的箱号、待选箱区号；

步骤2：导入Mij和Dij的分数、Tj现有任务数量；

步骤3：设置决策变量Xij为Binary矩阵；

步骤4：设置目标函数Z；

步骤5：设置3个约束条件（本例中箱区内的最大任务数量N取500）；

步骤6：编写程序。

通过相关数据的录入，为模型求解提供数据支持，从而直观地从求解结果中得到作业计划的最优分配，Aimms决策模型可在短时间内对所做方案进行求解，且所求的最优方案满足目标函数取得最大值。

3.1 已知数据获取与分析

根据模型中的已知参数定义，该模型需要获取的数据主要包括卸船箱基本信息和箱区基本信息。某时刻生产系统服务器获取到如表1所示10个等待选位的卸船箱，其中集装箱IRSU5008950为冷藏箱、IRSU5007890为危险品箱。

表1 卸船箱信息表

表2列出了每个堆场箱区可堆箱子属性的定义，其中A3箱区为冷藏箱箱区、B3箱区为危险品箱区，提单号与卸货港未指定则表示对应场位可堆放任意提单号和卸货港的箱子（表中IF为进口重箱，GP为普通干货箱）。

表2 箱区信息表

如图5所示，将距离分最近、近、中等、远、最远等5个等级。例如A1箱区相对于箱子1和2的距离最近，故打100分；A2箱区相对较近，故打80分；A3箱区相对距离中等，故打60分；B1箱区相对较远，则打40分；而B2和B3箱区相对最远，故打20分，希望尽量不要进入最远的箱区。按照上述距离规则Dij打分如表3所示。

图5 箱区布局案例示意图

表3 Dij分数数据表

各箱区堆存状态如图6～图11所示，A1箱区和B2箱区为堆放提单号为HS03D8765，来自某港的40 ft进重箱；A2箱区堆放小票箱，即将不同提单号的单个箱子放在一起；A3箱区为堆放提单号为YMQACTS1234567的冷藏箱箱区；B1箱区为空箱区；B3箱区为堆放来自某危险品箱区。

图6 A1箱区剖面图

图7 A2箱区剖面图

图8 A3箱区剖面图

图9 B1箱区剖面图

图10 B2箱区剖面图

图11 B3箱区剖面图

由以上信息可知，箱号IRSU5003253和IRSU5006389为同一提单号，且A1和B1箱区本身已存放此提单号HS03D8765的箱子，故尽量选择将同票箱放在一起。同时，A1箱区可靠粘，B2箱区可压粘。在本案例中，取压粘分数M1为100，靠粘分数M2为90。各箱区内没有箱子IRSU5002041的同票箱，将杂票箱视为一个同票箱箱区，可考虑将其放入A2的杂票箱箱区为最优，得100分。而冷藏箱和危险品箱这2个特殊箱则进入已有的冷藏箱区和危险品箱区，各得100分。B1箱区为空箱区，在空箱区内可开新位，在此取开新位分数M3为80分。其余分数可此类推，箱子进入各箱区所得的分数参数Mij如表4所示。

表4 Mij分数数据表

3.2 算例求解与分析

模型求解后得到图12所示的选位结果，并得到总分为876。其中，冷藏箱IRSU5008950选位进入了冷藏箱区A3；箱子IRSU5007034进入A1箱区抢位；箱子IRSU5003253进入A1箱区靠粘；箱子IRSU5006543、IRSU5004680、IRSU5008068、IRSU5003789进入空箱区B1，B1随即成为同票箱箱区；箱子IRSU5002041因场内还没有进入的同一提单号箱子且为小票箱，故进入A2杂货箱箱区；箱子IRSU5006389进入B2箱区压粘；危险品箱IRSU5007890选位进入了B3危险品箱区。经过大量的算例分析，证明了模型的有效性，且能达到较高的运算效率。

图12 卸船箱选位结果

经过大量的算例分析及系统测试，证明了此决策系统性能良好，在对实际场地策划进行决策的过程中能保持高效率的运行计算。如表5所示，由不同算例所需时间及内存对比可知，此决策系统在变量多的情况下计算时间较短，运行性能良好，且占用内存较小，在对实际问题进行求解时，可提高箱子选位效率。

表5 算例效率对比

计算时间对比结果可反映为系统在计算变量数为12～144时，所用时间存呈递增趋势且增势平缓；在计算变量数为144～500时，所用时间呈递增趋势且增幅较之前略大。

4 总结

本文通过对指定工艺流程的自动化集装箱码头智能动态选位问题的研究与实践，在分析与总结了不同场地计划员工大量宝贵经验的基础上，对自动化集装箱码头卸船箱进场智能选位进行了业务探索和理论分析，并建立了基于合同网技术的智能选位系统算法研究。

经过算例分析及实际的系统测试，证明了模型的有效性和实用性，证明了相关算法和数据库的结构合理性和较强的可拓展性。系统对较大规模的算例求解具有较好的收敛效果，算法的鲁棒性较高。通过不断改进，系统从索取数据到模型构建再到模型求解所占用的内存资源大大降低，具有一定的承压能力，保证了系统的稳定运行和实时性。系统的应用有助于提高码头作业线效率，减少翻箱次数，最大限度地利用场地资源，从而实现最终决策的最优化，具有实际的应用价值。