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



Скачать 30.79 Kb.
Дата17.01.2013
Размер30.79 Kb.
ТипДокументы

УДК 004(06) Информационные технологии


Н.Е. КЛИМЕНКО, М.В. СЕРГИЕВСКИЙ

Московский инженерно-физический институт (государственный университет)
РАЗРАБОТКА АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ПРЯМОУГОЛЬНЫХ ОБЪЕКТОВ В ДВУХМЕРНЫЙ КОНТЕЙНЕР
Предлагаются алгоритмы поиска глобально-оптимального решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер, основанные на эффективном кодировании исходных данных.
Задачи раскроя-упаковки составляют важный прикладной раздел дискретной оптимизации. Среди них выделяется задача ортогональной упаковки прямоугольных объектов в двухмерный контейнер. Актуальность проблемы создания эффективных алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер объясняется как широким практическим применением решения в различных областях, так и трудностью разработки адекватных математических моделей. Сложность решения этой задачи, как и всех других задач раскроя-упаковки, обусловлена их принадлежностью к классу NP-трудных, то есть для таких задач не существует методов, находящих точное решение за полиномиальное время [1].

Предлагаемый метод решения основан на использовании оригинального кодирования – представления заполняемого контейнера в виде числовой матрицы. Контейнер разбивается сеткой с равным шагом на прямоугольные области, каждой из которых ставится в соответствие элемент числовой матрицы. Исследованы два алгоритма, реализующих данный метод.

Первый из них: кодирование размещаемых объектов соответствующими им уникальными номерами в матрице-контейнере. При этом помещение в клетку матрицы некоторого числа интерпретируется как заполнение данного места в контейнере объектом с соответствующим номером. Алгоритм размещения для рассматриваемого представления создаёт все допустимые строки матрицы-контейнера. После чего методом ограниченного перебора из полученных строк составляются матрицы необходимой размерности. Построенная в итоге матрица и является лучшим из всех возможных решений. Возможно так же построение группы из заданного числа лучших решений.

Второй алгоритм основан на представлении контейнера в виде трёхмерной матрицы с булевыми элементами. Тогда каждой переменной соответствуют выделенная клетка плоского контейнера и номер объекта, который ею определяется. То есть по третьему индексу в трёхмерной матрице считается номер рассматриваемого объекта. Тогда появление единицы в некоторой трёхмерной клетке (i,j,k) соответствует заполнению клетки двухмерного контейнера (i,j) k-ым объектом. При указанном кодировании путём типовых преобразований задача сводится к задаче булева программирования в виде, удобном для решения при помощи алгоритма Балаша [2].

Оба предложенных алгоритма направлены на получение глобально- оптимального решения. Потому их работа очень чувствительна к размерности решаемой задачи.
При увеличении размерности время работы алгоритмов растёт экспоненициально, как это и должно быть для NP-трудных задач. На данный момент с помощью первого алгоритма в течение 10 минут решаются задачи с размерностью контейнера 60 х 10 при числе объектов до 32. При этом алгоритм гораздо более чувствителен к ширине, чем к длине контейнера: за тот же интервал времени может быть решена задача для контейнера 100 х 6, но задача 30 х 20 требует большего времени. Так же важным условием является то, что суммарная площадь объектов должна превышать площадь контейнера, так называемое условие избыточности.

Для второго из предложенных подходов на данный момент идет поиск оптимального варианта использования алгоритма Балаша. По своей природе рассматриваемая задача является задачей поиска максимума, и при достижении его лишь малая часть переменных принимает значение 1, что удобно для работы алгоритма Балаша. Использование подходящего для структуры кодирования алгоритма позволяет надеяться на применимость предлагаемого подхода к задачам большой размерности. Кроме того, значительно сократить время работы алгоритма позволяет априорное знание допустимого решения, то есть какого-либо заполнения контейнера.
Список литературы


  1. Валеева А.Ф. Конструктивные методы решения задач ортогональной упаковки и раскроя: Автореф, дис. ... д-ра техн. наук / Уфимский государственный авиа-тех. университет. Уфа, 2006.

  2. Немировский А.С, Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Радио и связь, 1979.




ISBN 978-5-7262-0883-1. НАУЧНАЯ СЕССИЯ МИФИ-2008. Том 11

Похожие:

Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconРазработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер
Для решения np-трудной задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер предлагается эффективный метод...
Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconРазработка и исследование бионических алгоритмов решения задачи параметрической оптимизации для автоматизации схемотехнического проектирования

Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconСтандартный контейнер, Стандартный сухой контейнер, Dry Container
Стандартный контейнер самый распространенный тип контейнеров. Применяется для перевозки большого ассортимента грузов, пригодных по...
Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconИсследование и разработка бионических методов и алгоритмов для решения задач транспортного типа

Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconРешение задачи маршрутизации на основе нейросетевых и иммунологических алгоритмов
Рассмотрена возможность использования обученного многослойного персептрона для решения задачи маршрутизации
Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconК. А. Кулаков, М. А. Крышень
Целью проекта является разработка алгоритмов генерации тестовых систем оданлду различных классов, разработка web-сервера Web-SynDic...
Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconРазработка алгоритмов поиска и обследования искусственных протяженных объектов с помощью автономного необитаемого подводного аппарата
Специальность: 05. 13. 18 – Математическое моделирование, численные методы и комплексы программ
Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconАнализ параллельных численных методов решения задачи коши для оду и устойчивости алгоритмов

Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconРабочая программа по истории, 7 класс мбоу «Татарско-Кандызская сош»
При выполнении творческих работ формируется умение определять адекватные способы решения учебной задачи на основе заданных алгоритмов,...
Разработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconМетодическое пособие Казань, 2009 г Данное методическое пособие предназначено для студентов, изучающих процесс разработки алгоритмов и программ для решения сложных задач по программированию
Тексты всех задач упрощены и исключены ограничения на память и время. Приведены идеи решения и примеры анализа нескольких конкретных...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org