DocumentCode :
618185
Title :
Tackling the Irregular Strip Packing problem by hybridizing genetic algorithm and bottom-left heuristic
Author :
Junior, Bonfim A. ; Pinheiro, Placido R. ; Saraiva, Rommel D.
Author_Institution :
Grad. Program in Appl. Inf., Univ. of Fortaleza, Fortaleza, Brazil
fYear :
2013
fDate :
20-23 June 2013
Firstpage :
3012
Lastpage :
3018
Abstract :
This paper addresses the Irregular Strip Packing problem, a particular case of Cutting and Packing problems in which a set of polygons has to be packed within a rectangular object. To identify good quality solutions, we propose a hybrid methodology based on a meta-heuristic engine (i.e., Genetic Algorithm) and a well known placement heuristic called Bottom-Left. In addition, differently from several approaches presented in the literature, we investigate the application of the No-fit Polygon as a placement tool for obtaining local optima. The results are further improved by a shrinking algorithm that works within the meta-heuristic component. To assess the potentials of the proposed methodology, computational experiments performed on a set of difficult benchmark instances of the Irregular Strip Packing problem are discussed here for evaluation purposes.
Keywords :
bin packing; combinatorial mathematics; genetic algorithms; bottom-left heuristic; bottom-left placement heuristic; cutting-and-packing problem; genetic algorithm; irregular strip packing problem; metaheuristic engine; no-fit polygon; shrinking algorithm; Benchmark testing; Biological cells; Genetic algorithms; Layout; Search methods; Shape; Strips; Combinatorial Optimization; Cutting and Packing; Genetic Algorithm; Hybrid Methods; Irregular Strip Packing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Evolutionary Computation (CEC), 2013 IEEE Congress on
Conference_Location :
Cancun
Print_ISBN :
978-1-4799-0453-2
Electronic_ISBN :
978-1-4799-0452-5
Type :
conf
DOI :
10.1109/CEC.2013.6557936
Filename :
6557936
Link To Document :
بازگشت