Розробка ефективніх алгоритмів оптимальної упаковки еліпсів
DOI:
https://doi.org/10.15587/1729-4061.2014.28015Ключові слова:
упаковка, еліпси, апроксимація, неперервні обертання, phi-функції, математична модель, нелінійна оптимізаціяАнотація
Розглядається задача упаковки набору еліпсів у контейнер мінімальних розмірів. Допускаються неперервні обертання еліпсів. Для моделювання відношень неперетинання еліпсів та належності еліпса контейнеру використається метод phi-функцій. Будується математична модель у вигляді задачі нелінійної оптимізації. Пропонуються ефективні алгоритми пошуку наближених та локально-оптимальних розв'язків. Наводяться результати чисельних експериментів для прямокутного, кругового, еліптичного контейнера.
Посилання
Toth, L. F. (1986). Packing of ellipses with continuously distributed area. Journal of Discrete Mathematics, Vol. 60, 263–267. doi:10.1016/0012-365X(86)90018-X.
Ting, J. M., Khwaja, M., Meachum, L. R., Rowell, J. D. (1993). An ellipse-based discrete element model for granular materials. Numerical and Analytical Methods in Geomechanics, Vol. 17 (9), 603–623. doi:10.1002/nag.1610170902.
Feng, Y., Han, K., Owen, D. (2002). An Advancing Front Packing of Polygons, Ellipses and Spheres. Discrete Element Methods, 93-98. doi:10.1061/40647(259)17.
Vickers, G. T. (2009). Nested Ellipses. Applied Probability Trust, Vol. 41(3), 131–137.
Xu, W. X., Chen, H. S., Lv, Z. (2011). An overlapping detection algorithm for random sequential packing of elliptical particles. Physica, Vol. 390, 2452–2467. doi:10.1016/j.physa.2011.02.048.Birgin, E. G., Bustamante, L. H., Callisaya, H. F., Martınez, J. M. (2013). Packing circles within ellipses. International transactions in operational research, Vol. 20 (3), 365–389. doi:10.1111/itor.12006.Kallrath, J., Rebennack, S. (2013). Cutting Ellipses from Area-Minimizing Rectangles. Journal of Global Optimization, Vol. 59 (2-3), 405–437. doi:10.1007/s10898-013-0125-3.
Kallrath, J. (2008). Cutting Circles and Polygons from Area-Minimizing Rectangles. Journal of Global Optimization, Vol. 43 (2-3), 299–328. doi:10.1007/s10898-007-9274-6.
Pankratov, A., Romanova, T., Subota, I. (2014). Optimal packing problem of ellipses taking into account minimal allowable distance. Journal of Numerical Mathematics, Vol. 1, 27–42.
Stoyan, Y., Pankratov, A., Romanova, T., Chernov, N. (2014). Quasi-phi-function for the mathematical modeling of geometric objects relationships. Reports of the National Academy of Sciences of Ukraine, Vol. 9, 49–54.
Chernov, N., Stoyan, Y., Romanova, T., Pankratov, A. (2012). Phi-Functions for 2D Objects Formed by Line Segments and Circular Arcs. Advances in Operations Research, 26. doi:10.1155/2012/346358.
Chernov, N, Stoyan, Y, Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications, Vol. 43 (5), 535–553. doi:10.1016/j.comgeo.2009.12.003.
Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T., Pankratov, A. (2014). Optimal clustering of a pair of irregular objects. Journal of Global Optimization. doi:10.1007/s10898-014-0192-0.
Wachter, A., Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, Vol. 106 (1), 25–57. doi:10.1007/s10107-004-0559-y.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2014 Александр Викторович Панкратов, Татьяна Евгеньевна Романова, Ирина Александровна Суббота
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
