[1]罗立宏,冯开平,叶家玮.基于摇瓶策略求解二维不规则件排样问题[J].南京理工大学学报(自然科学版),2015,39(02):194-201.
 Luo Lihong,Feng Kaiping,Ye Jiawei.2-D irregular polygon nesting with shaking bottle strategy[J].Journal of Nanjing University of Science and Technology,2015,39(02):194-201.
点击复制

基于摇瓶策略求解二维不规则件排样问题
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
39卷
期数:
2015年02期
页码:
194-201
栏目:
出版日期:
2015-04-30

文章信息/Info

Title:
2-D irregular polygon nesting with shaking bottle strategy
作者:
罗立宏12冯开平2叶家玮2
1.广东工业大学 数字媒体系,广东 广州 510006; 2.华南理工大学 土木与交通学院,广东 广州 510641
Author(s):
Luo Lihong12Feng Kaiping2Ye Jiawei2
1.Digital Media Department,Guangdong University of Technology,Guangzhou 510006,China; 2.School of Civil and Transportation Engineering,South China University of Technology, Guangzhou 510641,China
关键词:
排样 不规则件 模拟退火 重叠检测
Keywords:
nesting irregular polygons simulated annealing overlap testing
分类号:
TP391.9
摘要:
针对基于序列的二维排样问题求解策略的不足,提出采用“摇晃瓶子”的策略求解二维不规则件排样问题。基于图像和颜色直方图方法实现零件的重叠检测、出界检测和方案评价。对模拟退火提出两种改进措施:动态邻域尺度方法和并行退火方法。动态邻域尺度方法可使模拟退火用于摇瓶策略,解决了采用离散方法检测零件重叠时精度和时间的矛盾; 并行退火方法进一步加快了求解速度。实验对比证明了动态邻域算法和并行退火算法有效,且能满足工程应用要求。分析了动态邻域和并行退火的复杂度,从理论上说明了这两种方法缩短排样时间的原因。
Abstract:
The strategy of“shaking bottle”is presented to overcome the inadequacy of the strategy based on sequence in the 2-D nesting problem.Based on the image and color histogram,a new method for overlap testing,outside testing and estimating is put forward.Two measures are used to improve the simulated annealing(SA)algorithm:the dynamic neighborhood dimension and the parallel annealing.The dynamic annealing makes SA be used for the shaking bottle strategy,and overcomes the contradiction between precision and time in the discrete methods of polygon overlap testing.The parallel annealing speeds up the nesting velocity further.Experiments and comparison prove that the dynamic neighborhood and the parallel annealing algorithm are effective and can be used for engineering application.Complexity of the algorithm is analyzed and the reason why the nesting time is shorten is analysed theoretically.

参考文献/References:

[1] Kantorovich L V.Mathematical methods of organizing and planning production(An English translation on a Russian paper published in 1939)[J].Management Science,1960(6):363-422.
[2]贾志欣.排样问题的研究现状与趋势[J].计算机辅助设计与图形学学报,2004,16(7):890-897.
Jia Zhixin.State-of-the-art and future trends of cutting and packing studies[J].Journal of Computer Aided Design & Computer Graphics,2004,16(7):890-897.
[3]Bennell J A,Oliveira J F.A tutorial in irregular shape packing problems[J].Journal of the Operational Research Society,2009,60(SUPPL):93-105.
[4]贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计及图形学学报,2002,14(5):467-470.
Jia Zhixin Yin Guofu,Luo Yang.Two-dimensional irregular parts packing with genetic algorithm[J].Journal of Computer Aided Design & Computer Graphics,2002,14(5):467-470.
[5]Gomes A M,Oliveira J F.A 2-exchange heuristic for nesting problems[J].European Journal of Operational Research,2002,141(2):359-370.
[6]Bennell J A,Song X.A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums[J].Computers and Operations Research,2008,35:267-281.
[7]Burke E,Hellier R,Kendall G,et al.A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem[J].Operations Research,2006,54(3):587-601.
[8]Del Valle,Aline M,De Queiroz,et al.Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape[J].Expert Systems with Applications,2012,39(16):12589-12598.
[9]王桂宾,周来水,邓冬梅.基于模拟退火算法的矩形件排样[J].中国制造业信息化,2006,35(15):65-67,70.
Wang Guibin,Zhou Laishui,Deng Dongmei.The rectangular packing based on simulated annealing algorithm[J].Manufacture Information Engineering of China,2006,35(15):65-67,70.
[10]唐坚刚,刘丛,张丽红.基于改进遗传算法的不规则图形排样[J].计算机工程,2010,36(21):185-187.
Tang Jiangang,Liu Cong,Zhang Lihong.Irregular graph stock layout based on improved genetic algorithm[J].Computer Engineering,2010,36(21):185-187.
[11]梁利东,钟相强.船体零件智能优化排样系统的设计研究[J].船舶工程,2012,34(2):61-64.
Liang Lidong,Zhong Xiangqiang.Design and research on intelligent optimal nesting system for hull parts[J].Ship Engineering,2012,34(2):61-64.
[12]Dowsland K A,Dowsland W B,Bennell J A.Jostling for position:Local improvement for irregular cutting patterns[J].The Journal of the Operational Research Society,1998,49(6):647-658.
[13]梅颖.船体建造板材套料系统中排样优化算法与碰靠技术研究[D].广州:华南理工大学土木与交通学院,2010.
[14]Kirpatrick S,Gelatt Jr C D,Vecchi M P.Optimization by simulated annealing[J].Science,1983,220(13):671-680.
[15]Gomes A M,Oliveira J F.Solving irregular strip packing problems by hybridising simulated annealing and linear programming[J].European Journal of Operational Research,2006,17l(3):811-829.
[16]Stephen C H Leung,Lin Yangbin,Zhang Defu.Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem[J].Computers & Operations Research,2012,39(3):678-686.
[17]宋佩华,蒋联源,欧启忠.基于离散粒子群算法求解矩形件排样问题[J].计算机应用与软件,2008,25(1):238-240.
Song Peihua,Jiang Lianyuan,Ou Qizhong.Solving rectangular packing problem based on discrete particle swarm optimization algorithm[J].Computer Applications and Software,2008,25(1):238-240.
[18]Hopper E.Two-dimensional packing utilizing evolutionary algorithm and other meta-heuristic methods[D].Cardiff,UK:University of Wales,2000.
[19]张德富,陈竞驰,刘永凯,等.用于二维不规则排样的离散临界多边形模型[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.

备注/Memo

备注/Memo:
收稿日期:2013-03-09 修回日期:2013-04-27
基金项目:国家自然科学基金(50575046)
作者简介:罗立宏(1975-),男,博士,副教授,计算机辅助设计,图形图像处理,E-mail:luo_lihong98@163.com。
引文格式:罗立宏,冯开平,叶家玮.基于摇瓶策略求解二维不规则件排样问题[J].南京理工大学学报,2015,39(2):194-201.
投稿网址:http://zrxuebao.njust.edu.cn
更新日期/Last Update: 2015-04-30