英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

集装箱船舶贝内配载的快速优化约束模型

摘 要

集装箱船舶配载问题需要考虑到经济、环境等因素，是一个复杂的组合优化问题。本文制定的一种贝内配载方法可以在几分钟内快速得到一个较优解，用于大型船舶的配载规划。船舶配载问题分为两个阶段，一、主贝计划阶段，实现集装箱集合与贝集合的匹配；二、贝内计划阶段，确定集装箱在每个贝中的具体摆放位置。本文重点研究了贝内计划，并通过构建结合约束的整数规划模型解决了这一问题。贝内计划需要解决数百个集装箱的配载问题，是一个NP难题。然而，采用先进的约束求解器与建模技术可以加快求解速度，经过236个例子的实证（来自相关合作企业）检验发现，90%的情况下，该问题可以在1秒内得到优化。因此，从某种程度上说，在实际应用中，贝内计划可以在合理时间内得到优化。

关键字：集装箱船舶配载计划，贝内计划，约束规划，整数规划

1 简介

全球大约90%的非散货货物是通过集装箱船进行装载运输的。这里需要考虑的一个非常重要的经济因素是，班轮公司希望装载的时间尽可能短，一方面可以节省装卸的费用，另一方面，可以留出更多的时间用于运输，降低了海上运输的速度要求，还能减少燃料的使用量以及二氧化碳的排放量。多数情况下，配载计划是由配载员运用绘图工具手工绘制产生的，然而，由于配载规划难度较高并且存在许多可以改善的地方，现阶段有越来越多的学者开始关注这一领域，试图拓展规划工具与规划算法。实际上，因为配载员的工作时间限制，以及存在重复计算情况（如装载货物的改变、评价不同的配载方案等），要求这些算法的求解速度必须很快。根据行业发展的现状看，如果算法的求解速度超过了10分钟就会被视为不可行。

本文开发的一种配载优化方法与目前存在的最为成功的配载方法（例如文献[21,24,1]）非常相似，都将配载问题进行了分层。本文运用的两阶段方法如图1所示。首先，在主贝计划中，将集装箱分配到船上的各个贝位。其次，在贝内计划阶段，安排集装箱在每个贝位中的具体位置。

图1 主贝计划与贝内计划示意图

本文重点关注的是贝内计划，所采用的主贝计划方法同文献[16]，一个典型的集装箱船大约有100个贝位，这意味着贝内计划要解决100个独立的贝内集装箱布置规划问题。并且，配载计划的一个重要约束条件是，所有规划必须在10分钟内解决，包括主贝计划与贝内计划，并且二者不能并行解决。因此，本文的目标是1秒钟解决一个贝内配载问题。本文的难点在于，贝内计划是一个NP难题，在每个贝中，需要对数百个集装箱进行布置。

真正的贝内计划要考虑不同船的结构以及集装箱的不同类型，为了让研究更契合实际，作者与相关合作企业共同建立了一种具有代表性的甲板下集装箱配载模型（CSPBDL），这是迄今为止，在作者知识范围内，发表的最为详细的配载模型。

之后，本文将介绍整数规划模型（Integer Programming，IP）以及约束规划模型（Constraint Programming，CP），用来优化CSPBDL问题。CP模型采用了先进的建模技术，包括多视点、特定域修剪规则和动态下界等。IP模型采用0-1模规划，并运用切割加强LP松弛。

虽然贝内计划是个NP难题，并且规模较大，但是本文所设计的算法依然能够快速解决这一问题。本文验证了236个实例，这些实例均来自于相关合作企业的配载实例，见文献[12]。借助CP模型与先进的约束求解器，92%的实例都在1秒内获得了最优解。运用IP模型获得的结果稍逊于CP模型。这一令人惊讶的发现显示，实际贝内计划问题也可以快速得到优化的解。

本文内容大致如下：第二部分界定了本文所研究的问题，第三部分呈现了解决问题所需进行的相关工作，第四部分对IP模型进行了具体描述，第五部分给出了全局约束模型的介绍，第六部分描述的是本文所构建的CP模型，计算结果呈现在第七部分中。第八部分对结果进行了总结与展望。

2 问题现状

集装箱班轮是将集装箱组合起来，沿固定路线循环配送的船舶。船上存放货物的空间都被划分为贝，每个贝又以舱盖板为界，分为甲板上下两部分，舱盖板是水平的，用来防泄漏的，可以防止船舶进水并且保证集装箱摆放平稳，如图2所示。贝经横向划分为堆栈，与集装箱同宽，可以是2个二十英尺标箱组成一个堆栈，也可以是一个四十英尺标箱形成一个堆栈。贝的位置包括舱盖板上下的堆栈集，这些堆栈不一定相邻，图3左边显示了一个贝的典型箱位分布，所有堆栈垂直排列、层层堆叠。每个堆栈都有高度与重量限制，分配时必须满足这些约束。堆栈中的单元可以被划分成两个箱位，一个在前，一个在后。在后方的集装箱面朝船尾，在前方的集装箱面朝船头。由于存在冷藏集装箱，部分箱位还会配有插座，为冷藏集装箱供电，这些插座又称为冷藏插座。码头岸桥将从最上面的集装箱开始，进行装卸。

图2 集装箱船舶的贝分布图

图3 左边为一个贝的箱位分布，右边为堆栈的堆码方式

集装箱是一个存储货物的金属容器，拥有一定的长度、高度及重量，部分集装箱需要电能供应（即冷藏集装箱）。集装箱停泊卸货的港口又称为卸货港。集装箱有20英尺、40英尺以及45英尺长的三种，高度上又可分为8.06英尺与9.06英尺（9.06英尺集装箱又称为超高箱）。20英尺的高箱很罕见，本文建模时不考虑这种箱型。空的20英尺与40英尺集装箱重2吨左右，满载时，分别重24吨与30吨。宽箱比别的集装箱都要宽，只能以固定的肩并肩的模式放置。IMO集装箱携带有危险物品，必须按照复杂的分离规则进行放置。特种集装箱装载的货物尺寸超过了标准集装箱。宽箱、危险品集装箱、特种集装箱往往被放置船舶的特定区域。

每个偶数贝的箱位可以存放一个40英尺或45英尺的集装箱或者两个20英尺的集装箱。45英尺集装箱通常放置在甲板上放，那么其他的位置就被限制为20英尺或40英尺的集装箱。如果存在奇数贝箱位（这是由船的布局决定的），那就只能放置一个20英尺集装箱。例如，图3右侧显示舱盖以下，堆栈的偶数贝箱位混合装载了20英尺与40英尺的集装箱。在进行配载规划前，已经在船上的集装箱称为已装载集装箱。如果一个后到港的集装箱被放置在先到港的集装箱之上，那么这个后到港的集装箱就称为阻塞箱，而这种情况从经济角度看是非常不合理的。

本文研究的是偶数贝箱位的配载问题，在进行集装箱配载的时候考虑了船上可能已有集装箱的情况。由于实际问题中，集装箱的数量较大，配载的规划目标较多，本文联合合作企业开发了具有实际意义的舱盖板下配载模型（CSPBDL），舱盖板上方配载的约束条件和目标与甲板下方的配载基本相同。CSPBDL模型涵盖了配载问题的所有目标与约束条件，求解的算法也与模型有很高的相关度。具体地，CSPBDL模型包括许多堆栈规则，包括20英尺与40英尺集装箱的堆叠规则、冷藏箱、已装载集装箱的位置布局以及对集装箱的高度、重量等的约束。规划的目标要考虑翻箱以及缓解下游港口的配载压力。本文所研究的集装箱尺寸限制在20英尺、40英尺长，以及8.06英尺、9.06英尺高的范围内，包括冷藏箱和非冷藏箱。一个灵活的CSPBDL模型需要满足以下要求：

(1) 所有集装箱必须形成堆栈（集装箱不能悬挂在空气中）；

(2) 20英尺集装箱不能堆在40英尺集装箱上；

(3) 20英尺冷藏想必须被放置在有电源插座的箱位，一个40英尺冷藏箱的箱位上必须有至少一个插座；

(4) 每个箱位必须满足长度约束；

(5) 集装箱的总高度和总重量要满足堆栈的要求；

(6) 所有已装载的集装箱都要被放置在原始的位置上，不得移动；

(7) 偶数贝箱位要么为空，要么装满。

另外，CSPBDL模型的优化通常要满足以下目标：

(1) 使翻箱次数最少，翻箱一次需支付100单位的费用；

(2) 一个堆栈内货物的目的地尽可能相同，每有一个堆栈混装了不同目的港的货物就要支付20单位的费用；

(3) 减少堆栈的用量，提高堆栈的利用效率，每使用一个堆栈需要花费10单位的费用；

(4) 避免非冷藏箱占据冷藏箱箱位，如果非冷藏箱使用冷藏箱位需要多支付5单位的费用。

第2、3、4条法则是船公司在设计配载计划是一定会考虑的问题，由于船的航线涉及到多个卸货港，因此，每个配载计划到要考虑到后续港口的配载问题。尽可能少用堆栈可以提升船的空间利用率，也避免了许多不必要的翻箱操作，因此，配载是要尽可能把同一目的港的货物堆垛到一起。尽可能不占用冷藏箱的位置也是为后续港口装载冷藏箱提供方便。单位成本的计算也是实际配载工作中需要考虑的一个重要指标。

本文将配载问题简化为CSPBDL模型，所有集装箱被统一为40英尺，标准高度，同一个卸货港没有冷藏箱。模型中堆栈高度不设限制，不设冷藏箱插座。任意一个贝内计划，都可以通过CSPBDL模型找到最优解，这也证明了配载问题是NP难题。

3 文献综述

贝内计划优化算法可以作为单阶段配载问题进行研究，也可以成为多阶段配载问题的一部分。前一个研究方向，Avriel等在文献[6]和Dubrovsky与Penn在文献[10]还有Ambrosino与Sciomachen在文献[2]中都提出了简单模型解决整艘船的配载问题，与贝内计划的配载优化相似，Avriel等人运用了0-1整数规划模型，采用悬挂启发式算法求解，将船舶配载问题当作行列的集合进行研究，所有集装箱都被视为同一尺寸，建模目标为翻箱的次数最少。Dubrovsky与Penn提出利用启发式算法求解模型，其模型假设与Avriel等人研究的相同，但可灵活运用与多种类型的集装箱。Ambrosino与Sciomachen提出了一个CSP模型，虽然这个模型用来求解全航线的配载问题，但是模型中对贝内稳定性的约束降低，使之更符合实际贝内计划。这一模型增加了20英尺与40英尺集装箱约束，但是没有考虑冷藏箱与高箱，其目标为使集装箱翻箱次数最少且船舶配载的集装箱数量尽可能多。Aslidis于文献[4]中，Botter和Brinati在文献[7]中，Sciomachen与Tanfani在文献[18]以及Li等在文献 [15]中提出了一个更复杂的模型，包括了主贝计划中的诸多约束条件。Aslidis采用了一种堆叠的启发式算法，使配载结果满足翻箱次数最少的约束条件；Botter和Brinati以及Li等提出了0-1整数规划模型，Botter和Brinati还提出了两种启发式算法求解贝内计划，但这一算法无法推广到实际案例当中。Sciomachen与Tanfani设计了一种基于3D装箱模型的启发式算法，以翻箱次数最少为目标，考虑到了20英尺与40英尺的集装箱，并在模型中加入了高箱。

第二部分中，运用多阶段方法解决贝内计划的整船配载问题，Wilson和 Roach在文献[21]中采用禁忌搜索算法求解贝内计划，并且考虑了冷藏箱箱位、长度限制、最小化翻箱数以及避免同一堆栈内存储不同目的港集装箱等问题，文中说明次优解可以在很短的时间内计算得到，不过其实例中只显示了整船配载的计算结果，没有提供算法的实际计算过程。Kang与Kim在文献[14]中采用枚举法求解简单的贝内计划，在考虑了重量的情况下，优化了翻箱数与40英尺集装箱的排序问题。Ambrosino等在文献[3]中采用了0-1整数规划模型，选取了船的一部分贝位，对卸货港相同的货物进行配载规划。模型以配载时间最短为目标，研究了20英尺箱与40英尺箱，每个集装箱都根据其重量摆放在堆栈中。文章在实例部分生成了198标准集装箱船与2124标准集装箱船的完整配载计划，小船的最大贝容量为20个标准集装箱，大船为120个，并未给出计算时间。后续， Ambrosino等在文献[1]中提出采用结构化启发式方法解决这一子问题，此时，求解规模可以达到5632个标准集装箱，用时11.8s即可完成计算，不过文中没有给出具体的集装箱布局图。Zhang等在文献[23]中、Yoke等在文献[22]用多阶段方法求解贝内计划问题，每阶段求解的问题均相互关联。Guilbert与Paquin在文献[12]介绍了已布局的工业系统，为本文的实例研究提供了数据。他们认为在边界约束下，贝类计划可以作为一个线性规划模型考虑。其模型包含了全部集装箱，大部分的目标与约束在CSPBDL模型中都用到了。他们的研究对象为20英尺箱与40英尺箱，以堆栈的数量最少为目标，只在卸载集装箱时考虑翻箱问题，没有提出约束b。

4 整数规划模型

本文运用了二进制的整数规划模型及解决CSPBDL问题，表1描述了模型所用的常量值、常量集及变量。表格中，前三个变量o、p、e用来计算翻箱(h)、聚簇(i)以及使用的堆栈数(j)，第四个变量c是模型的决策变量，代表了配载计划，第五个变量为引入模型的符号变量，表示的是翻箱目标。这一整数规划模型可以定义为：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

目标函数（1）是CSPBDL问题中定义的4个目标值的加权之和，前三个目标值都可以直接计算得到，在模型中有具体数值可以求出这些结果。在求解第四个目标时，定义了储存在有冷藏箱插槽的位

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153749]，资料为PDF文档或Word文档，PDF文档可免费转换为Word