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.