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个记录一致。

0
下载
关闭预览

相关内容

Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【电子书】机器学习实战(Machine Learning in Action),附PDF
专知会员服务
126+阅读 · 2019年11月25日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
创业邦杂志
5+阅读 · 2019年3月27日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Python机器学习教程资料/代码
机器学习研究会
8+阅读 · 2018年2月22日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Learning to Weight for Text Classification
Arxiv
8+阅读 · 2019年3月28日
One-Shot Federated Learning
Arxiv
9+阅读 · 2019年3月5日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
创业邦杂志
5+阅读 · 2019年3月27日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Python机器学习教程资料/代码
机器学习研究会
8+阅读 · 2018年2月22日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员