1.摘要
本文解决了变压器行业中带有断刀约束的二维矩形切割问题，该问题要求从较大且大小不一的矩形中切割出一组矩形物品，其目标是最小化切割所需物品所使用的料箱数量。为了解决这个问题，本文提出了一种有效离散人工蜂群算法，其采用十进制编码方式，其中每个整数代表一种料箱或物品类型，并通过构造性启发式解码整数列表，以生成符合断刀切割约束的切割模式。此外，还设计了一种复制策略来提高解的质量。
2.问题描述
压板切割问题包括从一组变尺寸的压板中切割一组矩形物品，物品宽度为 w i w_i wi，高度为 h i h_i hi ，需求为 d i d_i di，其中 i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i∈{1,…,n}，压板宽度为 W t W_t Wt，高度为 H t H_t Ht，供给量为 D t D_t Dt，其中 t ∈ { 1 , … , m } t\in\{1,\ldots,m\} t∈{1,…,m}。在排列过程中物品可以旋转90°，当切割模式满足以下条件时，切割是可行的：物品完全放置在板内；物品不重叠；切割是无约束的断刀切割。
目标是尽可能多地利用剩余料，并节省原材料，最终的目标是最小化使用的原材料数量：
N b i n = ∑ W t H t N t / A s N_{bin}=\sum W_tH_tN_t/A_s Nbin=∑WtHtNt/As
其中, N t N_{t} Nt 是原材料压板 t t t 的数量, A s A_{s} As 是最小原材料压板的面积。
3.有效离散人工蜂群算法
本文提出了离散人工蜂群算法（DABC）用于解决二维切割问题，该问题因解空间庞大而难以通过传统精确方法解决，启发式算法易陷入局部最优。DABC通过局部改进与全局搜索相结合，避免了这一问题，并有效计算目标值。该算法在组合优化问题中的优异表现为其应用于2vMSCS-G问题提供了理论基础。
在DABC中，解决方案通过一个正整数列表表示，包含料箱类型和物品类型的编码，该解决方案包括编码列表、目标值和切割模式。
X = ( b 1 , b 2 , ⋯ , b m ; r 1 , r 2 , ⋯ , r n ) X=(b_1,b_2,\cdots,b_m;r_1,r_2,\cdots,r_n) X=(b1,b2,⋯,bm;r1,r2,⋯,rn)
其中， b t ∈ [ 1 , m ] , r i ∈ [ 1 , n ] b_t\in[1,m],r_i\in[1,n] bt∈[1,m],ri∈[1,n]。
DABC雇佣蜂阶段：蜜蜂通过交换操作生成邻近食物源的位置。随机选择编码对进行交换，并通过此操作更新解决方案。观察蜂阶段：观察蜂根据雇佣蜂提供的信息，随机选择更有利的源并通过部分匹配交叉法（PMX）生成新的邻居解。侦查蜂阶段：当源头被认为已耗尽时，侦查蜂生成新的解，并将其替换为原解。该阶段的解通过轮盘赌法和PMX方法生成。
解码过程Pack通过二叉树表示无约束断刀切割模式，叶节点为物品，H和V节点分别表示水平和垂直排列的子模式。Pack根据编码列表建立二叉树，将物品排列到料箱中，并根据面积最小化选择合适的子模式。
复制策略通过在垂直和水平方向复制切割模式，减少料箱空闲空间并优化物品排列。根据料箱尺寸和物品需求，选择复制次数较多的方向，以减少料箱使用并避免剩余物料，从而提升解决方案的质量。
4.结果展示
5.参考文献
[1] Luo Q, Rao Y, Du B. An effective discrete artificial bee colony for the rectangular cutting problem with guillotine in transformer manufacturing[J]. Applied Soft Computing, 2024, 159: 111617.
6.代码获取
xx
7.算法辅导·应用定制·读者交流
xx