A Partial Depth-Search Heuristic for Packing Spheres

AUTHOR(S):

TITLE

A Partial Depth-Search Heuristic for Packing Spheres

PDF BIBTEX

ABSTRACT

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