МЕТОДОЛОГИЯ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ МНОГОМЕРНЫХ ШАРОВ

image_print
DOI https://doi.org/10.15407/pmach2019.01.067
Журнал Проблемы машиностроения
Издатель Институт проблем машиностроения им. А. Н. Подгорного Национальной академии наук Украины
ISSN 0131-2928 (print), 2411-0779 (online)
Выпуск Том 22, № 1, 2019 (март)
Страницы 67-75

 

Автор

Г. Н. Яськов, Институт проблем машиностроения им. А. Н. Подгорного НАН Украины (61046, Украина, г. Харьков, ул. Пожарского, 2/10), e-mail: yaskov@ipmach.kharkov.ua, ORCID: 0000-0002-1476-1818

 

Аннотация

В статье рассматривается задача оптимального размещения шаров различной размерности в контейнерах произвольных геометрических форм. Согласно международной классификации эта задача относится к классу SPP (Sphere Packing Problems). Она заключается в размещении набора шаров (кругов, гипершаров) заданных радиусов в контейнере с заданными метрическими характеристиками. Целью данной работы является создание единой методологии решения задач SPP. Приведены основные постановки задачи: в виде задачи о рюкзаке; задачи с переменным размером контейнера и соответствующие математические модели. На выбор стратегии решения влияют вид постановки задачи, размерность пространства, в котором размещаются шары, метрические особенности шаров (равные или неравные), их количество, геометрическая форма контейнера, наличие технологических ограничений, ограничение на время счета. Структурными элементами методологии являются математические модели, способы построения начальных размещений, методы локальной и глобальной оптимизации. При разработке метода решения используется построение начальных допустимых размещений случайным, решетчатым способами, с помощью жадного алгоритма и путем решения вспомогательной задачи нелинейного программирования. В качестве методов локальной оптимизации рассматриваются модификации метода возможных направлений, метод внутренней точки, метод множителей Лагранжа и метод оптимизации по группам переменных. Для глобальной оптимизации используются метод перебора подмножеств шаров из заданного набора, метод перебора крайних точек области допустимых решений, реализованные с помощью алгоритма ветвей и границ, модификации методов сужающихся окрестностей, метод плавного перехода из одного локального минимума в другой на основе увеличения размерности задачи путем введения дополнительных переменных метрических характеристик, метод решения, реализованный в виде последовательности задач нелинейного программирования возрастающей размерности, метод мультистарта. Предложены стратегии решения задачи SPP для различных ее постановок.

 

Ключевые слова: шар, гипершар, упаковка шаров, задача о рюкзаке, задача с переменным размером, нелинейная оптимизация.

 

Полный текст: загрузить PDF

 

Литература

  1. Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наук. думка, 1986. 268 с.
  2. Waescher G., Haussner H. An improved typology of cutting and packing problems. Europ. J. Operational Research. 2007. Vol. 183. Iss. 5. P. 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047
  3. Hifi M., M’Hallah R. A literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research. 2009. Vol. 2009. P. 1–19. https://doi.org/10.1155/2009/150624
  4. Snoj L., Ravnik M. Effect of packing fraction variations on the multiplication factor in pebble-bed nuclear reactors. Kerntechnik. 2006. Vol. 71. No. 4. P. 208–213. https://doi.org/10.3139/124.100295
  5. Leary M., Merli L., Torti F., Mazur M., Brandt M. Optimal topology for additive manufacture: A method for enabling additive manufacture of support-free optimal structures. Materials and Design. 2014. Vol. 63. P. 678–690. https://doi.org/10.1016/j.matdes.2014.06.015
  6. Blyuss O., Koriashkina L., Kiseleva E., Molchanov R. Optimal Placement of Irradiation Sources in the Planning of Radiotherapy: Mathematical Models and Methods of Solving. Computational and Math. Methods in Medicine. 2015. Vol. 2015. P. 1–8. https://doi.org/10.1155/2015/142987
  7. Agapie S. C., Whitlock P. A. Random packing of hyperspheres and Marsaglia’s parking lot test. Monte Carlo Methods and Appl. 2010. Vol. 16. Iss. 3–4. P. 197–209. https://doi.org/10.1515/mcma.2010.019
  8. Conway H., Sloane N. J. A Sphere Packings, Lattices, and Groups. New York: Springer-Verlag, 1999. 706 p. https://doi.org/10.1007/978-1-4757-6568-7
  9. Torquato S., Stillinger, F. H. Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces. Physical Review E. 2006. Vol. 73. Iss. 3. P. 031–106. https://doi.org/10.1103/PhysRevE.73.031106
  10. Hifi M., Yousef L. A dichotomous search-based heuristic for the three-dimensional packing problem. Cogent Eng. 2015. Vol. 1. P. 1–15. https://doi.org/10.1080/23311916.2014.994257
  11. Zeng Z., Yu X., He K., Huang W., Fu Z. Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container. Europ. J. Operational Research. 2016. Vol. 250. Iss. 2. P. 615–627.  https://doi.org/10.1016/j.ejor.2015.09.001
  12. Sutou A., Dai Y. Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D. J. Optimization Theory and Appl. 2002. Vol. 114. Iss. 3.  P. 671–694.  https://doi.org/10.1023/A:1016083231326
  13. Zeng Z. Z., Huang W. Q., Xu R. C., Fu Z. H. An algorithm to packing unequal spheres in a larger sphere. Advanced Materials Research. 2012. Vol. 546–547. P. 1464–1469. https://doi.org/10.4028/www.scientific.net/AMR.546-547.1464
  14. Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy Algorithms for Packing Unequal Spheres into a Cuboidal Strip or a Cuboid. Asia-Pacific J. Operational Research. 2011. Vol. 28. No. 06. P. 739–753. https://doi.org/10.1142/S0217595911003326
  15. Birgin E. G., Sobral F. N. C. Minimizing the object dimensions in circle and sphere packing problems. Computers & Operations Research. 2008. Vol. 35. Iss. 7. P. 2357–2375. https://doi.org/10.1016/j.cor.2006.11.002
  16. Stoyan Yu., Yaskov G. Packing congruent hyperspheres into a hypersphere. J. Global Optimization. 2012. Vol. 52. Iss. 4. P. 855–868. https://doi.org/10.1007/s10898-011-9716-z
  17. Яковлев С. В., Яськов Г. Н., Коробчинский К. П. О методах переменного радиуса в задаче упаковки шаров в контейнеры. Питання прикл. математики i мат. моделювання: зб. наук. пр. Дніпро: ЛІРА. 2017. № 17. С. 265–272.
  18. Стоян Ю. Г.,Шайтхауер Г., Яськов Г. Н. Упаковка неравных шаров в различные контейнеры. Кибернетика и систем. анализ. 2016. № 3. С. 97–105.
  19. Yaskov G. N. Packing non-equal hyperspheres into a hypersphere of minimal radius. Проблемы машиностроения. 2014. Т. 17. № 1. С. 48–53.
  20. Stoyan Y., Yaskov G. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints. Transactions in Operational Research. 1998. Vol. 5. No. 1. P. 45–57. https://doi.org/10.1111/j.1475-3995.1998.tb00101.x
  21. Visscher W. M., Bolsterli M. Random Packing of Equal and Unequal Spheres in Two and Three Dimensions. Nature. 1972. Vol. 239. P. 504–507. https://doi.org/10.1038/239504a0
  22. Mueller G. Numerically packing spheres in cylinders. Powder Technology. 2005. Vol. 159. Iss. 2. P. 105–110. https://doi.org/10.1016/j.powtec.2005.06.002
  23. Яськов Г. Н. Упаковка большого числа конгруэнтных кругов в цилиндре.  Доп. НАН України. № 12. С. 43–49.
  24. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry. 2015. Vol. 43. Iss. 5. P. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003
  25. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. J. Global Optimization. Vol. 65. Iss. 2. P. 283–307. https://doi.org/10.1007/s10898-015-0331-2
  26. Stoyan Y., Yaskov G. Packing equal circles into a circle with circular prohibited areas. J. Computer Mathematics. 2012. Vol. 89. Iss. 10. P. 1355–1369. https://doi.org/10.1080/00207160.2012.685468
  27. Яськов Г. Н. Метод решения задачи размещения разных кругов с перспективным выбором начальных точек. Зб. наук. праць Харк. ун-ту повітряних сил. 2010. Вип. 3. № 25. С. 119–122.
  28. Wächter A., Biegler L. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Programming. 2006. Vol. 106. Iss. 1. P. 25–57. https://doi.org/10.1007/s10107-004-0559-y
  29. Stoyan Yu., Yaskov G. Packing unequal circles into a strip of minimal length with a jump Optimization Letters. 2014. Vol. 8. Iss. 3. P. 949–970. https://doi.org/10.1007/s11590-013-0646-1
  30. Yaskov G. N. Random packing of identical spheres into a cylindrical container. Системи обробки інформації. 2008. Вип. 1. № 68. С. 128–130.
  31. Stoyan Y., Chugay A. Packing cylinders and rectangular parallelepipeds with distances between them into a given region. J. Operational Research. 2009. Vol. 197. Iss. 2. P. 446–455. https://doi.org/10.1016/j.ejor. 2008.07.003
  32. Gondzio J. HOPDM (version 2.12) – a fast LP solver based on a primal-dual interior point method. J. Operational Research. 1995. Vol. 85. Iss. 1. P. 221–225. https://doi.org/10.1016/0377-2217(95)00163-K
  33. Meszaros C. On numerical issues of interior point methods. SIAM on Matrix Analysis and Appl. 2008. Vol. 30. Iss. 1. P. 223–235. https://doi.org/10.1137/050633354
  34. Torquato S., Uche O. U., Stillinger, H. Random sequential addition of hard spheres in high Euclidean dimensions. Physical Review E. 2006. Vol. 74. Iss. 6. P. 061–308. https://doi.org/10.1103/PhysRevE.74.061308
  35. Stoyan Y., Scheithauer G., Yaskov G. Packing of various radii solid spheres into a parallelepiped. Central Europ. J. Operations Research. 2003. Vol. 11. No. 4. P. 389–407.
  36. Stoyan Y., Yaskov G. Packing Identical Spheres into a Rectangular Parallelepiped. In: Bortfeldt A., Homberger J., Kopfer H., Pankratz G., Strangmeier R. (eds) Intelligent Decision Support. Gabler, 2008. P. 47–67. https://doi.org/10.1007/978-3-8349-9777-7_4
  37. Яськов Г. Н. Дерево решений для задачи размещения неравных шаров в шаре заданного радиуса. Інформаційні системи і технології ІСТ-2017: пр 6-ї міжнар. наук.-техн. конф. (Коблеве, 11–16 вер. 2017). Коблеве, 2017. С. 143–144.

 

Поступила в редакцию 14 января 2019 г.