A hybrid heuristic for the 0–1 knapsack problem with items of irregular shape

摘要

This research deals with the two-dimensional 0–1 knapsack problem considering items of irregular shape. In this version of the problem the items correspond to convex and non-convex polygons, while the knapsack has rectangular shape. We proposed a hybrid heuristic that combines GRASP and Simulated Annealing: begins with an initial solution and, thus, explores its neighborhood using a local search procedure in order to return better solutions. We also allowed the neighborhood of solutions with low occupation ratio to be explored in order to diversify the search in the search space. Due to irregular shape of the items, we use the no-fit-polygon computation to avoid items overlapping and for search by feasible points to pack items. The computational experiments shown the competitiveness of the algorithm proposed, since we improved recent results of the literature about this problem.