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

集装箱装载的约束条件——对发展现状的综述

摘要：装箱是供应链高效运作的关键一环。配载不合理会导致不必要的支出（例如额外的集装箱装船费用）和降低客户服务满意度（例如违反了协议达成的或客户设定的截止日期）。因此，装箱问题频繁地出现在研究供应链运作的文献中也不足为奇了。然而已经提出的方案对实践中遇到的约束问题没有加以足够的关注，所以被认为实用价值不大。

本文提出了对装箱领域的发展现状的看法。我们从实用的角度提出了处理装箱问题时应考虑的因素，并分析了这些因素是否以及如何在解决方法中体现。建模方法、分支定界算法和启发式算法也会加以论述。这考虑到评估该领域中已进行的研究的实际相关性。我们也会涉及一些目前尚未完善解决的问题并展望未来研究的机遇。

关键词：集装箱装载 切割 装入 约束条件 分支界定算法 启发式算法

1 引言

15多年前，Bischoff和Ratcliff（1995a）曾讨论过，“hellip;hellip;现有的解决装箱问题的方法只各自适用于实践中遇到的一小部分情况hellip;hellip;”（377页）。他们进一步提出了，“hellip;hellip;很多实际情况中常遇到的的重要因素在运筹学文献中并未得到充分关注。”（378页）。

这篇论文旨在论述装箱领域的发展现状，将对Bischoff和Ratcliff所提到的因素在文献中是否被考虑到、以及被考虑到什么程度给予特别的关注。这考虑到评估该领域中已进行的研究的实际相关性。

第3部分说明了如何划定我们研究的主题及引用了哪种文献。我们的调查研究基本上是通过确定每个出版物研究了哪类问题来开始的。同时，对应数据的一个简短的（正式的）统计分析也会在这部分呈现出来。

第4部分是我们研究的核心部分。与Bischoff和Ratcliff（1995a）的论文不同，文中对装箱的实际相关方面进行了详尽的分析。并且，业内从业者在访问中提出的要点也对我们的研究进行了补充。总体而言我们认为这些因素表现为约束条件。因此，作为我们研究的一个结果，我们提供了一个有关装箱约束条件的综合列表，并且第一次引入了依据类型分类的方案。此外，我们对约束条件进行分类并细致地描述了文献中提到的不同方法是如何处理各自的情况的。

第5部分,我们将对问题类型的观察结果和文献中考虑到的约束条件进行总结。并且对不同类型的建模方法和分支界定算法、启发式算法的发展现状也进行了简要的调查。第6部分总结得到了几个一般结论。尤其是我们也会涉及一些，从我们的角度来看，目前尚未完善解决的问题并展望未来研究的机遇。

我们的论述从装箱问题的定义和简单分类开始。

2装箱问题——定义和分类

装箱问题可以理解为几何分配问题，三维小物品（称之为货物）被分配（打包进入）三维矩形（立体）的大型物体（称之为集装箱），由此给定的目标功能得到优化、两者的几何性质也都保持不变。

· 所有的小物品都完全摆放在集装箱内

· 物品之间不相互重叠

像这样对分配问题进行正式描述的解决方案叫装载模式。

我们注意到这个大型物体实际上可能是一个集装箱，但是根据所给的定义，它也可能是一个卡车的货厢或者可以装到一定高度的托盘。

一般来说这些小物品可能会有各种规则（矩形的、球形的等等）或不规则的形状。然而，绝大多数装箱领域的文献处理的都只是规则物品。从文献的一般术语角度来说，我们把这些物品叫做“箱子”。

此外我们认为涉及到切割装入（Camp;P）的标准问题已经意味着，某些假设（比如关于目标功能、箱子和集装箱的分类等等）让装箱问题仍有待讨论。尤其是，无论何时装箱，与现存文献一样，我们都假设只允许垂直位置，即箱子的表面要与集装箱的地面和墙保持平行。

根据Wauml;scher等人(2007)介绍的类型学，可以区分关于集装箱和货物分类的装箱问题。集装箱（同样地也包括货物）无论形状和尺寸，只要是相同的就是同类型的。如果集装箱（货物）的分类是少种多量的，那么可以认为它们的类型是弱异类；如果没有或只有很少集装箱（货物）是相同形状和尺寸的，则称之为强异类。

另外，我们还可以区分装箱问题中，用于容纳货物的集装箱数量是否充足的情形。在这两种不同情形下所要实现的目标也不同。前者属于输入（值）最小化类型，后者属于输出（值）最大化类型。

输入（值）最小化问题有以下类型：

· 单一标准尺寸的切割储存问题（SSSCSP）

将一批弱异类的货物装入最少数量的相同集装箱中。

· 多种标准尺寸的切割储存问题（MSSCSP）

将一批弱异类的货物装入弱异类集装箱中，将已使用的集装箱的值最小化。

· 剩余切割储存问题（RCSP）

将一批弱异类的货物装入强异类集装箱中，将已使用的集装箱的值最小化。

· 单一容器尺寸装箱问题（SBSBPP）

将一批强异类的货物装入最少数量的相同集装箱中。

· 多种容器尺寸装箱问题（MBSBPP）

将一批强异类的货物装入弱异类集装箱中，将已使用的集装箱的值最小化。

· 剩余装箱问题（RBPP）

将一批强异类的货物装入强异类集装箱中，将已使用的集装箱的值最小化。

· 开放式尺寸问题（ODP）

将一批货物装入多种尺寸的单一集装箱，将集装箱体积最小化。

对Wauml;scher等人(2007)的类型学进行扩展，关于开放式尺寸问题（ODP）可以进一步区分弱异类货物（ODP/W）和强异类货物（ODP/S）问题。

输出（值）最大化问题有以下类型：

· 相同物品装箱问题（IIPP）

一个集装箱内装入最多数量的相同货物。

· 单一大型物体布置问题（SLOPP）

选择一批弱异类货物装入一个单一集装箱，使已装入的货物的值最大化。

· 多个相同大型物体布置问题（MILOPP）

选择一批弱异类货物装入一批相同集装箱，使已装入的货物的值最大化。

· 多个异类大型物体布置问题（MHLOPP）

选择一批弱异类货物装入一批（弱或强）异类集装箱，使已装入的货物的值最大化。

· 单一背包问题（SKP）

选择一批强异类货物装入一个单一集装箱，使已装入的货物的值最大化。

· 多个相同背包问题（MIKP）

选择一批强异类货物装入一批相同集装箱，使已装入的货物的值最大化。

· 多个异类背包问题（MHKP）

选择一批弱异类货物装入一批（弱或强）异类集装箱，使已装入的货物的值最大化。

我们注意到当货物数量与体积成比例时，输出（值）最大化等于集装箱空间利用率的最大化。

接下来将在这个分类的基础上进行描述。特别地，我们稍后会分析目前装箱文献中实际考虑了这些问题中的哪些。我们发现关于上文给出的术语“货物”和“集装箱”的定义，装箱问题在这里完全被看做是三维（3D）Camp;P问题。显然到目前我们已经避免使用这个形容词了，在接下来也会继续这么做。

3 综述文献——特征描述与基础分析

对于我们的论述，我们的分析仅限于在国际杂志、编辑卷及1980年至2011年末的会议记录上发表的对公众开放和已经用英文出版的文件。也包括2011年之前网络上公开的出版物。专刊、论文及工作文件则不考虑在内。

我们关注的出版物所处理的问题类型，相对于Wauml;scher等人(2007)是改进完善过的。有关于问题的延伸（例如车辆路径与装卸结合的问题）和变体（例如线上问题）的文献，我们也会加以关注。托盘上用于载货的空间也可以看做是一个集装箱容器。因此，关于三维托盘配载的文章也考虑在内。此外，关于切割装入问题的二元性，也包括三维切割问题方面的论文。另一方面，有些三维Camp;P问题，比如圆柱体物品的装箱（参见Correia等人2000年的文献），被简化为二维甚至一维问题，而这方面的文献却被忽视了。

最后，我们的文章没有参考三维Camp;P方面的决策类文献。这方面的研究似乎才刚开始，目前专注于所谓的垂直装入问题（OPP），无论给定的一组货物能否把所有箱子无重叠的垂直装入给定的矩形集装箱内，这个问题都要做决策。而在上文提及的装箱优化中，这个问题对解决方案的发展起着关键的作用（参见Fekete等人2007年的文献）。然而，相关资料依然很少（尽我所知，有关OPP的现只有三份，即，Fekete与Schepers（1997）、Fekete等人（2007）及Belov等人（2011）发表的文献），他们也并未真正地关注实际相关的约束条件。

至2011年12月，163份论文已被确定满足这些标准。附录A中的表格A.1列出了这些论文，确定了相应的问题类型并提到了涉及到的约束条件。一般地，我们会把这些论文里讨论的相应的问题类型也归为“装箱问题”，因为有大量文献明确地涉及到这类问题。不过，我们意识到一些论文实际上描述的可能是切割问题。表格1说明了装箱方面的文献数量是如何随时间发展的。

正如我们在Camp;P领域一般所见，装箱领域的出版物数量也在增长。尤其值得注意的是过去两年里（2010至2011）所出版的论文几乎和这之前五年（2005至2009）数量相当。

表格1 1980至2011年间已出版的有关装箱的论文数量

4 装箱约束条件

在这部分，我们将介绍在装箱时会遇到的实际相关的约束条件并确定他们是否以及如何在文献中体现。要区分大型物体相关约束条件（有关集装箱的约束条件）和小物品相关约束条件，后者可指独立物品（有关物品的约束条件）或一整批物品（有关货物的约束条件）。此外，约束条件也可能与大型物体和小物品间的关系有关。这在集装箱内物品的位置约束条件中表现出来。最后，约束条件可能与装箱过程有关，即与装载有关（有关装载的约束条件）。

装箱约束条件可以是硬性的也可以是柔性的。硬性约束条件是必须满足的；违反了硬性约束条件的装载模式是不可行的。柔性约束条件就只是保持，在一定限度内违背了也可以接受。

4.1 有关集装箱的约束条件

4.1.1 重量限制

一个集装箱装货一般不能超过某个重量限制。这样的约束条件可能并不总是很明显（也就是当需要装箱的物品由泡沫橡胶制品组成时），然而，当重物装箱时这些限制就很重要了。在这些情况下，重量限制可能比集装箱尺寸造成的空间约束更加严格。

在这163份装箱文献中，有23份（14.1%）涉及了重量限制，例如，Liu与Chen（1981）、Gehring与Bortfeldt（1997）、Terno等人（2000）、Chan等人（2006）Egeblad等人（2010）及Liu等人（2011a）的文献。在所有这些文献中，强调的都是硬性约束条件。

重量限制可以用一种直接的方式建立线性背包约束模型，已装物品的总重量必须小于或等于集装箱的重量限制。在装箱算法中，会对解决方案的可行性进行一个简单快速的检查。

在文献中，重量约束常反映一个针对特定Camp;P延伸问题的综合解决方案的问题，即集装箱装卸与车辆路径结合的问题，然而这并无意义（Gendreau等人（2006）、Tarantilis等人（2009）、Fuellerer等人（2010）、Lori与Martello（2010）、Wang等人（2010）、Bortfeldt（2011）的文献）。一批给定货物由中心仓库提供并发送给分散的客户，其中每个物品的特性除了几何尺寸还有重量。物品由一组车辆运输，这些车辆一般设定为同种且具有一定载荷能力（重量限制）。延伸问题的目标主要有，找到一组将总距离最小化的路线和一组相应的能满足每辆车空间和载重能力约束的装载模式。

Dereli与Das（2010）处理的是SKP类型的问题，集装箱的

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

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