This thesis addresses the geometric 0/1 knapsack problem. The goal of this NP-hard problem is finding the optimal packing of a rectangular container with a set of items of different sizes. We employed and tested various deterministic and stochastic approaches to solve this problem, including the best-fit-first strategy, the constructive heuristic algorithm, and the common perimeter heuristic. Additionally, we improved the performance of the insertion algorithms using global optimization algorithms such as simulated annealing and genetic algorithms. Among the employed insertion algorithms, the common perimeter heuristic performed the best. For all insertion algorithms, the greatest improvement was attained by using them in combination with the genetic algorithm.
|
