|Table of Contents|

2-D irregular polygon nesting with shaking bottle strategy


Research Field:
Publishing date:


2-D irregular polygon nesting with shaking bottle strategy
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
nesting irregular polygons simulated annealing overlap testing
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.


[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.
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.
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.
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.
Tang Jiangang,Liu Cong,Zhang Lihong.Irregular graph stock layout based on improved genetic algorithm[J].Computer Engineering,2010,36(21):185-187.
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.
[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.
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.
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.


Last Update: 2015-04-30