Методология решения задач размещения многомерных шаров
Ключевые слова:
шар, гипершар, упаковка шаров, задача о рюкзаке, задача с переменным размером, нелинейная оптимизацияАннотация
В статье рассматривается задача оптимального размещения шаров различной размерности в контейнерах произвольных геометрических форм. Согласно международной классификации эта задача относится к классу 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).
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2019 G. N. Yaskov
Это произведение доступно по лицензии Creative Commons «Attribution-NoDerivatives» («Атрибуция — Без производных произведений») 4.0 Всемирная.
Авторы, публикующиеся в этом журнале, соглашаются со следующими условиями:
- Авторы оставляют за собой право на авторство своей работы и передают журналу право первой публикации этой работы на условиях лицензионного договора (соглашения).
- Авторы имеют право заключать самостоятельно дополнительные договора (соглашения) о неэксклюзивном распространении работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном хранилище учреждения или публиковать в составе монографии), при условии сохранения ссылки на первую публикацию работы в этом журнале.
- Политика журнала позволяет размещение авторами в сети Интернет (например, в хранилищах учреждения или на персональных веб-сайтах) рукописи работы, как до подачи этой рукописи в редакцию, так и во время ее редакционной обработки, поскольку это способствует возникновению продуктивной научной дискуссии и позитивно отражается на оперативности и динамике цитирования опубликованной работы (см. The Effect of Open Access).
