|Table of Contents|

2-D irregular polygon nesting with shaking bottle strategy

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

Issue:
2015年02期
Page:
194-201
Research Field:
Publishing date:

Info

Title:
2-D irregular polygon nesting with shaking bottle strategy
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
PACS:
TP391.9
DOI:
-
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:
-
Last Update: 2015-04-30