二维一刀切装箱问题的两阶段启发式算法

• 论文 •

二维一刀切装箱问题的两阶段启发式算法

曹大勇，杨梅，科托夫·弗拉基米尔·米哈伊拉维奇，刘润涛

1.哈尔滨理工大学应用数学系，黑龙江哈尔滨150080；2.哈尔滨工业大学电气工程系，黑龙江哈尔滨150001；3.白俄罗斯国立大学应用数学与计算机系，白俄罗斯明斯克220030；4.哈尔滨理工大学信息与科学计算技术研究所，黑龙江哈尔滨150080

出版日期:2012-09-15 发布日期:2012-09-25

Two-stage heuristic algorithm for two-dimensional guillotine bin packing problem

CAO Da-yong, YANG Mei, V. M. Kotov, LIU Run-tao

1.Department of Applied Mathematics, Harbin University of Science and Technology, Harbin 150080, China;2.Department of Electrical Engineering, Harbin Institute of Technology, Harbin 150001, China; 3.Department of Applied Mathematics and Computer Science, Belarusian State University, Minsk 220030, Belarus;4.Institute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080, China

Online:2012-09-15 Published:2012-09-25

摘要/Abstract

摘要： 对用于二维带排样问题的Heuristic Recursive算法进行了调整,给出同一层中两个相邻浪费区域在满足一刀切约束下是否可合并的判定定理。构造了二维带排样问题的多递归层算法,并将它与一维装箱问题的最优匹配递减算法相结合,提出适应二维一刀切非旋转装箱问题的两阶段算法。在500组标准测试案例的基础上,与多种算法进行了比较。实验结果表明,所提算法在绝大多数测试案例上能够获得更好的排样布局。

关键词: 递归算法, 启发式算法, 一刀切, 二维非旋转装箱问题

Abstract: The Heuristic Recursive(HR)algorithm for two-dimensional strip packing problem was adjusted, and a judgment theorem which was used to determine whether two neighbor wasted spaces in same layer could be combine or not was presented. A multi-recursive algorithm for two-dimensional strip packing problem(2D-SPP)was constructed, and a Two-Stage Approach(TSA)for two-dimensional oriented guillotine bin packing problem was proposed by combining the algorithm with Best-Fit Decreasing(BFD)algorithm of one-dimensional bin packing problem. On the basis of 500 group benchmark problems, the approach was compared with multiple algorithms, the experiments showed that the proposed approach could obtain better results for almost all test instances.

Key words: recursive algorithms, heuristic algorithms, guillotine, 2D oriented bin packing problem

中图分类号:

TH164
TP311

曹大勇，杨梅，科托夫·弗拉基米尔·米哈伊拉维奇，刘润涛. 二维一刀切装箱问题的两阶段启发式算法[J]. .

CAO Da-yong, YANG Mei, V. M. Kotov, LIU Run-tao. Two-stage heuristic algorithm for two-dimensional guillotine bin packing problem[J]. .

[1]	汪逸晖,高亮. 乌鸦搜索算法的改进及其在工程约束优化问题中的应用[J]. 计算机集成制造系统, 2021, 27(7): 1871-1883.
[2]	高勃,张红艳,朱明皓. 面向智能制造的不规则零件排样优化算法[J]. 计算机集成制造系统, 2021, 27(6): 1673-1680.
[3]	顾文斌,李育鑫,钱煜晖,肖紫涵,秦展鹏. 基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2858-2871.
[4]	冷龙龙,赵燕伟,蒋海青,张春苗,王舜. 求解物流配送同时取送货低碳选址—路径问题的量子超启发式算法[J]. 计算机集成制造系统, 2020, 26(第3): 815-828.
[5]	曹浩,莫蓉,万能. 面向支撑力分布的桁架结构设计方法[J]. 计算机集成制造系统, 2020, 26(7): 1763-1770.
[6]	林煊,陈庆新,毛宁. 板式家具高速自动分拣系统出库及打包调度策略[J]. 计算机集成制造系统, 2020, 26(7): 1843-1854.
[7]	张景玲,刘金龙,赵燕伟,王宏伟,冷龙龙,冯勤炳. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
[8]	冷龙龙,赵燕伟,张春苗. 基于共享机制的自适应超启发式算法求解区域化低碳选址—路径问题[J]. 计算机集成制造系统, 2020, 26(5期): 1407-1424.
[9]	王亚娜,江文辉,王桐远,李延来. 垂直差异产品的产品组合、价格与库存联合决策[J]. 计算机集成制造系统, 2020, 26(11): 3129-3141.
[10]	吴秀丽,张志强,赵宁,李俊青. 超启发式文化基因算法优化生产与预维修集成调度问题[J]. 计算机集成制造系统, 2019, 25(第8): 1885-1896.
[11]	罗强,饶运清,刘泉辉,李世红. 求解矩形件排样问题的十进制狼群算法[J]. 计算机集成制造系统, 2019, 25(第5): 1169-1179.
[12]	管超,张则强,毛丽丽,李六柯. 双层过道布置问题的混合整数规划模型及启发式求解方法[J]. 计算机集成制造系统, 2018, 24(第8): 1972-1982.
[13]	尚正阳,顾寄南,丁卫,Enock A.Duodu. 求解二维矩形装箱问题的启发式算法[J]. 计算机集成制造系统, 2018, 24(第3): 583-590.
[14]	崔琪,吴秀丽,余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(第9期): 1917-1927.
[15]	刘玉琢,李铁克,王柏琳. 多种圆坯规格的无缝钢管坯料设计模型与算法[J]. 计算机集成制造系统, 2017, 23(第3期): 507-514.