An Algorithm to Packing Unequal Spheres in a Larger Sphere

Zhi Zhong Zeng; Wen Qi Huang; Ru Chu Xu; Zhang Hua Fu

doi:10.4028/www.scientific.net/AMR.546-547.1464

Paper Titles

The Extraction of Water Based on Texture Features Form Remote Sensing Information
p.1444

Design and Implementation of Interactive TV Portal Based on Ajax and Jquery
p.1448

Study on the Transmission Data Collection Technique of Network Applications
p.1453

The Implementation of the Internal Control Management Information System
p.1459

An Algorithm to Packing Unequal Spheres in a Larger Sphere
p.1464

Dynamic Resource Allocation Algorithm in Parlay Multi-Service Environment
p.1470

Research on Grid Scheduling and Resources Selection Algorithm
p.1478

Hardware Design of Coal Mine Safety Monitoring System Based on WSN
p.1483

The Hardware Implementation of a Lightweight Block Cipher Algorithm and a Message Authentication Algorithm
p.1489

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 546-547An Algorithm to Packing Unequal Spheres in a...

An Algorithm to Packing Unequal Spheres in a Larger Sphere

Abstract:

We consider the problem of packing unequal spheres into a larger sphere as dense as possible. This problem is seldom researched so far as we know, but its importance and real world applications have been widely revealed. In this paper, we present a method using the techniques of Tabu search, Quasi-human basin-hopping strategy, and BFGS method as its components to resolve this problem, and get some solutions for a serial of thoroughly selected instances.

You might also be interested in these eBooks

Electrical Insulating Materials and Electrical Engineering

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 546-547)

Pages:

1464-1469

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.546-547.1464

Citation:

Cite this paper

Online since:

July 2012

Authors:

Zhi Zhong Zeng, Wen Qi Huang, Ru Chu Xu, Zhang Hua Fu

Keywords:

Basin-Hopping, BFGS, NP-Hard, Quasi-Human, Spheres Packing, Tabu Search

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Y. G. Stoyan and A. Chugay, Packing cylinders and rectangular parallelepipeds with distancesbetween them into a given region, European Journal of Operational Research, vol. 197(2008), no. 2, p.446–455.

DOI: 10.1016/j.ejor.2008.07.003

Google Scholar

[2] S. R. Williams and A. P. Philipse, Random packing of spheres and sphero-cylinders simulated by mechanical contraction, Physics Review E, vol. 67(2003), Article ID 051301, 9 pages.

Google Scholar

[3] J. Wang, Packing of unequal spheres and automated radiosurgical treatment planning, Journal of Combinatorial Optimization, vol. 3(1999), no. 4, p.453–463.

Google Scholar

[4] Y. G. Stoyan, G. N. Yaskov, and G. Scheithauer, Packing of various radii solid spheres into a paralleliped, Central European Journal of Operational Research, vol. 11(2003), no. 4, p.389–407.

Google Scholar

[5] A. Sutou and Y. Dai, Global optimization approach to unequal global optimization approach to unequal sphere packing problems in 3D, Journal of Optimization Theory and Applications, vol. 114(2002), no. 3, p.671–694.

DOI: 10.1023/a:1016083231326

Google Scholar

[6] A. Müller, J. J. Schneider, and E. Schömer, Packing a multidisperse system of hard disks in a circular environment, Phys. Rev. E 79, 021102 , (2009).

DOI: 10.1103/physreve.79.021102

Google Scholar

[7] F. Glover, M. Laguna, Tabu Search, Kluwer Academic, Boston, (1997).

Google Scholar

[8] H. Q. Wang, W. Q. Huang, Q. Zhang and D. M. Xu, An improved algorithm for the packing of unequal circles within a larger containing circle, Eur. J. Oper. Res., vol. 141(2002), pp.440-453.

DOI: 10.1016/s0377-2217(01)00241-7

Google Scholar

[9] Dong C. Liu, Jorge Nocedal , On the limited memory BFGS method for large scale optimization, Mathematical Programming, vol. 45 (1989), pp.503-528.

DOI: 10.1007/bf01589116

Google Scholar

[10] J. F. Liu, Y. L. Wang and J. J. Pan, Effciently Packing Circles into a Larger Containing Circle, HPCA. LNCS., vol. 5938(2010), pp.250-256.

Google Scholar

[11] Wenqi Huang, Tao Ye, Global optimization method for finding dense packings of equal circles in a circle, Eur. J. Oper. Res., vol. 210( 2011), pp.474-482.

DOI: 10.1016/j.ejor.2010.11.020

Google Scholar

[12] Wenqi Huang, Zhizhong Zeng, Zhanghua Fu, Ruchu Xu, Using iterated local search for efficiently packing unequal disks in a larger circle, to be published in Advanced Materials Research.

DOI: 10.1109/csip.2012.6308788

Google Scholar