一种用于制造领域中具有剪切刀约束的二维可变尺寸箱子装箱问题的混合进化算法

针对变压器绝缘板切割中的二维可变尺寸带割线约束装箱问题，提出混合进化算法框架。通过多树结构编码实现最优板材序列生成，结合基于切割原理的布局策略和随机化选型机制，有效解决少类型高需求量的复杂场景。实验表明该算法在材料利用率、稳定性方面较现有方法提升4%-25%，标准差降低一个量级，且具有显著的统计显著性优势。

　　

强罗|卓赣唐|潘春荣|饶云青

江西科技学院机电工程学院，中国赣州，341000

摘要

本文研究了一种具有挑战性的二维变尺寸装箱问题变体，其特点包括多种箱子尺寸、剪裁约束、可旋转的物品以及少量高需求量的物品类型。该问题的提出源于变压器绝缘压板切割的工业应用。本文提出了一种混合进化算法来解决这一问题。该方法仅对板材类型进行编码，以优化其使用顺序，并通过处理编码结果利用启发式算法生成装箱方案。装箱方案以多树结构表示，并基于切割原理进行构建。在放置物品时，采用随机化策略从候选物品中选择，以避免局部最优解；同时通过复制单个物品来提高装箱的紧凑性。在三个数据集上的广泛实验表明，所提出的方法在获得高质量和稳健的解决方案方面具有优势。该算法在最小化、平均和最大化指标上均显著优于其他元启发式算法，实现了4%至25%的改进。更重要的是，它表现出前所未有的解决方案稳定性，其标准差比竞争对手低一个数量级。此外，随机化策略相较于确定性方法还有2.9%至7.2%的提升。统计测试证实了所有优势的显著性。

引言

二维装箱问题（2DBP）涉及将矩形物品装入容器中，目的是最大化容器空间的利用率以节省材料。生成的装箱方案可用于指导切割容器以取出物品。这是切割与装箱领域中的关键问题之一[1]。

2DBP具有广泛的工业应用，包括木材切割[2,3]、服装面料切割[4]、玻璃制造[5,6]和金属板切割[7]。优化装箱方案可以直接为企业创造巨大经济价值，因为这个问题与产品的材料成本密切相关。

本文研究了变压器绝缘部件生产过程中出现的2DBP问题变体。如图1所示，制造过程包括以下阶段：首先确定每个绝缘部件的封闭矩形尺寸（图1（A）；然后汇总相同矩形部件的需求量（图1（B）——根据压板厚度，五种不同类型的部件被归为两类，需求量分别为13和26；接着根据装箱方案切割压板以获得组件（图1（C）；切割后，将矩形部件堆叠并粘合（图1（D）；最后进行机械加工以达到目标部件的几何形状（图1（E）。

本文研究的特定装箱问题源于压板切割阶段。其目标是将多个矩形物品装入不同尺寸的压板中，以减少使用的压板数量，称为2DVSBP-G。尽管有许多文献研究了2DBP问题，但针对变压器压板切割的这一特定变体的研究仍然不足。其独特特征包括有限供应的变尺寸箱子、少数物品类型但每种类型数量较多，以及为支持高效堆叠处理而必须进行的剪裁。离散人工蜂群算法是一个值得注意的贡献[8]，它采用板材和物品类型编码，并结合基于分组的模式构建和部分模式复制。然而，其物品类型编码结合基于分组的原理可能在物品类型较少的情况下阻碍紧凑模式的形成，而部分模式复制策略可能会无意中复制未使用的空间，且这些部分模式的较大尺寸使得复制失败。

这些不足促使我们提出了本文的方法论发展。我们提出了一种混合进化算法，引入了三项关键创新：首先，我们使用“基于切割”的原理和多树结构来构建模式，并结合基于规则的启发式方法从剩余类型中选择下一个物品类型；其次，我们复制单个物品而不是部分模式，以实现更紧凑的布局；第三，为了降低贪婪选择导致的过早收敛风险，我们引入了一种概率选择前n个候选物品的随机化机制。

本研究的主要贡献如下：

•

针对2DVSBP-G的问题驱动解决方案框架：我们形式化并解决了这一工业变体问题，其特点包括有限的变尺寸压板、少数物品类型但每种类型数量较多，以及堆叠处理所需的强制剪裁。这项工作直接支持工业制造过程。

•

具有改进模式构建的混合进化算法：我们基于切割原理开发了多树结构模式表示方法，引入了提高装箱紧凑性的物品级复制策略，并结合了随机候选项选择机制以增强搜索多样性并减少过早收敛。

•

全面的计算评估和可复现的结果：所提出的方法在三个数据集上与最先进算法进行了对比测试，证明了其在材料利用率和稳健性方面的优越性。所有数据集和实现细节均提供以支持可复现性和未来研究。

本文的其余部分组织如下：第2节提供文献综述，涵盖经典2DBP及其变体；第3节详细阐述问题定义；第4节介绍所提出的方法；第5节报告计算实验和比较分析；第6节总结本文并讨论未来研究方向。

章节片段

文献综述

作为组合优化中的基本课题，2DBP吸引了数十年的研究，主要因其实际应用价值[1]。实际应用带来了由材料属性、切割技术和生产要求带来的复杂约束。这些实际考虑因素推动了解决方案方法的发展，形成了两条互补的研究方向：针对小规模、易处理实例的精确算法，以及启发式方法

问题定义

所研究的装箱问题涉及将一组矩形物品排列到容器中，目标是最大化容器空间的利用率。生成的装箱方案可用于指导切割容器以取出物品。这是切割与装箱领域中的关键问题之一[1]。

2DBP具有广泛的工业应用，包括木材切割[2,3]、服装面料切割[4]、玻璃制造[5,6]和金属板切割[7]。优化装箱方案可以直接为企业创造巨大经济价值，因为这个问题与产品的材料成本密切相关。

本文研究了变压器绝缘部件生产过程中出现的2DBP问题变体。如图1所示，制造过程包括以下阶段：首先确定每个绝缘部件的封闭矩形尺寸（图1（A）；然后汇总相同矩形部件的需求量（图1（B）——根据压板厚度，五种不同类型的部件被归为两类，需求量分别为13和26；接着根据装箱方案切割压板以获得组件（图1（C）；切割后，将矩形部件堆叠并粘合（图1（D）；最后进行机械加工以实现目标部件的几何形状（图1（E）。

本文研究的特定装箱问题源于压板切割阶段。其目标是将多个矩形物品装入不同尺寸的压板中，以减少使用的压板数量，称为2DVSBP-G。尽管有许多文献研究了2DBP问题，但针对变压器压板切割的这一特定变体的研究仍然不足。其独特特征包括有限供应的变尺寸箱子、少数物品类型但每种类型数量较多，以及为支持高效堆叠处理而必须进行的剪裁。离散人工蜂群算法是一个值得注意的贡献[8]，它采用板材和物品类型编码，并结合基于分组的模式构建和部分模式复制。然而，其物品类型编码结合基于分组的原理可能在物品类型较少的情况下阻碍紧凑模式的形成，部分模式复制策略可能会无意中复制未使用的空间，而这些部分模式的较大尺寸使得复制失败。

这些不足促使我们提出了本文的方法论发展。我们提出了一种混合进化算法，引入了三项关键创新：首先，我们使用多树结构结合“基于切割”的原理构建模式，并结合基于规则的启发式方法从所有剩余类型中选择下一个物品类型；其次，我们复制单个物品而不是部分模式，以实现更紧凑的布局；第三，为了降低贪婪选择导致的过早收敛风险，我们引入了一种概率选择前n个候选物品的随机化机制。

本研究的主要贡献如下：

•

针对2DVSBP-G的问题驱动解决方案框架：我们形式化并解决了这一工业变体问题，其特点包括有限的变尺寸压板、少数物品类型但每种类型数量较多，以及堆叠处理所需的强制剪裁。这项工作直接支持工业制造过程。

•

具有改进模式构建的混合进化算法：我们基于切割原理开发了多树结构模式表示方法，引入了提高装箱紧凑性的物品级复制策略，并结合了随机候选项选择机制以增强搜索多样性并减少过早收敛。

•

全面的计算评估和可复现的结果：所提出的方法在三个数据集上与最先进算法进行了对比测试，证明了其在材料利用率和稳健性方面的优越性。所有数据集和实现细节均提供以支持可复现性和未来研究。

本文的其余部分组织如下：第2节提供文献综述，涵盖经典2DBP及其变体；第3节详细阐述问题定义；第4节介绍所提出的方法；第5节报告计算实验和比较分析；第6节总结本文并讨论未来研究方向。

章节片段

文献综述

作为组合优化中的基本课题，2DBP吸引了数十年的研究，这主要归功于其实际应用价值[1]。实际应用带来了由材料属性、切割技术和生产要求带来的复杂约束。这些实际考虑因素推动了解决方案方法的发展，形成了两条互补的研究方向：针对小规模、易处理实例的精确算法，以及启发式方法

问题定义

所研究的装箱问题涉及将一组矩形物品排列到容器中，每个物品的宽度为$w_i$，高度为$h_i$，需求量为$d_i$（对于$i$ = 1, …, $n$），将这些物品放入一组可用的变尺寸箱子中。这些箱子的宽度为$W_t$，高度为$H_t$，供应量为$D_t$（对于$t$ = 1, …, $m$），箱子分为两种类型：剩余材料的有限供应和原材料的充足供应。物品在放置过程中可以旋转90°。如果装箱方案满足以下三个条件，则被认为是可行的：（a）所有物品完全位于

解决方案方法

2DVSBP-G问题是一个高度复杂的组合优化挑战，已被证明是NP完全问题[28]。有效的解决方案方法必须解决三个对结果有很大影响的决策层：物品排序、箱子排序和放置位置。前两个层次分别控制物品和箱子的排列顺序，第三个层次确定可行的放置位置并根据预定义的启发式规则选择放置位置。

计算测试

为了评估所提出算法的性能，我们进行了广泛的计算实验，并将其与文献中的竞争方法进行了比较[8]。所有实验都在配备32 GB RAM的Intel Core i7 3.40 GHz处理器和Windows操作系统的环境中执行。算法使用C++语言在Visual Studio 2022环境中编写，采用单线程执行。

我们在文献中提到的三个数据集（“m1gcut”、“m2gcut”和“m3gcut”）上评估了我们的方法，这些数据集来源于变压器

结论

本研究明确证明了所提出的算法（HEA）在解决具有剪裁约束的复杂二维变尺寸装箱问题（2DVSBP-G）方面的有效性。HEA中有一些针对问题的特定设计选择，用于提高解决方案质量。首先，仅对箱子类型进行编码——而不是同时编码箱子和物品——有效地将进化搜索集中在优化箱子排序上；其次，将基于切割原理的启发式方法与

数据可用性

数据将根据请求提供。

CRediT作者贡献声明

强罗：撰写——原始草案、资源获取、方法论、资金筹集、形式分析、概念化。卓赣唐：撰写——审稿与编辑、可视化、调查、形式分析、数据管理。潘春荣：撰写——审稿与编辑、资源获取。饶云青：撰写——审稿与编辑、监督、资源获取、调查、数据管理。