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

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

0.00 Avg rating0 Votes
Article ID: iaor20115803
Volume: 39
Issue: 1
Start Page Number: 64
End Page Number: 73
Publication Date: Jan 2012
Journal: Computers and Operations Research
Authors: , , ,
Keywords: heuristics, optimization: simulated annealing
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.