TY - JOUR
T1 - A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem
AU - Leung, Stephen C.H.
AU - Zhang, Defu
AU - Zhou, Changle
AU - Wu, Tao
PY - 2012/1
Y1 - 2012/1
N2 - The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average. © 2011 Elsevier Ltd. All rights reserved.
AB - The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average. © 2011 Elsevier Ltd. All rights reserved.
KW - Heuristic
KW - Knapsack packing problem
KW - Simulated annealing algorithm
UR - http://www.scopus.com/inward/record.url?scp=79957583976&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79957583976&origin=recordpage
U2 - 10.1016/j.cor.2010.10.022
DO - 10.1016/j.cor.2010.10.022
M3 - RGC 21 - Publication in refereed journal
SN - 0305-0548
VL - 39
SP - 64
EP - 73
JO - Computers and Operations Research
JF - Computers and Operations Research
IS - 1
ER -