The Heuristic Research For The Equal Sphere Packing Problem

After reviewing the past researches of the Sphere and Circle Packing problem, this paper points out that such problems are NP-hard and that until now there are no deterministic algorithms for solving them. The heuristic algorithms are effective approaches to tackle them.For dealing with the Equal Sphere Packing problem, this paper introduced the quasi physical model and the basic quasi physical algorithm, and has designed three heuristic strategies to improve the basic quasi physical algorithm. The fake sphere strategy guarantees the accuracy of feasible solutions. The quick quitting strategy cuts down unnecessary CPU time. The neighbor sphere strategy reduces the time complexity of calculating all item-item distances from O(n2) to O(n), where n is the number of equal spheres. The quasi physical algorithm which uses the three strategies serves as the local solver, denoted by AO. AO with a given initial configuration is a deterministic algorithm.Then, this paper has designed the serial symmetrical relocation strategy as the main global search strategy. The compounded algorithm Al is formed by combining the serial symmetrical relocation strategy with the local solver AO. Furthermore, the shake&fall strategy was designed as the auxiliary search strategy. The compounded algorithm A2 is formed by incorporating the shake&fall strategy into Al.Both Al and A2 start from a random initial configuration, generate O(n) new configurations by the serial symmetrical relocation strategy, and invoke AO to locally optimize the O(n2) new configurations in turn, and then select the densest configuration as the result. Because Al and A2 each time deal with only O(n) configurations, they can tackle relatively large instances.A2 packed up to 200 equal spheres in cubical and spherical containers. As to packing equal spheres in cubical container,65 world best known records among the instances of 1 to 200 spheres were found by A2. As to packing equal spheres in spherical container,25 world best known records among the instances of 1 to 72 spheres were found by A2, and most results of 73 to 200 spheres were newly found by A2. Especially, A2 successfully packed 68 spheres of radius 1 into a large sphere whose radius is less than 5, thus proved wrong a former conjecture, which stated that a large sphere of radius 5 can contain at most 67 spheres of radius 1.