基于边装边卸工艺的集装箱船配载决策

金健 宓为建 夏孟珏

摘要：针对超大型集装箱船边装边卸（dual cycling，DC）工艺下的配载问题，以DC工艺下集装箱船舱内配载规划为研究对象，构建以最小化场内翻箱数、设备移动次数等为目标的配载模型，并提出一种可行的蒙特卡洛树搜索（Monte Carlo tree search， MCTS）算法对该模型进行求解。通过实际算例证明了模型和算法的有效性，且本研究的相关成果已应用于码头实际生产，应用效果良好。本研究思路对集装箱码头相关计划调度研究及实现有借鉴意义。

关键词：集装箱码头; 船舶配载规划; 边装边卸工艺; 蒙特卡洛树搜索（MCTS）

中图分类号： U691.7

文献标志码： A

Abstract： Aiming at the stowage issue of very large container ships under dual cycling （DC） process， taking stowage planning in the container ship cabin under DC process as the research object， a stowage model is constructed， where the model objective is to minimize the number of overturning containers in yards， the number of equipment movement and so on. A feasible Monte Carlo tree search （MCTS） algorithm is proposed to solve the model. The effectiveness of the model and the algorithm is proved by a practical example， the related results of this study have been applied to the actual production of terminals， and the application effect is good. This research idea has reference significance for the research and realization of container terminal task planning and scheduling.

0 引 言

隨着集装箱船的大型化，集装箱码头单船每日集装箱作业箱量由不到1 000 TEU转为超过1 500 TEU，而集装箱码头的装卸设备并未根据箱量进行更新和重新设计。同时，国内各集装箱码头的服务特性对集装箱码头装卸效率提出了更高的要求，如潮期、晚截关、零截关等要求码头更高效地进行生产组织。然而，集装箱码头装卸效率在设备和操作层面已很难提升，在不更换硬件设备的条件下如果想一步提升装卸效率只能对装卸工艺进行改进。边装边卸（dual cycling，DC）工艺作为提升集装箱码头装卸效率的特殊装卸工艺，成为各集装箱码头针对船舶大型化普遍采取的工艺模式。

DC工艺是通过提升工艺循环过程中的有效作业占比，从而提升整个工艺作业效率的方法，具体指在满足条件的情况下单个岸桥在一个循环中同时进行装船和卸船作业的工艺流程。DC工艺具有能减少设备空驶从而减少能耗、提升效率的优点。DC工艺的应用需要满足一定的作业条件：卸空甲板箱，同时在舱内留有两列箱的空位;为岸桥同时配备装卸船箱区和设备;有针对性地制订设备和资源调度计划。

集装箱船配载问题是集装箱码头的关键决策问题，针对此问题的研究已有很多：王鸿鹏[1]运用知识推理技术设计了集装箱船自动配积载专家系统 ，并介绍了该系统的设计思想和实现原理;KANG等[2]和KIM等[3]分别提出了贪婪算法和树型搜索算法求解配载问题;AMBROSINO等 [4]强调主贝计划问题（master bay plan problem， MBPP），针对此问题提出基于规则方法的决策支持系统，使用约束满足方法求得可行解;WINTER[5]提出考虑装载的配载计划，主要用于优化岸桥的作业量均衡;CHO[6]和BOTTER等 [7]对集装箱船配载问题做了相应的假设和简化，构建了线性规划配载模型;AVRIEL等[8-9]建立了配载问题的0-1整数规划模型，并设计了一种启发式算法进行求解，大量仿真算例表明该算法求解效率和求解效果均较优;AMBROSINO等[10]以最小化总配载时间为优化目标，考虑箱型、船舶承载限制等实际作业约束建立了配载模型，但其将同一卸货港的集装箱配载于同一船贝的假设与实际操作有较大差别;SCIOMACHEN等[11]考虑三维装箱问题（three-dimensional bin packing problem， 3D-BPP），以装船总时间最短和岸桥利用率最高为目标优化配载计划;PACINO等[12]和DELGADO等[13]将配载分为解决多港口MBPP和完成船箱位计划两个阶段，首先通过解决MBPP处理不同港口集装箱冲突，再将MBPP处理结果作为船箱位计划的输入，从而进一步明确每个集装箱的具体船箱位;ZHAO等[14]在PACINO等[12]和DELGADO等[13]研究的基础上，将配载问题分为取箱点计算问题和发箱决策问题，考虑出口箱在箱区内的分布以及具体作业要求，设计了箱组贝配载模型;PARREO等[15]引入了集装箱平铺的特殊工艺，考虑危险货物集装箱，设计了一种

贪婪随机自适应搜索算法（greedy randomized adaptive search procedure， GRASP）求解船公司集装箱预配计划问题;SHEN等[16]设计了一种深度增强学习方法用于求解配载问题;COHEN等[17]把配载问题分为主计划和详细计划两个阶段，设计了一种遗传算法（genetic algorithm，GA），先解决主计划问题，再在详细计划中为每个集装箱分配具体位置; HELO等[18]针对集装箱货物属性和集装箱运输的特点，提出了一种新的配载效果评价标准。综上，目前对集装箱船配载问题的研究着重考虑船舶稳性等与船公司预配计划有关的决策因素，强调配载计划的可行性，对集装箱码头作业工艺、作业成本和作业效率的要求关注度不够。另外，目前并无针对超大型集装箱船配载特殊性的研究。

针对上述研究现状，本文以基于DC工艺的集装箱船配载问题作为研究对象，在超大型集装箱船对集装箱码头装卸效率提出更高要求的背景下，以DC工藝作为集装箱船装卸作业工艺要求，通过分析集装箱船在DC工艺下配载的重要决策因素构建配载模型，并设计算法求解此配载问题，通过算例分析证明所提出模型和算法的有效性。本文研究思路对研究集装箱码头其他相关决策问题具有一定的参考意义。

1 模型构建

1.1 集装箱船配载问题的特点

集装箱船配载问题具有以下特点：求解维度较多，问题复杂，解空间较大。本文研究的配载问题涉及在场箱、船箱位、配载顺序等3个维度，与常见的分配问题相比更复杂。问题约束多，采用传统智能搜索算法求解获得不可行解的情况较多。问题约束复杂，不可行解向可行解转化的机制复杂，算法迭代过程中将不可行解处理为可行解的难度较大。在规定时间内至少需要获得可行解。实际配载决策过程需要在限制时间内至少获得较优的可行解，以保证生产的正常进行。

1.2 集装箱船配载的主要决策因素

（1）场内翻箱。堆场内作业时如果先装船的集装箱位于后装船的集装箱正下方，则装船过程中需要挪开位于上方的集装箱，即翻箱。翻箱会增加设备的移动次数，降低装卸效率。

（2）堆场设备移动。堆场设备移动主要指堆场主要作业设备——场桥大车在箱区贝位之间的水平移动。

（3）船舶稳性。为保证按配载计划装船后船舶的稳性，在制订配载计划时，按船舶稳性要求预先计算集装箱船最优质量分布，最终集装箱船各箱位实际配载的集装箱质量尽量接近该箱位的预估质量，以保证最终配载计划满足船舶的适航性要求。

1.3 模型假设

（1）待配集装箱数量等于预配船图中给定的船舶贝内箱位数量。（2）各个待配集装箱在堆场中的具体堆存位置已知。（3）各类型待配集装箱的总数量与预配船各箱型箱位的总数量一致，即仅考虑箱型，存在可行的配载方案。（4）作业过程中机械设备均正常运行，不考虑故障或维修情况。（5）水平运输车辆数量满足岸桥装卸的基本要求。（6）岸桥装卸工艺为双20英尺（或单40英尺，1英尺=0.304 8 m）装卸工艺;场桥作业工艺为单箱作业工艺，即一次循环作业起吊一个集装箱。

1.4 符号定义

模型维度：I为堆场内待配集装箱的集合，i，i′∈I;J为待配载集装箱船箱位的集合，j，j′∈J;L为船舶贝内箱位所属列的集合，l，l′∈L;S为所有配箱次序的集合，s和s′为集装箱的配载顺序号，即s，s′∈S。

模型参数：Ti为0-1变量，表示集装箱i的箱型，其中1表示集装箱i为40英尺箱，0表示集装箱i为20英尺箱;Di为0-1变量，其中1表示集装箱i是高箱，0表示集装箱i是平箱; Hl为船舶贝内第l列的高箱数量;Gi为船舶贝内第l列的平箱数量;

Mj表示船舶贝内箱位j所能承载的质量上限;Mj表示船舶贝内箱位j所能承载的质量下限;Ri表示集装箱i的实际质量;Wj表示船舶贝内箱位j在预配阶段被预分的质量;Vj为0-1变量，若船上的箱位j为垫脚位则用1表示，否则用0表示;δ用于表示在船舶贝内单列上下两个箱位上重箱压轻箱的质量差上限值;ξ用于表示岸桥在进行双20英尺箱作业时，所要起吊的两个集装箱的质量差上限值;Wl表示船舶贝内单列所能承载的质量上限值;Yi表示集装箱i在堆场内的贝位号;Bi表示集装箱i在堆场内的箱区号;Cjj′为0-1变量，表示船箱位j与j′的作业位置关系，其中1表示船箱位j与j′的作业位置同属于一个作业大贝，0表示船箱位j与j′的作业位置不属于同一贝位;Pjj′为0-1变量，用于表示船舶贝内任意两个箱位在竖直方向上的位置关系，若箱位j所处位置在箱位j′的正上方，则取值为1，否则为0; Qii′为0-1变量，用于表示在堆场箱区贝内的任意两个集装箱之间在竖直方向上的关系，若集装箱i在堆场的位置处于集装箱i′的正上方，则取值为1，否则为0;Sjl为0-1变量，若箱位j属于l列，则取值为1，否则为0;Di表示集装箱i所属箱组的编号;Es表示第s个集装箱配载顺序的数字编号。

决策变量：Xisj为0-1决策变量，当第i个集装箱以顺序s配载到第j个船箱位时Xisj为1，否则为0。

辅助变量：αii′表示第i个集装箱与第i′个集装箱的发箱序号差;βii′为0-1变量，用于表示任意两个集装箱配载的先后顺序关系，当第i个集装箱比第i′个集装箱先配载时，取值为1，否则为0;s表示相邻顺序配载的集装箱所在区位的序号差;

φs为0-1变量，用于描述相邻顺序配载的集装箱是否在同一个区位内，若这两个集装箱不在同一个区位内则取值为1，否则为0;

Ψjj′表示船箱位j与j′上所配载的集装箱的质量差;ε1为每个配载船箱位上集装箱实际质量与预配质量的差;ε2为实际配载的集装箱质量与船箱位预配质量范围差值的上限;ε3为实际配载的集装箱质量与船箱位预配质量范围差值的下限。

1.5 集装箱船配载模型

基于DC工艺的集装箱船配载总模型如下：

式（1）、（4）、（7）为目标函数，其中：式（1）为最小化堆场内无效翻箱数目标，式（4）为最小化堆场内设备移动次数目标，式（7）为最小化船箱位质量差以保证稳性目标。式（8）～（22）依次表示单列内高箱和平箱数量限制、船箱位质量限制、重压轻质量限制、配载不悬空、单列总承载限制、作业顺序限制和双20英尺箱装卸顺序和质量限制约束。

2 算法设计

2.1 蒙特卡洛树搜索算法概述

蒙特卡洛树搜索（Monte Carlo tree search，MCTS）算法是一种在决策空间中随机采样并且根据结果构建搜索树，在给定结果域中寻找到最佳决策的方法[19]。MCTS算法具有以下特点：无须针对具体问题设计求解过程或者启发函数，但可以通过针对性的设计提升对特定问题的求解效率和求解效果;搜索树异步扩展，在分支多（更复杂）的搜索问题中比传统算法表现更好;在已取得可行解的情况下，算法可以随时终止，不需要等待算法最终完成来获得最优解;属于树搜索算法，可以用树搜索算法的优化方法进行优化;算法有可并行性，可以通过并行设计优化求解效果。

MCTS算法包括选择策略（selection policy）、扩展策略（expansion policy）、剪枝策略（pruning policy）、模擬策略（simulation policy）、回溯策略（backpropagation policy）等5个策略。通过把基于DC工艺的集装箱船配载模型目标和约束转换为树搜索结构所支持的表现形式，并集成嵌入到树搜索算法中，即可构建用于MCTS算法的基于DC工艺的集装箱船配载搜索树，对该配载问题进行决策。具体的算法流程见图1。

2.2 配载问题处理

选择策略。用于MCTS的选择策略有多种，本文选择UCT （upper confidence bound applied to trees）作为基于DC工艺的集装箱船配载选择策略：

式中：Xi为收益平均值，由模拟后获得的目标函数值确定;ρ为搜索广度系数。该选择策略从搜索树根节点开始，每一步选择回报值较优的节点作为下一个节点。

扩展策略。扩展策略指当前节点更新后，搜寻下一步所有可能的决策，即搜索当前节点所有可能的叶子节点的过程。在配载搜索树中，扩展策略为在当前配载状态下找出下一步存在哪个集装箱、具体以何种顺序配载到哪个具体船箱位，且该步配载满足前述配载模型中的所有约束。

剪枝策略。剪枝策略指在某些状态下对无解或解明显较差的节点作放弃处理。常用的剪枝方法有绝对修剪和相对修剪两种。因为配载问题专业性较强，需要相关的专业知识积累，所以本文选择使用配载领域知识进行针对性剪枝，修剪已知回报值较差的结果。具体剪枝策略为：根据配载约束限制，判断保留当前节点是否仍可能存在较好的配载结果，若不存在较好的配载结果，则修剪当前节点。

模拟策略。模拟策略指在当前节点的可用叶子节点中随机选择，选择原则为尽可能实现对现实世界的无偏估计。某叶子节点的总评价值Qi，对该总评价值进行最大值化处理。采用轮盘赌的方式，计算每个叶子节点被选择的概率Qi，采样概率为pi：

3 案例分析

为验证所提出模型的有效性和算法的计算效果，本文选取宁波大榭招商国际集装箱码头实际生产数据，用所提出的算法求解该基于DC工艺的集装箱船配载结果，并对求解结果进行分析。

3.1 算例描述

该算例为某集装箱船06H舱内配载数据。其预配信息和集装箱场地分布已知，集装箱分布于9个箱区内，总箱量为56 TEU。船箱位预配信息见图2，集装箱场地分布信息见图3，深色区域表示待配载的集装箱，集装箱上数据为集装箱质量。算例的实验环境为：处理器Intel Core i7 CPU，四核2.70 GHz，16.00 GB内存，Win7 64位操作系统。

3.2 结果分析

利用上节提出的算法对算例进行求解，最终配载顺序结果见图4。堆场内配载区位顺序依次为：1B→2D→4E→4D→8D→1G→1B→3E→2H→6H。场内翻箱次数为2;场桥大车总移动次数为9次，仅1B需场桥重复进入两次，即非整取箱区情况只出现1次，所有船箱位所配载集装箱均满足质量约束，且符合重压轻极限原则。其算法迭代的收敛曲线见图5。

收敛曲线显示，该算法在迭代至约1 400次时收敛至一个近似最优解，1 400次后适应度值呈现平稳状态，并未发现更优解，验证了算法的收敛性。

对同一算例重复计算10次，由于该算法为随机算法，每次收敛情况和最优解不同，多次实验搜索到最佳适应度值的平均迭代次数为1 389，平均最优适应度值0.392，平均运行时间137.2 s。算法在多次计算中得到的结果波动范围在可接受范围内，且收敛特性体现较为统一，说明MCTS算法在解决本问题中表现较为稳定，证明了MCTS算法的稳定性。同时，平均计算用时137.2 s体现了该算法较高的计算效率。以上求解结果分析和效果分析表明，MCTS算法在求解基于DC工艺的集装箱船配载问题中具有较好的计算效果和较高的计算效率，计算稳定性在可接受范围内。

因为配载问题有求解时间要求，所以针对不同规模算例给定一个求解时间上限，在限制计算时间的条件下求解算例。不同规模算例求解效果见表1（仅列举多目标中更重要且易量化分析的目标函数）。

不同规模算例的求解结果显示，针对较大规模的算例，MCTS算法也能在有限时间内获得可接受的求解结果，翻箱率可以限制在7%以内。

在实际生产应用方面，本文提出的MCTS算法被改进集成于集装箱码头智能配载系统中，已应用于上海港振东码头、明东码头和宁波大榭招商国际集装箱码头实际生产，实际效果达到甚至超过人工配载水平，对5 000 TEU以上级别的集装箱船（装卸最高箱量超过3 000 TEU级别）可实现智能配载，大大减少人工决策负担，提高了集装箱码头智能化水平。

4 结 论

本文核心研究内容和成果总结如下：

（1）通过分析基于边装边卸（DC）工艺的集装箱船装卸作业工艺特点，结合码头装卸作业要求和配载的基本原则，以降低场内翻箱数、减少堆场设备移动次数、保证船舶稳性为决策目标，提出了基于DC工艺的集装箱船配载模型。

（2）针对集装箱船配载问题的特点，将问题进行转换处理，应用目前人工智能领域广泛采用的蒙特卡洛树搜索（MCTS）算法，在使用更少人工经验的条件下求解集装箱船配载问题。

（3）使用提出的MCTS算法求解实际生产中的基于DC工艺的集装箱船配载问题算例，验证了算法的收敛性、有效性。

综上所述，本文所提出的针对超大型集装箱船DC工艺下的配载问题的模型和相应算法，可以有效解决基于DC工艺的集装箱船舱内配载这一复杂规划问题。从理论研究角度看，该研究思路和方法对于根据实际问题特性建模求解特殊的复杂混合规划问题有一定的借鉴意义;从应用研究角度看，该研究对实际生产作业中超大型集装箱船配载计划的制订以及集装箱码头智能计划调度均具有实际应用价值。

參考文献：

[1]王鸿鹏. 基于知识的集装箱船自动配积载专家系统[J]. 上海海事大学学报， 2002， 23（1）： 46-49.

[2]KANG J G， KIM Y D. Stowage planning in maritime container transportation[J]. Journal of the Operational Research Society， 2002， 53（4）： 415-426. DOI： 10.1057/palgrave.jors.2601322.

[3]KIM K H， KANG J S， RYU K R. A beam search algorithm for the load sequencing of outbound containers in port container terminals[J]. OR Spectrum， 2004， 26（1）： 93-116. DOI： 10.1007/s00291-003-0148-0.

[4]AMBROSINO D， SCIOMACHEN A. A constraints satisfaction approach for master bay plans[J]. Maritime Engineering and Ports， 1998， 36： 155-164.

[5]WINTER T. Online and real-time dispatching problems[D]. Berlin： Technical University of Braunschweig， 1999.

[6]CHO D W. Development of a methodology for containership load planning[D]. Oregon： Oregon State University， 1984.

[7]BOTTER R C， BRINATI M A. Stowage container planning： a model for getting an optimal solution[C]//7th International Conference on Computer Applications in the Automation of Shipyard Operation and Ship Design. IFIP Transactions B： Computer Applications in Technology， 1992： 217-229.

[8]AVRIEL M， PENN M. Exact and approximate solutions of the container ship stowage problem[J]. Computers & Industrial Engineering， 1993， 25： 271-274. DOI： 10.1016/0360-8352（93）90273-Z.

[9]AVRIEL M， PENN M， SHPIRER N， et al. Stowage planning for container ships to reduce the number of shifts[J]. Annals of Operations Research， 1998， 76： 55-71. DOI： 10.1023/A：1018956823693.

[10]AMBROSINO D， SCIOMACHEN A， TANFANI E. Stowing a containership： the master bay plan problem[J]. Transportation Research A， 2004， 38（2）： 81-99. DOI： 10.1016/j.tra.2003.09.002.

[11]SCIOMACHEN A， TANFANI E. A 3D-BPP approach for optimizing stowage plans and terminal productivity[J]. European Journal of Operational Research， 2007， 183： 1433-1446. DOI： 10.1016/j.ejor.2005.11.067.

[12]PACINO D， DELGADO A， JENSEN R M， et al. Fast generation of near-optimal plans for eco-efficient stowage of large container vessels[C]//Proceedings of the Second International Conference on Computational Logistics， 2011. Berlin， Heidelberg： Springer-Verlag， ICCL11： 286-301. DOI： 10.1007/978-3-642-24264-9_22.

[13]DELGADO A， JENSEN R M， JANSTRUP K， et al. A constraint programming model for fast optimal stowage of container vessel bays[J]. European Journal of Operational Research， 2012， 220： 251-261. DOI： 10.1016/j.ejor.2012.01.028.

[14]ZHAO Ning， MI Weijian， MI Chao， et al. Study on vessel slot planning problem in stowage process of outbound containers[J]. Journal of Applied Sciences， 2013， 13（20）： 26-43. DOI： 10.3923/jas.2013.4278.4285.

[15]PARREO F ， PACINO D ， ALVAREZ-VALDES R . A GRASP algorithm for the container stowage slot planning problem[J]. Transportation Research Part E： Logistics and Transportation Review， 2016， 94： 141-157. DOI： 10.1016/j.tre.2016.07.011.

[16]SHEN Yifan， ZHAO Ning， XIA Mengjue， et al. A deep Q-learning network for ship stowage planning problem[J]. Polish Maritime Research， 2017， 24（s1）. DOI： 10.1515/pomr-2017-0111.

[17]COHEN M W， COELHO V N， DAHAN A， et al. Container vessel stowage planning system using genetic algorithm[C]//European Conference on the Applications of Evolutionary Computation. Springer， Cham： Applications of Evolutionary Computation， 2017： 557-572. DOI： 10.1007/978-3-319-55849-3_36.

[18]HELO P， PAUKKU H， SAIRANEN T. Containership cargo profiles， cargo systems， and stowage capacity： key performance indicators[J]. Maritime Economics & Logistics， 2018： 1-21. DOI： 10.1057/s41278-018-0106-z.

[19]BROWNE C B， POWLEY E， WHITEHOUSE D， et al. A survey of Monte Carlo tree search methods[J]. IEEE Transactions on Computational Intelligence & AI in Games， 2012， 4（1）： 1-43. DOI： 10.1109/TCIAIG.2012.2186810.

（編辑 贾裙平）