正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.

Heuristic Algorithm for the Equal Circles Packing Problem in Equilateral Triangle Container

The equal circles packing problem studies how to place n circular objects of unitary radius into an equilateral triangle container with the edge length as small as possible without overlap.As a classical NP-hard problem,it has high theoretical value and wide applied background.The simulated annealing algorithm is a stochastic global search algorithm.To solve this packing problem,a heuristic algorithm is put forward by incorporating heuristic configuration update strategies,the local search strategy based on the gradient method and the dichotomous search strategy into the simulated annealing algorithm.The proposed algorithm adopts the heuristic configuration update strategies to produce new configurations and jump out of the local minima,the gradient method to search for lower-energy minima near newly generated configurations,and the dichotomous search strategy to gain the minimum edge length of the equilateral triangle container.The experimental results of 41 instances show that the proposed algorithm improves the present best results of 38 instances obtained by other algorithms,and is an effective algorithm for solving the equal circles packing problem in equilateral triangle container.