Методологія розв’язання задач розташування багатовимірних куль
Ключові слова:
куля, гіперкуля, упаковка куль, задача про рюкзак, задача зі змінним розміром, нелінійна оптимізаціяАнотація
В статті розглядається задача оптимального розміщення куль різної розмірності в контейнерах довільних геометричних форм. Згідно з міжнародною класифікацією ця задача належить до класу SPP (Sphere Packing Problems). Вона полягає в розміщенні набору куль (кругів, гіперкуль) заданих радіусів у контейнері з заданими метричними характеристиками. Метою даної роботи є створення єдиної методології розв’язання задач SPP. Наведено основні постановки задачі: у вигляді задачі про рюкзак і задачі зі змінним розміром контейнера та відповідні математичні моделі. На вибір стратегії розв’язання впливають вид постановки задачі, розмірність простору, в якому розміщуються кулі, метричні особливості куль (рівні чи нерівні), кількість розміщуваних куль, геометрична форма контейнера, наявність технологічних обмежень, обмеження на час обчислень. Структурними елементами методології є математичні моделі, способи побудови початкових розміщень, методи локальної й глобальної оптимізації. Під час розробки методу розв'язання використовується побудова допустимих розміщень випадковим, ґратчастим способами, за допомогою жадібного алгоритму й шляхом розв’язання допоміжної задачі нелінійного програмування. Як методи локальної оптимізації розглядаються модифікації методу можливих напрямів, метод внутрішньої точки, метод множників Лагранжа та метод оптимізації за групами змінних. Для глобальної оптимізації використовуються метод перебору підмножин куль із заданого набору, метод перебору крайніх точок області допустимих розв’язків, реалізовані за допомогою алгоритму гілок і меж, модифікації методів околів, що звужуються, метод плавного переходу з одного локального мінімуму в інший на основі збільшення розмірності задачі шляхом уведення додаткових змінних метричних характеристик, метод розв’язання, реалізований у вигляді послідовності задач нелінійного програмування зростаючої розмірності, метод мультистарту. Запропоновано стратегії розв’язання задач SPP для різних її постановок.Посилання
Stoyan, Yu. G. & Yakovlev, S. V. (1986). Matematicheskiye modeli i optimizatsionnyye metody geometricheskogo proyektirovaniya [Mathematical models and optimisation methods of geometric design]. Kiyev: Naukova Dumka, 268 p. (in Russian).
Waescher, G. & Haussner, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, vol. 183, iss. 5, pp. 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047
Hifi, M. & M'Hallah, R. (2009). A. literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research, vol. 2009, pp. 1–22. https://doi.org/10.1155/2009/150624
Snoj, L. & Ravnik, M. (2006). Effect of packing fraction variations on the multiplication factor in pebble-bed nuclear reactors. Kerntechnik, vol. 71, no. 4, pp. 208–213. https://doi.org/10.3139/124.100295
Leary, M., Merli, L., Torti, F., Mazur, M., & Brandt, M. (2014). Optimal topology for additive manufacture: A method for enabling additive manufacture of support-free optimal structures. Materials and Design, vol. 63, pp. 678–690. https://doi.org/10.1016/j.matdes.2014.06.015
Blyuss, O., Koriashkina, L., Kiseleva, E., & Molchanov, R. (2015). Optimal Placement of Irradiation Sources in the Planning of Radiotherapy: Mathematical Models and Methods of Solving. Computational and Mathematical Methods in Medicine, vol. 2015, pp. 1–8. https://doi.org/10.1155/2015/142987
Agapie, S. C. & Whitlock, P. A. (2010). Random packing of hyperspheres and Marsaglia's parking lot test. Monte Carlo Methods and Applications, vol. 16, iss. 3–4, pp. 197–209. https://doi.org/10.1515/mcma.2010.019
Conway, J. H. & Sloane, N. J. (1999). A sphere packings, lattices, and groups. New York: Springer-Verlag, 706 p. https://doi.org/10.1007/978-1-4757-6568-7
Torquato, S. & Stillinger, F. H. (2006). Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces. Physical Review E, vol. 73, iss. 3, 031106. https://doi.org/10.1103/PhysRevE.73.031106
Hifi, M. & Yousef, L. (2015). A dichotomous search-based heuristic for the three-dimensional packing problem. Cogent Engineering, vol. 2 (1), pp. 1–15. https://doi.org/10.1080/23311916.2014.994257
Zeng, Z., Yu, X., He, K., Huang, W., & Fu, Z. (2016). Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container. European Journal of Operational Research, vol. 250, iss. 2, pp. 615–627. https://doi.org/10.1016/j.ejor.2015.09.001
Sutou, A. & Dai, Y. (2002). Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D. Journal of Optimization Theory and Applications, vol. 114, iss. 3, pp. 671–694. https://doi.org/10.1023/A:1016083231326
Zeng, Z. Z, Huang, W. Q., Xu, R. C., & Fu, Z. H. (2012). An algorithm to packing unequal spheres in a larger sphere. Advanced Materials Research, vol. 546–547, pp. 1464–1469. https://doi.org/10.4028/www.scientific.net/AMR.546-547.1464
Kubach, T., Bortfeldt, A., Tilli, T., & Gehring, H. (2011). Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. Asia-Pacific Journal of Operational Research, vol. 28, no. 06, pp. 739–753. https://doi.org/10.1142/S0217595911003326
Birgin, E. G. & Sobral, F. N. C. (2008). Minimizing the object dimensions in circle and sphere packing problems. Computers & Operations Research, vol. 35, iss. 7, pp. 2357–2375. https://doi.org/10.1016/j.cor.2006.11.002
Stoyan, Yu. & Yaskov, G. (2012). Packing congruent hyperspheres into a hypersphere. Journal of Global Optimization, vol. 52, iss. 4, pp. 855–868. https://doi.org/10.1007/s10898-011-9716-z
Yakovlev, S. V., Yaskov, G. N., & Korobchinskiy, K. P. (2017). O metodakh peremennogo radiusa v zadache upakovki sharov v konteynery. [On variable radius methods in problems of packing spheres into containers]. Pytannia prykl. matematyky i mat. modeliuvannia: zb. nauk. pr. − Problems of Applied Mathematics and Mathematical Modeling. Collection of scientific papers, Dnirpo: LIRA, iss. 17, pp. 265−272 (in Russian).
Stoyan, Yu. G., Scheithauer, G., & Yaskov, G. N. (2016). Packing unequal spheres into various containers. Cybernetics and Systems Analysis, vol. 52, iss. 3, pp. 419−426. https://doi.org/10.1007/s10559-016-9842-1
Yaskov, G. N. (2014). Packing non-equal hyperspheres into a hypersphere of minimal radius. Journal of Mechanical Engineering, vol. 17, no. 1, pp. 48–53.
Stoyan, Y. & Yaskov, G. (1998). Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints. International Transactions in Operational Research, vol. 5, no. 1, pp. 45–57. https://doi.org/10.1111/j.1475-3995.1998.tb00101.x
Visscher, W. M. & Bolsterli, M. (1972). Random packing of equal and unequal spheres in two and three dimensions. Nature, vol. 239, pp. 504–507. https://doi.org/10.1038/239504a0
Mueller, G. E. (2005). Numerically packing spheres in cylinders. Powder Technology, vol. 159, iss. 2, pp. 105–110. https://doi.org/10.1016/j.powtec.2005.06.002
Yaskov, G. N. (2009). Upakovka bolshogo chisla kongruentnykh krugov v tsilindre [Packing a great number of spheres into a cylinder]. Dopov. Nac. akad. nauk Ukr. −Reports of the National Academy of Sciences of Ukraine, no. 12, pp. 43–49 (in Russian).
Chernov, N., Stoyan, Yu., & Romanova, T. (2015). Mathematical model and efficient algorithms for object packing problem. Computational Geometry, vol. 43, iss. 5, pp. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003
Stoyan, Y., Pankratov, A., & Romanova, T. (2016). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, vol. 65, iss. 2, pp. 283–307. https://doi.org/10.1007/s10898-015-0331-2
Stoyan, Y. & Yaskov, G. (2012). Packing equal circles into a circle with circular prohibited areas. International Journal of Computer Mathematics, vol. 89, iss. 10, pp. 1355–1369. https://doi.org/10.1080/00207160.2012.685468
Yaskov, G. N. (2010). Metod resheniya zadachi razmeshcheniya raznykh krugov s perspektivnym vyborom nachalnykh tochek [Method of solving the problem of packing different circles with choice of perspective initial points]. Zb. nauk. prats Kharkivskogo universitetu povitryanyh syl − Scientific Works of Kharkov National Air Force University, iss. 3, no. 25, pp. 119−122 (in Russian).
Wächter, A. & Biegler, L. T. (2006). On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Mathematical Programming, vol. 106, iss. 1, pp. 25–57. https://doi.org/10.1007/s10107-004-0559-y
Stoyan, Yu. & Yaskov, G. (2014). Packing unequal circles into a strip of minimal length with a jump algorithm. Optimization Letters, vol. 8, iss. 3, pp. 949–970. https://doi.org/10.1007/s11590-013-0646-1
Yaskov, G. N. (2008). Random packing of identical spheres into a cylindrical container. Systemy obrobky informatsii, iss. 1, no. 68, pp. 128−130.
Stoyan, Y. & Chugay, A. (2009). Packing cylinders and rectangular parallelepipeds with distances between them into a given region. European Journal of Operational Research, vol. 197, iss. 2, pp. 446–455. https://doi.org/10.1016/j.ejor.2008.07.003
Gondzio, J. (1995). HOPDM (version 2.12) – a fast LP solver based on a primal-dual interior point method. European Journal of Operational Research, vol. 85, iss. 1, pp. 221–225. https://doi.org/10.1016/0377-2217(95)00163-K
Meszaros, C. (2008). On numerical issues of interior point methods. SIAM Journal on Matrix Analysis and Applications, vol. 30, iss. 1, pp. 223–235. https://doi.org/10.1137/050633354
Torquato, S., Uche, O. U., & Stillinger, F. H. (2006). Random sequential addition of hard spheres in high Euclidean dimensions. Physical Review E, vol. 74, iss. 6, pp. 061308. https://doi.org/10.1103/PhysRevE.74.061308
Stoyan, Y., Scheithauer, G., & Yaskov, G. (2003). Packing of various radii solid spheres into a parallelepiped. Central European Journal of Operations Research, vol. 11, no. 4, pp. 389–407.
Stoyan, Y. & Yaskov, G. (2008). Packing identical spheres into a rectangular parallelepiped. In: Bortfeldt, A., Homberger, J., Kopfer, H., Pankratz, G., & Strangmeier, R. (eds) Intelligent Decision Support. Gabler, pp. 47–67. https://doi.org/10.1007/978-3-8349-9777-7_4
Yaskov, G. N. (2007). Derevo resheniy dlya zadachi razmeshcheniya neravnykh sharov v share zadannogo radiusa. Informatsiini systemy i tekhnologii IST-2017: pr 6-i mizhnar. nauk.-tekhn. konf. (Kobleve, 11–16 ver. 2017) [Solution tree for the problem of packing unequal spheres in a sphere of a given radius. Informational systems and technologies IST-2017: Proceedings of 6th int. sc. and techn. seminar]. Kobleve, pp. 143–144 (in Russian).
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2019 G. N. Yaskov
Ця робота ліцензується відповідно до Creative Commons Attribution-NoDerivatives 4.0 International License.
Автори, які публікуються в цьому журналі, погоджуються з наступними умовами:
- Автори залишають за собою право на авторство своєї роботи і передають журналу право першої публікації цієї роботи на умовах ліцензійного договору (угоди).
- Автори мають право самостійно укладати додаткові договори (угоди) з неексклюзивного поширення роботи в тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати в складі монографії), за умови збереження посилання на першу публікацію роботи в цьому журналі.
- Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у сховищах установи або на персональних веб-сайтах) рукопису роботи як до подачі цього рукопису в редакцію, так і під час її редакційної обробки, оскільки це сприяє виникненню продуктивної наукової дискусії і позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
