На правах рукописи

ВАЛИАХМЕТОВА Юлия Ильясовна

МУЛЬТИМЕТОДНАЯ ТЕХНОЛОГИЯ

МОДЕЛИРОВАНИЯ ОРТОГОНАЛЬНОЙ УПАКОВКИ

И РАЗМЕЩЕНИЯ

ПРЯМОУГОЛЬНО-ОРИЕНТИРОВАННЫХ ЗАГОТОВОК

05.13.18 – Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Уфа 2008

Работа выполнена в ГОУ ВПО «Уфимский государственный авиационный технический университет»

на кафедре вычислительной математики и кибернетики и кафедре компьютерной математики

Научный руководитель д-р техн.наук, доц.

Филиппова Анна Сергеевна

Официальные оппоненты д-р техн. наук, профессор Норенков Игорь Петрович д-р физ.-мат. наук, профессор Спивак Семен Израильевич

Ведущая организация ГОУ ВПО «Самарский государственный аэрокосмический университет им. акад. С.П.Королева»

Защита состоится 17 октября 2008 г. в 14.00 часов на заседании диссертационного совета Д-212.288. Уфимского государственного авиационного технического университета по адресу: 450000, Уфа-центр, ул. К. Маркса 12, УГАТУ

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан «»_2008г.

Ученый секретарь диссертационного совета д-р техн. наук, проф. Миронов В.В.

Общая характеристика работы

Актуальность проблемы. Задачи ортогональной упаковки и размещения прямоугольно-ориентированных предметов представляют собой важный прикладной раздел исследования операций, кратко именуемый задачами размещения.

Сложность решения задач размещения обусловлена их принадлежностью к NP-трудным задачам комбинаторной оптимизации. Исследуемые задачи являются NP-трудными в сильном смысле, так как содержат в качестве подзадач также NPтрудные задачи. Во многих случаях применение точных методов для их решения невозможно из-за больших затрат вычислительного времени. В связи с этим большое значение приобретает разработка и исследование эвристических методов оптимизации, в том числе метаэвристик. Важную роль выполняют и способы кодирования и дешифровки упаковок. Однако классические алгоритмы оставляют желать лучших результатов. Интерпретация генов как прямоугольников, а хромосом – как списков, устанавливающих порядок их подачи на упаковку, является эффективной не всегда, о чем свидетельствуют исследования многих ученых (Е.Folkenauer, А.Bortfeldt, И.П.Норенков, Э.А.Мухачева).

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

Размещение прямоугольно-ориентированных заготовок на предприятиях, занимающихся проектированием и изготовлением тары, также на сегодняшний день в большинстве случаев осуществляется вручную, что является малоэффективным и влечет за собой неоправданные расходы материала и временного ресурса. Специфика задачи такова, что адаптация алгоритмов решения прямоугольного раскроя к условиям прямоугольно-ориентированного раскроя представляет собой довольно трудомкий процесс. Также можно говорить и о том, что многие известные алгоритмы, хорошо решающие задачи прямоугольного раскроя, становятся малоэффективными при адаптации их на прямоугольно-ориентированный раскрой.Для задач размещения прямоугольно-ориентированных заготовок и размещения грузов в грузовых отсеках транспортных средств целесообразен полный перебор заготовок на каждом шаге конструирования размещения. Эта процедура выполняется в любом алгоритме мультиметодной технологии.

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

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

Для ее достижения были поставлены и решены следующие задачи:

1. Разработать математические модели задач загрузки транспортного средства и задач размещения прямоугольно-ориентированных заготовок на листах при производстве картонной тары с учетом технологических и организационных ограничений.

2. Разработать мультиметодную технологию моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок.

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

4. Провести численный эксперимент на стандартных тестовых задачах ортогональной упаковки и анализ эффективности разработанных мультиметодных декодеров и алгоритмов.

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

На защиту выносятся:

1. Математические модели задач загрузки транспортного средства и размещения прямоугольно-ориентированных заготовок при производстве тары.

2. Мультиметодная технология моделирования ортогональной упаковки, включающая в себя новые декодеры – мультиметодный декодер (Multi-Method Decoder, MMD) и мультиметодный декодер с либеральными эвристиками (MultiMethod Decoder with Liberal heuristics, MMD(Lib)), и методики дискриминации и форсирования эвристик.

3. Методы и алгоритмы расчета ортогональной упаковки и размещения прямоугольно-ориентированных заготовок с использованием мультиметодной технологии: одноточечный мультиметодный алгоритм (1+1)-МЕА и генетический мультиметодный алгоритм GMA.

4. Анализ результатов численных экспериментов и рекомендации по использованию созданных алгоритмов.

5. Программный продукт, реализующий методы локальной оптимизации и разработанные декодеры в применении к задачам размещения на листы и в полубесконечную полосу.

Научная новизна работы. Новыми в работе являются:

1. Разработана мультиметодная технология моделирования прямоугольной упаковки, отличающаяся от существующих использованием набора простых эвристик в качестве кода упаковки, и являющаяся инструментарием для создания новых и модификации известных алгоритмов с целью повышения их эффективности.

2. Предложен мультиметодный одноточечный эволюционный алгоритм (1+1)-МЕА и расширенная версия генетического алгоритма И.П.Норенкова, которые используют мультиметодную интерпретацию элементов эволюции, что позволяет сократить вычислительное время и добиться лучшего приближения получаемых решений к нижней границе.

3. Предложены новые алгоритмы-декодеры MMD и MMD(Lib), предназначенные для моделирования ортогональной упаковки, отличающиеся от других способом конструирования упаковки - с помощью списка простых эвристик, каждая из которых использует полный перебор для выбора и размещения заготовки.

Включение этих декодеров в общие алгоритмы расширяет область поиска рациональных решений.

4. Модифицированы методы дискриминации с использованием форсирования эвристик для алгоритмов-декодеров, отличающиеся от общепринятых подходов комбинирования эвристик выделением неравновероятных интенсивностей применения отдельных эвристик, что позволило управлять интенсивностью их применения с целью повышения эффективности общего алгоритма.

5. Математическое и программное обеспечение, реализующее работу мультиметодных алгоритмов с возможностью выбора декодеров MMD и MMD(Lib) для решения задач загрузки транспортного средства и задач размещения прямоугольно-ориентированных заготовок при проектировании картонной тары.

Практическая значимость работы: программная реализация эволюционных алгоритмов на основе мультиметодной технологии показала целесообразность ее развития, а также преимущества в сравнении с известными классическими способами применения эвристических методов к задачам размещения на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах. По полученным результатам разработанный алгоритм может быть рекомендован к решению задач прямоугольноориентированного размещения на листовой и рулонный материал с определенным набором диапазонов значений вероятностных показателей для входящих в состав декодера эвристик. Разработанный комплекс внедрен на ряде предприятий, в том числе на ООО «Европак» и ООО «Матрица-Трейд», а также в учебном процессе, в том числе на факультете информатики и робототехники Уфимского государственного авиационного технического университета и в Башкирском государственном аграрном университете.

Апробация работы Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: 13-я Байкальская международная школа-семинар «Методы оптимизации и их приложения» (Иркутск, 2005); Международная уфимская зимняя школа-конференция по математике и физике для студентов, аспирантов и молодых ученых (Уфа, БГУ, 2005); Зимняя школа для аспирантов и молодых ученых (Уфа, УГАТУ, 2006, 2007); 1-я Всероссийская научно-практическая конференция молодых ученых.

Молодые ученые в реализации приоритетного национального проекта «Развитие АПК» (Уфа, 2006); 3-я Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2006); научные семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 10 работ, в том числе 1 статья в рецензируемом журнале из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2008613940 и №2008613941.

Структура и объем работы Диссертация состоит из введения, пяти глав и заключения. Объем работы составляет 176 страниц машинописного текста, включая 25 рисунков, 16 таблиц, и библиографию, содержащую 120 названий.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении к диссертации обоснована актуальность работы; сформулирована цель и задачи исследования; приведены результаты, выносимые на защиту;

отмечена их практическая значимость и научная новизна. Приведены сведения об апробации работы и публикациях.

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

Различают задачи одномерной упаковки (1D Bin Packing, 1DBP) и раскроя (1D Cutting stock, 1DCS), задачи прямоугольной упаковки в полубесконечную полосу (1.5DBP) (термин 1.5D ввел в 1980г. A.Hinxman) и задачи прямоугольной упаковки в листы (2DBP). Задачи упаковки и гильотинного раскроя различаются технологией разрезания материала. Также выделяют задачи упаковки в открытую область (квадрант), задачи трехмерной загрузки контейнеров и задачи о максимальном покрытии. Выделяются в отдельный класс задачи размещения сложных геометрических фигур.

Задачи упаковки (BP) являются типичными представителями NP-трудных проблем и для их решения применяются методы полного перебора с отсечением неперспективных вариантов. Ввиду NP-трудности размерность решаемых задач невелика (200 для 1D и 20 для 1.5D и 2D). Поэтому наряду с точными применяются приближенные и эвристические алгоритмы, в том числе получившие широкое распространение – метаэвристики. Среди последних раньше других получили развитие генетические алгоритмы. Что касается двумерных задач, то эффективность зависит и от организации генетических процедур (кроссовера и мутации), а также от способа кодирования и алгоритма-декодера, с помощью которого происходит конструирование размещения.

Исследуемый в диссертации генетический алгоритм разработан на основе блочных технологий, начало которых получено в работах А.С.Мухачевой. В диссертации разработаны новые декодеры – MMD и MMD(Lib).

Генетические алгоритмы отличаются не только различными декодерами, но и трактовкой основных генетических элементов. Используется идентификация:

ген – блок, хромосома – совокупность блоков. В диссертации используется оригинальная методика, предложенная И.П. Норенковым: ген – метод упаковки очередного предмета.

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

Во второй главе приводятся постановки и математические модели рассматриваемых технических проблем: задачи загрузки транспортного средства и задачи размещения прямоугольно-ориентированных предметов. Они сводятся к модели ортогонального размещения прямоугольников при дополнительных ограничениях. Приводятся формулировки задач ортогональной упаковки в полубесконечную полосу (1.5DBP) и на листы (2DBP). Глава посвящена рассмотрению способов кодирования и декодирования упаковок. Описаны основные принципы генетических и эволюционных алгоритмов, приведены описания общих стратегий работы этих алгоритмов. Приведены описания некоторых алгоритмов-декодеров блочной технологии, а также декодера комбинирования эвристик (Heuristics Combination Decoder, HCD) И.П.Норенкова.

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

В реальных ситуациях представляет интерес технологический раскрой, о котором можно судить по времени технической подготовки, связанной с расчетом рациональных карт раскроя, а также по экономии материальных ресурсов за счет плотного размещения заготовок. На сегодняшний день в России около 30% печатной продукции составляет картонная и бумажная тара для различной продукции. Одним из предприятий, занимающихся изготовлением картонной тары, является ООО «Европак».

Существует множество типов картонной бумаги, которые отличаются между собой толщиной, покрытием и другими характеристиками. На предприятии всегда имеется определенный ассортимент листового и рулонного картона, при этом размеры листов и ширина рулона – стандартные, и их можно найти в соответствующих справочниках. Тип картона определяет величину технических припусков, размеры клапанов и прочие характеристики упаковок.

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

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

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

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

Исходная информация: W, L, m,, n, x, y, w, l, где W – ширина, L – длина листа картона, m – количество заготовок, - вектор флагов разрешения на поворот заготовок на 90, 180, 270 ; n (n1, n2,..., n j,..., nm ), где n j – количество прямоугольников в прямоугольно-ориентированной заготовке с номером угольника с номером k, входящего в заготовку с номером j, k 1, n j, j 1, m ;

при задании входных данных каждая заготовка описывается в своей системе координат; w ( w k ), l (l k ), где ( w k, l k ) – длина и ширина прямоугольника с ноj j jj мером k, входящего в заготовку с номером j, k 1, n j, j 1, m.

Выходная информация: минимальные координаты ( x k, y k ) каждого пряj j моугольника в прямоугольно-ориентированных заготовках в единой системе координат полубесконечной полосы или листа, k 1, n j, j 1, m.

k 1, n j, j 1, m при условиях допустимости упаковки:

1 ортогональное размещение прямоугольников в упаковке: для ( xi, yi ) и неперекрытие заготовок с гранями объектов: для всех i 1, m :

Задача загрузки транспортного средства. Предположим, что условное предприятие путем организации регулярных рейсов осуществляет поставки в Россию крупногабаритных грузов промышленного назначения с нескольких складских центров, расположенных в Европе. Очередной рейс заключается в последовательном прохождении транспортным средством (ТС) задействованных складов для загрузки товаров, последним пунктом является склад разгрузки в г. Москве.

Необходимо составить заказ на доставку рейсом, максимизирующим прибыль, которую получит предприятие от его реализации. Адаптируя данную схему к конкретным условиям, следует отметить, что компания использует однотипные ТС с фиксированными параметрами грузового отсека. Модуль выбора ТС в данном случае является незначимым, его можно исключить из схемы. Работа модуля расчета маршрута будет заключаться только в решении задачи коммивояжера, т.е.

определении порядка прохождения складов, необходимого для соблюдения требования комфортности размещения, и в подсчете затрат, пропорциональных пробегу.

Основным звеном схемы становится модуль размещения. Будем считать, что каждому грузу соответствует прямоугольный контейнер, имеющий длину, ширину и высоту. В силу специфики поставляемых товаров кантовка контейнеров запрещена, т.е. их не разрешается переворачивать и ставить друг на друга. При этом повороты контейнеров в плоскости основания возможны. Высота каждого контейнера не превосходит высоту H грузового отсека ТС. Данные замечания позволяют представлять контейнеры в виде их двумерных проекций на плоскость оснований, грузовой отсек ТС – в виде прямоугольной области, а всю задачу можно свести к двумерной задаче упаковки контейнеров 2DBP [11]. Важной здесь является интерпретация требования комфортности размещения, т.к. мы имеем дело не с последовательной разгрузкой транспортного средства, а с его последовательной дозагрузкой, порядок которой определяется порядком прохождения ТС задействованных складских пунктов.

Исходная информация задается в виде S; s; c, где S – площадь основания грузового отсека ТС, s – вектор площадей оснований контейнеров, с – вектор стоимостей. Исходная информация: W, L, Q, m, w, l, Z, G, g, где W – ширина, L – длина грузового отсека ТС, Q – количество потребителей, m – количество грузов, номером j, входящего в заявку от пункта с номером k, k 1, Q, j 1, mk, ( z k ), j 1, m k, k 1, Q – матрица весов грузов; G – грузоподъемность ТС, ( g k ), k 1, Q, j 1, mk – матрица наименований грузов.

Выходная информация: ( x k, y k ) - минимальные координаты грузов, Требуется минимизировать свободное пространство в грузовом отсеке допустимость упаковки, выполнение (1 ),( 2 ),(3 );

комфортность разгрузки: если порядок обхода клиентов (1,2,3,..., Q), {g1,..., g m } – неупорядоченное множество грузов, предназначенных для досgk k k тавки в пункт с номером k, то порядок загрузки отсека ТС k 1j Под комфортностью разгрузки здесь понимается то, что при загрузке ТС необходимо учитывать, в каком порядке придется выгружать контейнеры. Порядок, в котором контейнеры будут разгружаться, определяется очередностью обхода пунктов разгрузки.

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

Наиболее известным представителем алгоритмов, базирующихся на безуровневой технологии, является декодер «нижний-левый» (Bottom Left, BL).

Уровневые алгоритмы выбирают пакуемые элементы согласно некоторой стратегии, и каждый новый элемент размещается с выравниванием по левому и нижнему краю. Через правую сторону прямоугольника максимальной длины проводят вертикальную линию. Область оказывается разбитой на уровни прямоугольной формы, содержащие целиком все покрывающие их прямоугольники.

Однако при применении уровневых технологий неизбежными оказываются потери за счет введения уровней большой длины. Эта технология, безусловно, удобна для гильотинных раскроев.

Алгоритмы блочной технологии используют декодеры блочной структуры.

Через правую сторону каждого прямоугольника проводят вертикальную линию.

По мере размещения прямоугольников формируют и модифицируют блоки. Совокупность блоков образует вертикальную блок-структуру.

С целью улучшения схем размещения, полученных с помощью алгоритмов, основанных на приведенных технологиях, применяются многопроходные алгоритмы, в том числе метаэвристики.

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

В качестве блока оптимизации в работе используются два алгоритма - генетический алгоритм GMA и одноточечный эволюционный алгоритм (1+1)-MЕА, которые на этапе оценки получаемых решений и построении эскиза размещения используют декодер. Важнейшим моментом, влияющим на эффективность системы упаковки, является внутреннее представление информации или способ кодирования упаковки. В работе предложен новый способ кодирования последовательностью эвристик.

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

Мультиметодная технология (Multi-Method Technology, MMT) позволяет расширить перечень возможных подходов при создании новых декодеров и алгоритмов для решения задач размещения. Мультиметодные декодеры обладают свойством универсальности и могут использоваться любым из алгоритмов, при этом повышая эффективность общего алгоритма.

При создании нового декодера необходимо: 1). Определить набор простых эвристик, с помощью которых будет конструироваться схема размещения. 2). Задать каждой из входящих в декодер эвристик определенное значение вероятности ее использования. Это можно сделать, например, на основе результатов предварительного численного исследования. 3). Рекомендуется применить метод форсирования эвристик, то есть выделить наиболее эффективную эвристику и повысить ее приоритет за Рис. 1 – Размещение компонента в оче- декодера учитывается специфика класса редном участке затрат адаптировать уже имеющийся алгоритм к определенному типу задач путм внедрения в ядро алгоритма мультиметодного декодера. Примером использования MMT при создании алгоритма решения задач размещения стал разработанный мультиметодный эволюционный алгоритм, который создан на базе нового декодера. Разработанные мультиметодные алгоритмы и декодеры могут применяться для решения многих прикладных задач.

Технология ММТ предполагает применение для очередного шага размещения случайных из заданного набора алгоритмов для размещения лучшей детали.

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

Задача разбивается на множество подзадач, последовательное решение которых дает решение исходной задачи. Для решения подзадач формулируется набор альтернативных элементарных эвристик:

S1) выбирается еще не упакованная деталь, обеспечивающая минимальный вертикальный зазор gap 0 ; если gap 0, то деталь размещается вплотную к тому краю участка, на котором меньше (по абсолютной величине) горизонтальный зазор z ; если деталей с gap 0 нет, то участок ширины a и длины h объявляется пустотелым и заполняется фиктивным элементом (рис.1.);

S 2) из неразмещенных деталей с неотрицательным значением вертикального зазора gap выбирается деталь, обеспечивающая минимальный горизонтальный зазор z при исходной ориентации; если таких деталей нет, то делается попытка найти подходящую деталь при повернутой ориентации; в противном случае, если заготовок с gap 0 нет, то участок ширины a и длины h объявляется пустотелым и заполняется фиктивной деталью;

S 3) то же, что и в S 2, но сначала исследуются заготовки повернутыми на S 4) выбирается деталь с наибольшей площадью и с неотрицательным зазором gap.

Полученный конструктивный алгоритм является декодером комбинирования эвристик (Heuristics Combination Decoder, HCD). Задача сводится к поиску и использованию рациональной последовательности эвристик, применяемых в подзадачах. Направленный перебор решений осуществляется с помощью генетического алгоритма. Главная особенность заключается в том, что аллелями служат не значения проектных параметров, а имена эвристик, используемых для определения этих значений: i–й ген соответствует i–й подзадаче, аллелями являются имена эвристик, именно среди них генетический алгоритм и выбирает объекты последовательности, приближаясь к оптимальной перестановке.

Разработан мультиметодный декодер (Multi-Method Decoder, MMD), включенный в среду генетического мультиметодного алгоритма GMA, а затем и в эволюционный одноточечный алгоритм (1+1)-МЕА, и представляющий расширение списка эвристик. Помимо предложенных в оригинальном алгоритме были добавлены следующие:

S 5) выбирается еще не размещенная деталь, обеспечивающая минимальный горизонтальный зазор gapR 0 при повороте на 90 ; если gapR 0, то деталь размещается вплотную к тому краю участка, на котором меньше (по абсолютной величине) вертикальный зазор z ; если деталей с gapR 0 нет, то участок шириной a и высотой h объявляется пустотелым и заполняется фиктивным элементом;

S 6) выбирается деталь с наибольшей площадью и с неотрицательным зазором gap R при повороте на 90 ; если таковых нет среди еще не размещенных деталей, то рассматриваемая область объявляется пустотелой.

Мультиметодный декодер с либеральными эвристиками (Multi-Method Decoder with Liberal heuristics, MMD(Lib)) был разработан на базе декодера MMD.

Этот декодер также получен расширением перечня простых эвристик. При работе он использует уже не только S1 S 6, но еще и набор «либеральных» эвристик:

S1L ) выбирается деталь, обеспечивающая максимальный вертикальный зазор gap 0 ; если gap 0, то деталь размещается вплотную к тому краю участка, на котором больше (по абсолютной величине) горизонтальный зазор z ;

S 2L) из деталей с неотрицательным значением вертикального зазора gap выбирается деталь, обеспечивающая максимальный горизонтальный зазор z при исходной ориентации; если таких деталей нет, то делается попытка найти подходящую деталь при повороте на 90 ;

S 3L) то же, что и в S 2 L, но сначала исследуются заготовки повернутыми на 90 ;

S 4L) выбирается деталь с наименьшей площадью среди еще не размещенных заготовок и с неотрицательным зазором gap ;

S 5L) выбирается деталь, обеспечивающая максимальный вертикальный зазор gapR 0 при повороте на 90 ; если gapR 0, то деталь размещается вплотную к тому краю участка, на котором больше (по абсолютной величине) горизонтальный зазор zR ;

S 6L) выбирается деталь с наименьшей площадью к и с неотрицательным зазором gap R.

Основной идеей, заложенной в описанных эвристиках, является максимизация незаполненного остатка занятой части полосы, т.е. принцип, противоположный «жадности». Введение в рассмотрение такого множества эвристик при конструировании размещений позволяет уменьшить вероятность застревания алгоритма в локальном оптимуме.

Мультиметодный генетический алгоритм GMA построен по принципам описанной технологии. В качестве декодеров могут быть использованы алгоритмы MMD и MMD(Lib), отличающиеся только наборами задействованных простых эвристик.

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

В четвертой главе описывается разработанный программный продукт, а также ряд численных экспериментов, направленных на исследование эффективности предложенных декодеров и алгоритмов для решения задач размещения.

Цель проведенных исследований в следующем: 1). определение рационального набора входных параметров Среднее отклонение от нижней границы (% ) Рис. 2 – Результаты численного эксперимента MMD(Lib) при решении задач размещения на листы и в полосу между собой, а также с другими известными алгоритмами в рамках применения генетического метода; 5). сравнение результатов, полученных декодерами MMD и MMD(Lib) при решении задач размещения на листы и в полосу между собой, а также с другими известными алгоритмами в рамках применения эволюционного одноточечного алгоритма (1+1)-МЕА; 6). определение целесообразности включения в состав декодеров «либеральных» эвристик; 7). определение эффективности метода дискриминации простых эвристик.

Исследование эффективности алгоритмов-декодеров при использовании генетических алгоритмов и алгоритма (1+1)-MЕА. Целью этого численного эксперимента являлось сравнение эффективности генетического мультиметодного алгоритма (GMA) с эволюционным одноточечным алгоритмом с декодером замещения (NS(Sub)) как двух представителей генетических алгоритмов, а также с алгоритмом муравьиной колонии (ACP) и с мультиметодным эволюционным алгоритмом ((1+1)-MЕА). Для тестирования использовались примеры из библиотеки задач OR-Library, предложенные S.Fekete и J.Schepers, для которых известны значения нижних границ. В алгоритме ACP количество итераций – 500, а количество агентов составило 30; количество итераций для алгоритма GMA – 4000. Эти результаты сравнивались с нижней границей ( p ). Показателем эффективности алгоритма служит информация вида N ( S ; t ), где N – полученное число использованных листов, S – номер последней результативной итерации, t – затраты времени (в секундах). Диаграмма, иллюстрирующая среднее отклонение от нижней границы для каждого из алгоритмов, приведена на рис.2.

Результаты проведенного эксперимента показывают эффективность мультиметодного алгоритма для решения задачи размещения прямоугольных объектов на листы. В результате эксперимента следует отметить значительные преимущества (1+1)-МЕА, следующий по результативности – генетический мультиметодный алгоритм GMA. Таким образом, подтверждена эффективность мультиметодного алгоритма для решения задач размещения на листы; при решении задач размещения в полосе на всех классах задач алгоритм GMA работает гораздо эффективнее, если используется декодер MMD.

В пятой главе описаны методика проведения и результаты численных экспериментов, направленных на исследование эффективности методов дискриминации и форсирования эвристик. Цель следующих опытов – определение значений вероятностей для эвристических методик, входящих в состав каждого из декодеров для повышения эффективности алгоритмов. В составе эволюционного одноточечного алгоритма (1+1)-МЕА тестируются декодеры HCD, MMD и MMD(Lib).

Все 500 задач из статей Berkley и Wang, задачи из статей Martello и Vigo (задачи размещения в полубесконечной полосе), а также задачи, предложенные S.P.Fekete и J.Schepers (задачи размещения на листах) были решены каждой из эвристик в отдельности, и для каждой из них было определено значение (относительное отклонение полученного решения от нижней границы) по формуле Вероятность выбора эвристики должна быть обратно пропорциональна величине относительного отклонения, полученного этой эвристикой при решении задач. В то же время все эвристики образуют полную группу несовместных событий. С учетом этих условий по формуле P( Si ) были рассчитаны значения вероятностей.

Эксперимент показал, что с помощью метода дискриминации эвристик удается существенно повысить эффективность общего алгоритма решения задач размещения в полосе декодером MMD. Однако декодер MMD(Lib) при дискриминации эвристик показал результаты, значительно уступающие предыдущим, когда эвристики применялись с одинаковой вероятностью. В связи с этим было решено лишь приблизительно рассчитывать значения вероятностей для определения характера соотношения их величин. Так, например, эвристика S1 в обоих декодерах работает эффективнее остальных. За ней следующая по эффективности – S4, и на третьем месте – S2. Значит, можно искусственно увеличить вероятность появления S1 и соответственно уменьшить вероятность появления остальных эвристик.

Вероятности «либеральных» эвристик можно уменьшить, чтобы снизилось количество ухудшающих решение шагов. Такое «искусственное» завышение вероятности появления для лучшей на данном классе задач эвристики получило название форсирования эвристик.

С целью подбора рационального набора вероятностей была проведена еще одна серия экспериментов. Полученные результаты подтверждают предположение о необходимости форсирования наиболее эффективных эвристических методик за счет уменьшения долей «либеральных» и позволяют рекомендовать к использованию все три декодера с учетом методов дискриминации и форсирования эвристик на следующих классах задач:

Задачи размещения в полубесконечной полосе: при исходных данных задач классов С1 и С2:

МMD(Lib): p( S1) 0.8, p( S 2) 0.042, p( S 4) 0.064, Задачи размещения на листы: при исходных данных задач 2-го и 3-го типов:

MMD(Lib): p( S1) 0.071, p( S 2) 0.069, p( S 4) 0.8, p( S1L) 0.022,

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

Создана мультиметодная технология разработки алгоритмов и повышения их эффективности для решения задач ортогональной упаковки и размещения прямоугольно-ориентированных заготовок:

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

2. Разработана мультиметодная технология (Multi-Method Technology, ММТ) моделирования ортогональной упаковки и размещения прямоугольноориентированных заготовок, основанная на генетическом методе комбинирования эвристик и идеях их ранжирования, отличающаяся от существующих технологий использованием новых способов декодирования с дискриминацией и форсированием. Мультиметодная технология позволяет создавать новые эволюционные алгоритмы решения задач упаковки и размещения.

3. Разработан мультиметодный одноточечный эволюционный алгоритм ((1+1) – Multi-Method Evolution Algorithm, (1+1)-MЕА) и модификация генетического алгоритма - мультиметодный генетический алгоритм (Genetic Multi-method Algorithm, GMA) с мультиметодной интерпретацией элементов эволюции, основанный на использовании новых мультиметодных алгоритмов-декодеров. Их особенностью является представление упаковки в виде последовательности применения эвристик. Для эвристик, входящих в состав декодеров, определены вероятностные параметры и реализованы их дискриминация и форсирование с целью улучшения получаемых решений. Экспериментально подтверждена высокая эффективность алгоритмов при решении задач загрузки транспортных средств и размещения прямоугольно-ориентированных заготовок на листах при проектировании картонной тары, а именно для задачи размещения заготовок на листах мультиметодные методы показывают лучшие результаты в классе примеров «мелкие предметы» и «мелкие и крупные предметы» по сравнению с традиционными методами. Разработанные алгоритмы на основе мультиметодной технологии позволяют при загрузке ТС сократить свободные области в 2 – 3 раза, а при размещении прямоугольно-ориентированных заготовок – в 4 – 5 раз.

4. Поставлена серия численных экспериментов, направленных на определение эффективности разработанных декодеров в составе генетического мультиметодного алгоритма (Genetic Multi-method Algorithm, GMA) и мультиметодного одноточечного эволюционного алгоритма (1+1)-MЕА, а также на сравнение их с другими ранее известными алгоритмами. Результаты численных экспериментов показали, что при использовании разработанных алгоритмов коэффициент использования материала повышается на 5 – 10% по сравнению с традиционными методами, а в сравнении с лучшими современными алгоритмами – на 1,5 – 2,5%.

5. Предложена методика использования мультиметодной технологии для решения задач составления расписания, задач ортогональной трехмерной упаковки, задач фигурного раскроя, задачи покрытия и др. Мультиметодная технология реализована в виде алгоритмов и прикладного программного обеспечения в среде программирования Borland Delphi 7.0. Разработанное программное обеспечение имеет развитый интерфейс и может использоваться как автономно, так и в составе комплексов программ упаковки и размещения. Результаты диссертационной работы приняты к внедрению в виде алгоритмов и программного обеспечения в производственный процесс на ООО«ЕвроПак» и ООО«Матрица-Трейд» (Уфа). В результате внедрения отходы материала при раскрое картона снижены на 14%, а загрузка грузового отсека на 5 – 7% интенсивнее традиционной.

СПИСОК ПУБЛИКАЦИЙ

1. Мультиметодный генетический алгоритм для решения задач ортогональной упаковки. / А.С.Филиппова, Ю.И. Валиахметова // Информационные технологии. 2007. №12. С. 50 – 57.

2. Алгоритмы декодирования прямоугольных упаковок: краткий обзор современных подходов./ Э.А.Мухачева, А.С.Мухачева, Ю.И.Алентьева (Валиахметова) // Методы оптимизации и их приложения. 13-я Байкальская международная школа-семинар : труды шк.-сем.2005. Т.1. Математическое программирование.

С.543 – 549.

3. Декодирование прямоугольных упаковок: основные направления разработки алгоритмов./ Э.А.Мухачева, Ю.И.Алентьева (Валиахметова) // Принятие решений в условиях неопределенности : сб. науч. тр.Уфа: УГАТУ, 2005. С. 76 – 81.

4. Сравнительный анализ алгоритмов упаковки прямоугольноориентированных многоугольников в полубесконечную полосу. / Ю.И.Алентьева (Валиахметова), Л.И.Васильева, Л.М.Карамова // Принятие решений в условиях неопределенности : сб. науч. тр. Уфа: УГАТУ, 2005. С.253 – 5. Эвристический алгоритм для решения задач комбинаторной оптимизации на базе методик И.П.Норенкова. / Ю.И.Алентьева (Валиахметова) // Интеллектуальные системы обработки информации и управления : сб. ст. Рег. зимн. шк.-сем.

аспирантов и молодых ученых, 16 – 19 февраля 2006. Уфа : Технология, 2006. Т.1.

С.253 – 259.

6. Обзор алгоритмов упаковки прямоугольно-ориентированных многоугольников в полубесконечную полосу. / Ю.И.Алентьева (Валиахметова), Л.И.Васильева, Л.М.Карамова // Принятие решений в условиях неопределенности. Уфа : УГАТУ, 2005. Вып. 2, ч.1. С. 88 – 92.

7. Программный продукт для решения задач раскроя-упаковки с применением генетического алгоритма И.П. Норенкова / Ю.И.Алентьева (Валиахметова), В.И.Карамов // Молодые ученые в реализации приоритетного национального проекта «Развитие АПК» : материалы 1-й Всерос. науч.-практ. конф. молодых ученых. Ч. 2. С. 29 – 36.

8. Применение эвристических подходов И.П.Норенкова в составе гибридного алгоритма для решения задач раскроя-упаковки прямоугольных заготовок / Ю.И.Алентьева (Валиахметова) // Проблемы оптимизации и экономические приложения : 3-я Всерос. конф. матер. конф. (Омск, 11 – 15 июля 2006) Омск. филиал Ин-та математики им. С.Л.Соболева СО РАН. Омск : Изд-во ОмГТУ, 2006. С.72.

9. Модификация мультиметодного генетического алгоритма для решения задач ортогональной упаковки. / Ю.И.Алентьева (Валиахметова), Л.И.Васильева // Принятие решений в условиях неопределенности : межвуз. науч. сб. Уфа :

УГАТУ, 2007.С.64 – 72.

10. Мультиметодные алгоритмы в задачах ортогональной упаковки. / Ю.И.Валиахметова, Л.И.Васильева, Л.М.Карамова // Фундаментальная математика и ее приложения в естествознании : сб. тр. Всерос. шк.-конф. для студентов, аспирантов и молодых ученых. Математика.Уфа : РИЦ БашГУ, 2008. Т.2. С.49 – 58.

МУЛЬТИМЕТОДНАЯ ТЕХНОЛОГИЯ

МОДЕЛИРОВАНИЯ ОРТОГОНАЛЬНОЙ УПАКОВКИ

И РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНО-ОРИЕНТИРОВАННЫХ ЗАГОТОВОК

Специальность 05.13.18 - Математическое моделирование,

АВТОРЕФЕРАТ

диссертации на соискание ученой степени Подписано в печать 15.09.08.Формат 60х84 1/16.

Бумага офсетная. Печать плоская. Гарнитура Таймс.

Усл. печ. л. 1,0. Усл.кр.-отт. 1,0. Уч.-изд. л. 0,9.

ГОУ ВПО Уфимский государственный авиационный технический университет