BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Hifi Mhand (Université de Picardie Jules Verne, Italy), Yousef Labib (Université de Picardie Jules Verne, Italy)
Width Beam and Hill-Climbing Strategies for the Three-Dimensional Sphere Packing Problem
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 421 - 428, rys., tab., bibliogr. 21 poz.
Słowa kluczowe
Algorytmy, Metody heurystyczne, Eksperyment badawczy
Algorithms, Heuristics methods, Scientific experiment
In this paper we propose to enhance a width-beam search in order to solve the three-dimensional sphere packing problem. The goal of the problem is to determine the minimum length of the container having fixed width and height, that packs $n$ predefined unequal spheres. The width-beam search uses a greedy selection phase which determines a subset of eligible positions for packing the predefined items in the target object and selects a subset of nodes for exploring some promising paths. We propose to handle lower bounds in the tree and apply a hill-climbing strategy in order to diversify the search process. The performance of the proposed method is evaluated on benchmark instances taken from the literature. The obtained results are compared to those reached by some recent methods available in the literature. Encouraging results have been obtained.(original abstract)
Pełny tekst
  1. Birgin E. G. and Sobral F.N.C. Minimizing the object dimensions in circle and sphere packing problems. Computers & Operations Research, 35, 2357-2375, 2008 (DOI: 10.1016/j.cor.2006.11.002).
  2. Della Croce F., Ghirardi M. and Tadei R.. Recovering beam search approach for combinatorial optimization problems. Journal of Heuristics, 10, 89-104, 2004 (DOI: 10.1023/B:HEUR.0000019987.10818.e0).
  3. Farr R. S.. Random close packing fractions of log-normal distributions of hard spheres. Powder Technology, 245, 28-34, 2013 (DOI: 10.1016/j.powtec.2013.04.009).
  4. Hifi M. and M'Hallah R. A literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research, Article ID 150624, 22 p, 2009 (
  5. Hifi M. and M'Hallah R. and Saadi T.. Algorithms for the constrained two-staged two-dimensional cutting problem. INFORMS, Journal on Computing, 20 212-221, 2008.
  6. Hifi M. and M'Hallah R. Beam search and non-linear programming tools for the circular packing problem, International Journal of Mathematics in Operational Research, 1, 476-503, 2009 (DOI: 10.1504/IJ-MOR.2009.026278).
  7. Hifi M. and Saadi T. A cooperative algorithm for constrained twostaged two-dimensional cutting problems. International Journal of Mathematics in Operational Research, 9, 104-124, 2010 (DOI: 10.1504/IJOR.2010.034363).
  8. Hifi M. and Yousef L. A dichotomous search-based heuristic for the three-dimensional sphere packing problem. Working paper, Exposed in the Seminary of ROAD Team, Laboratory EPROAD, Universi e de Picardie Jules Verne, october 2013.
  9. Kubach T., Bortfeldt A., Tilli T., and Gehring H. Greedy algorithms for packing unequal sphere into a cuboidal strip or a cuboid. Asia-Pacific Journal of Operational Research, 28(06), 739-753, 2011 (DOI: 10.1142/S0217595911003326).
  10. Kubach T., Bortfeldt A., Tilli T., and Gehring H. Parallel greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. Working Paper, Department of Management Science, University of Magdeburg, (Diskussionsbeitrag der Fakult at fur Wirtschaftswissenschaft der FernUniversit at in Hagen). No 440, Hagen 2009.
  11. Li Y. and Ji W. Stability and convergence analysis of a dynamicsbased collective method for random sphere packing. Journal of Computational Physics, 250, 373-387, 2013 (DOI: 10.1016/
  12. Lochmann K., Oger L., and Stoyan D. Statistical analysis of random sphere packings with variable radius distribution. Solid State Sciences. 8(12), 1397-1413, 2006 (DOI: 10.1016/j.solidstatesciences.2006.07.01).
  13. M'Hallah R. and Alkandari A. Packing unit spheres into a cube using VNS. Electronic Notes in Discrete Mathematics, 39(1), 201-208, 2012.
  14. M'Hallah R., Alkandari A., and Mladenovi c N. Packing unit spheres into the smallest sphere using VNS and NLP. Computers & Operations Research, 40(2), 603-615, 2013 (DOI: 10.1016/j.cor.2012.08.019).
  15. Ow P. S. and Morton T. E. Filtered beam search in scheduling, International Journal of Production Research, 26, 297-307, 1988 (DOI:10.1080/00207548808947840).
  16. Soontrapa K. and Chen Y. Mono-sized sphere packing algorithm development using optimized Monte Carlo technique. Advanced Powder Technology, 24(6), 955-961, 2013 (DOI: 10.1016/j.apt.2013.01.007).
  17. Stoyan Y., Yaskow G., and Scheithauer G. Packing of various radii solid spheres into a parallelepiped. Central European Journal of Operational Research, 11, 389-407, 2003.
  18. Sutou A. and Dai Y.. Global optimization approach to unequal sphere packing problems in 3D. Journal of Optimization Theory and Applications, 114, 671-694, 2002 (DOI: 10.1023/A:1016083231326).
  19. Wang J. Packing of unequal spheres and automated radio-surgical treatment planning. Journal of Combinatorial Optimization, 3, 453-463, 1999 (DOI: 10.1023/A:1009831621621).
  20. Wascher G., Haussner H. and Schumann H.. An improved typology of cutting and packing problems. European Journal of Operational Research, 183, 1109-1130, 2007 (DOI: 10.1016/j.ejor.2005.12.047).
  21. Yavuza M. Iterated beam search for the combined car sequencing and level scheduling problem. International Journal of Production Research, 51, 3698-3718, 2013 (DOI:10.1080/00207543.2013.765068).
Cytowane przez
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu