PDFAbstract: This paper proposes a new heuristic for packing non-identical spheres into a three-dimensional container of fixed dimensions. Given a set that contains n spheres, the objective is to place a subset of spheres so as to maximize the volume occupied by these ones. The proposed heuristic is based on an idea that applies a two-level look-forward search. The computational investigation indicates that the heuristic is effective since it improves most of the best known results in the literature on the used instances.
Keywords: Packing problems, Packing spheres, Heuristic, Look-Forward, Knapsack REFERENCES [1] R. Alvarez-Valdes, A. Martinez and J. M. Tamarit, A branch & bound algorithm for cutting and packing irregularly shaped pieces, Int. J. Prod. Econ. 145, 2013, pp. 463–477. [1] R. Alvarez-Valdes, A. Martinez and J. M. Tamarit, A branch & bound algorithm for cutting and packing irregularly shaped pieces, Int. J. Prod. Econ. 145, 2013, pp. 463–477. [2] J. A. George, J. M. George and B. W. Lamar, Packing different-sized circles into a rectangular container, European J. Oper. Res. 84, 1995, pp. 693–712. [3] D. He, N. N. Ekere and L. Cai, Computer simulation of random packing of unequal particles. Phys. Rev. E. 60, 1999, 7098. [4] K. Hitti and M. Bernacki, Optimized droping and rolling (ODR) method for packing of polydisperse spheres, Appl. Math. Model. 37, 2013, pp. 5715–5722. [5] W. Q. Huang, Y. Li, H. Akeb and C. M. Li, Greedy algorithms for packing unequal circles into a rectangular container. J. Oper. Res. Soc. 56, 2005, pp. 539–548. [6] Y.–K. Joung and S. D. Noh, Intelligent 3D packing using a grouping algorithm for automative container engineering, J. Comput. Des. Eng. 1, 2014, pp. 140–151. [7] T. Kubach, A. Bortfeldt, T. Tilli and H. Gehring, Greedy algorithms for packing unequal sphere into a cuboidal strip or a cuboid, Asia Pac. J. Oper. Res. 28, 2011, pp. 739–753. [8] Y. Li and W. Ji, Stability and convergence analysis of a dynamics–based collective method for random sphere packing, J. Comput. Phy. 250, 2013, pp. 373–387. [9] C. O. Lopes and J. E. Beasley, A formulation ´ space search heuristic for packing unequal circles in a fixed size circular container, European J. Oper. Res. 251, 2016, pp. 64–73. [10] S. Martello and M. Monaci, Models and algorithm for packing rectangles into the smallest square, Comput. Oper. Res. 63, 2015, pp. 161– 171. [11] A. Martinez-Sykora, R. Alvarez-Valdes, J. Bennell and J. M. Tamarit, Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts, Omega 52, 2015, pp. 15–32. [12] R. M’Hallah, A. Alkandari and N. Mladenovic,´ Packing unit spheres into the smallest sphere using VNS and NLP. Comput. Oper. Res. 40, 2013, pp. 603–615. [13] K. Soontrapa and Y. Chen, Mono-sized sphere packing algorithm development using optimized Monte Carlo technique. Ad. Powder Technol. 24, 2013, pp. 955–961. [14] W. Visscher and M. Bolsterli, Random packing of equal and unequal spheres in two and three dimensions, Nature. 239, 1972, pp. 504–507. [15] T. Zauner, Application of a force field algorithm for creating stringly correlated multiscale sphere packings. J. Comput. Phys. In Press, 2016. [16] J. Wang, Packing of unequal spheres and automated radiosurgical treatment planning. J. Comb. Optim. 3, 1999, pp. 453–463. [17] Y. Wu, W. Li, M. Goh and R. Souza, Threedimensional bin packing problem with variable bin height, European J. Oper. Res. 202, 2010, pp. 347–355.
Cite this paper
Hakim Akeb. (2016) A Partial Depth-Search Heuristic for Packing Spheres. International Journal of Mathematical and Computational Methods, 1 , 120-127
Copyright © 2016 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0