Розробка математичної моделі і методу розв’язання задачі оптимізації упаковки еліпсоїдів в опуклий контейнер
DOI:
https://doi.org/10.15587/1729-4061.2018.140722Ключові слова:
оптимальна упаковка, еліпсоїди, опуклий контейнер, метод phi-функції, моделювання відношень розміщення, нелінійна оптимізаціяАнотація
У даній роботі розглядається задача оптимальної упаковки заданого набору еліпсоїдів у опуклому контейнері мінімального об’єму. Еліпсоїди задані розмірами напівосей і параметрами розміщення у локальній системі координат та допускають неперервні обертання і трансляції. У якості контейнера може виступати кубоїд (прямокутний паралелепіпед), циліндр, куля, еліпсоїд або опуклий багатогранник. Для аналітичного опису відношень неперетену еліпсоїдів застосовуються квазі-phi-функції. Для моделювання відношень включення використовуються квазі-phi-функції або phi-функції залежно від форми контейнеру. Використовуючи відповідні засоби моделювання будується математична модель у вигляді задачі нелінійного програмування.
Розроблено стратегію розв’язання, в основі якої лежить метод мультистарту. Пропонується швидкий алгоритм генерації початкових точок з області допустимих розв’язків та спеціальна оптимізаційна процедура, що зводить початкову задачу великої розмірності O(n2) зі великою кількістю нелінійних нерівностей до послідовності підзадач нелінійного програмування з меншою розмірністю O(n) та з меншою кількістю нелінійних нерівностей.
Оптимізаційна процедура дозволяє значно зменшити (від 10 % до 90 % в залежності від розмірності задачі) обчислювальні ресурси, такі як час та пам’ять. В залежності від форми контейнера, обмежень на орієнтацію еліпсоїдів (можливість безперервних поворотів, фіксована орієнтація) та особливостей метричних характеристик еліпсоїдів в результаті розв’язання задачі отримані локально-оптимальні або гарні допустимі розв’язки. В роботі проведені чисельні експерименти для різних форм контейнерів (включаючи циліндр, кубоїд, кулю, еліпсоїд)Посилання
- Chazelle, B., Edelsbrunner, H., Guibas, L. J. (1989). The complexity of cutting complexes. Discrete & Computational Geometry, 4 (2), 139–181. doi: https://doi.org/10.1007/bf02187720
- Choi, Y.-K., Chang, J.-W., Wang, W., Kim, M.-S., Elber, G. (2009). Continuous Collision Detection for Ellipsoids. IEEE Transactions on Visualization and Computer Graphics, 15 (2), 311–325. doi: https://doi.org/10.1109/tvcg.2008.80
- Uhler, C., Wright, S. J. (2013). Packing Ellipsoids with Overlap. SIAM Review, 55 (4), 671–706. doi: https://doi.org/10.1137/120872309
- Donev, A. (2004). Improving the Density of Jammed Disordered Packings Using Ellipsoids. Science, 303 (5660), 990–993. doi: https://doi.org/10.1126/science.1093010
- Bezrukov, A., Stoyan, D. (2006). Simulation and Statistical Analysis of Random Packings of Ellipsoids. Particle & Particle Systems Characterization, 23 (5), 388–398. doi: https://doi.org/10.1002/ppsc.200600974
- Man, W., Donev, A., Stillinger, F. H., Sullivan, M. T., Russel, W. B., Heeger, D. et. al. (2005). Experiments on Random Packings of Ellipsoids. Physical Review Letters, 94 (19). doi: https://doi.org/10.1103/physrevlett.94.198001
- Kallrath, J. (2015). Packing ellipsoids into volume-minimizing rectangular boxes. Journal of Global Optimization, 67 (1-2), 151–185. doi: https://doi.org/10.1007/s10898-015-0348-6
- Birgin, E. G., Lobato, R. D., Martínez, J. M. (2015). Packing ellipsoids by nonlinear optimization. Journal of Global Optimization, 65 (4), 709–743. doi: https://doi.org/10.1007/s10898-015-0395-z
- Stoyan, Y., Romanova, T. (2012). Mathematical Models of Placement Optimisation: Two- and Three-Dimensional Problems and Applications. Modeling and Optimization in Space Engineering, 363–388. doi: https://doi.org/10.1007/978-1-4614-4469-5_15
- Stoyan, Y., Romanova, T., Pankratov, A., Chugay, A. (2015). Optimized Object Packings Using Quasi-Phi-Functions. Springer Optimization and Its Applications, 265–293. doi: https://doi.org/10.1007/978-3-319-18899-7_13
- Stoyan, Y. G., Patsuk, V. M. (2014). Covering a convex 3D polytope by a minimal number of congruent spheres. International Journal of Computer Mathematics, 91 (9), 2010–2020. doi: https://doi.org/10.1080/00207160.2013.865726
- Romanova, T., Bennell, J., Stoyan, Y., Pankratov, A. (2018). Packing of concave polyhedra with continuous rotations using nonlinear optimisation. European Journal of Operational Research, 268 (1), 37–53. doi: https://doi.org/10.1016/j.ejor.2018.01.025
- Ipopt home page. Available at: https://projects.coin-or.org/Ipopt
- Wolfram Language & System Documentation Center. Available at: http://reference.wolfram.com/language/ref/FindArgMin.html
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2018 Olha Khlud, Olexander Pankratov, Olexander Pankratov, Tetyana Romanova, Tetyana Romanova
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
