Mundim L.R.,UFG CAC |
De Queiroz T.A.,UFG CAC
38th Latin America Conference on Informatics, CLEI 2012 - Conference Proceedings | Year: 2012
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. © 2012 IEEE.
De Queiroz T.A.,UFG CAC |
Miyazawa F.K.,University of Campinas
Proceedings of the 2013 39th Latin American Computing Conference, CLEI 2013 | Year: 2013
This work deals with the 0-1 knapsack problem in its two-dimensional variant, when there is a conflict graph related to pairs of conflicting items. Conflicting items must not be packed together in a same bin. This problem also arises as a subproblem in the bin packing problem and in supply chain scenarious. We propose a heuristic that generates iteratively a solution using a so called greedy randomized procedure. In order to avoid local optima solutions, a penalization memory list is used, and several packing strategies under a two-dimensional grid of points are considered. The heuristic solutions are compared with those ones computed by means of an integer programming model, also proposed in this work and solved with CPLEX solver. The heuristic got optimal solutions for 75% of the instances in a lower CPU time compared with that to solve the integer model. © 2013 IEEE.