田　维　张　煜　程惠敏

(武汉理工大学物流工程学院　武汉　430063)

船舶实配现实约束下的装箱排序问题研究*

田维张煜程惠敏

(武汉理工大学物流工程学院武汉430063)

摘要：针对现实约束下的船舶装箱排序问题，利用整数规划方法，以最小化装船时间以及翻倒箱时间成本为目标，构建了该问题的数学模型.利用ILOG CPLEX和分支定界算法，对不同规模案例，按照三种装船发箱规则进行求解，能够获得船舶实配约束下装箱排序问题的精确解，并且发现不同的发箱规则对问题求解的速度和解的质量，有明显的规律特征.算例结果表明，模型构建正确，能够快速求解中小型规模案例.

关键词：船舶配载；装箱排序；整数规划；分支定界

0引言

目前，集装箱运输方式已经成为海上交通货流运输的主要作业方式，在工作效率和经济效率的双重要求下，集装箱的合理装船过程就成为了提高工作效率和经济效率的主要手段之一.堆场集装箱装船至集装箱船舶的装箱排序问题是典型的NP-hard组合优化问题[1]，受到堆场集装箱的摆放、作业机械、集卡运输、船舶结构等因素的影响.因此，研究港口集装箱的装载顺序与装载位置问题，实现有序装载，从而使得装船后船舶的稳定性较高，并减少后续港口的翻箱率，对集装箱船舶运输作业过程有着十分重要的意义.

近年来，已有一些学者对集装箱的装箱排序进行了研究，如王莉莉等[2]对装船顺序的优化过程建立了模型，但模型只考虑了翻箱情况，没有考虑集装箱装船时间的优化；张维英等[3]研究了预配优化模型，但研究的重点是在贝(bay)位选择上，对贝位中集装箱排序没有进行具体研究；李坤等[4]构建了多贝位的整数规划模型，采用禁忌搜索算法求解；祝慧灵等[5]将问题扩展到全航线，船舶贝结构被划分成多个箱位块，不涉及具体贝内箱位的安排，采用遗传算法求解；Maria等[6]建立了最小化装船时间和翻箱的数学模型，但对于集装箱在堆场如何发箱，以及对配载的影响没有进行研究；Ana等[7]结合路径优化建立了多船多港口配载和船舶路径问题的模型，研究主要针对的是全航线的成本的优化，对装箱排序问题研究得不够深入.

文中主要以船舶实配的过程为研究对象，将船舶的贝作为集装箱装载容器，并考虑集装箱后续港口装卸顺序、强度、横倾和堆场集港箱堆码一定等现实约束，探讨集装箱的装载顺序和装载位置，并实现最短装卸时间和最少翻箱量的目标.

1集装箱船装箱排序问题的描述

装箱排序，指的是集装箱按照一定的顺序、服从一定的规则有序装载到集装箱船内指定位置的搬运过程.集装箱的装箱排序问题，分为2个问题：装箱和排序.

装箱是集装箱与箱位的一一对应过程，这种对应性需要考虑很多因素.在船舶装箱过程中，不同重量的集装箱必须对应合适的箱位，以确保船舶的稳定和平衡.而且所有的集装箱在装船后，必须在重量分布上呈现出一种较为均匀的状态，以维持船舶的横倾平衡.在装船过程中，装船时间是影响船舶在港口停靠时间的重要因素，对运输效率的提升至关重要.因此，本文将集装箱的装船时间最为优化目标，尽可能地减少集装箱的装船时间.

排序是集装箱由陆侧起重机装船并按照指定顺序进入集装箱船舱内的过程，一般而言集装箱的装船顺序也就是堆场集装箱的提箱顺序.集装箱的提箱顺序往往会对集装箱的装箱有较大的影响，在不同的顺序规则下，集装箱的装船时间、装载后的位置、船舶的稳定性及后续港的翻箱情况都可能出现较大差异.而翻箱的出现会极大的降低装卸效率，因而本文也将翻箱量作为另一个优化目标.因此，合理安排堆场集装箱的提箱顺序，可以提高集装箱装箱排序过程的工作效率，同时降低运输成本、作业成本，最终提高船、货、港三方的集体经济效益.

在实际中，码头堆场和船舶中的集装箱均是按照贝、列和层的三维空间摆放.一般情况下，集装箱的重量、尺寸、航线、目的港等信息不可随意更改.本文研究的堆场集装箱集合虽然是运往多个目的港的，但都是属于同一条船.在集装箱的装船过程中，应将重量大、航程远的集装箱放在船舶的下面，以避免船舶在后续港口的翻倒箱操作，从而减少运作成本.在整个装船过程中，始终要保持船舶的稳性，同时要尽可能地减少集装箱的装船时间.

2集装箱装船配载模型

2.1模型假设

考虑堆场与船舶的实际情况，本文给出配载问题以下假设：(1)不考虑危险品箱和冷藏箱等特殊箱，只考虑具有相同尺寸的标准集装箱；(2)堆场出口箱已经按类别和目的港进行了分类，同目的港的集装箱已经按照轻、中、重3种类型进行了从下到上的堆码，即堆场集装箱装船时，在堆场内不存在倒箱；(3)堆场集装箱集合装载到船舶的一个贝位内，则船舶待装贝位的容量不小于堆场待装箱集合的势，见图1.

图1　集装箱装载

2.2基本参数

N为堆场待装载到船舶某贝的集装箱集合；I为贝内列的集合；J为贝内层的集合；D为堆场集装箱目的港的集合；k为堆场待装载到船舶贝内的集装箱编号，对应其装船顺序，k∈N={1,2,…,n}；Ji为船舶该贝第i列所有箱位的集合；p=(i,j)为船舶该贝第i列第j层的箱位，i∈I={1,2,…,‖I‖}；j∈Ji={1,2,…,‖Ji‖};L(p)为船舶该贝左侧的箱位的集合；R(p)为船舶该贝右侧的箱位的集合；tp为集装箱装到船舶上p箱位的装船时间，由于陆侧起重机初始位置在船舶最左边的上方，每一层从左向右装船时间逐一递增，按列从上向下装船时间逐一递增，则tp=i+‖J‖-j；π(p)为船舶箱位p上面紧挨它的箱位，即π(p)=(i,j+1)；ωk为集装箱k的重量；θk为集装箱k的重量等级，其值取0，1，2，分别表示轻箱、中箱、重箱，而它们的重量取值范围分别为:轻箱(0,10]t；中箱(10,20]t；重箱(20,30]t；dk为集装箱k的目的港，dk∈D={1,2,…,m}；STi为船舶该贝第i列最大允许的积载强度，一般取80t；HM为船舶贝的最大允许横倾力矩；HM=(‖I‖-1)(d+Δ)δ/2，其中：d为集装箱的宽度，取d=2.438m；Δ为相邻2个集装箱之间的间隙，取Δ=0.3m；δ为力矩敏感系数，可取5，10，15，…，HM的单位为：kN·m.

决策变量为：xkp为集装箱k是否装到船舶上p箱位，为0-1决策变量；ξkp为箱位π(p)的集装箱是否为p箱位集装箱的阻塞箱，为0-1决策变量.

2.3模型

优化目标是使装船时间最小，同时保证在后续港卸船时的翻倒箱数最少.

装船时间是将集装箱从堆场装载到船上的过程中消耗的时间，在堆场消耗的时间(包括堆场提箱时间和吊车行走时间)几乎是固定不能再进行优化的，故本文考虑的装船时间为将集装箱装载到船上的时间.

翻箱时间是船舶贝内相邻集装箱存在阻塞所导致的后续港口卸船所产生的额外操作时间.在后续港卸船时，当且仅当对某个集装箱卸载，才对位于其上方的集装箱进行翻箱操作，翻箱是将阻塞箱放到岸上，待目标箱卸载后，再装回到船上的同一位置，过程见图2.为了便于计算，这2步操作的时间用该集装箱2倍的装/卸时间来表示，将这个操作时间作为惩罚，加上装船时间进行优化.

图2　翻箱操作过程

综上，目标函数：

式中：第1项为堆场集装箱的装船时间，第2项为翻倒箱时间.

约束条件:

1) 同一个箱位最多放一个集装箱，即

(1)

2) 一个集装箱必须占用一个箱位，即

(2)

3) 船舶配载时集装箱不悬空，即

(3)

4) 船舶装载时，堆场先发箱不能置于后发箱的上面，即

(4)

5) 船舶贝位单列的堆积约束，即

(5)

6) 船舶该贝的横倾力矩约束，即

(6)

7) 船舶配载重量等级重不压轻，即

(7)

8) 决策变量ξkp计算

(8)

以上，式(1)～(4)是集装箱装船的规则约束，式(5)～(7)是船舶航行的安全性能约束，式(8)是用来限制变量ξkp的值.

3案例分析

3.1案例描述

对于堆场集装箱的提箱顺序有3种策略，在这样的情况下，堆场不存在翻箱操作：(1)按照层，由高到低顺序提箱(记为R1)；(2)按照列，由左到右顺序发箱(记为R2)；(3)根据目的港，按照层由高到低顺序发箱(记为R3).

假设船舶贝结构有小、中、大3种，见图3，分别记为B1,B2,B3.每种贝结构的每一列的最大承重量如图所示.

图3　贝位图(单位：t)

假设堆场某贝的集装箱个数有12(2个目的港，4列堆放)、28(3个目的港，6列堆放)、40(3个目的港，6列堆放)3种.对每种集装箱个数的集合由Excel随机生成不同重量的案例.以下用B(贝)、N(集装箱数目)、D(目的港数)、R(提箱策略)组合表示案例，如B1-N12-D2-R1-1表示12个集装箱(有2个目的港)的第一个随机案例在第一种提箱策略下装载到船舶B1结构的情况.

3.2案例结果及分析

3.2.1初始案例求解

由于案例具有随机性，故本文针对每个场景下的5个随机案例，均采取了多次仿真求取平均值的处理方式，每一个案例均经过了5次仿真过程，以保证结果的精确性和有效性.

将堆场12个集装箱、28个集装、40个集装箱分别按3种提箱策略，使用CPLEX中的分支定界算法求解.所得到的数据经过处理和分析整理后见表1.

表1　案例的数据处理结果

由于模型对翻箱进行了惩罚，故模型求解的最优解几乎没有翻箱数，即船舶在初始港装船后，后续港卸船时基本不需要翻箱，这就减少了船舶的装卸时间.由表1可知，与R2，R3策略相比，R1策略的运算时间最长，且贝结构越大，集装箱数目越多，即问题规模越大，R1与R2，R3的运算时间的差距越大.

3.2.2增大目的港案例求解

将堆场12个集装箱的目的港增大为4，即集装箱目的港按列从左到右依次为4，3，2，1.将28个集装箱的目的港增大为6，即集装箱目的港按列从左到右依次为6，5，4，3，2，1.提箱策略只有按层和按列2种，再次求解，数据结果见表2.

表2　增大目的港后的案例数据处理结果

而将堆场40个集装箱的目的港增大为6求解.发现有很多案例在两小时内无法求出结果，5个随机案例的求解，数据结果如表3.

表3　B3-N40-D6的数据计算结果

注：*表示案例在2 h内无计算结果.

由此可知，增加集装箱的目的港数，运算时间也会增加.当贝结构增大为B3，堆场集装箱的目的港数增大为6时，问题规模增大，导致该模型程序在2 h内无法求解.并且在R1策略下，模型求解更难.故下面将对此类案例进一步分析.

3.2.3改变力矩敏感系数求解

现改变力矩敏感系数δ的值，进一步分析.选择B3-N40-D6-R1-3和B3-N40-D6-R2-3两个案例分别改变力矩敏感系数.计算结果见表4.

表4　不同δ值下的案例求解结果

由表4可知，当问题规模扩大后，在微小的横倾力矩约束下，模型在2 h内无法求解，若增大横倾力矩系数，即放宽横倾力矩约束，模型有解.而且同样的堆场集装箱集合装载到同样的船舶贝内，不同的提箱顺序下的求解结果明显不同，R1策略使得问题更为复杂，求解时间更长，需要的横倾约束更宽.

4结 束 语

本文提出了以解决堆场集装箱集合装载到船舶的某个贝位确定位置的装箱排序问题，并构建了该问题的混合整数规划模型.该模型可以利用CPLEX中的分支定界算法进行求解.进一步，本文还分析了不同的堆场集装箱提箱策略对船舶配载情况的影响，3种提箱策略相比，按层提箱策略明显增加了模型求解的难度，最容易引起后续港卸船时的翻箱.而堆场中混装集装箱的目的港越多，问题越复杂，模型求解时间越长，但若放宽横倾约束，求解时间可缩短.

参 考 文 献

[1]黎明,翟金刚.集装箱装船顺序的多目标整数规划优化模型[J].计算机应用研究,2012,29(10):3635-3639.

[2]王莉莉,于红.集装箱装船顺序优化模型及遗传算法[J].计算机工程与应用,2008,44(5):234-238.

[3]张维英,林焰,纪卓尚，等.集装箱船全航线预配优化模型与算法研究[J].大连理工大学学报,2008,48(5):673-678.

[4]李坤,唐立新.集装箱码头装船计划问题建模与优化研究[J].控制工程,2015,22(4):683-689.

[5]祝慧灵,计明军.集装箱船舶全航线配载优化模型与改进遗传算法[J].交通运输工程学报,2014,14(5):59-67.

[6]MARIA F M, MARCELLO S, GREGORIO S. The terminal-oriented ship stowage planning problem[J]. European Journal of Operational Research,2014,239(1):256-265.

[7]ANA M, JORGE O, CARINA P. A mathematical model for the container stowage and ship routing problem[J]. Math Model Algor,2013,12(3):217-231.

Research on Sequencing and Bin Packing Problem with Practical Vessel Stowage Constraints

TIAN WeiZHANG YuCHENG Huimin

(SchoolofLogisticsEngineering,WuhanUniversityofTechnology,Wuhan430063,China)

Abstract：In order to solve the sequencing and bin packing problem with practical vessel stowage constraints, a mathematical model of the problem is constructed based on integer programming method, which aims at minimizing the loading time and overstowing time cost. According to three kinds of container sending rules, exact solutions of the cases in different scales of the problem can be obtained by using ILOG CPLEX and branch & bound algorithm. In addition, some obvious characteristics of the speed and quality of the solutions are discovered. The experiment results show that this model is effective and the cases in medium and small scales of the problem can be solved.

Key words：ship stowage; sequencing and bin packing problem; integer programming; branch & bound algorithm

收稿日期：2016-03-26

中图法分类号：U695.2

doi:10.3963/j.issn.2095-3844.2016.03.024

田维(1990- )：女，硕士生，主要研究领域为物流系统建模与优化

*国家自然科学基金项目资助(71372202)