牛王强 褚建新 张耀周 徐 涛

(上海海事大学航运技术与控制工程交通行业重点实验室1) 上海 201306) (上海振华重工(集团)股份有限公司陆上重工设计研究院2) 上海 200125)

基于数学规划方法的集装箱船舶自动配载研究进展*

牛王强1)褚建新1)张耀周2)徐 涛2)

(上海海事大学航运技术与控制工程交通行业重点实验室1)上海 201306) (上海振华重工(集团)股份有限公司陆上重工设计研究院2)上海 200125)

给出了数学规划方法处理配载问题的一般思路，从船方和码头方两个角度给出了自动配载问题近十多年的研究进展，指出大容量集装箱船舶和新型装卸设备的出现，以及实时配载策略是自动配载研究的下一个挑战.

集装箱船；船舶配载；数学规划；贝位选择；贝内排箱

0 引 言

集装箱船舶配载是指确定集装箱在船舱的最优位置的过程[1-2].集装箱码头方对配载的要求是，在满足船方要求的基础上，尽可能提高装卸速度，提高码头的利用效率，从而提高码头的经济效益[3-7].

目前，文献中的集装箱船舶自动配载方法有5类：仿真方法(simulation based upon probability)、启发式方法(heuristic driven)、数学规划模型(mathematical programming approach)，专家系统(rule-based expert system)、决策支持系统(decision support systems)[8-10].集装箱船舶的快速自动配载有助于减轻配载员的工作量，有助于提高船方和码头方的经济效益.

数学规划方法的特点是模型准确度高，可扩展性好[11]，是目前最重要的自动配载方法.数学规划方法处理配载问题的一般思路是，首先建立配载问题的整数规划模型，然后设计适当的启发式算法获得配载的次优解.配载的各类业务规则可以由目标函数反映，也可以融入约束条件，也可以嵌入在启发式搜索算法中.为了行文简洁，以下给出各专业词汇的英文简写定义：整数规划，Integer program (IP)；0-1规划，binary program (BIP)；混合整数规划,mixed integer program (MIP)；非线性整数规划,nonlinear integer program (NIP)；约束规划，constraint programming (CP)；贝位选择，group-to-bay (G2B)；贝内排箱，container-to-slot (C2S).

1 船方的优化配载

近十多年来，船方自动配载问题的一个里程碑工作是1999年英国学者Wilson和Roach提出的两阶段分块求解策略，该工作为后续的研究奠定了基调.

1999年，英国Glamorgan大学数学与计算系的Wilson和Roach[12]提出将船舶自动配载问题分为两阶段完成.他们对配载员的人工配载过程进行了分析.指出，配载员首先利用框架性的General Arrangement Document文件完成配载的2个目标：(1)每个目的港货物所占的货物空间最少；(2)每个目的港同时工作的岸桥数量最多.再根据信息更详细的Outline Plan文件完成配载的另外3个目标：(3)舱盖移动的次数最少；(4)倒箱量最少(over-stows)；(5)集装箱所占的货物块最少.这一阶段，配载员不关注每个具体集装箱在船舱的具体位置，而是关注集装箱的总体分布，即将同一目的港同一类型的一群集装箱配置到某块船舶箱位，从而完成封面船图.接着配载员根据最详细的bay plan文件，完成配载的3个目标：(6)倒箱量最少(re-handles)；(7)重下轻上；(8)不同目的港的集装箱放在一个堆垛中的数量最少，给每个集装箱指定具体箱位，生成各个船贝(bay)的箱位图.

结合前人有关集装箱成块配载的工作，以及对配载员配载过程的分析，Wilson和Roach提出将船舶配载问题分为两阶段完成.第一阶段解决舱块选择(group-to-block)子问题，完成集装箱在船上的总体布置.他们将集装箱按照目的港、类型等分成不同的群(group)，也将船贝划分成块(block)，按照配载员的优化目标(1)～(5)，将集装箱群配置到船贝分块.第二阶段解决贝内排箱(C2S)子问题，为每个集装箱指定具体箱位.该阶段完成配载员的优化目标(6)～(8)，给每个货舱块内的集装箱指定具体箱位.

研究表明，第一阶段的分块思想，使得配载可行解个数由几千个下降到100以内，且保存着配载问题的固有特性.同时，第二阶段可行解的搜索空间也减少了许多.英国学者的分块思想以及2阶段策略奠定了后来研究的基调，后续的研究几乎都受到他们工作的影响，不同之处主要是块的大小、各阶段的求解算法、两阶段是同步求解还是顺序求解、船舶稳性的加入等.

文献中，阶段一因货舱块大小的选取不同，有舱块选择(group-to-block)、船贝分块选择(group-to-hold[13])、贝位选择(group-to-bay[14])等，相应的阶段二的container-to-slot问题是舱块排箱、船贝分块排箱、贝位排箱等提法.目前，中文文献将第一阶段称为贝位选择问题，第二阶段称为贝位排箱问题[15-16].将第二阶段命名为贝内排箱更符合Wilson和Roach的思想.

2002年，韩国科学技术院的Kang和Kim基于两阶段策略研究了船舶自动配载问题.2002年，以色列理工学院的Dubrovsky等研究了贝内排箱问题[17].2005年，大连理工大学张维英等研究了集装箱船舶的自动配载问题[18]，采用基于二叉搜索树的启发式装箱算法求解.2007年和2011年，她们对混合目的港和单一目的港的贝内排箱问题也进行了研究.

2011～2012年，丹麦哥本哈根大学的Delgado等基于2阶段策略研究了集装箱船舶的快速自动配载问题.对阶段一的贝位选择问题，考虑了船舶的稳性约束.对阶段二的贝内排箱问题，对比了BIP和CP 2种模型的求解结果.

表1给出了船方的自动配载方法综合比较.预配图的计算都采用了Wilson和Roach的二阶段分块策略，对9 984TEU大船的配载，最快的计算时间小于6 min，符合船方期望的10 min配载时间要求.船方自动配载的首要目标是全航线的翻箱量少，船舶的稳性要求一般由约束条件给出，或者融合在模型的求解算法中.求解算法都是启发式算法，有分支限定法、禁忌搜索、基因算法等.

Wilson和Roach的二阶段分块求解策略是对配载员人工配载过程的模拟，对人工配载过程的进一步挖掘与数学抽象是船舶自动配载的一个重要研究方向.

表1 船方的自动配载方法比较

2 码头方的优化配载

码头方的船舶配载问题复杂度与船方的配载问题复杂度是相当的，不同之处是码头方更关注的是堆场翻箱量少，装卸设备利用率高等.Wilson和Roach的二阶段分块求解预配图策略对码头方实配图的生成仍然有着重要的借鉴作用.

2001年，德国汉堡港口及仓储物流公司steenken等研究了给定船舶的预配图后，堆场跨运车的实时调度问题[19].他们将集装箱进行分批处理，每一批20～60箱，对每批箱子进行1 min内实时优化.出现4类实时性影响因素时，停止当前的集装箱调度算法，对即将调度的20～30箱实时优化，其余出口箱进行全局优化，完成集装箱调度的实时动态调整.

2004年，意大利Genova大学的Ambrosino等研究了主贝计划问题MBPP(master bay plan problem)，该问题实质是考虑了装载时间的船舶配载问题[20].他们采用了单阶段策略进行求解.但是，在设计启发式搜索算法时，仍然采用了先贝位选择，压缩解空间，然后贝内排箱的思想.

2004年，韩国釜山国立大学的Kim等研究了场桥码头出口箱的装载顺序问题[21].他们提出了堆场箱簇(yard-clusters)的概念.同尺寸(TEU，FEU)、同目的港、同类型(干箱、冷藏箱、空箱、特种箱)、同堆场贝的集装箱构成一个堆场箱簇.采用两阶段策略求解，第一阶段的搜索确定堆场箱簇的装载顺序.第二阶段的搜索确定每个堆场箱簇内集装箱的装载顺序.

2006年，Ambrosino等又提出了主贝计划问题的三阶段求解算法[22].第一阶段进行贝位选举.第二阶段完成贝内排箱.第三阶段，交换船贝，使得配载结果满足船舶的稳性要求.2006年，西班牙Pompeu Fabra大学的alvarez研究了正面吊码头集装箱船舶的自动配载问题[23].2006年，日本神户大学的Imai等研究了场桥码头集装箱船舶的自动配载问题[24].

2011年，中国海洋大学杨杰敏等研究了场桥码头集装箱船舶的自动配载问题.提出了船舶配载的3层规划方法.第l层是作业路分配.即确定合理的桥吊作业计划及每个船贝的作业时间表，目标是最短的装卸船完工时间.第2层是堆场动态取箱.即确定船贝分块从堆场上哪些贝取箱，目标是最佳的堆场作业计划.第3层是贝内排箱.

2014年，意大利Calabria大学的Monaco等研究了跨运车码头集装箱船舶的自动配载问题.提出用两步启发式算法来进行模型的求解.第一步进行初始可行解的构造，第二步在初始可行解的邻域进行优化搜索.

表2给出了码头方的自动配载方法综合比较.对于500 TEU的配载，计算时间是1 min，目前尚没有万TEU大船的配载报道.码头方的船舶配载模型、求解方法与船方的船舶配载问题是类似的，求解算法也全是启发式算法.码头方自动配载的首要目标是堆场翻箱量少，装卸设备利用率高(岸桥、场桥的工作时间少，行驶距离短等).

表2 码头方的自动配载方法比较

3 结 束 语

目前，营运中的大型集装箱船容量已经达到14 770 TEU，而建造中的集装箱船容量已经超过18 000 TEU.2万TEU以上大型集装箱船舶的出现，进一步增加了配载问题的解空间，如何进行船舶的快速自动配载仍需要不断研究.双小车双起升岸桥[25]、AGV伴侣、立体装卸码头等新型集装箱装卸设备的出现，对码头方的船舶配载提出了新的挑战.新装卸设备下的船舶自动配载方法也需要进一步研究.

目前，仅有德国学者有关堆场跨运车的实时调度策略研究.在装船过程中，当岸桥、场桥、AGV等装卸设备故障时，或者集装箱故障时，优化的实时自动配载策略也需要进一步研究.

[1]MONACO M F, SAMMARRA M, SORRENTINO G. The terminal-oriented ship stowage planning problem[J]. European Journal of Operational Research, 2014,239(1):256-265.

[2]杨杰敏,丁香乾,郭保琪,等.大型港口集装箱船舶智能配载的集成算法研究[J].中国海洋大学学报：自然科学版,2011(10):121-127.

[3]沈继平.集装箱码头配载业务初探[J].集装箱化,2007(1):9-13.

[4]卫家骏.集装箱船智能配载研究[D].大连:大连海事大学,2012.

[5]张维英,林 焰,纪卓尚.集装箱船全航线bay位排箱优化模型[J].上海交通大学学报,2007(2):199-204.

[6]STEENKEN D, VOB S, STAHLBOCK R. Container terminal operation and operations research-a classification and literature review[J]. OR Spectrum, 2004,26(1):3-49.

[7]杨杰敏.基于作业资源优化调配的集装箱码头智能配载关键技术研究[D].青岛:中国海洋大学,2011.

[8]WILSON I D, ROACH P A. Container stowage planning: a methodology for generating computerised solutions[J]. Journal of the Operational Research Society, 2000,51(11):1248-1255.

[9]张维英.集装箱船全航线配载智能优化研究[D].大连:大连理工大学,2005.

[10]张维英,林 焰,纪卓尚,等.Review of containership stowage plans for full routes[J]. 船舶与海洋工程学报：英文版,2008(4):278-285.

[11]PACINO D, DELGADO A, JENSEN R M, et al. Fast generation of near-optimal plans for eco-efficient stowage of large container vessels[C]. In: Bose JW, Hu H, Jahn C, Shi X, Stahlbock R, Vob S, editors. Computational logistics: Springer Berlin Heidelberg, 2011：286-301.

[12]WILSON I D, ROACH P A. Principles of combinatorial optimization applied to container-ship stowage planning[J]. Journal of Heuristics, 1999,5(4):403-418.

[13]KANG J G, KIM Y D. Stowage planning in maritime container transportation[J]. Journal of the Operational Research Society, 2002,53(4):415-426.

[14]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(1):251-261.

[15]张维英,林 焰,纪卓尚,等.基于指派问题的bay位排箱优化模型与算法[J].大连理工大学学报,2011(1):61-67.

[16]朱明华.多工况集装箱船配载与堆场翻箱优化研究[D].上海:上海交通大学,2011.

[17]DUBROVSKY O, LEVITIN G, PENN M. A genetic algorithm with a compact solution encoding for the container ship stowage problem[J]. Journal of Heuristics, 2002,8(6):585-599.

[18]张维英,林 焰,纪卓尚,等.Model and algorithm for container ship stowage planning based on bin-packing problem[J].船舶与海洋工程学报：英文版,2005(3):30-36.

[19]STEENKEN D, WINTER T, ZIMMERMANN U. Stowage and transport optimization in ship planning[G]. Grotschel M, Krumke S O, Rambau J. Online Optimization of Large Scale Systems: Springer Berlin Heidelberg, 2001：731-745.

[20]AMBROSINO D, SCIOMACHEN A, TANFANI E. Stowing a containership: The master bay plan problem[J]. Transportation Research Part A: Policy and Practice, 2004,38(2):81-99.

[21]KIM K, KANG J, RYU K. A beam search algorithm for the load sequencing of outbound containers in port container terminals[J]. OR Spectrum, 2004,26(1):93-116.

[22]AMBROSINO D, SCIOMACHEN A, TANFANI E. A decomposition heuristics for the container ship stowage problem[J]. Journal of Heuristics, 2006,12(3):211-233.

[23]ALVAREZ J. A heuristic for vessel planning in a reach stacker terminal[J]. Journal of Maritime Research, 2006,3(1):3-16.

[24]IMAI A, SASAKI K, NISHIMURA E, et al. Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks[J]. European Journal of Operational Research, 2006,171(2):373-389.

[25]STAHLBOCK R, VOB S. Operations research at container terminals: a literature update[J]. OR Spectrum, 2008,30(1):1-52.

Review of Container Ship Automatic Stowage Based on Mathematical Programming Approaches

NIU Wangqiang1)CHU Jianxin1)ZHANG Yaozhou2)XU Tao2)

(KeyLaboratoryofMarineTechnologyandControlEngineering，MinistryofCommunications，ShanghaiMaritimeUniversity，Shanghai201306,China)1)(OnshoreHeavyIndustriesR&DInstitute,ShanghaiZhenhuaHeavyIndustryCo.,Ltd,Shanghai200125,China)2)

Mathematical programming approaches are the most important methods for container ship automatic stowage problem. First, the general idea is given to show how to deal with container stowage problem by a mathematical programming method; then works of automatic stowage problem in recent ten years are reviewed from the point of view of shipping lines and ports; finally, two future challenges of automatic stowage problem are pointed out, one is the emergence of super-sized container ship and novel loading and unloading equipments, and the other is real time stowage strategies.

container ship; ship stowage; mathematical programming; group-to-bay; container-to-slot

2015-01-28

*国家发改委发改办高技术项目(批准号：[2013]2519号)、2013年度上海市战略性新兴产业重点项目资助

U695.22

10.3963/j.issn.2095-3844.2015.03.015

牛王强(1977- )：男，博士，讲师，主要研究领域为船舶、港口自动化与网络控制