An effective heuristic for the two-dimensional irregular bin packing problem

Citation

Lopez-Camacho E, Ochoa G, Terashima-Marin H & Burke E (2013) An effective heuristic for the two-dimensional irregular bin packing problem. Annals of Operations Research, 206 (1), pp. 241-264. https://doi.org/10.1007/s10479-013-1341-4

Abstract
This paper proposes an adaptation, to the two-dimensional irregular bin packing problem of the Djang and Finch heuristic (DJD), originally designed for the one-dimensional bin packing problem. In the two-dimensional case, not only is it the case that the piece's size is important but its shape also has a significant influence. Therefore, DJD as a selection heuristic has to be paired with a placement heuristic to completely construct a solution to the underlying packing problem. A successful adaptation of the DJD requires a routine to reduce computational costs, which is also proposed and successfully tested in this paper. Results, on a wide variety of instance types with convex polygons, are found to be significantly better than those produced by more conventional selection heuristics.

Keywords
2D bin packing problem; Irregular packing; Heuristics; Djang and Finch heuristic

Journal
Annals of Operations Research: Volume 206, Issue 1

People

Professor Gabriela Ochoa

Professor, Computing Science