Одержано 12.12.2023; Виправлено 09.01.2024; Прийнято 19.03.2024

Надруковано 29.03.2024; Вперше Online 31.03.2024

https://doi.org/10.34229/2707-451X.24.1.1

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.85

Пакування м’яких багатокутників у прямокутній області мінімальної висоти

О.П. Мелащенко ¹ ,   Т.Є. Романова ^{2 *} ,   О.В. Панкратов ¹ ,   С.Б. Шеховцов ³ ,   К.Г. Мартінес-Гомес ⁴

¹ Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків

² Університет Лідса, Велика Британія

³ Харківський національний університет радіоелектроніки, Україна

⁴ Університет штату Нуево-Леон (UANL), Мексика

^* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

У роботі досліджено задачу пакування опуклих багатокутників, що мають змінну просторову форму відповідно до коефіцієнту розтягування (м’які багатокутники), в прямокутній області мінімальної висоти. Розміщення об'єктів, що мають змінну просторову форму, використовується, наприклад, у біології, матеріалознавстві, механіці, землевідведенні та логістиці. Інтерес до цих проблем також обумовлений моделюванням структур пористих середовищ під тиском, наприклад, для створення тестових моделей штучних цифрових кернів. Елементи пористих середовищ можуть деформуватися під дією зовнішньої сили, однак маса кожної частинки залишається незмінною. Це відповідає збереженню площі для двовимірного випадку. Багатокутні об’єкти мають бути повністю розміщені у контейнері (обмеження включення) та не перетинатися (обмеження неперетину) за умови їх вільних трансляцій, неперервних обертань, перетвореннях розтягування та збереження їх площі. Для аналітичного опису обмежень розміщення багатокутників змінної форми застосовано метод phi-функцій. Визначено квазі-phi-функції для опису умов неперетину та phi-функції для опису умов включення. Задачу пакування сформульовано у вигляді моделі нелінійного програмування. Запропоновано стратегію, яка складається з наступних етапів: генерація допустимих стартових точок; пошук локальних мінімумів задачі для кожної стартової точки із застосуванням методу декомпозиції; вибір найкращого варіанту. Для пошуку розумних допустимих розміщень застосовано алгоритм оптимізації пакування оригінальних багатокутників з використанням їх гомотетичних перетворень. Основою методу декомпозиції оптимізаційної задачі пакування м’яких багатокутників є ітераційна процедура, яка дозволяє звести задачу великої розмірності до послідовності задач нелінійного програмування значно меншої розмірності (лінійної по відношенню до числа об’єктів). Надано числові приклади для м’яких орієнтованих прямокутників та м’яких неорієнтованих правильних багатокутників.

 

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

 

Цитувати так: Мелащенко О.П., Романова Т.Є., Панкратов О.В., Шеховцов С.Б., Мартінес-Гомес Г. К. Пакування м’яких багатокутників у прямокутній області мінімальної висоти. Cybernetics and Computer Technologies. 2024. 1. С. 5–17. https://doi.org/10.34229/2707-451X.24.1.1

 

Список літератури

           1.     Yagiura M., Umetani S., Imahori S., Hu Y. Cutting and Packing Problems. From the Perspective of Combinatorial Optimization. Tokyo: Springer, 2024. ISBN 978-4-431-55290-1

           2.     Fischer A., Scheithauer G. Cutting and packing problems with placement constraints. Optimized Packings with Applications. Springer Optimization and Applications. 2015. 105. P. 119–156. https://doi.org/10.1007/978-3-319-18899-7_6

           3.     Kallrath J. Cutting & Packing beyond and within Mathematical Programming. Business Optimisation Using Mathematical Programming. 2021. P. 495–526. https://doi.org/10.1007/978-3-030-73237-0_15

           4.     Jiang J., Garikipati K., Rudraraju S. A Diffuse Interface Framework for Modeling the Evolution of Multicell Aggregates as a Soft Packing Problem Driven by the Growth and Division of Cells. Bulletin of Mathematical Biology. 2019. 81. P. 3282–3300. https://doi.org/10.1007/s11538-019-00577-1

           5.     Yuan Q., Li Z., Gao Y., Wang Y.H., Li X. Local responses in 2D assemblies of elliptical rods when subjected to biaxial shearing. Acta Geotechnica. 2019. 14. P. 1685–1697. https://doi.org/10.1007/s11440-019-00844-4

           6.     Chen Y., Yuan M., Wang Z., Zhao Y., Li J., Hu B., Xia C. Structural characterization and statistical properties of jammed soft ellipsoid packing. Soft Matter. 2021. 17. P. 2963. https://doi.org/10.1039/D0SM01699C

           7.     Bui, Q.T., Vidal, T. & Hà, M.H. On three soft rectangle packing problems with guillotine constraints. J Glob Optim. 2019. 74. P. 45–62. https://doi.org/10.1007/s10898-019-00741-w

           8.     Zuo Q. The Three-dimensional Bin Packing Problem for Deformable Items. IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). Kuala Lumpur, Malaysia. 2022. P. 0911-0918. https://doi.org/10.1109/IEEM55944.2022.9989600

           9.     Blunt M.J. Multiphase Flow in Permeable Media: A Pore-Scale Perspective. Cambridge: Cambridge University Press. 2017. https://doi.org/10.1017/9781316145098

       10.     Eichheimer P., Thielmann M., Popov A., Golabek G.J., Fujita W., Kottwitz M.O., Kaus B.J.P. (2019). Pore-scale permeability prediction for Newtonian and non-Newtonian fluids. Solid Earth. 2019. 10 (5). 1717–31. https://doi.org/10.5194/se-10-1717-2019

       11.     Dong X., Liu H., Hou J., Zhang Z., Chen Z. Multi-thermal fluid assisted gravity drainage process: a new improved-oil-recovery technique for thick heavy oil reservoir. J. Petrol. Sci. Eng. 2015. 133. P. 1–11. https://doi.org/10.1016/j.petrol.2015.05.001

       12.     Al-Nakhli A., Tariq Z., Mahmoud M., Abdulraheem A., Al Shehri D. A novel thermochemical fracturing approach to reduce fracturing pressure of high strength rocks. Abu Dhabi Int. Petroleum Exhibition & Conf., SPE-197593- MS. 2019. https://doi.org/10.2118/197593-MS

       13.     Romanova T., Stoyan Yu., Pankratov A., Litvinchev I., Kravchenko O., Duryagina Z., Melashenko O., Chugai A. Optimized packing soft ellipses. Chapter in book Human-Assisted Intelligent Computing. 2023. P. 9.1–9.16. https://doi.org/10.1088/978-0-7503-4801-0ch9

       14.     Torres J., Hitschfeld N., Ruiz R.O., Ortiz-Bernardin A. Convex Polygon Packing Based Meshing Algorithm for Modeling of Rock and Porous Media. Lecture Notes in Computer Science. Springer, Cham. 2020. 12141. https://doi.org/10.1007/978-3-030-50426-7_20

       15.     Burke E., Kendall G. A New Approach to Packing Non-Convex Polygons Using the No Fit Polygon and Meta-Heuristic and Evolutionary Algorithms. Adaptive Computing in Design and Manufacture V. Springer, London. 2002. https://doi.org/10.1007/978-0-85729-345-9_17

       16.     Pankratov A., Romanova T., Shekhovtsov S., Grebennik I., Pankratova J. Packing Irregular Polygons using Quasi Phi-functions. 2020 10th International Conference on Advanced Computer Information Technologies (ACIT). Deggendorf, Germany, 2020. P. 1–5. https://doi.org/10.1109/ACIT49673.2020.9208979

       17.     Peralta J., Andretta M., Oliveira J.F. Solving irregular strip packing problems with free rotations using separation lines. 2017. https://doi.org/10.5220/0006602700710077

       18.     Peralta J., Andretta M., Oliveira J. Packing Circles and Irregular Polygons using Separation Lines. In Proceedings of the 7th International Conference on Operations Research and Enterprise Systems (ICORES 2018). 2018. P. 71–77. https://doi.org/10.5220/0006602700710077

       19.     Kallrath J., Romanova T., Pankratov A., Litvinchev I., Infante L. Packing convex polygons into minimum perimeter convex hulls. Journal of Global Optimization. 2023. 85 (1). P. 39–59. https://doi.org/10.1007/s10898-022-01194-4

       20.     Litvinchev I., Infante L., Romanova T., Martinez-Noa A., Gutierrez L. Optimized packing soft convex polygons. Computer Science and Engineering in Health Services. COMPSE 2022. EAI/Springer Innovations in Communication and Computing. Springer, Cham. 2024. https://doi.org/10.1007/978-3-031-34750-4_7

       21.     Stoyan Yu., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization. 2016. 65 (2). P. 283–307. https://doi.org/10.1007/s10898-015-0331-2

       22.     Romanova T., Stoyan Y., Pankratov A., Litvinchev I. , Marmolejo J.A. Decomposition algorithm for irregular placement problems. In Intelligent Computing and Optimization, AISC. 2019. 1072. P. 214–221. https://doi: doi:10.1007/978-3-030-33585-4_21

       23.     Li J., An X., Wang J., Zhao H., Zou R., Dong K., Gou D. Experimental study on 3D vibrated packing densification of mono-sized dodecahedral particles. Powder Technology. 2020. 367. P. 703–712. https://doi.org/10.1016/j.powtec.2020.04.020

       24.     Romanova T., Bennell J., Stoyan Y., Pankratov A. Packing of concave polyhedra with continuous rotations using nonlinear optimization. European Journal of Operational Research. 2018. 268 (1). P. 37–53. https://doi:10.1016/j.ejor.2018.01.025

       25.     Romanova T., Litvinchev I., Pankratov A. Packing ellipsoids in an optimized cylinder. European Journal of Operational Research. 2020. 285 (2). P. 429–443. https://doi.org/10.1016/j.ejor.2020.01.051

       26.     Leao A.S., Toledo F.M.B., Oliveira J.F., Carravilla M.A., Alvarez-Valdés R. Irregular packing problems: a review of mathematical models. European Journal of Operational Research. 2020. 282. P. 803–822. https://doi.org/10.1016/j.ejor.2019.04.045

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна