Методологія розв’язання задач пошуку оптимального розміщення тривимірних тіл

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 технології адитивного виробництва, у інформаційно-логістичних системах, що забезпечують оптимізацію перевезення та зберігання вантажів.

 

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

 

Повний текст: завантажити PDF

 

Література

  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/571743https://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 р.

Прийнята до друку