2维不规则条带装箱问题的一种启发式求解算法

The Solving Two-Dimensional Irregular Striping Problem by a Heuristic Algorithm

不规则条带装箱问题是切分与布局问题的子问题,且在工业制造领域中尤为常见.该文针对2维不规则单箱装箱问题(two-dimensional irregular single bin size bin packing problem)中的特殊变种条带装箱问题,提出结合闵可夫斯基和(即闵可夫斯基加法)与遗传算法的综合求解的算法,其中遗传算法在优化算法中起到整体框架的作用,并在通过闵可夫斯基和寻找到候选放置位置后使用启发式的方法进行放置,同时讨论了在特定情况下该算法与传统优化方法的对比效果.在实际数据测试(50块数据集)中,较成熟的商业软件SVGnest得到的最终面积利用率为78.94%,应用该文的启发式算法,最终面积实用率提升到81.2%.

Irregular striping is a matter of sharding and layout,and is especially common in industrial manufactu-ring.The comprehensive solution by using Minkowski and genetic algorism is proposed in this paper to solve two-dimensional irregular single bin size bin packing problem,especially on variant strip boxing.Genetic algorism builds the framework for the solution and the Minkowski method provides the placing position and heuristic algorithm.The comparison results between this algorism with the traditional optimization method are also discussed.In the actual data test(50 data sets),the final area utilization rate obtained by the mature commercial software SVGnest is 78.94%,and the final area utility rate is increased to 81.2%by using this heuristic algorithm.