顆粒堆積問題在材料、化工、土木等許多領域，皆為相當重要且受到關注的問題。為了深入瞭解材料的性質，研究者往往需要探討組成材料的顆粒之堆積狀況，例如各顆粒與鄰近顆粒之接觸狀況、粒徑分佈對堆積密度之影響，以及許多其他性質。由於顆粒行為的複雜以及材料製備的困難，以實驗方法並不一定能獲得理想的成果。而使用電腦模擬顆粒堆積有許多優點，例如：(1)可大量重複試驗、(2)易作多次破壞性測試、(3) 可對堆積過程及結果作完整的觀察。因此，過去的文獻中有許多學者提出各種電腦模擬顆粒堆積的方法，但由於過去文獻之研究成果僅限於無容器的特殊狀況、二度空間的堆積、坍度測試、或極少量之顆粒數之三維堆積。故本研究針對此一主題提出一套方法模擬三維正球的堆積。
在方法的架構上，本研究以最佳化方法為基礎建構模型與求解之主要工具。研究中以數學模型描述球、容器、與球在容器中的行為，藉此模擬在三維空間中將一定量之球裝入長方體容器中，並逐步調整各球在空間中之位置。為了避免在向下壓密的過程中產生局部阻塞的現象，本研究採用求解組合最佳化問題常用之模擬退火法（Simulated annealing heuristic）之概念，使所有球之整體行為呈現向下壓密，但各球之局部行為則允許適度向上膨鬆。
在堆積模擬的過程中電腦須隨時嚴格保持各球之間不得產生相互疊合之現象，以維持模擬的正確性。此部份的計算耗費大量的電腦時間。為了提高模擬效率，本研究在演算法以及資料結構上提出數種方法以減少對電腦計算量之需求。藉由記憶容器中各球相互間的位置關係，當調整球在容器中的位置時，可有效率的判斷是否會與它球發生疊合現象，進而縮短計算時間。在記憶位置關係資料時，可容許此資料與真實各球的位置間有適量的誤差，由於不必隨時保持所有資料之絕對正確性，因此計算時間得以大幅縮減。而經由對誤差量之精確掌控，模擬程序仍然能夠得到正確無誤之堆積結果。此外，本研究並發展一套機制使演算法在壓密的過程中能夠自動調整部份參數，而達到提高效率之目的。本論文並發展數種壓密模擬策略並各別進行分析與測試以探討其基本性質。
利用本研究所發展的方法，論文中對單一粒徑以及混合粒徑之正球堆積作測試，並探討各種狀況下所能達到之最大密度。測試結果顯示單一粒徑之堆積密度接近理論最大密度，並經由測試發現在最大密度的六方最密堆積中，單一顆粒的錯置足以對整體密度造成相當之影響。在混合粒徑測試中並發現兩種不同粒徑正球混合堆積時，兩種顆粒之粒徑比例以及兩種顆粒之數量比例對整體密度均有規律性之影響。而在求解效率測試中也發現本研究所提出之求解效率改善方法，能大幅縮短堆積模擬的時間。

Problems related to the packing of particles are studied in many areas such as Material Science, Chemical Engineering, and Civil Engineering. These problems serve as an important theoretical foundation for analysis on properties of materials. For example, how the particles contact each other when packed, how the size distribution of the particles affect the density, and others. Due to the compexity of particles and other difficulties, not all problems can be studied experimentally. On the other hand, simulations conducted in computers have a number of important advantages, including (a) experiments can be repeated easily; (b) destructive analyses can be performed repeatedly, and (c) the packing process as well as the result can be thoroughly observed. Therefore, a number of simulating methods have been proposed in the literature. Problems investigated in the past include packing in 2-dimension, slump testing, and 3-dimensional packing of very few particles. In this research, we develop a framework for the simulation of spheres in 3-dimension.
The core of the methodology used in this research is a set of optimization tools used to construct and solve a system that describes a set of spheres. We develop a mathematic system to characterize the spheres, the container, and the behavior of spheres in the container. With this system we simulate the process of filling a given set of spheres into a container, followed by a series of adjustments on the locations of each individual sphere in order to increase the overall density. We apply the widely used Simulated annealing heuristic to avoid interlocking among the spheres. This heuristic allows individual spheres to move in any direction, including upwards, while increasingly concentrating the spheres toward the bottom of the container.
One key issue in the correctness of the simulation result is to strictly prevent the spheres from overlapping with each other or with a container wall. The required computation consumes a significant portion of the CPU time. We increase the efficiency by using a special data structure. The simulation program maintains a table that keeps the distance between every pair of spheres. By simple table-lookup, one can determine the pairs of spheres that need not be checked for overlapping following an adjustment. Flaws are allowed in the table to minimize computation time. By carefully controlling the error margins, simulation correctness can be maintained. We also developed a mechanism to enable the system to adjust some of the parameters automatically in the simulation process. Several strategies are developed and tested for the simulation of particle compacting, and basic properties of the strategies are studied in detail.
With the methodologies developed in this research, we simulated the packing of mono-sized spheres as well as mixed-sized spheres to determine the maximum density under various conditions. For a set of mono-sized spheres the simulation is able to achieve densities close to the theoretical upper bound. Computational results show that in hexagonal close packed spheres, a small displacement on one single particle can result in significant loss in overall density. By packing spheres of two different sizes together, we observed trends concerning how the ratio of the number of large spheres and small spheres affect the overall density. We also confirmed the efficiency of our method.

1. 楊承道，三維顆粒堆積模擬，國立成功大學土木工程研究所碩士論文，1999年。
2. G. A. Bird, “Molecular Dynamics and the Direct Simulation of Gas Flow,” Oxford Science Publications, Oxford (1994).
3. P. A. Cundall, “A Computer Model of Simulating Progressive Large Scale Movement in Blocky Rock System,” Symposium of International Society of Rock Mechanics, Nancy, France (1971).
4. L. Faina, “A global optimization algorithm for the three-dimensional packing problem,” European Journal of Operational Research 126, pp.340 - 354 (2000).
5. H. J. Herrmann and M. Müller, “Simulations of granular materials on different scales,” Computer Physics Communications 127, pp.120 - 125 (2000).
6. S. Jakobs, “On genetic algorithms for the packing of polygons,” European Journal of Operational Research 88, pp. 165 - 181 (1996).
7. G. K. Knopf and J. K. Dickinson, “A moment based metric for 2-D and 3-D packing,” European Journal of Operational Research 122, pp.133 - 144 (2000).
8. Y. Lee, C.-T. Yang, and C.-S. Chien, “ A 3D ellipsoid-based model for packing of granular particles,” Int. J. of Computer Applications in Technology, Vol. 17, No.3, pp. 148 – 155 (2003).
9. C. Lesaffre, V. Mineau, D. Picart, and H. V. Damme, “Densification under vibration of a saturated granular packing,” C.R. Acad, Sci. Paris, t.1, Série IV, pp.647 - 653 (2000).
10. H. G. Matuttis, S. Luding, and H. J. Herrmann, “Discrete element simulations of dense packings and heaps made of spherical and non-spherical particles,” Powder Technology 109, pp.278 - 292 (2000).
11. M. Nicodemi, “Domains growth and packing properties in driven granular media subject to gravity,” Physica A 285, pp. 267 - 278 (2000).
12. Y. G. Stoyan, M. V. Novozhilova, and A. V. Kartashov, “Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem,” European Journal of Operational Research 92, pp. 193 - 210 (1996).
13. Y. G. Stoyan and V.N. Patsuk, “A method of optimal lattice packing of congruent oriented polygons in the plane,” European Journal of Operational Research 124, pp.204 - 216 (2000).
14. H.-F. Teng, S.-L. Sun, D.-Q. Liu, and Y.-Z. Li, “Layout optimization for the objects located within a rotating vessel – a three -dimensional packing problem with behavioral constraints,” Computers & Operations Research 28, pp.521 - 535 (2001).
15. F. Trentadue, “A micromechanical model for a no-linear elastic granular material based on local equilibrium conditions,” International Journal of Solids and Structures 38, pp.7319 – 7342 (2001).
16. O. Tsoungui, D. Vallet, and J.-C. Charmet, “Numerical model of crushing of grains inside two-dimensional granular materials,” Powder Technology 106, pp. 190 - 198 (1999).
17. A. B. Yu, L. F. Liu, and Z. P. Zhang, “Dynamic simulation of the centripetal packing of mono-sized spheres,” Physica A 268, pp. 433 - 453 (1999).