基于启发式动态分解算法的矩形件优化排样

doi:10.11772/j.issn.1001-9081.2013.07.1908

计算机应用 ›› 2013, Vol. 33 ›› Issue (07): 1908-1911.DOI: 10.11772/j.issn.1001-9081.2013.07.1908

基于启发式动态分解算法的矩形件优化排样

李波¹,王石²,施松新³,胡俊勇¹

1. 湖北文理学院机械与汽车工程学院，湖北襄阳 441053
2. 东莞华中科技大学制造工程研究院信息技术部，广东东莞 523808
3. 华中科技大学机械科学与工程学院，武汉 430074

收稿日期:2013-01-16 修回日期:2013-02-22 出版日期:2013-07-01 发布日期:2013-07-06
通讯作者: 李波
作者简介:李波(1977-)，男，四川隆昌人，讲师，博士，主要研究方向：智能优化、先进制造；王石(1977-)，男，广东东莞人，高级工程师，硕士，主要研究方向：智能优化；施松新(1978-)，男，湖北襄阳人，副教授，博士，主要研究方向：计算机仿真。
基金资助:
国家863计划项目(2011A0405);湖北文理学院博士科研基金资助项目

Optimum packing of rectangles based on heuristic dynamic decomposition algorithm

LI Bo¹,WANG Shi²,SHI Songxin³,HU Junyong¹

1. School of Mechanical and Automotive Engineering, Hubei University of Arts and Science, Xiangyang Hubei 441053, China
2. Ministry of Information Technology, DG-HUST Manufacturing Engineering Institute, Dongguan Guangdong 523808, China
3. School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan Hubei 430074, China

Received:2013-01-16 Revised:2013-02-22 Online:2013-07-06 Published:2013-07-01
Contact: LI Bo

摘要/Abstract

摘要： 针对二维矩形件优化排样问题，提出了一种启发式动态分解算法，其可扩展用于三维及多容器全局排样求解。根据排放矩形件对容器进行正交动态分解，计算放置耦合度选择最佳子容器，通过干涉关系实现所有容器状态更新，实现大规模复杂排样问题的快速高效求解。对国际上公认Bench-mark多个问题例的计算结果表明，所提算法与同类算法相比优势明显，布局利用率提高达9.4%，计算效率提升达95.7%，并且已在商业化排样软件AutoCUT中应用，应用前景良好。

关键词: 矩形件排样, 启发式, 动态分解, 优化

Abstract: To solve the optimum packing of two-dimensional rectangle layout problem, a heuristic dynamic decomposition algorithm was proposed, which can be used in the three-dimensional rectangule layout and global optimization problems. The container was orthogonally decomposed according to the emission rectangles, and the best sub-container was selected according to the degree of place coupling, then the state of all containers was updated by the interference relationship, so the large-scale and complex problem can be solved quickly and efficiently. The experimental results of the Bench-mark cases internationally recognized show that the proposed algorithm has better performance compared with similar algorithms, in which the layout utilization efficiency is increased by 9.4% and the calculating efficiency is improved up to 95.7%. Finally the algorithm has been applied to the commercialized packing software AutoCUT, and it has good application prospects.

Key words: rectangle-packing, heuristic, dynamic decomposition, optimization

中图分类号:

TH301.06

李波王石施松新胡俊勇. 基于启发式动态分解算法的矩形件优化排样[J]. 计算机应用, 2013, 33(07): 1908-1911.

LI Bo WANG Shi SHI Songxin HU Junyong. Optimum packing of rectangles based on heuristic dynamic decomposition algorithm[J]. Journal of Computer Applications, 2013, 33(07): 1908-1911.

参考文献

［1］LODI A, MARTELLO S, MONACI M. Two-dimensional packing problems： a survey ［J］. European Journal of Operational Research, 2002, 141(2)： 241-252.

［2］LEUNG J Y T, TAM T W, WONG C S, et al. Packing squares into square ［J］. Journal of Parallel and Distributed Computing, 1990, 10(3)： 271-275.

［3］LIU D Q, TENG H F. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles ［J］. European Journal of Operational Research, 1999, 112(2)： 413-419.

［4］HIFI M, M'HALLAH R. A hybrid algorithm for the two-dimensional layout problem： the cases of regular and irregularshapes ［J］. International Transactions in Operational Research, 2003, 10(3)： 195-216.

［5］MARTELLO S, MONACI M, VIGO D. An exact approach to the strip-packing problem ［J］. INFORMS Journal on Computing, 2003, 15(3)： 310-319.

［6］陈端兵，黄文奇.求解矩形 packing 问题的贪心算法［J］．计算机工程，2007,33(4)：160-162.

［7］张德富，韩水华，叶卫国．求解矩形Packing问题的砌墙式启发式算法［J］．计算机学报,2008,31(3)：509-515.

［8］梁军，王强，程灿，等．基于离散粒子群算法的矩形件优化排样［J］．计算机工程与设计,2007,28(11)：5359-5510.

［9］LIN C C. A genetic algorithm for solving the two-dimensional assortment problem ［J］. Computers and Industrial Engineering, 2006, 50(1)： 175-184.

［10］LEUNG S C H, ZHANG D F, SIM K M. A two-stage intelligent search algorithm for the two-dimensional strip packing problem ［J］. European Journal of Operational Research, 2011, 215(1)： 57-69.

［11］LEUNG S C H, ZHANG D F. A fast layer-based heuristic for non-guillotine strip packing ［J］. Expert Systems with Applications： An International Journal, 2011, 38(10)：13032-13042.

［12］LEUNG S C H, ZHANG D F, ZHOU C L, et al. A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem ［J］. Computers and Operations Research, 2012, 39(1)： 64-73.

［13］何琨, 黄文奇.三维矩形 Packing问题的拟人求解算法［J］.中国科学：信息科学,2010,40(12)：1586-1595.

［14］VASSILIADIS V S. Two-dimensional stock cutting and rectangle packing： binary tree model representation for local search optimization methods ［J］. Journal of Food Engineering, 2005, 70(3)： 257-268.

[1]	牛瑞华, 杨俊, 邢斓馨, 吴仁彪. 基于卷积注意力模块和双通道网络的微表情识别算法[J]. 计算机应用, 2021, 41(9): 2552-2559.
[2]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[3]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[4]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[5]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[6]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[7]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[8]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[9]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[10]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[11]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[12]	汤安迪, 韩统, 徐登武, 谢磊. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
[13]	程美英, 钱乾, 倪志伟, 朱旭辉. 信息筛选多任务优化自组织迁移算法[J]. 计算机应用, 2021, 41(6): 1748-1755.
[14]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.
[15]	蔡瑞光, 张德生, 肖燕婷. 参数独立的加权局部均值伪近邻分类算法[J]. 计算机应用, 2021, 41(6): 1694-1700.

基于启发式动态分解算法的矩形件优化排样

Optimum packing of rectangles based on heuristic dynamic decomposition algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics