Layout problems for arc objects in convex domains
Ключевые слова:
задача упаковки, произвольные объекты, непрерывные вращения, допустимые расстояния, phi -функции, генератор пространства решений, нелинейная оптимизацияАннотация
Предлагается новая методология решения оптимизационных задач компоновки произвольных объектов в контейнерах, ограниченных дугами окружностей и отрезками прямых. Допускаются непрерывные трансляции и вращения объектов. Между объектами заданы минимально допустимые расстояния. Для моделирования ограничений непересечения, включения и ограничений на допустимые расстояния используется метод phi-функций. Строится математическая модель в виде задачи нелинейного программирования. Описывается процедура генерации области допустимых решений с применением phi-деревьев, которая позволяет формировать системы неравенств с гладкими функциями. Предлагается эффективный алгоритм поиска локально оптимальных решений. Важной составляющей разработанной оптимизационной процедуры является LORA алгоритм, который сводит задачу нелинейного программирования с большим числом нелинейных неравенств к последовательности NLP-задач с меньшим числом неравенств, что значительно сокращает вычислительные ресурсы для локальной оптимизации. Разработан оригинальный решатель для задач негладкой оптимизации, который использует символьное представление неравенств и обеспечивает точное вычисление элементов матриц Якобиана и Гессиана. Поиск локальных минимумов NLP-задач выполняется с помощью IPOPT. Предлагаемая методология эффективна для решения задач компоновки произвольных объектов и позволяет получать «хорошие» локально оптимальные решения за приемлемое время.
Библиографические ссылки
Wascher, G., Hauner, H., Schuma, H.: An improved typology of cutting and packing problems. European Journal of Operational Research. 183, 1109-1130 (2007).
Gomes, A. M. Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry Volume 11 (2014)| Part 1 (DOI) 10.3182/20130522-3-BR-4036.00113, – P. 378-383.
Chazelle, B., Edelsbrunner, H., Guibas, L.J.: The complexity of cutting complexes. Discrete & Computational Geometry. 4(2), 139–81 (1989).
ennell J.A., Oliveira J.F.: The geometry of packing problems: A tutorial. European Journal of Operational Research. 184:397–415 (2008).
Bennell, J.A., Oliveira J.F, A tutorial in irregular shape packing problem, Journal of the Operational Research Society, 60:s93-s105 (2009).
Blazewicz, J., Drozdowski, M., Soniewicki, B., Walkowiak, R.: Two-dimensional cutting problem basic complexity results and algorithms for irregular shapes. Found. Cont. Eng., 14(4), 137-60 (1989).
Burke E.K. Complete and robust no-fit polygon generation for the irregular stock cutting problem / E.K. Burke, R. S. R. Hellier, G. Kendall, G. Whitwell. EJOR 2007 27-49.
Whitwell G. Novel Heuristic and Metaheuristic Approaches to Cutting and Packing. School of Computer Science and Information Technology. University of Nottingham; 2005, PhD Thesis, 313 p.
Burke, E.K., Hellier, R., Kendall, G., Whitwell, G.: Irregular packing using the line and arc no-fit polygon. Operations Research. 58(4), 948–970 (2010).
Milenkovic, V.: Rotational polygon containment and minimum enclosure using only robust 2d constructions. Computational Geometry. 13(1), 3–19 (1999).
Milenkovic, V.: Rotational polygon overlap minimization and compaction. Computational Geometry. 10(4), 305–318 (1998).
Pedro Rocha, Rui Rodrigues, A. Miguel Gomes, Franklina M.B. Toledo, Marina Andretta Circle/ Covering Representation for Nesting problems with continuous rotations. Preprints of the 19th World Congress, The International Federation of Automatic Control, Cape Town, South Africa. August 24-29, 2014.
Leung, Stephen C.H. Lin, Yangbin Zhang, Defu Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem Computers & Operations Research, v.39, no.3, 2012 March, p.678(9) (ISSN: 0305-0548).
J. Bennell, G. Scheithauer, Yu. Stoyan, and T. Romanova (2010) Tools of mathematical modelling of arbitrary object packing problems// J. Annals of Operations Research, Publisher Springer Netherlands: V 179, Issue 1, pp. 343-368.
Chernov N., Stoyan Y., Romanova T. (2010) Mathematical model and efficient algorithms for object packing problem// Computational Geometry: Theory and Applications, vol. 43:5, pp. 535-553.
Chernov N, Stoyan Y, Romanova T and Pankratov A (2012) Phi-functions for 2D objects formed by line segments and circular arcs. Advances in Operations Research. doi:10.1155/2012/346358.
Bennell J., Scheithauer G., Stoyan Y., Romanova T., and Pankratov A. (2014) Global optimisation"Optimal clustering of a pair of irregular objects" Journal of Global Optimisation, JOGO-D-13-00328R2.
Pankratov A.V., Stoyan Yu. G. Placement of non-convex polygons with rotations into a non-convex polygon// Proc. Workshop Cutting Stock Problems. – 2005. Alutus, Miercurea-Ciuc, Romania. – P. 29-36.
Wachter, A., Biegler, L. T. (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming.106, 1, 25-57.
Yu. Stoyan, A. Pankratov, T. Romanova (2015) Cutting and Packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization. Journal of Operational Research Society, DOI 10.1057/jors.2015.94.
Josef Kallrath and Steffen Rebennack, "Cutting Ellipses from Area-Minimizing Rectangles" Journal of Global Optimisation, (2013), DOI10.1007/s10898-013-0125-3.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2016 А. В. Панкратов, T. Romanova, A. Kotelevskiy
Это произведение доступно по лицензии Creative Commons «Attribution-NoDerivatives» («Атрибуция — Без производных произведений») 4.0 Всемирная.
Авторы, публикующиеся в этом журнале, соглашаются со следующими условиями:
- Авторы оставляют за собой право на авторство своей работы и передают журналу право первой публикации этой работы на условиях лицензионного договора (соглашения).
- Авторы имеют право заключать самостоятельно дополнительные договора (соглашения) о неэксклюзивном распространении работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном хранилище учреждения или публиковать в составе монографии), при условии сохранения ссылки на первую публикацию работы в этом журнале.
- Политика журнала позволяет размещение авторами в сети Интернет (например, в хранилищах учреждения или на персональных веб-сайтах) рукописи работы, как до подачи этой рукописи в редакцию, так и во время ее редакционной обработки, поскольку это способствует возникновению продуктивной научной дискуссии и позитивно отражается на оперативности и динамике цитирования опубликованной работы (см. The Effect of Open Access).
