A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 1, January 2012, Pages 64-73

Stephen C.H., Leung , Defu, Zhang , Changle, Zhou , Tao, Wu

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…