Obstruction map local search solution for 2D irregular bin packing problem with cache acceleration

摘要

In the field of the operational research, the cutting & packing problems are one of the most significant studied subjects. Among these problems, bi-dimensional irregular packing problems, which admits polygonal shaped items, are computationally challenging due to its geometrical complexity. Several advances were obtained for the irregular strip packing problem; however, it is very lacking for bin packing problems. Therefore, in this work, a strip packing solution is adapted to deal with the single size irregular bin packing problem. The proposed solution employs the obstruction map, which aids the overlap minimization for the dotted board model. Such approach is efficient as it reduces the search space by enforcing a grid placement restriction for items. Furthermore, a map caching acceleration strategy is studied in order to further improve its performance. Two solutions are proposed for the adaptation to the bin packing problem and preliminary tests were performed to check their applicabilities. Results show that the proposed approaches may be feasible, specially if the items are preassigned to objects. Moreover, tests showed that the map caching acceleration improved the performance of the algorithms by a factor of two.