УПАКУВАННЯ ОПУКЛИХ ГОМОТЕТИЧНИХ БАГАТОГРАННИКІВ В КУБОЇД

image_print
DOI https://doi.org/10.15407/pmach2018.02.045
Журнал Проблеми машинобудування
Видавець Інститут проблем машинобудування ім. А. М. Підгорного Національної академії наук України
ISSN 0131-2928 (print), 2411-0779 (online)
Випуск Том 21, № 2, 2018 (червень)
Сторінки 45–59

 

Автори

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

А. М. Чугай, Інститут проблем машинобудування ім. А. М. Підгорного НАН України (61046, Україна, м. Харків, вул. Пожарського, 2/10), ORCID: 0000-0002-4079-5632

 

Анотація

У роботі розглядається оптимізаційна задача упакування заданого набору гомотетичних довільно орієнтованих опуклих багатогранників без їх взаємного перетинання у прямому паралелепіпеді мінімального об’єму. Як конструктивні засоби математичного моделювання поставленої задачі пропонується використовувати метод Ф-функції. На основі Ф-функції для двох опуклих неорієнтованих  багатогранників будується математична модель задачі та досліджуються її основні властивості, які впливають на вибір стратегії  розв’язання поставленої задачі. Отримана математична модель подає задачу у вигляді класичної задачі нелінійного програмування, що дозволяє використовувати для пошуку розв’язку сучасні солвери. Пропонуються ефективні методи пошуку  припустимих початкових точок і локально оптимальних розв’язків, що ґрунтуються на гомотетичних перетвореннях. Для пошуку локальних екстремумів сформульованих оптимізаційних задач розроблено спеціальний метод декомпозиції, який дозволяє значно зменшити обчислювальні витрати за рахунок значного зменшення кількості нерівностей. Ключова ідея процедури оптимізації дозволяє генерувати підмножини області припустимих розв’язків на кожному етапі пошуку локального екстремуму. Для пошуку локальних екстремумів використовувались паралельні обчислення, що дозволило скоротити часові витрати.  Наведено числові приклади. Запропоновані в роботі методи можуть бути використані для розв’язання задачі упакування неопуклих багатогранників.

 

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

 

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

 

Література

  1. Petrov M., 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. No. 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. No. 49 (12). P. 1–5. https://doi.org/10.1016/j.ifacol.2016.07.540
  4. Karabulut K., İ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., Du J., Chen G., Yiran Z. Parallel Particle Bee Colony Algorithm Approach to Layout Optimization. Computational and Theoretical Nanoscience. 2016. No. 13 (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. No. 29. P. 396–401.
  8. Birgin E. G., Lobato R. D., Martіnez J. M. Packing ellipsoids by nonlinear optimization. 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. Global Optimization. 2016. No. 65 (2). P. 283–307. https://doi.org/10.1007/s10898-015-0331-2
  10. Fasano G. 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. 2009. No. 42 (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 Joung, Sang Do Noh. Noh Intelligent 3D packing using a grouping algorithm for automotive container engineering. Computational Design and Eng. 2014. No. 1 (2). P. 140–151. https://doi.org/10.7315/JCDE.2014.014
  14. Kallrath J. Packing ellipsoids into volume-minimizing rectangular boxes. Global Optimization. 2016. 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. Article ID 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. 2016. Vol. 1. No. 4 (79). P. 39–47. https://doi.org/10.15587/1729-4061.2016.60847
  18. Stoyan Y., Yaskov G. Packing unequal circles into a strip of minimal length with a jump algorithm Optimization Letters. 2014. No. 8. Iss. 3. P. 949–970. https://doi.org/10.1007/s11590-013-0646-1
  19. 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

 

Надійшла до редакції 17 січня 2018 р.