.png){kind=icon}
.png){kind=icon}
Return
An efficient deterministic heuristic algorithm for the rectangular packing problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2019.106097.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper presents a deterministic heuristic algorithm for solving the NP-hard two-dimensional rectangular packing problem with the objective of maximizing the filling rate of a rectangular sheet. The key component of the proposed algorithm is a best-fit constructive procedure, according to which, the rectangles are packed into the sheet one by one and each rectangle is packed into the sheet by an angle-occupying placement with maximum fit degree. To further improve the algorithm's searching ability, a look-ahead strategy and a multistart method are introduced. The proposed algorithm is evaluated on five sets of 112 well-known test instances, and the computational results disclose that the proposed algorithm is competitive with the current state-of-the-art algorithms. The effects of the essential components of the proposed algorithm are investigated by a series of experimental analysis. Additionally, we adapt the proposed packing strategy to solve a variant of 2DRP, the constrained two-dimensional cutting (or packing) (CTDC) problem. Computational experiments on 21 classical CTDC problem instances and comparisons with two state-of-the-art algorithms verifies the effectiveness and efficiency of the adapted algorithm.
Keywords:
Packing
Two-dimensional rectangular packing problem
Angle-occupying placement
Multistart strategy
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6.5
Papers:
1.0W
Citations:
3.8W