Упаковка выпуклых гомотетичних многогранников в кубоид
Ключевые слова:
упаковка, гомотетичные многогранники, вращение, оптимизация, Ф-функцииАннотация
В работе рассматривается оптимизационная задача упаковки заданного набора гомотетичних произвольно ориентированных выпуклых многогранников без их взаимного пересечения в прямом параллелепипеде минимального объема. Как конструктивные средства математического моделирования поставленной задачи предлагается использовать метод Ф-функции. На основе Ф-функции для двух выпуклых неориентированных многогранников строится математическая модель задачи, и исследуются ее основные свойства, которые влияют на выбор стратегии решения поставленной задачи. Полученная математическая модель представляет задачу в виде классической задачи нелинейного программирования, что позволяет использовать для поиска решения современные Солверы. Предлагаются методы поиска допустимых начальных точек и локально оптимальных решений, основанные на гомотетичных преобразованиях. Для поиска локальных экстремумов сформулированных оптимизационных задач разработан специальный метод декомпозиции, который позволяет значительно уменьшить вычислительные затраты за счет значительного уменьшения количества неравенств. Ключевая идея процедуры оптимизации позволяет генерировать подмножества области допустимых решений на каждом этапе поиска локального экстремума. Для поиска локальных экстремумов использовались параллельные вычисления, что позволило сократить временные затраты. Приведены числовые примеры. Предложенные в работе методы могут быть использованы для решения задачи упаковки невыпуклых многогранников.Библиографические ссылки
Petrov, M. S., Gaidukov, V. V., Kadushnikov, R. M. (2004). Numerical Method for Modeling the Microstructure of Granular. Materials Powder Metallurgy and Metal Ceramics, No. 43 (7–8), pp. 330–335.
Wang, Y., Lin, C. L., Miller, J. D. (2016). 3D Image Segmentation for Analysis of Multi-Size Particles in a Packed Particle Bed. Powder Technology, No. 301, pp. 160–168.
Verkhoturov, M., Petunin, A., Verkhoturova, G., Danilov, K., Kurennov, D. (2016). The 3D Object Packing Problem into a Parallelepiped Container Based on Discrete-Logical Representation. IFAC-PapersOnLine, No. 49(12), pp. 1–5.
Karabulut, K. A., İnceoğlu, M. (2004). Hybrid Genetic Algorithm for Packing in 3D with Deepest Bottom Left with Fill Method. Advances in Inform. Systems, No. 3261, pp. 441–450.
Cao, P., Fan, Z., Gao, R., Tang, J. (2016). Complex Housing: Modeling and Optimization Using an Improved Multi-Objective Simulated Annealing Algorithm. Proc. ASME, No. 60563, V02BT03A034.
Guangqiang, L. A., Fengqiang, Z., Rubo, Z., Du, Jialu, Chen, G.,Yiran, Z. (2016). Parallel Particle Bee Colony Algorithm Approach to Layout Optimization. J. Computational and Theoretical Nanoscience, No. 13(7), pp. 4151–4157.
Torczon, V., Trosset, M. (1998). From Evolutionary Operation to Parallel Direct Search: Pattern Search Algorithms for Numerical Optimization. Computing Sci. and Statistics, No. 29, pp. 396–401.
Birgin, E. G., Lobato, R. D., Martіnez, J. M. (2016). Packing Ellipsoids by Nonlinear Optimization. J. Global Optimization, No. 65, pp. 709–743.
Stoyan, Y., Pankratov, A., Romanova, T. (2016). Quasi-Phi-Functions and Optimal Packing of Ellipses. J. Global Optimization, No. 65 (2), pp. 283–307.
Fasano, G. A. (2013). Global Optimization Point of View to Handle Non-Standard Object Packing Problems. J. Global Optimization, No. 55(2), pp. 279 –299.
Egeblad, J. Nielsen, B. K.,Brazil, M. (2009). Translational Packing of Arbitrary Polytopes. Computational Geometry: Theory and Appl., No. 42(4), pp. 269–288.
Liu, X., Liu, J., Cao, A.,Yao, Z. (2015). HAPE3D – a New Constructive Algorithm for the 3D Irregular Packing Problem. Frontiers of Information Techn. & ElectronicEng., No. 16(5), pp. 380–390.
Youn-Kyoung, Joung, Sang, Do Noh (2014). Intelligent 3D Packing Using a Grouping Algorithm for Automotive Container Engineering. J. Computational Design andEng., No. 1(2), pp. 140–151.
Kallrath, J. (2016). Packing Ellipsoids into Volume-Minimizing Rectangular Boxes. J. Global Optimization, No. 67 (1–2), pp. 151–185.
Stoyan, Y. G., Chugay, A. M. (2014). Packing Different Cuboids with Rotations and Spheres into a Cuboid. Advances in Decision Sci. Available at https://www.hindawi.com/journals/ads/2014/571743.
Stoyan, Y. G., Semkin, V. V., Chugay, A. M. (2016). Modeling Close Packing of 3D Objects. Cybernetics and Systems Analysis, No. 52(2), pp. 296–304.
Pankratov, O., Romanova T., Stoyan Y., Chuhai, A. (2016). Optimization of Packing Polyhedra in Spherical and Cylindrical Containers. Eastern European J. Enterprise Techn., Vol. 1, No. 4(79), pp. 39–47.
Stoyan, Y., Yaskov, G. (2014). Packing Unequal Circles into a Strip of Minimal Length with a Jump Algorithm. Optimization Letters, No. 8(3), pp. 949–970.
Stoyan, Y. G., Chugay, A.M. (2016). Mathematical Modeling of the Interaction of Non-Oriented Convex Polytopes. Cybernetic Systems Analysis, 2012, No. 48, pp. 837–845.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2018 Yu. G. Stoyan, A. M. Chugay
Это произведение доступно по лицензии Creative Commons «Attribution-NoDerivatives» («Атрибуция — Без производных произведений») 4.0 Всемирная.
Авторы, публикующиеся в этом журнале, соглашаются со следующими условиями:
- Авторы оставляют за собой право на авторство своей работы и передают журналу право первой публикации этой работы на условиях лицензионного договора (соглашения).
- Авторы имеют право заключать самостоятельно дополнительные договора (соглашения) о неэксклюзивном распространении работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном хранилище учреждения или публиковать в составе монографии), при условии сохранения ссылки на первую публикацию работы в этом журнале.
- Политика журнала позволяет размещение авторами в сети Интернет (например, в хранилищах учреждения или на персональных веб-сайтах) рукописи работы, как до подачи этой рукописи в редакцию, так и во время ее редакционной обработки, поскольку это способствует возникновению продуктивной научной дискуссии и позитивно отражается на оперативности и динамике цитирования опубликованной работы (см. The Effect of Open Access).
