基于模拟退火的贯通约束不规则排样

摘要/Abstract

摘要： 针对带贯通性约束的不规则凸多边形的排样问题，提出了一种分阶段构造算法。为了控制每个阶段新生成的组合图形的形状,构造过程引入变动的形状权重，算法运行早期采用较小权重使图形组合具有较高出材率,而在后期采用较大的权重得到类似矩形的复合。基于模拟退火思想引入温度参数控制权重的变化率，在早期和后期形状权重变化率较小而在中期变化率较大。采用ESICUP标准测试数据分别对常数散列、线性散列和温控散列进行对比,结果表明温控散列函数能有效提高排样效率和排样出材率。

关键词: 不规则排样, 贯通约束, 模拟退火, 形状权重

Abstract: A layered constructive algorithm was proposed for 2D irregular guillotine bin packing problems. Variant shape weighs were introduced to control the shapes of each evolved block, which indicated the similarity of the resulted shape to rectangle in each iteration. To get better utilization, smaller shape weights were used in early periods to get shapes with higher ratio of utilization, while larger weights were introduced in the last periods to let the shape be similar to rectangle. Based on simulated annealing, a parameter named temperature was introduced to control the change rate weights. The change of shape weights was smaller in early and later periods and larger in middle periods. Based on ESICUP standard test data, several weight adjustment strategies were examined, including fixed weight, linear change and temperature-controlled change, the results show that temperature-controlled change effectively improves the layout effiency and the material rate of layout.

Key words: irregular bin packing, guillotine constraint, simulated annealing, shape weight

中图分类号:

TP391

韩伟, 张子成. 基于模拟退火的贯通约束不规则排样[J]. 中国机械工程.

Han Wei, Zhang Zicheng. A Simulated Annealing Algorithm for Irregular Guillotine Packing Problems[J]. China Mechanical Engineering.

参考文献

[1]Bennell J A, Oliveira J F. A Tutorial in Irregular Shape Packing Problems[J]. Journal of the Operational Research Society, 2009, 60(1):93-105.

[2]Bennell J, Scheithauer G, Stoyan Y, et al. Tools of Mathematical Modeling of Arbitrary Object Packing Problems[J]. Annals of Operations Research, 2010, 179(1):343-368.

[3]李敬花，樊付见，王昊，等.遗传模拟退火融合算法求解工程二维排样问题[J].计算机集成制造系统，2011，17(9)：1962-1967.

Li Jinghua，Fan Fujian，Wang Hao, et al. Combination Genetic Simulated Annealing Algorithms for Solving Two-dimensional Packing Problem[J]. Computer Integrated Manufacturing Systems ，2011，17(9)：1962-1967.

[4]张德富，陈竞驰，刘永凯,等.用于二维不规则排样的离散临界多边形模型[J].软件学报，2009，20(6)：1511-1520.

Zhang Defu，Chen Jingchi，Liu Yongkai,et al. Discrete No-fit Polygon, a Simple Structure for the 2-D Irregular Packing Problem[J]. Journal of Software，2009，20(6)：1511-1520.

[5]梁利东，钟相强.粒子群算法在不规则件排样优化中的应用[J].中国机械工程，2010，21(17)：2050-2052.

Liang Lidong，Zhong Xiangqiang. Applications of Particle Swarm Optimization for Solving Irregular Part Nesting Problems[J]. China Mechanical Engineering，2010，21(17)：2050-2052.

[6]Christofides N, Hadjiconstantinou E. An Exact Algorithm for Orthogonal 2-D Cutting Problems Using Guillotine Cuts[J]. European Journal of Operational Research, 1995, 83(1):21-38.

[7]戈鹏，邱厌庆，刘柱胜,等. 一刀切问题的优化二叉树排样[J].计算机集成制造系统，2011，17(2)：329-337.

Ge Peng，Qiu Yanqing，Liu Zhusheng, et al. Optimized Binary Tree Packing of Guillotine Problem[J]. Computer Integrated Manufacturing Systems, 2011,17(2)：329-337.

[8]王桂兰，成亚云，朱龙彪,等.满足“一刀切”要求的木工板排样优化研究[J].工程设计学报，2014，21(3)：212-216.

Wang Guilan，Cheng Yayun，Zhu Longbiao, et al. Research on Optimum "Guillotine Cutting" Lay Out of Carpentry Board[J]. Chinese Journal of Engineering Design，2014，21(3)：212-216.

[9]Hifi M, MHallah R, Saadi T. Algorithms for the Constrained Two-staged Two-dimensional Cutting Problem[J]. Informs Journal on Computing, 2008, 20(2):212-221.

[10]曹大勇，杨梅，科托夫·弗拉基米尔·米哈伊拉维奇,等.二维一刀切装箱问题的两阶段启发式算法[J].计算机集成制造系统，2012，18(9)：1954-1963.

Cao Dayong，Yang Mei，Kotov V M, et al. Two-stage Heuristic Algorithm for Two-dimensional Guillotine Bin Packing Problem[J]. Computer Integrated Manufacturing Systems，2012，18(9)：1954-1963.

[11]韩伟,马福民.带贯通约束的不规则排样分阶构造算法[J].小型微型计算机系统，2012（11）：2421-2424.

Han Wei，Ma Fumin. Layered Constructive Algorithm for Irregular Guillotine Packing Problem[J]. Journal of Chinese Computer Systems，2012（11）：2421-2424.

[12]Han W,Bennell J A, Zhao X, et al. Construction Heuristics for Two-dimensional Irregular Shape Bin Packing with Guillotine Constraints[J]. European Journal of Operational Research, 2013, 230(3):495-504.

[1]	管超;张则强;朱立夏;毛丽丽. 双层过道布置问题的混合整数非线性规划模型及两阶段改进模拟退火算法[J]. 中国机械工程, 2019, 30(08): 975-983.
[2]	方一鸣, 郑贺军, 刘乐, 胡春洋. 基于模拟退火-粒子群算法优化支持向量机参数的连铸漏钢预报[J]. 中国机械工程, 2017, 28(12): 1462-1467.
[3]	闵壮, 彭芳瑜, 郑妍, 闫蓉. 基于设计公差约束的螺旋桨配准问题[J]. 中国机械工程, 2017, 28(02): 167-172.
[4]	潘尚峰, 卢超, 彭一波. 基于改进BP神经网络的机床基础部件可再制造性评价模型[J]. 中国机械工程, 2016, 27(20): 2743-2748.
[5]	朱传军 , 宋文家, 张超勇, 曹静 , 朱孟周. 基于维修时间窗的柔性作业车间调度优化研究[J]. 中国机械工程, 2016, 27(10): 1337-1343.
[6]	孙士平;曾庆龙;吴建军. 基于改进模拟退火算法的复合材料层合板屈曲优化[J]. 中国机械工程, 2015, 26(12): 1676-1683.
[7]	张怀亮;邹佰文;肖雷. 一种辨识磨粒群分形无标度区的新算法[J]. 中国机械工程, 2014, 25(3): 371-376.
[8]	尹庆1;谷正气1,2;陶坚1;伍文广1;徐亚1. 电动轮自卸车动力总成悬置系统分析与优化[J]. 中国机械工程, 2013, 24(20): 2826-2831.
[9]	董德威;颜云辉;张尧;李骏. 矩形件优化排样的自适应遗传模拟退火算法[J]. 中国机械工程, 2013, 24(18): 2499-2504.
[10]	陈盛1, 赵东标1, 陆永华1, 刘, 凯1, 章永年2. 螺纹参数测量中工件定位误差分析和补偿[J]. 中国机械工程, 2013, 24(14): 1956-1960.
[11]	刘卫宁, 马刚, 刘波. 基于层次化的云制造服务组合研究[J]. 中国机械工程, 2013, 24(10): 1349-1356.
[12]	徐立云, 史楠, 段建国, 李爱平. 基于特征加工元的复杂箱体类零件工艺路线优化[J]. 中国机械工程, 2013, 24(02): 202-208.
[13]	李修琳, 鲁建厦, 柴国钟, 汤洪涛, 蒋玲玲. 基于混合遗传算法的混流混合车间协同调度问题[J]. 中国机械工程, 2012, 23(8): 935-940.
[14]	刘爱军1, 2, 杨育1, 邢青松1, 陆惠3, 张煜东4. 含精英策略的小生境遗传退火算法研究及其应用 [J]. 中国机械工程, 2012, 23(5): 556-563.
[15]	王淑旺, 刘志峰, 胡迪, 高洋, 蒋浩. 基于不确定规划的产品拆卸序列规划[J]. 中国机械工程, 2012, 23(18): 2143-2148.