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

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

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

　　《物流技术与应用》(月刊)创刊于1996年，由北京科技大学主办。本刊是物流行业知名的精品名刊;广泛报道物流热点、实用技术、经典案例、最新信息。

　　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算法具有以下特点：无须针对具体问题设计求解过程或者启发函数，但可以通过针对性的设计提升对特定问题的求解效率和求解效果;搜索树异步扩展，在分支多(更复杂)的搜索问题中比传统算法表现更好;在已取得可行解的情况下，算法可以随时终止，不需要等待算法最终完成来获得最优解;属于树搜索算法，可以用树搜索算法的优化方法进行优化;算法有可并行性，可以通过并行设计优化求解效果。