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

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

作　　者：滕毅 邓明昱 张嘉琛 陈忆群[1] 王记红 郑怡 TENG Yi;DENG Mingyu;ZHANG Jiachen;CHEN Yiqun;WANG Jihong;ZHENG Yi(Department of Computer Science,Guangdong University of Education,Guangzhou Guangdong 510303,China;School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou Guangdong 510275,China)

机构地区：[1]广东第二师范学院计算机学院,广东广州510303 [2]中山大学计算机学院,广东广州510275

出　　处：《江西师范大学学报（自然科学版）》2024年第1期45-51,共7页Journal of Jiangxi Normal University(Natural Science Edition)

基　　金：国家自然科学基金(62172452);广东省普通高校青年创新人才类课题(2021KQNCX061);广东省教育厅高等教育专项课题(2022GXJK287)资助项目.

摘　　要：不规则条带装箱问题是切分与布局问题的子问题,且在工业制造领域中尤为常见.该文针对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.

关 键 词：闵可夫斯基 遗传算法 装箱问题 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]