英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
装箱问题：一个问题发生器及其数值模拟FFD包装和MTP的实验
PETRA SCHWERIN和GERHARD WASCHER马丁路德大学，哈勒威登堡，德国
本文提出了装箱问题（Bin-Packing Problem ，BPP）的问题生成器，该方法被推荐用于未来精确启发式求解方法的实证评估。还有一些数值实验是使用FFD Packing来执行的，以便识别装箱问题的难题类别。从结果中可以明显看出，Martello 和Toth之前的测试设计，作者试图验证他们的MTP方法的解决方案的能力，对这种设计一直存在着偏见。因此，已经对来自更具挑战性的问题类别的实例进行了MTP的新实验。我们的结果证实了最普遍的观点，即MTP代表了装箱问题的精确解法的最新技术，尽管在合理的计算时间内问题的程度可以被证明是最佳的，但看起来仍然不太令人满意。
关键词：装箱，启发式，FFD包装，MTP，数值实验
1.引言
装箱问题是一个典型的或问题。它需要将一组给定重量的小物体（物品）打包成相同尺寸（容量）的最小数量的大物体（容器），以便对于每个箱子小物体的总重量不超过其容量。根据迪克霍夫的切割和包装的类型（Dyckhoff，1990），这是一个类型为1/V/I/ M的问题，它被称为NP-完全。因此，研究集中在启发式解决方法（参见Coffman等人，1984），其中FFD包装可能是最知名的。使这种方法具有吸引力的原因不仅在于实施起来快速且容易，而且尽管它具有相当简单的性质，但它似乎提供了高质量的解决方案。实际上，最坏情况和平均情况分析的结果支持后一种观察。由FFD方法提供的目标函数值和最佳目标函数值之间的最坏情况比率是1.5，即适用于所有装箱问题实例（参见Simchi-Levi，1994）。对于足够多的项目，这个比率减少到11/9 = 1.222 ...（参见Coffman et al，1984）。平均而言，由FFD方法提供的目标函数值不超过最优目标功能价值超过2％（约翰逊，1973年，引用于Garey and Johnson，1979）。尽管FFD和其他包装算法的解决方案质量已经有了明显的研究，但仍有必要对这方面进行研究。特别是，了解哪些因素会使装箱问题变得困难并确定FFD方法无法令人满意地解决的问题实例的类别将是很有趣的。
可能由于推测的优秀解决方案质量的启发式只有极少数装箱问题的确切方法已被描述在文献中。少数例外包括Hon和Christofides（1971），Hung和Brown（1978）以及Vance等人的方法（1994） 。MTP（Martello和Toth，1990）经常被认为是目前最先进的方法（Falkenauer，1995）。这种方法的引入伴随着一些数值实验的结果。但是，如后面将介绍的，由于测试设计不令人满意，这些结果似乎并不令人信服。
在本文中，我们将尝试通过一些数值实验来提高有关装箱问题启发式和精确方法性能的知识。特别是，我们打算确定难以解决的问题实例类别，因此可以将其视为新开发方法的基准。 为了做到这一点，我们首先介绍了在实验中使用的问题生成器装箱问题GEN（第2节）。
我们建议将这个问题发生器用于未来的数值实验，因为它可以直接比较不同研究的结果。在第3节中，我们概述了我们的数值实验是如何设计的。 FFD包装的测试结果在第4节中介绍。第5节专门用于MTP的实验。由于MTP使用FFD计算初始界限，所以首先讨论我们的FFD结果对于MTP评估的影响。根据我们自己的FFD包装测试结果，还重新考虑了以前MTP的测试结果（Martello和Toth，1990）。经过这些预备后，MTP的结果将呈现出来，这些结果基于更可靠的实验设计。最后，在第6节中，我们总结了未来研究的一些领域。
- 一个装箱问题的问题发生器
2.1. 装箱问题的问题参数
我们注意到，装箱问题的每个实例都完全由三元组（C，n，w）描述，其中C表示容器容量，n是要打包的项目数，以及n - 相应项目权重的向量。由于装箱问题的每个实例都由n 2个组件组成，因此n也可以称为问题实例的大小，或简称为问题大小。
显然，箱容量C和问题大小n可以首先考虑作为装箱问题的参数。此外，权重w1，w“取值的间隔可能对算法的计算时间和解决方案质量产生严重影响。因此引入额外的问题参数来表征这个间隔。当我们获得一个等价的问题实例时，如果容量C和所有项目权重w1，w“乘以一个正常数，就足以定义这些参数与C有关。通过v1我们表示一个下界，v2和与料仓容量C有关的物品的相对重量的上限，即。
2.2.产生测试问题
每个三元组（C，n，，）描述了一个特定的，同类的装箱问题实例。对于固定的问题参数C，n，和，任何测试问题都可以解释为一个n维随机变量的实现。不失一般性，我们假定它的组成部分是整数。 装箱问题GEN进一步假设组件在区间内均匀分布，并通过以下两个步骤来确定它们的值：
（1）生成在（）上均匀分布的随机变量Y的实现，即Y~U():
= ( (—,)-randi(0, 1)).0 randi(0, 1).
randi（0,1）是均匀分布在开放区间（0,1）中的随机数。
（2）舍入到下一个整数：
=[]
随机变量的任何其他分布也可以在此阶段的装箱问题GEN中实现，只是相同。我们注意到，不一定产生n个不同的物品重量。如果区间的大小（-）C不显着大于n，则情况尤其如此。
为了生成均匀分布的伪随机数，已经选择了乘法同余方法的一个特殊变体，即Lehmer发生器。我们在装箱问题GEN中的实现与用于一维切割库存问题的CUTGEN1相同。就像CUTGEN1一样，发生器的可移植性和随机数的可重复性可以保证适用于不同的计算机和编程语言。发电机是在Gau和Wascher（1995）中进行了全面描述，我们也可以参考该文献的细节实现。本文附录提供了装箱问题GEN的FORTRAN源代码。
2.3.例
设一类问题实例的特征为（C，n，）=（1000,20,0.2,0.7）。 装箱问题GEN已经产生了150个问题，使用1996作为伪随机数发生器的种子。对于测试问题1和150，项目权重如下所示：
测试问题1：
w=（651,638,578,555,524,507,504,475,435,433,408,402,383,349,341,294,221,207,207,202）
测试问题150：
w=（698,671,653,583,515,511,490,489,474,450,390,383,363,332,322,303,271,241,227,204）的情况下。
3.解决方案的质量和最优化的验证
为了评估FFD包装和MTP的解决方案质量，我们主要参考每个问题类别的实例数量，可以验证它是否能找到最佳解决方案。这里不考虑与最佳目标函数或下限的（平均）偏差，因为根据这个标准，两种方法的解的质量都可以被接受。整数一维切割库存问题（1D-CSP）的解决方法测试结果表明，与最佳目标函数值的相对偏差与算法评估没有太大的相关性，而是绝对值。 Wascher和Gau（1996）解决了这个问题的4000个实例中的3984个，这个问题可以被看作是一个装箱问题的高多重版本（参见Hochbaum和Shamir，1991），以达到最优。对于其余的情况，可以显示所获得的目标函数值最多超过最佳值一个单位。
事实上，解决ID-CSP实例的想法也被用于FFD Packing和MTP的实验中。特别是生成的解的最优性还没有通过传统的边界L1，L2和L3（参见Martello和Toth，1990）从bin packing的理论中得到证实，但是IRU Bound最初是为了1D-CSP的最优目标函数值。这个界限是基于 - 同时伪造 - 整数舍入（IRU）性质的1D-CSP，其假定1D-CSP的最优目标函数值可以通过将最优目标函数将相应的连续放宽的1D-CSP的值转换为下一个整数。 Marcotte（1986）已经证明，这种性质并不适用于1D-CSP的所有实例;然而，看起来很难找到矛盾的数字例子。也许更重要的是，IRD Bound和实际最优值之间的差距（完整性差距）大于1的情况下，没有一个C-SP的实例是已知的。因此可以得出结论，IRU界限为1D-CSP的最优目标函数值提供了一个极好的界限。 IRU Bound的另一个优点是可以在合理的计算时间内解决大问题实例，即Gilmore和Gomory（1961）的列生成技术。由于装箱问题和1D-CSP的形式等价，IRU Bound可以立即用作装箱问题的最优目标函数值的新的界限L4。在另一篇论文（Wascher and Schwerin，1998）中，作者表明L4实际上比计算时间可接受的增加的代价优于传统边界L1，L2和L3。因此它也被用于在下面给出的实验中确定最佳解决方案。
4. FFD包装的实验
4.1. FFD包装的简要特性
FFD包装启发式的主要思想是首先包装“最重的”物品，然后用较小的物品填充剩余的空间。 所以包装分两个阶段组织。 首先，根据项目的权重，项目列表按照不增加的顺序进行排序。 所有箱都假定为空并从1到m编制索引。 然后，在所获得的订单中，物品被包装到箱中，使得每个物品被分配到其适合的最低索引箱。 当所有项目都被打包时，该算法终止。
表1.通过FFD包装（N = 100）已经被证明为最佳的问题实例的数量
4.2. FFD包装的测试问题
对于问题类的定义，已经选择了以下参数值：
仓容量：C = 1000
问题大小：n = 20;40;...;180;200
项目权重的下限：= 0.001;0.05;0.25;0.35
项目权重的上限： = 0.1;0.2;...;0.9;1.0
通过组合这些参数值可以获得440类问题。 从每个等级100（= N）通过装箱问题GEN生成测试问题，使得在FFD包装的测试中总共使用了44,000个实例。 对于每个问题类别，问题生成器已经重新启动，并且已经根据以下公式选择了一个起源：
起源（C，n，）= ·（C/ 10） n·（C / 100） C
4.3.结果
FFD Packing的测试结果如表1所示。它们表明关于FFD Packing平均解决方案质量的一般声明可能相当具有误导性，并会模糊算法行为的实际差异。虽然对于一些问题类别，FFD包装倾向于将每个实例解决为最佳状态，但完全失败。一些积极的结果可以立即解释：
对于C = 1000，= 0.001和= 0.1，问题发生器提供了大约50的平均物品重量的测试问题。为了适应n = 20个项目，例如只有两种最佳解决方案是可能的：全部物品可以装入一个箱子，或者需要第二个箱子。如果应用于第二种实例，则FFD包装将为第一个容器生成相当密集的包装。之后，只剩下几件容易被第二个垃圾箱容纳的物品。对于其他问题的规模可以得出类似的论证方式，因此这类问题事实上必须被认为是非常容易的FFD包装。
对于C = 1000，v = 0.25和 = 0.3，也获得了“完美”结果。只要测试问题中不超过三项重量w = 250，就可以通过连续填充三个（任意）项目的分箱来生成解决方案，直到所有项目都被分配为止。只有最后一个箱子可以装满少于三件物品。只有在 - 不太可能的情况下，生成的问题实例包括超过三个重量w = 250的项目，才有可能用四个项目填充一个或多个仓。对于一个最佳解决方案，可能不需要用四个物品包装一个箱子，但如果是这样，FFD包装将为最后要包装的物品产生这样的包装，其然后是重量w = 250。
显然，= 0.35已经获得了微不足道的问题实例。这个特性的两个项目最多可以安装在一个仓中。根据FFD包装，这两个项目是包装在一起，提供最密集的包装方案。由于无法将另一个物品打包在同一个容器中，因此解决方案必须是最佳的。
测试结果也与理论平均情况分析的结果相匹配。尽管我们在解决方案质量评估中使用了不同的标准，但很显然FFD包装对通常考虑用于平均案例分析的问题类别中的测试问题起到了很好的作用（参见Ong et al，1984），即类别（C = 1000，n，= 0.001,0.11.0）。对于不同的问题大小n，通过FFD Packing（85.1％（n = 160）和95.7％（n = 20））已经得到了最优解决（参见表1（a）的最后一行）。然而，测试结果也表明，FFD包装不能一般地令人满意地解决装箱问题，因为平均情况分析的结果可能会存在虚假现象。
启发式特别失败的实例在于类别（C = 1000，n lt;100，v = 0.15,0.2 lt;v2 lt;0.7）和类别（C = 1000，，= 0.25,0.40.5）。
显然，考虑这些问题类别以评估其他算法是有意义的，FFD包装尚未令人满意地解决这些问题。 MTP尤其如此，它使用FFD来生成初始解决方案。为了识别这些类别，我们引用已经通过FFD Packing最优解决的问题实例的百分比p（这里与完全解决的问题实例的绝对数量相同）。我们称之为实例的类（C，n，）：
（FFD-）容易，如果100 80，
（FFD-）很难，如果80 20，
极其（FFD-）困难，如果20 0。
关于MTP解决方案质量的讨论将主要基于对FFD-困难（浅灰色阴影）和极端FFD-hard问题类（深灰色阴影;参见表1（a） - （e））的额外计算实验。 ）。
4.4.使装箱问题（FFD-）变得困难的因素
在附图中，表1（a） - （e）中的材料已根据不同的尺寸汇总并以图形方式呈现。已经确定了三个影响FFD包装
全文共10590字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[9524]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
