Covering, corner-searching and occupying: A three-stage intelligent algorithm for the 2d multishape part packing problem

PLoS One. 2022 May 31;17(5):e0268514. doi: 10.1371/journal.pone.0268514. eCollection 2022.

Abstract

The bin packing problem has a wide range of applications in industry. With the upgrade of the task difficulty, the traditional 2d rectangular layout algorithm can no longer meet the needs of modern industry, such as express packing task and exoplanet ore collection task. The express or ore samples come in heterogeneous shapes so they cannot all be treated as rectangular pieces. In this paper, we propose a three-stage method called covering, corner-searching and occupying (C,S&O) to solve the two-dimensional multishape part packing problem. The objective of the packing problem variant is to ensure maximum use of the raw material and minimize the trim loss. The algorithm cannot make use of information about the sequence of future objects that are going to arrive, only knowing the shape and size of the coming one, and the coming part must be packed into the bin immediately after its arrival without buffering or readjusting. The method of C,S&O hybridizes the idea of "gold corners, silver edges and grass belly" in the Chinese game Go and the method of finding picture corners in machine vision. In the first stage, the rectangular bin and the coming part are transformed into matrix representation, and generating the position matrix that indicates possible ways of packing the part into the bin. In the second stage, the suitable layout position of the coming part is obtained using machine vision image processing technology for reference. The third stage is calculating the environment matching degree to determine the current optimal placement orientation. In order to facilitate the display of the simulation results, only three shapes of parts are considered in the simulation, rectangle, circle and triangle. The experimental results show the effectiveness of this method. Consulting the literature, it is found that this paper is the first to propose a layout method for multishape manufacturing parts.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms*
  • Computer Simulation
  • Image Processing, Computer-Assisted*

Grants and funding

This research was supported by the National Natural Science Foundation of China (No. 11772023). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. The authors didn’t received salary from any of our funders.