Optimal packing of convex polytopes using quasi-phi-functions

Авторы

  • A. V. Pankratov Институт проблем машиностроения им А. Н. Подгорного НАН Украины, Ukraine
  • T. E. Romanova Институт проблем машиностроения им А. Н. Подгорного НАН Украины, Ukraine
  • A. M. Chugay Институт проблем машиностроения им А. Н. Подгорного НАН Украины, Ukraine

Ключевые слова:

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

Аннотация

Рассматривается задача упаковки выпуклых многоранников в прямоугольном контейнере минимального объема. Допускаются непрерывные трансляции и повороты многогранников. Учитываются минимально допустимые расстояния, заданные между многогранниками. Для формализвации ограничений размещения применяются свободные от радикалов квази-phi-функции и псевдонормализованные квази-phi-функции. Использование квази-phi-функций, вместо phi-функций, позволяет упростить вид ограничений непересечения многогранников и описать в аналитическом виде ограничения на минимально допустимые расстояния, заданные между многогранниками. Однако процесс оптимизации требует большего числа параметров, включая дополнительные переменные для квази-phi-функций. Строится математическая модель в виде задачи нелинейного программирования. Предлагается эффективный метод решения, включающий: алгоритм, основанный на гомотетических преобразованиях геометрических объектов для построения допустимых стартовых точек, и процедура локальной оптимизации, которая позволила значительно уменьшить размерность задачи, а также сократить вычислительные ресурсы (время и память). Приводятся результаты численных экспериментов, которые демонстрируют эффективность предложенной методологии решения задачи упаковки выпуклых многогранников.

Биографии авторов

A. V. Pankratov, Институт проблем машиностроения им А. Н. Подгорного НАН Украины

доктор технических наук

T. E. Romanova, Институт проблем машиностроения им А. Н. Подгорного НАН Украины

доктор технических наук

A. M. Chugay, Институт проблем машиностроения им А. Н. Подгорного НАН Украины

кандидат технических наук

Библиографические ссылки

Wаscher, G., Hauner, H., Schumann, H. (2007).”An improved typology of cutting and packing problems”. Eur. J. Oper. Res. 183(3,16): 1109–1130.

Chazelle, B., Edelsbrunner, H., Guibas, L.J. (1989). “The complexity of cutting complexes.” Discr. & Comput. Geom. 4(2): 139–81.

Aladahalli, C., Cagan, J., Shimada, K. (2007). “Objective function effect based pattern search – theoretical framework inspired by 3D component layout.” J. Mech. Design. 129: 243–254.

Cagan, J., Shimada, K., Yin, S. (2002). “A survey of computational approaches to three-dimensional layout problems.” Comp.-Aided Des. 34: 597–611.

Egeblad, J. (2008). “Heuristics for multidimensional packing problems.” PhD Thesis.

Egeblad, J., Nielsen, B.K., Odgaard, A. (2007). “Fast neighborhood search for two- and three-dimensional nesting problems.” Eur. J. Oper. Res. 183(3):1249–1266.

Fasano, G. (2008). “MIP-based heuristic for non-standard 3D-packing problems.” 4OR: Quart. J. Belgian, French and Italian Oper. Res. Soc. 6(3): 291–310.

Gan, M., Gopinathan, N., Jia, X., Williams, R.A. (2004). “Predicting Packing Characteristics of Particles of Arbitrary Shapes.” KONA, 22: 82–93.

Jia, X., Gan, M., Williams, R.A., Rhodes, D. (2007). “Validation of a digital packing algorithm in predicting powder packing densities.” Powder Tech. 174: 10–13.

Korte, A.C.J, Brouwers H.J.H. (2013). “Random packing of digitized particles.” Powder Techn. 233: 319–324.

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.

Li, S.X., Zhao, J., Lu, P., Xie, Y. (2010). “Maximum packing densities of basic 3D objects.” Chin. Scien. Bull. 55(2): 114–119.

Sriramya, P., Varthini, P.B. (2012). “A State-of-the -Art Review of Bin Packing Techniques.” Eur. J. Scien. Res. 86(3): 360–364.

Birgin, E.G., Martinez, J.M., Nishihara, F.H., Ronconi, D.P. (2006). “Orthogonal packing of rectagular items within arbitrary convex regions by nonlinear optimization.” Comput. Oper. Res. 33: 3535–3548.

Birgin, E., Martínez, J., Ronconi, D. (2005). “Optimizing the packing of cylinders into a rectangular container: A nonlinear approach.” Eur. J. of Oper. Res. 160 (1): 19–33.

Egeblad, J., Nielsen, B.K., Brazil, M. (2009). “Translational packing of arbitrary polytopes.” http://www.sciencedirect.com/science/journal/09257721">Comp. Geom.http://www.sciencedirect.com/science/journal/09257721/42/4"> 42(4): 269–288.

Fasano, G. A. (2013). “Global Optimization point of view for non-standard packing problems.” J. Glob. Optim. 55(2): 279–299.

Petrov, M.S., Gaidukov, V.V., Kadushnikov, R.M. (2004). ”Numerical method for modelling the microstructure of granular materials.” Powder Metall. and Metal Ceram. 43 (7-8): 330–335.

Torquato, S., Jiao, Y. (2009). “Dense polyhedral packings: Platonic and Archimedean solids.” Phys. Rev. 80: 041104.

Y. Stoyan, N. Gil, G. Scheithauer, A. Pankratov, I. Magdalina (2005). “Packing of convex polytopes into a parallelepiped.” Optimization. 54(2): 215 – 235.

Chernov, N., Stoyan, Y., Romanova, T. (2010). “Mathematical model and efficient algorithms for object packing problem”. Comput. Geom.: Theory and Appl. 43(5): 535–553.

Stoyan, Y., Chugay, А. (2012). “Mathematical modeling of the interaction of non-oriented convex polytopes”. Cyber. and Syst. Anal. 48 (6): 837–845.

StoyanYu., Chugay A. (2011). “Construction of radical free phi-functions for spheres and non-oriented polytopes.” Rep. of NAS of Ukraine. №12: 35-40.

Stoyan Yu,. Pankratov А., Romanova Т., Chernov N. (2014). “Quasi-phi-function for mathematical modelling of geometric objects interactions.” Rep. of NAS of Ukraine 9: 53–57.

Wachter, A., Biegler, L.T. (2006). “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming.” Math. Program. 106 (1): 25–57.

Stoyan, Y., Yaskov, G. (2012). “Packing congruent hyperspheres into a hypersphere” Journal of Global Optimization, 52(4): 855–868 .

Chernov, N., Stoyan, Y., Pankratov, A., Romanova, T. (2014). “Quasi-phi-functions and optimal packing of ellipses.” Subm. to J. of Glob. Optim.

Загрузки

Опубликован

2015-07-14

Выпуск

Том 18 № 2 (2015)

Раздел

Прикладная математика

Лицензия

Copyright (c) 2015 A. V. Pankratov, T. E. Romanova, A. M. Chugay

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NoDerivatives» («Атрибуция — Без производных произведений») 4.0 Всемирная.

Авторы, публикующиеся в этом  журнале, соглашаются со следующими условиями:

  • Авторы оставляют за собой право на авторство своей работы и передают журналу право первой публикации этой работы на условиях лицензионного  договора (соглашения).
  • Авторы имеют право заключать самостоятельно дополнительные договора (соглашения) о неэксклюзивном распространении работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном хранилище учреждения или публиковать в составе монографии), при условии сохранения ссылки на первую публикацию работы в этом журнале.
  • Политика журнала позволяет размещение авторами в сети Интернет (например, в хранилищах учреждения или на персональных веб-сайтах) рукописи работы, как до подачи этой рукописи в редакцию, так и во время ее редакционной обработки, поскольку это способствует возникновению продуктивной научной дискуссии и позитивно отражается на оперативности и динамике цитирования опубликованной работы (см. The Effect of Open Access).