Архив статей журнала

КОМБИНИРОВАННЫЙ ПОИСК ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДВУМЕРНОЙ УПАКОВКИ ГЕОМЕТРИЧЕСКИХ ФИГУР СЛОЖНЫХ ФОРМ (2024)
Выпуск: № 3 (2024)
Авторы: Курейчик Владимир Викторович, Халенков Александр Юрьевич

ассмотрена задача двумерной упаковки геометрических фигур сложных форм. Задачи данного класса отнесены к классу NP-трудных проблем комбинаторной оптимизации. Помимо этого, упаковка фигур сложных геометрических форм, является одним из наиболее сложных подтипов задачи двумерной упаковки. В связи с этим необходима разработка эффективных эвристических подходов к решению данной задачи. В статье дана постановка задачи, описаны ее основные особенности, приведены ограничения и условия характерные для данного подтипа задачи двумерной упаковки. Описан критерий для подсчета эффективности решения. Для решения данной задачи в статье предлагается архитектура комбинированного поиска, состоящая из двух метаэвристических вычислительных алгоритмов. В данной архитектуре в качестве оптимизационных методов были реализованы модифицированный генетический и роевой мультиагентный биоинспирированный алгоритм, основанный на поведении пчелиной колонии. Данные алгоритмы позволяют получать наборы квазиоптимальных решений за полиномиальное время. Приведены преимущества от использования предлагаемого подхода. Для проверки эффективности предложенного подхода был разработан программный продукт, который использует предложенную архитектуру и метаэвристические вычислительные алгоритмы при решении поставленной задачи. Разработка программного продукта велась на языке программирования C++ и написана в среде разработки Microsoft Visual Studio Code. Проведен вычислительный эксперимент на наборе тестовых примеров-бенчмарок. По результатам экспериментальных исследований сделан вывод об эффективности предложенного комбинированного поиска при решении задачи двумерной упаковки геометрических фигур сложных форм в сравнении с решениями, базирующимися на классических алгоритмах.

Сохранить в закладках