Методология решения задач поиска оптимального размещения трехмерных тел

image_print
DOI https://doi.org/10.15407/pmach2020.02.060
Журнал Проблемы машиностроения
Издатель Институт проблем машиностроения им. А.Н. Подгорного Национальной академии наук Украины
ISSN 0131-2928 (print), 2411-0779 (online)
Выпуск Том 23, № 2, 2020 (июнь)
Страницы 60–71

 

Авторы

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

А. М. Чугай, Институт проблем машиностроения им. А. Н. Подгорного НАН Украины (61046, Украина, г. Харьков, ул. Пожарского, 2/10), e-mail: chugay.andrey80@gmail.com, ORCID: 0000-0002-4079-5632

 

Аннотация

Работа посвящена решению оптимизационных задач упаковки трехмерных тел путем построения точных математических моделей и разработки подходов, основанных на применении оптимизационных методов нелинейного программирования и современных решателей. Разработаны конструктивные средства математического и компьютерного моделирования отношений ориентированных и неориентированных трехмерных тел, граница которых образована цилиндрическими, коническими, сферическими поверхностями и плоскостями, в виде новых классов Ф-функций и квази Ф-функций. На базе разработанных средств математического моделирования построено и исследовано базовую математическую модель задачи оптимальной упаковки трехмерных тел, границы которых образованы цилиндрическими, коническими, сферическими поверхностями и плоскостями, а также различные ее реализации, которые охватывают широкий класс научных и прикладных задач упаковки трехмерных тел. Разработана общая методология решения задач упаковки трехмерных тел, допускающих одновременно непрерывные повороты и трансляции. Предложены стратегии, методы и алгоритмы решения оптимизационных задач упаковки трехмерных тел с учетом технологических ограничений (минимально допустимые расстояния, зоны запрета, возможность непрерывных трансляций и вращений). На основании предложенных средств математического моделирования, математических моделей, методов и алгоритмов, создано программное обеспечение с использованием технологии параллельных вычислений для автоматического решения оптимизационных задач упаковки трехмерных тел. Полученные результаты могут быть использованы при решении задач оптимизации компоновочных решений для компьютерного моделирования в материаловедении, в порошковой металлургии и нанотехнологиях, при оптимизации процесса 3D-печати для SLS технологии аддитивного производства, в информационно-логистических системах, обеспечивающих оптимизацию перевозки и хранения грузов.

 

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

 

Литература

  1. Petrov M. S., Gaidukov V. V., Kadushnikov R. M. Numerical method for modelling the microstructure of granular materials. Powder Metallurgy and Metal Ceramics. 2004. No. 43 (7–8). P. 330–335. https://doi.org/10.1023/B:PMMC.0000048126.87171.f9.
  2. Wang Y., Lin C. L., Miller J. D. 3D image segmentation for analysis of multisize particles in a packed particle bed. Powder Techn. 2016. Vol. 301. P. 160–168. https://doi.org/10.1016/j.powtec.2016.05.012.
  3. Verkhoturov M., Petunin A., Verkhoturova G., Danilov K., Kurennov D. The 3D object packing problem into a parallelepiped container based on discrete-logical representation. IFAC-PapersOnLine. 2016. Vol. 49. Iss. 12. P. 1–5. https://doi.org/10.1016/j.ifacol.2016.07.540.
  4. Karabulut K. A., İnceoğlu M. Hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. Advances in Inform. Systems. 2004. No. 3261. P. 441–450. https://doi.org/10.1007/978-3-540-30198-1_45.
  5. Cao P., Fan Z., Gao R., Tang J. Complex housing: modelling and optimization using an improved multi-objective simulated annealing algorithm. Proc. ASME. 2016. No. 60563, V02BT03A034. https://doi.org/10.1115/DETC2016-60563.
  6. Guangqiang L. A., Fengqiang Z., Rubo Z., Jialu Du., Chen G., Yiran Z. Parallel particle bee colony algorithm approach to layout optimization. J. Computational and Theoretical Nanoscience. 2016. Vol. 13. No. 7. P. 4151–4157. https://doi.org/10.1166/jctn.2016.5263.
  7. Torczon V., Trosset M. From evolutionary operation to parallel direct search: Pattern search algorithms for numerical optimization. Computing Sci. and Statistics. 1998. No. 29. P. 396–401.
  8. Birgin E. G., Lobato R. D., Martіnez J. M. Packing ellipsoids by nonlinear optimization. J. Global Optimization. 2016. No. 65. P. 709–743. https://doi.org/10.1007/s10898-015-0395-z.
  9. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. J. Global Optimization. 2016. No. 65 (2). P. 283–307. https://doi.org/10.1007/s10898-015-0331-2.
  10. Fasano G. A. Global optimization point of view to handle non-standard object packing problems. J. Global Optimization. 2013. No. 55 (2). P. 279–299. https://doi.org/10.1007/s10898-012-9865-8.
  11. Egeblad J., Nielsen B. K., Brazil M. Translational packing of arbitrary polytopes. Computational Geometry: Theory and Appl. 2009. Vol. 42. Iss. 4. P. 269–288. https://doi.org/10.1016/j.comgeo.2008.06.003.
  12. Liu X,. Liu J., Cao A., Yao Z. HAPE3D ‑ a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Techn. & Electronic Eng. 2015. No. 16 (5). P. 380–390. https://doi.org/10.1631/FITEE.1400421.
  13. Youn-Kyoung J., Sang, D. N. Intelligent 3D packing using a grouping algorithm for automotive container engineering. J. Computational Design and Eng. 2014. Vol. 1. Iss. 2. P. 140–151. https://doi.org/10.7315/JCDE.2014.014.
  14. Kallrath J. Packing ellipsoids into volume-minimizing rectangular boxes. J. Global Optimization. 2017. No. 67 (1–2). P. 151–185. https://doi.org/10.1007/s10898-015-0348-6.
  15. Stoyan Y. G., Chugay A. M. Packing different cuboids with rotations and spheres into a cuboid Advances in Decision Sci. 2014. Availabel at https://www.hindawi.com/journals/ads/2014/571743.  https://doi.org/10.1155/2014/571743.
  16. Stoyan Y. G. , Semkin V. V., Chugay A. M. Modeling close packing of 3D objects. Cybernetics and Systems Analysis. 2016. No. 52 (2). P. 296–304. https://doi.org/10.1007/s10559-016-9826-1.
  17. Pankratov O., Romanova T., Stoyan Y., Chuhai A. Optimization of packing polyhedra in spherical and cylindrical containers. Eastern European J. Enterprise Techn. Vol. 1. No. 4 (79). P. 39–47. https://doi.org/10.15587/1729-4061.2016.60847.
  18. Stoyan Y. G., Chugay A. M. Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetic Systems Analysis. 2012. No. 48. P. 837–845. https://doi.org/10.1007/s10559-012-9463-2.
  19. Чугай А. М. Решение задачи упаковки кругов в выпуклый многоугольник с помощью модифицированного метода сужающихся окрестностей. Радиоэлектроника и информатика. 2005. № 1. С. 58–63.
  20. Stoian Y. E., Chugay A. M., Pankratov A. V. Two approaches to modeling and solving the packing problem for convex polytopes. Cybernetic Systems Analysis. 2018. No. 54. P. 585–593. https://doi.org/10.1007/s10559-018-0059-3.

 

Поступила в редакцию 11 февраля 2020 г.