We address the NP-hard problem of finding a non-overlapping dense packing pattern for n Unequal Circle items in a two-dimensional Square Container (PUC-SC) such that the size of the container is minimized. Based on our previous work on an Action Space based Global Optimization (ASGO) that approximates each circle item as a square item to efficiently find the large unoccupied spaces, we propose an optimization algorithm based on the Partitioned Action Space and Partitioned Circle Items (PAS-PCI). The PAS is to partition the narrow action space on the long side to find two equal action spaces to fully utilize the unoccupied spaces. The PCI is to partition the circle items into four groups based on size for the basin hopping strategy. Experiments on two sets of benchmark instances show the effectiveness of the proposed method. In comparison with our previous algorithm ASGO on the 68 tested instances that ASGO published, PAS-PCI not only gains smaller containers in 64 instances and matches the other 4 but also runs faster in most instances. In comparison with the best record of the Packomania website on a total of 98 instances, PAS-PCI finds smaller containers on 82 and matches the other 16. Note that we updated 19 records for (47-48, 51-54, 57, 61-72) that had been kept unchanged since 2013.
翻译:在二维广场集装箱(PUC-SC)中,为不平等环形物品找到不重叠的密集包装模式,以便尽可能缩小集装箱的尺寸。根据我们以前关于基于行动空间的全球优化(ASGO)的工作,将每个圆项作为一个平方项目相近,以便有效地找到大型空地,我们提议基于分割行动空间和分割环形物品(PAS-PCI)的优化算法。考绩制度的目的是在长侧分割狭小的行动空间,找到两个平等的行动空间,以充分利用未占用的空间。PCI将圆项分成四组,根据流域新建战略的规模划分成四组。对两组基准实例的实验显示了拟议方法的有效性。与我们以前对ASGO所公布的68个测试案例的ASGO算法相比,PAS-PCI不仅在64个案例中获得较小的集装箱,而且与其他4个案例相匹配,而且在多数情况下也运行得更快。与Packomani网站在总共98个案例中的最佳记录相比,PAS-PCI在5747个记录上与我们所更新的188个记录一致。