Способы конструирования алгоритмов геометрического размещения

Анна Сергеевна Филиппова, Элина Ильдаровна Дяминова

Аннотация


Рассматриваются подходы и методики разработки алгоритмов решения оптимизационных задач геометрического размещения. Большинство проблем подобного рода относятся к классу задач раскроя-упаковки и имеет не полиномиальную сложность. В статье дан обзор технологий разработки новых алгоритмов, таких как: послойная, уровневая, безуровневая, блочная, матричная технологии, а также технология на основе специальных геометрических структур. Приведены примеры. Предложены алгоритмы локального поиска оптимума на основе блочной и матричной технологии. Рассмотрен вариант развития матричной технологии – использование для решения задачи размещения многоугольных ортогональных фигур внутри сложной области

Ключевые слова


задача геометрического размещения; послойная технология; уровневая технология; безуровневая технология; блочная технология; матричная технология; многосвязный ортогональный полигон; размещение многоугольных объектов

Полный текст:

PDF

Литература


Стоян Ю. Г. Математические модели и оптимизаци-онные методы геометрического проектирования. Киев: Наукова думка, 1986. [ Y. G. Stoyan, Mathematical models and optimization methods of geometric planning, (in Russian). Kiev: Naukova Dumka, 1986. ]

Забелин С. Л., Фроловский В. Д. Разработка и иссле-дование моделей, методов и алгоритмов для синтеза и анализа решений задач геометрического покрытия // Вестник Сиб-ГУТИ. 2013. № 2. С. 42–53. [ S. L. Zabelin, V. D. Frolovsky, “The models, methods and algorithms of ge-ometrical covering problems solutions synthesis and analysis elaboration and research,” (in Russian), in Vestnik Sib-GUTI, no. 2, pp. 42-53, 2013. ]

Filippova A. S., Valiakhmetova J. I. Optimal use of re-sources: cutting-packing problem // Advances in Economics and Optimization: Collected Scientific Studies Dedicated to the Memory of L. V. Kantorovich. NY, United States of America, 2014. P. 435–487. [ A. S. Filippova, J. I. Valiakhmetova, “Optimal use of resources: cutting-packing problem,” (in English), in Advances in Economics and Optimization: Collected Scientific Studies Dedicated to the Memory of L. V. Kantorovich. NY, United States of America, pp. 435-487, 2014. ]

Филиппова А. С., Дяминова Э. И. Технологии разра-ботки алгоритмов геометрического размещения // Infor-mation Technologies for Intelligent Decision Making Support (ITIDS'2016) Proc. of the 4th International Conference. 2016. P. 219–223. [ A. S. Filippova, E. I. Dyaminova, “The technolo-gies of geometric placing algorithms development,” (in Rus-sian), in Information Technologies for Intelligent Decision Making Support (ITIDS'2016) Proc. of the 4th International Conference, 2016, pp. 219-223. ]

Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangular Modules // Comput. Aeded Design. 1976. No. 8(1). P. 27–33. [ A. Adamovicn, A. Albano, “Nesting two-dimensional shapes in rectangular Modules,” in Comput. Aeded Design, no. 8(1), pp. 27–33, 1976. ]

Lodi A., Martello S., Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing prob-lems Algorithms // INFORMS J. Comput. 1999. No. 11. P. 345–357. [ A. Lodi, S. Martello, D. Vigo, “ Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems Algorithms,” in INFORMS J. Comput, no. 11, pp. 345-357, 1999. ]

Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces // European Journal of Operation Research. 2006. No. 172(3). P. 814–837. [ A. Bortfeldt, “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces,” in European Journal of Operation Research, no. 172(3), pp. 814–837, 2006. ]

Baker B. S., Goffman Jr. E. G., Riverst R. L. Orthogonal packing in two dimensions // SIAM J. Comput. 1980. P. 846–855. [ B. S. Baker, Jr. E. G. Goffman, R. L. Riverst, “Orthogonal packing in two dimensions,” in SIAM J. Comput, no. 9, pp. 846-855, 1980. ]

Мухачева А. С. Технология блочных структур ло-кального поиска оптимума в задачах прямоугольной упа-ковки // Информационные технологии. Новые технологии, 2004. № 5. С. 19–31. [ A. S. Mukhacheva, “The block structure technology of local optimum search in 2D packing problems,” (in Russian), in Information Technologies, no. 5, pp. 19-31, 2004. ]

Хасанова Э. И., Филиппова А. С. Задача размеще-ния геометрических объектов на многосвязном ортого-нальном полигоне // Математическое программирование и приложения: матер. Всеросс. конф. Екатеринбург: УрО РАН, 2011. №12. С. 215 [ E. I. Hasanova, A. S. Filippova, “The problem of placing geometric objects in a multi-coherent orthogonal polygon,” (in Russian), in Matematicheskoye pro-grammirovaniye i prilozheniya: Proc. Workshop, Ekaterinburg, no. 12, p. 215 ]

Мухачева Э. А., Валиахметова Ю. И., Хасано-ва Э. И., Телицкий С. В. Проектирование размещения ор-тогональных объектов на полигонах с препятствиями // Информационные технологии. 2010. №10. С. 16–22. [ E. A. Mukhacheva, J. I. Valiakhmetova, E. I. Hasanova, S. V. Telitsky, “The placing of orthogonal objects in polygon with barriers projection,” (in Russian), in Informacionnie tehnologii, no. 10, pp. 16-22, 2010. ]

Филиппова А. С., Валиахметова Ю. И., Хасано-ва Э. И. Многокритериальная оптимизация: комплексная задача геометрического покрытия и раскроя // Приклад-ная математика и фундаментальная информатика: еже-годный научный журнал. Омск: изд-во ОмГТУ, 2014. №1. С. 112–115. [ A. S. Filippova, E. I. Hasanova, J. I. Valiakhmetova, “Multicriteria optimization: the complex problem of geometric covering and cutting,” (in Russian), in Prikladnaya matematika i fundamentalnaya informatika: Annual Scientific Journal, Omsk, no. 1, pp. 112-115, 2014. ]

Романова Т. Е., Кривуля А. В., Злотник М. В. Транс-ляционное покрытие // Reports of the National Academy of Science of Ukraine, 2008. No. 7. P. 48–53. [ T. E. Romanova, A. V. Krivulya, M. V. Zlotnik, “Translational covering,” (in Rus-sian), in Reports of the National Academy of Science of Ukraine, no. 7, pp. 48-53, 2008. ]

Дяминова Э. И., Хасанов Р. И., Филиппова А. С. Матричная модель представления данных в автоматизи-рованных системах оптимального размещения ортого-нальных объектов // Оптимизация и моделирование в автоматизированных системах: материалы Всерос. моло-дежной научной школы. Воронеж: ФГБОУ ВО «Воронеж-ский государственный технический университет», 2017. Ч. 1. С. 37–43. [ E. I. Dyaminova, R. I. Hasanov, A. S. Filippova, “Data presentation matrix model in automated systems of orthogonal objects optimal placing,” (in Russian), in Optimiza-cia i modelirovanie v avtomatizirovannih sistemah: Proc. Workshop, Voronezh, 2017, vol. 1, pp. 37-43. ]

Использование эвристик для поддержки принятия решений при размещении геометрических объектов в многосвязный ортогональный полигон / А. С. Филиппова [и др.] // Труды VII Всероссийской научной конференции «Информационные технологии интеллектуальной под-держки принятия решений», (Уфа-Ставрополь-Ханты-Мансийск, Май 28-30). 2019. Т. 1. С. 131–142. [ A. S. Filippova, et al. “Using heuristics for decision support when placing geometric objects in a multi-coherent orthogo-nal polygon,” (in Russian), in Proc. 7th Workshop on Infor-mation Technologies for Information Technologies for Intelli-gent Decision Making Support (ITIDS’2019), 2019, vol. 1, pp. 131-142. ]

Stoyan Y. G., Patsuk V. M. Covering polygonal set by identical circles // Computational Optimization and Applica-tions. Vol. 46, Issue 1. P. 75–92. [ Y. G. Stoyan, V. M. Patsuk, “Covering polygonal set by identical circles,” in Computational Optimization and Applications, vol. 46, issue 1, pp. 75-92. ]

Стоян Ю. Г., Пацук В. Н. Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров // Reports of the National Academy of Science of Ukraine. 2009. No. 5. P. 41–45. [ Y. G. Stoyan, V. M. Patsuk, “The method of covering a convex polyhedral set with a minimum number of identical orbs,” (in Russian), in Reports of the National Academy of Science of Ukraine, no. 5, pp. 41-45, 2009. ]

Картак В. М., Фабарисова А. И. Методы целочис-ленного линейного программирования в задаче опти-мального размещения полиминообразных фигур // При-кладная математика и фундаментальная информатика: Сб. науч. тр. Омск: изд-во ОмГТУ, 2015. №2. С. 76–81. [ V. M. Kartak, A. I. Fabarisova, “Integer linear programming methods in the polymino-shaped figures optimal placing prob-lem,” (in Russian), in Prikladnaya matematika i fundamental-naya informatika: Annual Scientific Journal, Omsk, no. 2, pp. 76-81, 2015. ]


Ссылки

  • На текущий момент ссылки отсутствуют.


(c) 2019 Анна Сергеевна Филиппова, Элина Ильдаровна Дяминова