Paper Info
Title
A multiobjective evolutionary algorithm for the 2D Guillotine Strip Packing Problem
Abstract
This paper presents a specialized multiobjective evolutionary algorithm SPEA2 (Strength Pareto Evolutionary Algorithm 2) coupled, separetely, with four placement heuristics for solving the 2D Guillotine Strip Packing Problem. In this study, the problem requires minimization of both the amount of wasted material and the number of independent cuts required by a packing. With the goal of solving this multiobjective version of the problem, the construction phase of the GRASP algorithm (Greedy Randomized Adaptive Search Procedure) is used to generate a portion of the initial population of SPEA2. Four different placement heuristics, Next-Fit, a variation of Next-Fit, Best-Fit and First-Fit, were coupled with SPEA2 and were tested on a set of test data. The results show that the presented methodology is able to generate a good set of candidate solutions for each test problem. A statistical comparison methodology, based on multiobjective principles, was used to compare the four algorithm variants.
Year
DOI
Venue
2012
10.1109/CEC.2012.6256469
Evolutionary Computation
Keywords
Field
DocType
Pareto optimisation,bin packing,evolutionary computation,greedy algorithms,randomised algorithms,search problems,statistical analysis,2D guillotine strip packing problem,GRASP algorithm,SPEA2,best-fit placement heuristic,cutting stock problem,first-fit placement heuristic,greedy randomized adaptive search procedure,next-fit placement heuristic,next-fit variation placement heuristic,placement heuristics,specialized multiobjective evolutionary algorithm,statistical comparison methodology,strength Pareto evolutionary algorithm 2
Mathematical optimization,Algorithm design,Evolutionary algorithm,Computer science,Evolutionary computation,Greedy algorithm,Heuristics,Artificial intelligence,Cutting stock problem,Greedy randomized adaptive search procedure,Machine learning,Bin packing problem
Conference
ISBN
Citations 
PageRank 
978-1-4673-1508-1
0
0.34
References 
Authors
0
5
Name
Order
Citations
PageRank
Dayanne G. Coelho100.34
Elizabeth F. Wanner27521.37
Sergio R. Souza300.34
Eduardo G. Carrano413917.90
Robin C. Purshouse562830.00