An open space based heuristic for the 2D strip packing problem with unloading constraints

摘要

This paper studies the two-dimensional strip packing problem with unloading constraints. Given a set of items (represented by rectangles) belonging to different customers and a rectangular strip with fixed width and open length, the objective is to pack all the items into the strip such that the used length is minimized. In addition, the resulting packing must satisfy the unloading constraints. Based on the characteristics of this problem, this paper employs the open space to represent the candidate position. An open space based first-fit heuristic is proposed to generate a packing pattern for a given sequence of items. An implementation using the segment tree is provided. Finally, a randomized local search without any parameter is used to improve the solution by trying different sequences. The computational results on well-known instances show that the proposed approach outperforms existing approaches in the literature. In additional, we test our approach on the two-dimensional orthogonal packing problem with unloading constraints, the results show that our approach is capable of finding feasible solutions for 283 open instances. (C) 2019 Elsevier Inc. All rights reserved.