В. А. Чеканин
Список книг автора В. А. Чеканин
Разработка алгоритма уплотнения упаковки для повышения эффективности прямоугольного раскроя
Статья содержит описание разработанного итерационного алгоритма уплотнения упаковки, в основе которого лежит идея локального перераспределения размещенных в контейнере объектов. Предложены шесть правил выбора объектов для их удаления из контейнера и последующего более рационального размещения с помощью однопроходного эвристического алгоритма. Приведены результаты тестирования алгоритма уплотнения упаковки на тестовых задачах рулонного раскроя.
Программная реализация эффективной структуры данных для задач ортогональной упаковки различной размерности
В статье рассматривается многоуровневая связная структура данных, обеспечивающая возможность быстрого управления свободными пространствами ортогональных контейнеров в процессе заполнения их объектами. Программная реализация предложенной структуры данных, выполненная инвариантно относительно размерности задачи, делает ее применимой при решении задач прямоугольного раскроя и ортогональной упаковки произвольной размерности. Авторами приведены результаты вычислительного эксперимента на тестовых задачах трехмерной ортогональной упаковки, подтверждающие эффективность применения многоуровневой связной структуры данных. Приведено описание прикладного программного обеспечения, разработанного для решения различных типов задач прямоугольного раскроя и ортогональной упаковки объектов.
Эффективная модель управления объектами в задачах ортогональной упаковки и прямоугольного раскроя
В статье рассматривается новая модель управления объектами в контейнерах, обеспечивающая возможность конструирования ортогональных упаковок произвольной размерности при решении оптимизационных задач ортогональной упаковки и прямоугольного раскроя. Приведены алгоритмы размещения и удаления ортогональных объектов. Показана эффективность применения предложенной модели на тестовых задачах трехмерной ортогональной упаковки.
Оптимизация решения задачи ортогональной упаковки
Рассмотрена задача многомерной ортогональной упаковки объектов в общем виде. Для конструирования ортогональной упаковки объектов произвольной размерности предложена модель «виртуальные объекты». Для оптимизации решения задачи упаковки применяется мультиметодный генетический алгоритм. Предложены новые эвристики размещения объектов. Разработанные алгоритмы реализованы в виде программного модуля, построенного на основе предложенной авторами универсальной библиотеки классов задач упаковки. Представлены результаты вычислительных экспериментов на эталонных задачах двухмерной прямоугольной упаковки.