东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

求解不等圆Packing问题的一个启发式算法

ISSN号：1000-1239
期刊名称：《计算机研究与发展》
时间：0
分类：TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
作者机构：[1]华中师范大学教育信息技术工程研究中心,武汉430079, [2]华中科技大学计算机科学与技术学院.武汉430074
相关基金：国家自然科学基金项目（10471051）;国家“九七三”重点基础研究发展规划基金项目（2004CB318000）;“十一五”国家科技支撑计划重点基金项目（2006BAK11B01） The two dimensional （2D） circle packing problem is a famous cutting and packing problem. It consists of placing a given set of circles in a container without overlap. The usual objective is to maximize the material utilization and hence to minimize the ＂waste＂ area. This problem is known to be NP-hard and is encountered in many industries （textile, paper, glass, etc）. For NP-hard problems, there does not exist an algorithm that is complete, rigorous and efficient. Consequently, various heuristic algorithms have been proposed for circle packing problems. In this paper, two novel placement heuristics are proposed to solve the circle packing problem, the key idea of which is a quantified measure called degree of placement to evaluate the benefit of packing a circle into the container. Computational results show that the performance of the presented algorithm outperforms that of two previous reported algorithms in the literature. Our work is supported by the National Science Foundation of China （10471051） and partially supported by the National Grand Fundamental Research 973 Program of China （2004CB318000）.

关键词： NP难问题, 圆形PACKING问题, 启发式算法, 占角动作, 有限枚举策略, NP-hard problem, circle packing problem, heuristic algorithm, corner placement, boundedenumeration

中文摘要：

求解具有NP难度的圆形packing问题具有很高的理论与实用价值．现提出一个启发式方法，求解了货运中常遇到的矩形区域内的不等圆packing问题．此算法首先将待布局圆按半径大小降序排列，然后用占角动作来逐个放置．通过试探性地放入一个或多个待布局圆，给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度．在放置每一个圆时，以贪心的方式选取当前具有最大优度的占角动作来放置．最后用测试算例验证了算法的高效性．

英文摘要：

Circle packing problem, one of the NP hard problems, is of great theoretical and practical value. To solve the circle packing problem that encounters in the field of transportation of freight, a heuristic algorithm is proposed for finding a good arrangement of multiple different-sized circles within a larger rectangular container. In this algorithm, the circles are sorted by non-increasing order of radius and packed into the container one by one according to the order. Each circle should be placed inside the container by a corner placement so that the circle does not overlap any other circle and is tangent with two previously packed circles. By pseudo-placing one or more circles to be packed, two greedy methods are introduced to evaluate the benefit of a corner placement, one of which is the degree of placement, and the other is a bounded enumeration strategy that is based on the first one. At each iteration of packing in the resulting algorithm, each circle is packed into the container by a corner placement with the highest benefit according to the bounded enumeration strategy. The experimental results are presented, showing the effectiveness of this algorithm.

同期刊论文项目