Hierarchical Search-Embedded Hybrid Heuristic Algorithm for Two-Dimensional Strip Packing Problem

Mengfan Chen, Kai Li, Defu Zhang, Ling Zheng, Xin Fu

Abstract

Two dimensional strip packing problem implies a sort of NP-hard combinational optimization, where a set of rectangles are defined all for filling a strip with finite width and infinite height being minimized. Optimization taking no account of rotation and guillotine constraints remains problematic in solving the problem. This paper proposes a new variant of a hybrid heuristic algorithm for optimizing solutions of the strip packing problem. This algorithm involves three key improvements: the building of δ scoring rules for selecting rectangles, the use of the red-black trees that stores rectangle indices for quickly locating the most suitable rectangles, and the embedding of a hierarchical method into a random local search to implement an optimization solution. Comparative studies show that the proposed algorithm variant outperforms state-of-the-art algorithms on almost all benchmark datasets.
BibTeX
@article{chen2019hierarchical,
  author = {Mengfan Chen and Kai Li and Defu Zhang and Ling Zheng and Xin Fu},
  title = {{Hierarchical Search-Embedded Hybrid Heuristic Algorithm for Two-Dimensional Strip Packing Problem}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2953531},
}

Loading related content...

Figure