三阶段分层启发式算法求解装箱问题

沙特国王大学学报基于三阶段分层启发式算法求解平衡约束优素福·哈拉特巴林大学信息技术学院，巴林阿提奇莱因福奥文章历史记录：收到2021年2021年6月30日修订2021年7月8日接受2021年7月15日在线提供保留字：3D装箱问题负载平衡箱方向A B S T R A C T本研究主要探讨三个平行单箱装箱问题。其目的是将不同尺寸和重量的n个箱子装入最少数量的均衡箱子中。盒子可以根据六种可能的方向旋转。平衡箱子的体积和重量是非常重要的。为了实现这一目标，一个三阶段的启发式开发。在第一阶段，生成不同的可能层。每一层都是由相同类型的盒子按照共同的给定方向包装而成。第二阶段使用在阶段1中形成的层生成解决方案候选者。在阶段3中，待运输的箱子被放置在阶段2的候选解决方案之后的箱子中，该解决方案给出了最佳的体积和/或重量利用率。所提出的启发式成功地验证了通过详尽的实验研究，使用各种问题的实例，并涉及与其他现有的启发式比较。©2022由Elsevier B.V.代表沙特国王大学出版。这是一篇开放获取的文章，CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍装 箱 问 题 是 一 个 强 NP- 难 的 组 合 优 化 问 题 ， Korte et al.（2012）。问题是找到一个合适的包装的项目与不同的大小和重量到最小数量的箱子相同或不同的能力。这个问题有许多变化，取决于箱子的尺寸;是否相同或不同的在现实世界的情况下，目标不仅是确定具有最少箱的包装，而且还要生成平衡箱。事实上，装载到飞机货物、卡车或集装箱船中的箱子的质心应该尽可能地落平衡垃圾箱可以提高运输的安全性和效率，并最大限度地减少燃料消耗，Mongeau和Bes（2003年）。在装载物品时以使用最少数量的箱子为目的来平衡箱子是一个多目标冲突问题。沙特国王大学负责同行审查本研究的动机问题本研究主要探讨三个平行单箱装箱问题。重点是确定在最少数量的箱子中物品的最佳正交放置。物品必须按照灵活的旋转方式放置，不得重叠。我们提出了一个三阶段的层为基础的启发式，产生可行的解决方案，显示哪些项目被放置在每个箱和它们的排列方式。第一阶段形成不同的层，每个层根据特定的取向包含相同的物品。在第二阶段中，使用在第一阶段中开发的不同层的最佳可能组合来生成可行的装载空间利用解决方案。最后，一个可行的解决方案（在箱子的体积和重量利用率方面本文的组织结构如下。第二分析了三维装箱问题的相关在第3节中，详细描述了问题的约束条件和目标，第4报告了计算结果。最后，第五部分总结了本文，并提出了一些未来的工作。电子邮件地址：yharrath@uob.edu.bhhttps://doi.org/10.1016/j.jksuci.2021.07.0071319-1578/©2022由Elsevier B. V.出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comY. 哈拉特沙特国王大学学报6426P●¼我ð Þ2. 文献综述经典的多维装箱问题考虑的是箱子数量的最小化。这个问题在文献中得到了广泛的研究。精确的算法，算法和下限已经开发。Martello和Vigo（1998）研究了二维装箱问题，提出了基于分枝定界算法的第一精确方法。Martello等人（2000年）研究了3D情况，并引入了离散角点集以减少其先前精确方法的搜索空间。在Fekete和Schepers（2004）和Fekete et al. （2007）通过区间图定义了多维填充的隐式表示。作者认为，在一个可行的包装盒的相对位置，然后定义一个图形描述的项目在箱子中的重叠的基础上，他们在每个正交轴上的投影。根据这样的特征，作者提出了一个两级搜索树。Eley（2002）提出了一种使用由一种或两种类型的盒子组成的块的概念的算法。此外，Zhang et al. （2012）提出了一种基于多层搜索的单箱3D装箱问题的块加载算法。所研究的问题的一个变体侧重于平衡所使用的箱子的负载。近年来，虽然这些额外的约束增加了问题的复杂性，但该问题吸引了一些研究者。Kaluzny和Shaw（2009年）提出了数学公式来解决确定货物中一组物品的布置问题，以优化单个箱子中的负载平衡。同样的问题在Junqueira et al. （2012），并考虑到更现实的限制，如货物的垂直和水平稳定性和承载强度。针对这一问题，提出了混合整数线性规划模型。除了最小化装载箱中的未使用体积外，现实应用中还遇到许多其他限制，例如稳定性、物品的易碎性、重量分布以及旋转箱子的可能性，Paquay等人（2016）。提出了一种混合整数线性规划方法，并在小规模算例上进行了验证。Trivella和Pisinger（2016）的作者专注于寻找需要最小数量平衡箱的物品包装。负载平衡是通过迫使垃圾箱的质心位于稳定区域内来处理的。Kaabi等人（2018）提出了一种启发式算法，该算法根据权重的降序对项目进行排序，并同时将其放置在预定义的最小数量的箱中，其中在需要时使用附加箱。基于层的建设性方法已经在确保负载平衡的文献。Costa和Captivo（2016）解决了在负载稳定性和箱子方向约束、卡车重量限制以及卡车内部重量均匀分布下的真实世界单卡车包装问题。提出了一种基于层布置方法的构造性启发式算法，该算法包括一个用于放置盒子的角选择策略。在Saraiva等人（2015）中，提出了一种用于多重装箱问题的层构建算法。该算法首先建立水平层的相同的项目，然后greatest生成包装模式，每次加载一层。同样，Ebrahim等人（2019）的作者开发了一种基于层的方法，该方法包括三个阶段，以获得平衡。提出了二维装箱问题的无向模型Clautiaux等人（2007年）也研究了同一问题的不同情景。而在Boschetti（2004）中，作者研究了该问题的3D版本，并开发了2个新的下界。Liao和Hsu（2013）发表了一项更近期的相关工作，提出了新的更好的理论下限。3. 解决方案方法3.1. 假设条件和制约因素所研究的三维装箱问题包括将n个长方体箱子装入一组相同的长方体箱子中，这些箱子的重量和体积都相同。箱子根据其尺寸分为不同的类型。我们考虑了非定向模型，其中允许盒子根据图1所示的六个不同方向旋转。这个问题的约束条件如下。每个盒子都应该完全放在箱子里。箱子不能在箱子内重叠。每个包装盒平行于垃圾箱在一个给定的箱子中装载的箱子的总重量不应超过其最大允许重量。目标是将箱子装入最少数量的平衡箱中。下面是用来描述这个问题的主要符号。● t：长方体类型的数量：尺寸方面● n i：类型i的盒子的数量; i ^l. 不n：所有类型的盒子总数：ntn1/1● m：用于包装n个箱子的箱子数量● D;L;H：料仓的深度、长度和高度● W：垃圾箱● d i; l i和h i：i型箱的深度、长度和高度; i 1/4 1. . 不● w k：箱子的重量k;k1/4.. n● w：第i类箱子的最大允许重量; i¼ 1. 不● S1：平行于长度为L的x轴的箱侧● S2：平行于长度为H● S3：平行于长度D3.2. 三阶段分层启发式算法（TSLBH）3.2.1. 阶段1在第一阶段中，所有可行的水平层相同的盒子被生成通过考虑六个盒子的方向。为了形成水平层，根据图1所示的六个方向中的一个，将最大数量的相同箱子平行于箱子的底部放置。任何层都将包含相同类型的盒子，所有盒子都放置在给定的方向上。总共可以形成6t个不同的水平层。形成水平层的步骤在算法1中示出。这个算法的线性复杂度为O t.此外，在实践中，t不是一个很大的数字，因为不同箱子类型的数量是有限的，正如从FedEx收集的数据所证实的那样。算法1.阶段1：生成水平图层装满了垃圾箱。 箱子中的层由相同的物品组成，相似的方向。项目的旋转是在有限数量的研究中考虑的附加约束。允许旋转的问题称为无向装箱问题。 在Dell1：in：t; D; L; di; li; h ii 1;. ; tout：n ip，... ;t;p¼ 1;. ; 6（每种盒子类型i和每种盒子方向的每一个水平层的最大盒子数量 （第30页）●●●●我Y. 哈拉特沙特国王大学学报64271/1DL¼h1;ph2;pht;pShi;p1/1di;pli;p2：fori← 1 tot doFig. 1. 六种可能的盒子方向。10：如果（Ptri;p×hi;pH），则<3：对于p←1到6，4：n← bc×b C i;p11：S i;p←Stri;p层的盒子类型i，根据朝向p5：returnni;p6：结束锻造7：结束在算法1的步骤4中，di;p表示盒类型i的根据取向p平行于S3的边的长度，并且li;p是盒类型i的根据取向p平行于S1的边的长度。例如，d1; 31/4 l和l1; 31/4h。3.2.2. 阶段2在该阶段中，生成关于箱的体积的所有可行的解决方案。这是通过使用在阶段1中发现的层的不同组合填充箱来实现的。一个可行的解决方案可以通过垂直放置水平层，每个包含相同类型的盒子。箱中的选定图层可以在框类型或框方向方面有所不同。算法2详细描述了生成候选解的过程。注意，hi;p表示盒类型i的边的长度，其平行于S2（垂直边），根据方向p。算法2.阶段2：生成关于箱的体积的可行解1：in：t; D; L; H; di; li; hi; i1;.. . t out：S：可行解集。2：S←£第三章：对于p←1到6，第四章：对于r1;p←1到bHc做5：对于r2;p←1到bHc做6：.七点。八点。第九章：对于r t;p← 1到bHc do12：S←S Si;p13：如果结束14：结束15：结束16：结束17：结束18：返回S变量r i;pi¼ 1;. ;t p¼ 1;.在算法2中使用的是包含根据取向p的类型i的盒子的层的数量，其可以垂直地适合于仓。由于实际中不同盒子类型的数量是有限的，因此该算法中嵌套循环的数量并不庞大。此外，由公式bHc给出的内环迭代次数的上限是一个小常数，从箱的尺寸除以I.因此，算法2具有恒定的复杂度，并且可以在很短的时间内生成可行解集S。请注意，算法2生成的可行解只考虑箱的体积约束。在阶段3的算法3中将考虑箱3.2.3. 阶段3所提出的方法的第3阶段受到Ebrahim等人（2019）开发的LBA-3DBPP算法的启发。该阶段允许在算法2的结果的帮助下，通过将箱子装载到最小数量的箱中来生成可行的解决方案。算法3中所示的伪代码说明了该阶段的步骤。其主要思想是通过检查每种类型的未打包箱子的数量来迭代填充箱子。在每次迭代中，我们选择算法2中生成的候选解，该候选解使用箱的体积的最大值并遵守其最大允许权重。如果剩下的未包装的Y. 哈拉特沙特国王大学学报6428ðÞðÞðjjmhi;p不新台币H←----YHjSj66ðÞ←¼ ¼ j j如果盒子的体积小于一个箱子的体积，那么最后一个箱子被填满，算法停止。请注意，第6行中的while循环的条件确保每种类型都有足够的盒子来形成一个解决方案。否则，即使最后一个箱子的总重量可能对负载平衡目标产生负面影响，也使用新箱子来放置剩余的箱子第11行和第14行之间的嵌套for循环使用来自集合S的最佳可能解决方案候选以顺序方式填充空箱。每个箱子都是以一种方式填充的，它包含重箱和轻箱之间的混合物，以保证箱子之间的一定程度的平衡。行与行之间的for循环图15和图19通过移除添加到当前箱子的那些箱子来更新剩余的未打包箱子的集合，并且移动到填充下一个箱子。算法3具有多项式复杂度，如引理1所示。术语Ht不会对算法产生负面影响-民Rithm复杂度，因为分数是常数，并且t通常具有非常小的值。引理1. 算法3具有一复杂度Omaxtn2log n;民证据1.算法3在第6行中包括一个while循环，它迭代n次。从第7行到第9行的for循环在每一行中转t次，它对剩下的ni个项进行排序。由于排序任务可以在大约nlogn时间内完成，因此，从第6行到第9行的算法的时间复杂度属于O tn2logn。第6行中的while循环与第11行到第22行的嵌套for循环相连接，其复杂度为Ont S。根据算法2，集合S的大小可以在最内层循环中增加1。因为在该算法中有t个嵌套循环，每个循环都转b个H个循环-因此，集合S的大小可以如等式中所示有界。（一）.17：fori← 1 tot do第18章：你是我的女人19：结束20：休息21：如果结束22：结束第23章：结束4. 计算实验为了测试和验证所提出的启发式，一个广泛的实验研究进行了使用联邦快递的真实参数。事实上，箱子尺寸及其最大重量容量、箱子类型及其可能的尺寸和重量以及每天可以接收的箱子数量范围都来自当地的联邦快递办事处。考虑了一种类型的箱和三种类型箱子和箱子的尺寸见表1。不幸的是，我们无法获得箱子数量及其权重的真实数据，这就是为什么我们使用随机计算生成20个不同的问题实例，箱子数量n在1/2 10 0 ;20000 0 0范围内。 重量w k;k 1/4. 类型i的每个盒子的n;i1. t在区间0中随机设置;wi.启发式算法的三个阶段使用Visual Studio 2017C#语言和MS SQL Server 2014数据库实现，以存储箱子和箱子参数以及运输细节。64位Windows 10 Lenovo PC，8.0 GB使用DDR4 SDRAM、Intel CoreTM i7 6700 CPU@3： 40GHz、4个内核和8个逻辑处理器。4.1. 第一实施所提出的试探法的第1阶段的结果总结在表2中。表中的每个值ni;p表示不 bhi;pc1/1Ht民ð1Þ根据给定的盒取向P形成层的类型I的盒的最大数量。阶段2的优点是提供了根据不同取向将箱子装载到箱子中的多种选择。因此，垃圾箱将得到保证。算法3. 第三阶段：生成可行的解决方案（平衡箱）1：in：t;W;n i i¼ 1;. ;t;n out：m填充的平衡箱。2：S←fS1;S2;. ;S r;. ;SjSjg解候选集在第二3：n ir←解S r;i1; 2;.中类型i的盒子的数量 ; t;r1; 2;.. . ; S4：m05：将S按箱子的容积利用率降序排序6：当（有箱子要打包）时7：fori← 1 tot do8：将剩余的ni个未打包的盒子按其重量9：结束10： W Sr ←011：对于r←1到jSj，12：fori← 1 tot do13：WSr←WSr=2个最重的箱子+2个最轻的箱子14：结束15：if（W Sr

下载后可阅读完整内容，剩余1页未读，立即下载