Задача оптимизації упаковки багатогранників в сферичному та ціліндричному контейнерах

Автор(и)

  • Александр Викторович Панкратов Інститут проблем машинобудування ім. А. М. Підгорного вул. Дм. Пожарського 2/10, м. Харків, Україна, 61046, Україна https://orcid.org/0000-0002-2958-8923
  • Татьяна Евгеньевна Романова Інститут проблем машинобудування ім. А. М. Підгорного вул. Дм. Пожарського, 2/10, м. Харків, Україна, 61046, Україна https://orcid.org/0000-0002-8618-4917
  • Андрей Михайлович Чугай Інститут проблем машинобудування ім. А. М. Подгорного НАН України вул. Пожарського, 2/10, м. Харків, Україна, 61046, Україна https://orcid.org/0000-0002-4079-5632
  • Юрий Евгеньевич Стоян Інститут проблем машинобудування ім. А. М. Подгорного НАН України вул. Пожарського, 2/10, м. Харків, Україна, 61046, Україна https://orcid.org/0000-0001-5234-3986

DOI:

https://doi.org/10.15587/1729-4061.2016.60847

Ключові слова:

упаковка, багатогранники, неперервні обертання, квазі-phi-функція, математична модель, нелінійна оптимізація

Анотація

Розглядається задача оптимальної упаковки неорієнтованих багатогранників у кулі або циліндрі. Будується математична модель у вигляді задачі нелінійного програмування. Пропонується метод розв’язання, що включає швидкий алгоритм побудови допустимих стартових точок і оптимізаційну процедуру, яка скорочує обчислювальні ресурси при пошуку локально-оптимальних рішень.

Біографії авторів

Александр Викторович Панкратов, Інститут проблем машинобудування ім. А. М. Підгорного вул. Дм. Пожарського 2/10, м. Харків, Україна, 61046

Доктор технічних наук, старший науковий співробітник

Відділ математичного моделювання

Татьяна Евгеньевна Романова, Інститут проблем машинобудування ім. А. М. Підгорного вул. Дм. Пожарського, 2/10, м. Харків, Україна, 61046

Доктор технічних наук, професор, провідний науковий співробітник

Відділ математичного моделювання

Андрей Михайлович Чугай, Інститут проблем машинобудування ім. А. М. Подгорного НАН України вул. Пожарського, 2/10, м. Харків, Україна, 61046

Кандидат технічних наук, старший науковий співробітник

Відділ математичного моделювання та обчислювальних методів

Юрий Евгеньевич Стоян, Інститут проблем машинобудування ім. А. М. Подгорного НАН України вул. Пожарського, 2/10, м. Харків, Україна, 61046

Аспірант

Відділ математичного моделювання та обчислювальних методів

Посилання

  1. Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183 (3), 1109–1130. doi: 10.1016/j.ejor.2005.12.047
  2. Chazelle, B., Edelsbrunner, H., Guibas, L. J. (1989). The complexity of cutting complexes. Discrete & Computational Geometry, 4 (2), 139–181. doi: 10.1007/bf02187720
  3. Cagan, J., Shimada, K., Yin, S. (2002). A survey of computational approaches to three-dimensional layout problems. Computer-Aided Design, 34 (8), 597–611. doi: 10.1016/s0010-4485(01)00109-9
  4. Sriramya, P., Varthini, P. B. (2012). A State-of-the-Art Review of Bin Packing Techniques. Eur. J. Scien. Res., 86 (3), 360–364.
  5. Gan, M., Gopinathan, N., Jia, X., Williams, R. A. (2004). Predicting Packing Characteristics of Particles of Arbitrary Shapes. KONA Powder and Particle Journal, 22, 82–93. doi: 10.14356/kona.2004012
  6. Jia, X., Gan, M., Williams, R. A., Rhodes, D. (2007). Validation of a digital packing algorithm in predicting powder packing densities. Powder Technology, 174 (1-2), 10–13. doi: 10.1016/j.powtec.2006.10.013
  7. De Korte, A. C. J., Brouwers, H. J. H. (2013). Random packing of digitized particles. Powder Technology, 233, 319–324. doi: 10.1016/j.powtec.2012.09.015
  8. Li, S. X., Zhao, J. (2009). Sphere assembly model and relaxation algorithm for packing of non-spherical particles. Chin. J. Comp. Phys., 26 (3), 167–173.
  9. Li, S., Zhao, J., Lu, P., Xie, Y. (2010). Maximum packing densities of basic 3D objects. Chinese Science Bulletin, 55 (2), 114–119. doi: 10.1007/s11434-009-0650-0
  10. Aladahalli, C., Cagan, J., Shimada, K. (2007). Objective Function Effect Based Pattern Search—Theoretical Framework Inspired by 3D Component Layout. Journal of Mechanical Design, 129 (3), 243–254. doi: 10.1115/1.2406095
  11. Egeblad, J., Nielsen, B. K., Odgaard, A. (2007). Fast neighborhood search for two- and three-dimensional nesting problems. European Journal of Operational Research, 183 (3), 1249–1266. doi: 10.1016/j.ejor.2005.11.063
  12. Fasano, G. (2007). MIP-based heuristic for non-standard 3D-packing problems. 4OR, 6 (3), 291–310. doi: 10.1007/s10288-007-0049-1
  13. Liu, X., Liu, J.-M., Cao, A.-X., Yao, Z.-L. (2015). HAPE3D – a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology & Electronic Engineering, 16 (5), 380–390. doi: 10.1631/fitee.1400421
  14. Egeblad, J., Nielsen, B. K., Brazil, M. (2009). Translational packing of arbitrary polytopes. Computational Geometry, 42 (4), 269–288. doi: 10.1016/j.comgeo.2008.06.003
  15. Fasano, G. (2012). A global optimization point of view to handle non-standard object packing problems. Journal of Global Optimization, 55 (2), 279–299. doi: 10.1007/s10898-012-9865-8
  16. Stoyan, Y. G., Gil, N. I., Pankratov, A. et al. (2004). Packing Non-Сonvex Polytopes into a Parallelepiped. Technische Universitat Dresden. Available at: http://www.math.tu-dresden.de/~scheith/ABSTRACTS/PREPRINTS/04-non-conv.pdf
  17. Chernov, N., Stoyan, Y., Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry, 43 (5), 535–553. doi: 10.1016/j.comgeo.2009.12.003
  18. Stoyan, Y. G., Chugay, A. M. (2012). Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetics and Systems Analysis, 48 (6), 837–845. doi: 10.1007/s10559-012-9463-2
  19. Stoyan, Yu., Chugay, A. (2011). Construction of radical free phi-functions for spheres and non-oriented polytopes. Rep. of NAS of Ukraine, 12, 35–40.
  20. Stoyan, Y., Pankratov, A., Romanova, T. (2015). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, 1–25. doi: 10.1007/s10898-015-0331-2
  21. Fischer, K., Gärtner, B., Kutz, M. (2003). Fast Smallest-Enclosing-Ball Computation in High Dimensions. Proc. 11th European Symposium on Algorithms (ESA), 630–641. doi: 10.1007/978-3-540-39658-1_57
  22. Belov, G. (2002). A Modified Algorithm for Convex Decomposition of 3D Polyhedra,” Technical report MATH-NM-03-2002, Institut für Numerische Mathematik, Technische Universität, Dresden. Available at: http://www.math.tudresden.de/~belov/cd3/cd3.ps
  23. Wächter, A., Biegler, L. T. (2005). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106 (1), 25–57. doi: 10.1007/s10107-004-0559-y

##submission.downloads##

Опубліковано

2016-02-27

Як цитувати

Панкратов, А. В., Романова, Т. Е., Чугай, А. М., & Стоян, Ю. Е. (2016). Задача оптимизації упаковки багатогранників в сферичному та ціліндричному контейнерах. Eastern-European Journal of Enterprise Technologies, 1(4(79), 39–47. https://doi.org/10.15587/1729-4061.2016.60847

Номер

Том 1 № 4(79) (2016): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2016 Александр Викторович Панкратов, Татьяна Евгеньевна Романова, Андрей Михайлович Чугай, Юрий Евгеньевич Стоян

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.