автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Об одном приближении плотной упаковки

Московский государственный университет имени М.В.Ломоносова

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

Псиола Виктор Вадимович

ОБ ОДНОМ ПРИБЛИЖЕНИИ ПЛОТНОЙ УПАКОВКИ

Специальность 05.13.17. — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации гга соискание ученой степени кандидата физико-математических наук

3 НОЯ 2011

Москва — 2011

4858323

4858323

Работа выполнена на кафедре Математической Теории Интеллектуальных Систем Механико-математического факультета Московского государственного университета имени М.В.Ломоносова

Научный руководитель: кандидат физико-математических наук, доцент Строгалов Александр Сергеевич;

Официальные оппоненты:

доктор физико-математических наук, профессор Гашков Сергей Борисович;

доктор физико-математических наук Махортов Сергей Дмитриевич.

Ведущая организация: Московский энергетический институт (технический университет).

Защита диссертации состоится 23 ноября 2011 года в 1645 на заседании диссертационного совета Д.501.002.16 при Московском государственном университете им. М.В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Главное здание, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-маг тематического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 21 октября 2011 г.

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

А.А. Корнев

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

Актуальность темы. Важным направлением современных технологических и бизнес процессов является оптимизация производства. В рамках этого направления существует известный класс оптимизационных задач по упаковке предметов в контейнеры и подборе оптимального числа контейнеров для указанного набора предметов. Такие задачи часто возникают на практике в различных сферах деятельности человека. К их числу относятся, например, оптимизация упаковки груза при транспортировке, раскройки материала, составлении расписания, планировании размещения элементов ira чипе и другие. Содержательно подобные задачи могут быть сформулированы следующим образом: задано конечное множество *предметовобладающих определенными геометрическими свойствами, а так мсе «контейнер» или несколько, также обладающий аналогичными геометрическими свойствами. Требуется найти такую расстановку предметов в контейнере (ах), чтобы их поместилось как можно больше (по объельу) или они заняли минимальное количество контейнеров. В другой постановке эта же задача называется «задачей о раскрое» материала, когда контейнер требуется разрезать на максимальное количество кусков заданной геометрии. В данном случае задача «упаковки» предметов в контейнер и задача его «разрезания» на предметы эквивалентны.

Решение подобных задач востребовано как в одномерном, так и в многомерном пространстве, в частности в 2-х и 3-х мерном. В общем случае задачи укладки многомерных предметов предполагают нахождение расстановки произвольных фигур в контейнер, заданный так же произвольной фигурой. Однако, подобная постановка слишком сложна в формулировке, решении и описании результата. По этой причине наиболее интересной и востребованной на практике является постановка задачи, когда конфигурации предметов и контейнера для укладки являются прямоугольниками в 2-мерном случае и прямоугольными параллелепипедами в 3-мерном. Задачи упаковки и раскроя в такой постановке принято называть «ортогональными», в английской терминологии «Bin Packing Problem» (ВРР) и «Cutting Stock Problem» (CSP). соответственно. Эти задачи и для одномерного и 2- или 3-мерного случаев относятся к классу NP-полных. NP-полнота в одномерной задачи показана в работе известна1, NP-полноту задач в 2- и 3-мерных случаях мож-

1М. Гэри, Д. Джонсон Вычислительные машины и труднорешаемые

но доказать из этого факта.

В настоящее время остается открытым вопрос существования полиномиального алгоритма для решения ОТ-полных задач. Большинство исследователей сходятся во мнении, что такого алгоритма не существует. Это означает, что все известные точные алгоритмы, решающие какую-либо из ИР-полных задач (в частности задачу об упаковке), имеют в общем случае экспоненциальную временную сложность, что эквивалентно полному перебору всех возможных вариантов. Как следствие, уже при относительно небольшом количестве объектов, время работы программ, реализующих такие алгоритмы, будет неприемлемо большим для использования на практике даже при вычислениях на суперкомпьютерах. Более того, увеличение процессорной мощности в будущем в сотни и тысячи раз не позволит существенно ускорить известные алгоритмы переборного типа.

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

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

задачи. М.: Мир, 1982.

2 А. Ф. Валеева Конструктивные методы для решения задач ортогональной упаковки и раскроя. ГОУ ВПО Уфимский государственный авиационный технический университет, Диссертационная работа на соискание ученой степени доктора технических наук, 2006.

ковки, что и является основной целью настоящей работы.

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

• разработать алгоритмы нахождения приближенного решения 2- и 3-х мерной задачи об упаковке предметов, основанные на моделирование эвристических методов принятия решения, используемых человеком;

• дать теоретические и экспериментальные оценки скорости и качества работы алгоритма;

• создать программную реализацию алгоритма и математико-компьютерной модели эвристического принятия решения, архитектура которой допускает высокую степень адаптивности к дополнительным ограничениям на решение задачки;

• внедрить, проверить и проанализировать результаты работы созданной программы на практике в сфере транспортной логистики.

Методологической основой и научно-теоретической базой диссертации являются работы отечественных и зарубежных ученых о методах решения NP-полных задач и других алгоритмах анализа и обработки данных. Исследования в области оптимизации укладки и раскроя в многомерном случае велись и ведутся различными специалистами как в России, так и за рубежом. Еще в 1951 году российские ученые JI.B. Канторович и В.А. Залгал-лер изложили в своей книге «Рациональный раскрой промышленных материалов» подходы к решению задачи раскроя материала в одномерном и 2-мерном случаях с помощью методов линейного программирования. Аналогичные методы получили развитие в 60-е годы за рубежом в работах Р. Gilmore, R. Gomory, а позднее G. Scheithauer, J. Temo и у нас в работах Э.А. Мухачсвой, И.В. Романовского и других. Кроме методов линейного программирования, для нахождения точного решения применяются иногда и комбинаторные методы. В них выделяются подмножества допустимых решений и отсеиваются те, которые пе содержат оптимальных. Такие методы были предложены, например, И.В. Романовским, Н.П. Христовым и СВ. Кацевым.

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

Для решения задач 3-мерной упаковки используются в основном эвристические методы. Большая часть таковых, по мнению D. Pisinger3, базируется на следующих подходах.

• Построения стен/слоев — контейнерное пространство разделяется на вертикальные слои/стены, которые заполняются ящиками автономно. На внутренних этапах этих алгоритмов могут использоваться различные идеи и методы.

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

• Гильотинный разрез — построение дерева, в котором каждая ветвь — часть гильотинного разреза контейнера.

• Построение блоков — рекурсивное заполнение контейнера блоками, состоящими из сходных ящиков.

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

3Pisinger D. Heuristics for the container loading problem. European Journal of Operational Research. 2002. N141. P. 382-392.

слое используются комплексные эвристики, заданные взвешенной суммой различных характеристик объекта выбора. Возможность использования в качестве стратегии выбора не одной определенной эвристики, а нескольких в совокупности рассматривается, например, в работах Норенкова И.П.4 Однако, там применяется вероятностный выбор той или иной стратегии, при этом количество стратегий для выбора очень не велико (четыре). В данной работе предпочтительность использования той или иной стратегией оценивается некоторой числовой характеристикой и выбор осуществляется на основе взвешенной суммы этих характеристик, то есть каждая стратегия вносит свой вклад в каждом случае выбора. При этом количество рассматриваемых стратегий существенно больше (в совокупности - 35).

Научная новизна исследования заключается в следующем.

• Разработаны алгоритмы нахождения приближенного решения 2- и 3-мерных вариантов задач об упаковке, основанные на формализованных мультиэвристиках.

• Доказаны теоретические оценки скорости предложенных алгоритмов и эффективность структуры их структуры для решения поставленных задач.

• Предложены методы их оптимизации с помощью нейронных сетей и генетических алгоритмов.

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

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

4Норспкоа И.П., Косачевский О.Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации. Информационные технологии. 1999. №2. С. 2-8. Норепков И.П. Эвристики и их комбинации в генетических методах. Информационные технологии. 1999. N2 I. С.2-7. 69.

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

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

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

2. Доказательство полиномиальной оценки скорости работы этих алгоритмов.

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

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

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

Внедрение. Созданная программная реализация математико-компыотерной модели, успешно внедрена и эффективно работает на таких крупных предприятиях как «Пивоваренная компания "Балтика"», «Шатура-Мебель» и «Русклимат». Помимо этого она работает в виде общедоступного опКпе-сервиса расчётов на сервере www.packer3d.ru, с помощью которого пользователи осуществляют в среднем по 1000 расчётов в месяц, атак же успешно распространяется в виде «локальной версии» программы расксгЗс!-уегЗ. Интерес, который пользователи проявляют как к программным продуктам,

так и к online-сервису показывает, что разработанный алгоритм и его реализация вполне приемлема и удобна для практического использования. По отзывам и анализу статистики использования можно сделать вывод, что успешное внедрение алгоритма на предприятии позволяет снизить расходы на грузоперевозки до 20%. При этом скорость работы данной реализации алгоритма вполне приемлема при решении задач возникающих на практике. Например, даже с учетом различных дополнительных ограничений, скорость расчёта оптимальной укладки 500 предметов 50 различных типов составляет меньше минуты на компьютере с процессорной мощностью 2 гигагерца.

Эффективность внедрения разработанной программной системы можно оценить, например, по результатам работы в компании «Балтика» эта система осуществляет обязательный предварительный расчёт загрузки продукции в вагоны на девяти заводах компании. Её внедрение привело к увеличению загрузки каждого вагона в среднем на 7%. С учетом объемов грузооборота компании это позволяет экономить на перевозке нескольких вагонов в день, что приводит к существенной оптимизации расходов на грузоперевозки. Помимо прямой экономии внедрение системы дало существенный косвенный положительный эффект — информация о точном заполнении вагона грузом появляется у менеджеров заранее, до поступление вагона на склад и его загрузки. При этом не возникает ситуаций, когда запланированный груз не поместился в вагон. Данный факт позволил существенным образом сократить время простоя вагона на складе, исключив ситуации его перезагрузки.

Апробация работы. Результаты были представлены на механико-математическом факультете МГУ им. М.В. Ломоносова на кафедральном семинаре кафедры МаТИС «Теория автоматов» (рук. проф. В.Б. Кудрявцева) в 2008 году, на семинаре кафедры дискретной математики «Модели и методы дискретной математики» (рук. проф. О.М. Касим-Заде) в 2009 году, неоднократно на семинаре «Математическое моделирование сложных систем и процессов» (рук. доц. A.C. Строгалов и проф. И.Н. Молодцов) в 2006-2009 годах, на научном семинаре «Проблемы современных информационно-вычислительных систем» под руководством д. ф.-м. н., проф. В. А. Васенина в 2011 году.

Кроме того результаты докладывались на XIII Международной конференции «Проблемы теоретической кибернетики» в Казани в 2002 году, на «днях науки» в рамках выставки-ярмарки Земли Се-

верный Рейн Веетфалия в Московском государственном университете путей сообщения (МИИТ) в 2003 году, на IX международной конференции «Интеллектуальные системы и компьютерные науки» г. Москва в 2006 году, на десятом международном научном семинаре «Дискретная математика и ее приложения» г. Москва в 2010 году, на научной конференции «Знания — Онтологии — Теории» (ЗОНТ-2011) в институте Математики им. С. Л. Соболева СО РАН г. Новосибирск в 2011 году.

Публикации. Основные положения и выводы диссертации были опубликованы в 6 статьях (см. [1, 2, 3, 4, 5, 6]), 5 из которых в журналах из перечня, рекомендованного ВАК Минобрнауки России.

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

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

Содержание работы

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

Первая глава работы посвящена непосредственно описанию алгоритмов решения 2- и 3-мерных задач об упаковке, построенного на базе комплексных эвристик. Алгоритм решения 3-мерной задачи включает в себя алгоритм 2-мерной и является основным для рассмотрения. Сначала вводятся обозначения и предлагается

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

Алгоритм построен таким образом, что процесс формирования решения задачи разбивается не несколько подзадач, которые решаются многократно по циклу на различных этапах алгоритма. В каждой из этих подзадач требуется осуществить выбор из нескольких вариантов. Если делать этот выбор методом полного перебора, то будет найдено наилучшее решение задачи в 2-мерном ортогональном случае, и в некотором ограниченном классе решений в 3-мерном случае. Однако, использование метода полного перебора, приводит к неприемлемо большому времени работы алгоритма (экспоненциальная зависимость от количества предметов). По этой причине каждый раз, когда требуется выбрать решение подзадачи из нескольких вариантов, вместо полного перебора в алгоритме для принятия решения используется эвристический функционал качества. Результатом применения этого функционала к каждому варианту решения подзадачи является действительное число и в качестве окончательного решения выбирается вариант с наибольшим значением функционала. Каждый такой функционал имеет полиномиальную сложность вычисления, что в совокупности приводит к тому, что сложность работы всего алгоритма также является полиномиальной. Таким образом для решения каждой подзадачи используется вариант жадного алгоритма, где в качестве критерия выбирается эвристический функционал качества.

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

1. Время работы предложенного алгоритма для решения 2-мерной ортогональной задачи об упаковке можно оценить сверху как О^4), где N — количество предметов в задаче.

2. Время работы предложенного алгоритма для решения 3-мерной ортогональной задачи об упаковке можно оценить сверху как 0(Л^5), где N — количество предметов в задаче.

3. Время работы предложенного алгоритма для решения 3-мер-

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

комбинированием предметов в прямоугольные блоки можно оценить сверху как О (М5х1п10(М)), где N — количество предметов в задаче.

4. Для любой индивидуальной 2-мерной ортогональной задачи об упаковке предложенный алгоритм «полного перебора» находит решение, эквивалентное наилучшему. При этом время работй алгоритма зависит только от количества предметов и не зависит от характеристик линейных размеров.

5. Для любой индивидуальной 3-мерной задачи об упаковке, для которой существует решение на 100% заполняющие контей-нер(ы), предложенный алгоритм «полного перебора» находит решение, эквивалентное наилучшему, то есть заполняющее коптейнер(ы) на 100%. При этом время работы алгоритма зависит только от количества предметов и не зависит от характеристик линейных размеров.

6. Для любой индивидуальной 2-мерной ортогональной задачи об упаковке существуют такие функционалы качества линейной сложности, использование которых в предложенном алгоритме, гарантирует нахождение алгоритмом наилучшего решения этой задачи. При этом время работы алгоритма с такими функционалами зависит только от количества предметов и может быть оценено сверху как 0(ДГ4), где N — количество предметов в задаче.

7. Для любой индивидуальной 3-мерной задачи об упаковке, для которой существует решение на 100% заполняющие контей-нер(ы), существуют такие функционалы качества линейной сложности, использование которых в предложенном алгоритме, гарантирует нахождение алгоритмом наилучшего решения этой задачи. При этом время работы алгоритма с такими

функционалами зависит только от количества предметов и

может быть оценено сверху как 0(Л^5), где N — количество предметов в задаче.

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

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

Исходя из того, что найти наилучшее решение 3-мерной задачи об упаковке для большого количества предметов не представляется возможным, то экспериментальная оценка качества работы алгоритма осуществлялась для таких индивидуальных задач, наилучшее решение которых на 100% заполняет объём контейнера. Класс таких задач достаточно большой, чтобы результаты эксперимента можно было считать показательными для всего объема индивидуальных задач. Полученные результаты эксперимента показывают, что независимо от количества предметов и количества типоразмеров в задаче среднее качество работы алгоритма составляет 85% от наилучшего решения. Такое качество при высокой скорости работы является вполне достаточным для эффективного использования алгоритма на практике.

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

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

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

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

В пятой главе описаны особенности программной реализации алгоритмов и различных вариантов внедрения программных систем расчёта оптимальной загрузки транспортных средств на предприятиях. Кроме практического внедрения алгоритмов в виде программных систем, основным вариантом их реализации является линейка раскегЗс!-уегЗ, представляющая собой набор полнофункциональных законченных «коробочных» программных продуктов, которые распространяются на коммерческой основе в виде ряда отдельных модификаций. Разные модификации имеют разный набор функциональных возможностей. Таким образом каждый пользователь может выбрать ту модификацию, которая подходит ему по соотношению цена/качество. Из названия видно, что в этих продуктах реализовано третье поколение алгоритма, которое разработано по результатом длительного тестирования программ на реальных задачах и их адаптации к пожеланиям пользователей. В приложениях к диссертационной работе приведены скриншоты (снимки экрана) различных программных реализаций алгоритма и визуальных результатов работы алгоритма на показательных примерах. Помимо особенностей реализации и внедрения предложенного в работе алгоритма, в пятой главе описаны другие программные продукты сторонних разработчиков, решающих такие же и смежные алгоритмические задачи, возникающие на практике вместе с

задачей укладки.

Основные результаты работы

В данной работе решены несколько основных задач:

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

• доказаны полиномиальные оценки скорости работы разработанных алгоритмов и эффективность их структуры для решения поставленных задач;

• доказано существование алгоритма переборного типа для нахождения наилучшего решения 2-мерной ортогональной задачи об упаковке, число шагов которого зависит только от числа предметов, а также невозможность его обобщения на 3-мерный случай;

• предложены методы оптимизации их коэффициентов с использование генетических алгоритмов и нейронный сетей;

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

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

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

Благодарности. Автор выражает благодарность зав.кафедрой МаТИС проф.Кудрявцеву В.Б. за постоянное внимание к работе, отдельную благодарность моему научному руководителю доц. Строганову A.C. многолетняя совместная работа с которым позволила выработать основные идеи алгоритма и разрешить много принципиальных трудностей, возникавших при написании работы. Так же хотелось бы выразить благодарность проф.Васенину В.А. за ценные замечания по работе, которые способствовали её улучшению.

Список литературы

[1] В. В. Псиола. О приближенном решении 3-х мерной задачи об упаковке на основе эвристик. Интеллектуальные системы, 11, вып. 1-4, 2007. С.83-101

[2] В.В. Псиола. Особенности программной реализации алгоритма Packer3d. МГУ им. М.В. Ломоносова - Москва, 2009. 16 с. Деп. в ВИНИТИ 01.04.09, № 181-В2009

[3] В.В. Псиола. Оценки качества работы алгоритма Packer3d (теория и практика). МГУ им. М.В. Ломоносова - Москва, 2009. 35 с. Деп. в ВИНИТИ 01.04.09, № 182-В2009

[4] В.В. Псиола. Об одной особенности двумерной задачи о рюкзаке. Материалы X Международного семинара "Дискретная математика и ее приложения"(Москва, МГУ, 1-G февраля 2010 г.) / Под редакцией О. М. Касим-Заде. — М.: Изд-во механико-математического факультета МГУ, 2010. С.418-420

[5] В.В. Псиола. Эвристический алгоритм приближенного решения задачи об упаковке. Нейрокомпьютеры: разработка, применение», №9, 2011.

[6] В.В. Псиола. Обзор основных нейросетевых моделей. Интеллектуальные системы, 4, вып. 3-4, 1999. С. 139-173

Подписано в печать 19.10.2011 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1151 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

Введение

Формулировка задачи и её актуальность.

Одномерный случай упаковки.

Современное состояние задачи.

Цели работы.

Основное содержание работы.

1 Постановка задачи и описание алгоритмов

1.1 Формальная постановка задачи.

1.2 Общая идея алгоритма

1.3 Алгоритм комбинирования предметов.

1.4 Сведение 3-мерной укладки к 2-мерной.

1.5 Выбор области укладки для 2-мерного алгоритма.

1.6 Алгоритм 2-мерной укладки

1.7 Модель принятия решения на основе функционалов качества

2 Оценки сложности и качественных характеристик

2.1 МР-полнота задач укладки.

2.2 Доказательства полиномиальности алгоритма.

2.3 Качественные характеристики алгоритма.

2.4 Экспериментальные оценки алгоритма.

3 Вопросы нахождения коэффициентов

3.1 Принципы подбора коэффициентов

3.2 Общая оптимизация генетическими алгоритмами

3.3 Динамический выбор с помощью нейронных сетей.

3.4 Улучшение качества за счет ограниченного перебора

4 Модификации задачи и алгоритмов

4.1 Обозначения

4.2 Дополнительные ограничения.

4.3 Особенности модификаций алгоритмов укладки.

4.4 Модификации алгоритмов.

5 Практическая реализация и внедрения

5.1 Особенности программной реализации.

5.2 Внедрения.

5.3 Существующие альтернативные решения.

5.4 Смежные задачи.

Формулировка задачи и её актуальность

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

Решение подобных задач востребовано как в одномерном, так и в многомерном пространстве, в частности в 2-х и 3-х мерном. В общем случае задачи укладки многомерных предметов предполагают нахождение расстановки произвольных фигур в контейнер, заданный так же произвольной фигурой. Однако, подобная постановка слишком сложна в формулировке, решении и описании результата. По этой причине наиболее интересной и востребованной на практике является постановка задачи, когда конфигурации предметов и контейнера для укладки являются прямоугольниками в 2-мерном случае и прямоугольными параллелепипедами в 3-мерном. Задачи упаковки и раскроя в такой постановке принято называть «ортогональными» [4], в английской терминологии «Bin Packing Problem» (ВРР) и «Cutting Stock Problem» (CSP), соответственно. Эти задачи и для одномерного и 2- или 3-мерного случаев относятся к классу ИР-полных (в том случае, если параметры расстановки заданы в пространстве Ж+). МР-полнота в одномерной задачи показана в работе [1]. Из этого факта можно легко доказать ^-полноту задач в 2- и 3-мерных случаях1.

В настоящее время остается открытым вопрос существования полиномиального алгоритма для решения КР-полных задач. Большинство исследователей сходятся во мнении, что такого алгоритма не существует. Это означает, что все известные точные алгоритмы, решающие какую-либо из КР-полных задач (в частности задачу об упаковке), имеют в общем случае экспоненциальную временную сложность, что эквивалентно полному перебору всех возможных вариантов. Как следствие, уже при относительно небольшом количестве объектов, время работы программ, реализующих такие алгоритмы, будет неприемлемо большим для использования на практике даже при вычислениях на суперкомпьютерах. Более того, увеличение процессорной мощности в будущем в сотни и тысячи раз не позволит существенно ускорить известные алгоритмы переборного типа.

В силу изложенных выше причин особенное внимание привлекают алгоритмы, которые позволяют найти близкое (в том или ином смысле) к оптимальному решение задач такого типа за приемлемое время. Существуют различные типы таких алгоритмов [4], однако все они не гарантируют нахождения оптимального решения и в многомерном случае оценка качества их работы существенно затруднена. Практическая применимость этих алгоритмов осложняется еще и тем обстоятельством, что, зачастую, найденная расстановка должна быть не только близка к оптимальной, но и удовлетворять большому количеству дополнительных ограничений. В зависимости от особенностей предметной области набор ограничений и дополнительных условий может быть очень разнообразным.

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

Одномерный случай упаковки

В одномерном случае есть две следующие канонические постановки задачи упаковки предметов [1].

1 Подробно МР-полнота задач обсуждается в разделе 2 1

• Задача «о рюкзаке»: задано конечное мноэюество V «предметов» и для каждого из и € II «размер» в (и) е и «стоимость» у (и) £ а так же положительное число В > тах{в{и) : и £ и} — «ель-кость рюкзака». Требуется найти такое подмножество и' С и, что ^1иеи'3(и) < В и величина ^иеи,у{и) принимает наибольшее возможное значение.

• Задача об «упаковке в контейнеры»: задано конечное множество V «предметов» и «размеры» в (и) е [0,1]; для као/сдого предмета и 6 II требуется найти такое разбиение множества и на непересекающиеся подмножества £/1, £/2,. •, чтобы сумма размеров предметов в каждом подмноэюестве не превосходила 1 и чтобы к было наименьшим возможным.

Для них известны следующие оценки качества работы:

• для любой индивидуальной задачи I об упаковке в контейнеры, если решение полученное алгоритмом «в первый подходящий»2, а ОРТ{1) — наилучшее решение этой задачи, выполнено неравенство ^ОРТ{1) + 2;

• для любой индивидуальной задачи I об упаковке в контейнеры, если РРИЦ) — решение получетюе алгоритмом «в первый подходящий в порядке убывания»3, а ОРТ{1) — наилучшее решение этой задачи, выполнено неравенство < уОРТ{1) + 4.

Таким образом в общем случае доказано, что наиболее очевидные эвристические алгоритмы решения этой задачи дают решение не хуже чем на 70% и 78% от оптимального, и эта оценка алгоритмов является не улучшаемой в известном смысле [1]. Двух- и трехмерные варианты этой задачи заведомо не проще одномерной, поэтому оценки качества работы подобных алгоритмов в многомерном случае вряд ли могут быть лучше.

Для задачи «о рюкзаке» ситуация несколько другая: существуют полиномиальные алгоритмы, решающие задачу с любой заранее заданной точностью. В настоящей работе, упоминая задачу о рюкзаке (особенно в ее 3-мерном варианте), будет подразумеваться, что удельная стоимость предметов в(и)/и(и) равна единице. Подобное ограничение оставляет одномерную

2 «в первый подходящий» - алгоритм упаковки предметов в контейнеры при котором очередной предмет помещается в контейнер с минимальным номером, у которого свободное место не меньше размера предмета.

3«в первый подходящий в порядке убывания» - алгоритм «в первый подходящий», примененный к предметам, отсортированным в порядке убывания размера. задачу в классе NP-полных [1]. Наиболее очевидный «жадный алгоритм», примененный для решения этой задачи, имеет погрешность 2. Однако, там же показано, что для любого наперед заданного числа к € существует простая модификация «жадного алгоритма» [13], которая за полиномиальное время позволяет решить задачу о рюкзаке с погрешностью не более чем 1 + (1 /к). К сожалению, для такой модификации, полином, оценивающий скорость работы, имеет число к в показателе, что делает её неприменимой на практике. Для оценки качества работы алгоритм еще используют статистические оценки погрешности работы алгоритма. Они вычисляется как отклонения результата, полученного алгоритмом, от оптимального решения на некотором ограниченном наборе индивидуальных задач, сгенерированных в соответствии с каким-либо законом распределения. Подобные статистические оценки погрешности могут существенным образом отличаться от теоретических и дают слабое представление о качестве работы алгоритма на наиболее плохих индивидуальных задачах. В частности для алгоритмов «в первый подходящий» и «в первый подходящий в порядке убывания» решения задачи об «упаковке в контейнеры» оценка в среднем получается равной 1.07 и 1.02, в то время как в худшем случае она равна 1.7 и 1.22 соответственно [1].

Современное состояние задачи и подходы к её решению

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

Дано: множество 3-мерных предметов (прямоугольных параллелепипедов), заданных тремя числами из определяющими их линейный размер, а так otee три числа из Z+; определяющих размеры контейнера (так же прямоугольного параллелепипеда).

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

Постановка 2-мерной задачи аналогична.

Исследования в области оптимизации укладки и раскроя в многомерном случае велись и ведутся различными специалистами как в России, так и за рубежом. Еще в 1951 году российские ученые JI.B. Канторович и В.А. Залгаллер изложили в своей книге «Рациональный раскрой промышленных материалов» подходы к решению задачи раскроя материала в одномерном и 2-мерном случаях с помощью методов линейного программирования. Второе издание этой книги было в 1971 году [2]. Аналогичные методы получили развитие в 60-е годы за рубежом в работах P. Gilmore, R. Gomory, а позднее G. Scheithauer, J. Temo и у нас в работах Э.А. Мухачевой, И.В. Романовского и других. Кроме методов линейного программирования, для нахождения точного решения применяются иногда и комбинаторные методы. В них выделяются подмножества допустимых решений и отсеиваются те, которые не содержат оптимальных. Такие методы были предложены, например, И.В. Романовским, Н.П. Христовым и СВ. Кацевым [4].

В связи с тем, что задачи упаковки и раскроя относятся к классу NP-полных, методы нахождения точного решения, включая комбинаторные и методы линейного программирования, не позволяют решать задачи большой размерности за приемлемое на практике время. Поэтому исследователями уделяется пристальное внимание разработке приближенных и эвристических методов. Эвристические алгоритмы-— это алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального решения задачи [3]. Среди них выделяют методы локального поиска-оптимума, в которых поиск оптимальных решений ведется в окрестности некоторого начального допустимого решения, а также конструктивные методы, в которых искомая расстановка предметов строится покомпонентно, путём добавлением нового компонента к частично построенному решению. Каждый из этих подходов имеет свои достоинства и недостатки, а также имеет множество различных алгоритмов, к ним относящихся [4].

В алгоритмах локального »поиска сначала используется механизм кодирования/декодирования расстановки предметов, для чего используются так называемые «декодеры». Декодеры - это алгоритмы, восстанавливающие эскиз упаковки и вычисляющие значение целевой функции. Для этого с помощью декодера достаточно найти прямую схему кодирования, которой является последовательность координат (х,у), удовлетворяющая условиям допустимости упаковки. Затем с помощью декодера переходят к прямой схеме. Известны различные алгоритмы-декодеры. Наибольшее распространение получил декодер нижний-левый (Bottom Left, BL). Алгоритмы локального поиска начинают поиск с некоторого начального решения, заданного своим кодом, и итеративно пытаются заменить текущее решение на лучшее в специально определенной окрестности. Обзор таких методов решения задач укладки и раскроя можно найти, например, в работах [5] и [6]. В частности к таким методам относятся методы поиска решения с помощью «генетических алгоритмов» [25], в которых код расстановки предметов, полученных соответствующим алгоритмом декодером, рассматривается как геномом.

Конструктивный алгоритм должен определять не только стратегию выбора очередного предмета для установки, но и стратегию выбора места установки этого предмета в контейнере. Например, на основе стратегии упаковки FF — «в первый подходящий», о которой говорилось в предыдущем разделе, различные исследователи (Е. Coffman, F. Chung и др.) рассматривают стратегии: «следующий по убыванию длины» (NFDL); «первый по убыванию подходящей длины» (FFDL); «лучший подходящий по убыванию длины» (BFDL), в которых каждый новый элемент упаковывается с выравниванием по левому и нижнему краю. Другими исследователями (J. Berkey, P. Wang) предложен алгоритм «ограниченный следующий подходящий» (FNF) сразу упаковывает элементы в ограниченные контейнеры. Алгоритм «ограниченный первый подходящий» (FFF) использует стратегию FFD — текущий элемент упаковывается на самый нижний допустимый уровень первого контейнера. Если такого уровня нет, то создается новый уровень в текущем контейнере либо в первом подходящем контейнере [4]. Известны стратегии выбора места для укладки без учета уровней упакованных предметов, основная из них называется «нижний-левый» (Bottom-Left, BL) [7] и состоит в последовательной установке предмета в самый нижний левый угол ломанной границы, образованной ранее установленными предметами. Для этой стратегии доказано, что в наихудшем случае она дает решение в 3 раза хуже оптимального [8]. Существуют и модификации этой стратегии, позволяющие, например, добиться оценки 2.5 раза от оптимального в наихудшем случае [9]. Существуют и другие стратегии выбора места для установки предметов: «ограниченный нижний-левый» (FBL), «переменные направления» (Alternate Directions, AD) и т.п. В 2003 году Н. Keller, V, Kotov предложили новый приближенный алгоритм дающий решение в худшем случаем не более чем 2 от оптимального Авторы утверждают, что этот вопрос оставался открытым до того момента

4].

Для решения задач 3-мерной упаковки используются в основном эвристические методы [4]. Большая часть таковых, по мнению D. Pisinger [10], базируется на следующих подходах.

• Построения стен/слоев: контейнерное пространство разделяется на вертикальные слои/стены, которые заполняются ящиками автономно. На внутренних этапах этих алгоритмов могут использоваться различные идеи и методы.

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

• Гильотинный разрез: построение дерева, в котором каждая ветвь часть гильотинного разреза контейнера.

• Построение блоков: рекурсивное заполнение контейнера блоками, состоящими из сходных ящиков.

В данной работе к рассмотрению предлагается эвристический конструктивный однопроходный алгоритм приближенного решения 3-мерной задачи об упаковке, который является комбинацией подходов построения по слоям и блокам. В качестве стратегий выбора предмета для упаковки, слоя и места для его установки в этом слое используются комплексные эвристики, заданные взвешенной суммой различных характеристик объекта выбора. Возможность использования в качестве стратегии выбора не одной определенной эвристики, а нескольких в совокупности рассматривается, например, в работах Норенкова И.П. [11, 12]. Однако, там применяется вероятностный выбор той или иной стратегии, при этом количество стратегий для выбора очень не велико (четыре). В данной работе предпочтительность использования той или иной стратегией оценивается некоторой числовой характеристикой и выбор осуществляется на основе взвешенной суммы этих характеристик, то есть каждая стратегия вносит свой вклад в каждом случае выбора. При этом количество рассматриваемых стратегий существенно больше (в совокупности - 35).

Цели работы

В качестве основных целей работы можно сформулировать следующие:

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

• получение теоретических и экспериментальных оценок сложности и качества работы алгоритма;

• исследование возможностей адаптации алгоритма к различным модификациям задачи;

• создание программной реализации алгоритма и анализ особенностей её внедрения на практике;

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

Результаты данной работы были представлены на механико-математическом факультете МГУ им. М.В. Ломоносова: на кафедральном семинаре кафедры МаТИС «Теория автоматов» (рук. проф. В.Б. Кудрявцева) в 2008 году; на семинаре кафедры дискретной математики «Модели и методы дискретной математики» (рук. проф. О.М. Касим-Заде) в 2009 году; неоднократно на семинаре «Математическое моделирование сложных систем и процессов» (рук. доц. A.C. Строганов и проф. И.Н. Молодцов) в 2006-2009 годах; на научном семинаре «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина в 2011 году.

Помимо этого отдельные результаты докладывались: на XIII Международной конференции «Проблемы теоретической кибернетики» в Казани в 2002 году; на «днях науки» в рамках выставки-ярмарки Земли Северный Рейн Вестфалия в Московском государственном университете путей сообщения (МИИТ) в 2003 году; на IX международной конференции «Интеллектуальные системы и компьютерные науки» г. Москва в 2006 году; на десятом международном научном семинаре «Дискретная математика и ее приложения» г. Москва в 2010 году; на научной конференции «Знания — Онтологии — Теории» (ЗОНТ-2011) в институте Математики им. С. Л. Соболева СО РАН г. Новосибирск в 2011 году.

Основные положения и выводы диссертации были опубликованы в 6 статьях (см. [14, 15, 16, 17, 18, 29]), 5 из которых в журналах из перечня, рекомендованного ВАК Минобрнауки России.

Основное содержание работы

Первая глава работы посвящена непосредственно описанию алгоритмов решения 2- и 3-мерных задач об упаковке, построенного на базе комплексных эвристик. Алгоритм решения 3-мерной задачи включает в себя алгоритм 2-мерной и является основным для рассмотрения. Сначала вводятся обозначения и предлагается формальная постановка задачи. Затем приводится функциональная модель алгоритма, подробное описание их составных частей. Далее идет описание эвристических функционалов принятия решений и подробное обоснование выбора слагаемых этих функционалов для данной задачи.

Алгоритм построен таким образом, что процесс формирования решения задачи разбивается не несколько подзадач, которые решаются многократно по циклу на различных этапах алгоритма. В каждой из этих подзадач требуется осуществить выбор из нескольких вариантов. Если делать этот выбор методом полного перебора, то будет найдено наилучшее решение задачи в 2-мерном ортогональном случае, и в некотором ограниченном классе решений в 3-мерном случае. Однако, использование метода полного перебора, приводит к неприемлемо большому времени работы алгоритма (экспоненциальная зависимость от количества предметов). По этой причине каждый раз, когда требуется выбрать решение подзадачи из нескольких вариантов, вместо полного перебора в алгоритме для принятия решения используется эвристический функционал качества. Результатом применения этого функционала к каждому варианту решения подзадачи является действительное число и в качестве4 окончательного решения выбирается вариант с наибольшим значением функционала. Каждый такой функционал имеет полиномиальную сложность вычисления, что в совокупности приводит к тому, что сложность работы всего алгоритма также является полиномиальной. Таким образом для решения каждой подзадачи используется вариант жадного алгоритма, где в качестве критерия выбирается эвристический функционал качества.

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

1. Время работы предложенного алгоритма для решения 2-мерной ортогональной задачи об упаковке можно оценить сверху как 0(А/'4), где N — количество предметов в задаче.

2. Время работы предложенного алгоритма для решения 3-мерной ортогональной задачи об упаковке можно оценить сверху как 0(т\г5), где N — количество предметов в задаче.

3. Время работы предложенного алгоритма для решения 3-мерной ортогональной задачи об упаковке с предварительным комбинированием предметов в прямоугольные блоки можно оценить сверху как х 1п10(-/V)), где N — количество предметов в задаче.

4. Для любой индивидуальной 2-мерной ортогональной задачи об упаковке предложенный алгоритм «полного перебора» находит решение, эквивалентное наилучшему. При этом время работы алгоритма зависит только от количества предметов и не зависит от характеристик линейных размеров.

5. Для любой индивидуальной 3-мерной задачи об упаковке, для которой существует решение на 100% заполняющие контейнер(ы), предложенный алгоритм «полного перебора» находит решение, эквивалентное наилучшему, то есть заполняющее контейнер(ы) на 100%. При этом время работы алгоритма зависит только от количества предметов и не зависит от характеристик линейных размеров.

6. Для любой индивидуальной 2-мерной ортогональной задачи об упаковке существуют такие функционалы качества линейной сложности, использование которых в предложенном алгоритме, гарантирует нахождение алгоритмом наилучшего решения этой задачи. При этом время работы алгоритма с такими функционалами зависит только от количества предметов и может быть оценено сверху как 0(1V4), где N — количество предметов в задаче.

7. Для любой индивидуальной 3-мерной задачи об упаковке, для которой существует решение на 100% заполняющие контейнер(ы), существуют такие функционалы качества линейной сложности, использование которых в предложенном алгоритме, гарантирует нахождение алгоритмом наилучшего решения этой задачи. При этом время работы алгоритма с такими функционалами зависит только от количества предметов и может быть оценено сверху как 0(Л^5), где N — количество предметов в задаче.

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

Исходя из того, что найти наилучшее решение 3-мерной задачи об упаковке для большого количества предметов не представляется возможным, то экспериментальная оценка качества работы алгоритма осуществлялась для таких индивидуальных задач, наилучшее решение которых на 100% заполняет объём контейнера. Класс таких задач достаточно большой, чтобы результаты эксперимента можно было считать показательными для всего объема индивидуальных задач. Полученные результаты эксперимента показывают, что независимо от количества предметов и количества типоразмеров в задаче среднее качество работы алгоритма составляет 85% от наилучшего решения. Такое качество при высокой скорости работы является вполне достаточным для эффективного использования алгоритма на практике.

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

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

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

В пятой главе описаны особенности программной реализации алгоритмов и различных вариантов внедрения программных систем расчёта оптимальной загрузки транспортных средств на предприятиях. Кроме практического внедрения алгоритмов в виде программных систем, основным вариантом их реализации является линейка раскегЗс!-уегЗ, представляющая собой набор полнофункциональных законченных «коробочных» программных продуктов, которые распространяются на коммерческой основе в виде ряда отдельных модификаций. Разные модификации имеют разный набор функциональных возможностей. Таким образом каждый пользователь может выбрать ту модификацию, которая подходит ему по соотношению цена/качество. Из названия видно, что в этих продуктах реализовано третье поколение алгоритма, которое разработано по результатом длительного тестирования программ на реальных задачах и их адаптации к пожеланиям пользователей. В приложениях к диссертационной работе приведены скриншоты (снимки экрана) различных программных реализаций алгоритма и визуальных результатов работы алгоритма на показательных примерах. Помимо особенностей реализации и внедрения предложенного в работе алгоритма, в пятой главе описаны другие программные продукты сторонних разработчиков, решающих такие же и смежные алгоритмические задачи, возникающие на практике вместе с задачей укладки.

Заключение

В данной работе решены несколько основных задач:

• для 2- и 3-мерных задач об упаковке предметов реализована математико-компыотерная модель механизма принятия решений человеком на основе эвристик, сформулированная в виде алгоритмов;

• доказаны полиномиальные оценки скорости работы разработанных алгоритмов и эффективность их структуры для решения поставленных задач;

• доказано существование алгоритма переборного типа для нахождения наилучшего решения 2-мерной ортогональной задачи об упаковке, число шагов которого зависит только от числа предметов, а также невозможность его обобщения на 3-мерный случай;

• предложены методы оптимизации их коэффициентов с использование генетических алгоритмов и нейронный сетей;

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

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

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

Благодарности. Автор выражает благодарность зав.кафедрой Ма-ТИС проф.Кудрявцеву В.Б. за постоянное внимание к работе, отдельную благодарность моему научному руководителю доц. Строганову A.C. многолетняя совместная работа с которым позволила выработать основные идеи алгоритма и разрешить много принципиальных трудностей, возникавших при написании работы. Так же хотелось бы выразить благодарность проф.Васенину В.А. за ценные замечания по работе, которые способствовали её улучшению.

1. М. Гэри, Д. Джонсон Вычислительные машины и труднореша-емые задачи. М.: Мир, 1982.

2. Л.В. Канторович, В.А. Залгаллер Рациональный раскрой промышленных материалов. Новосибирск: Наука. 1971. 299с.

3. И.Х. Сигал, А. П. Иванова Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. — Учеб. пособие. — Изд. 2-е, испр. — М.: ФИЗМАТЛИТ. 2003. 240с.

4. А. Ф. Валеева Конструктивные методы для решения задач ортогональной упаковки и раскроя. ГОУ ВПО Уфимский государственный авиационный технический университет, Диссертационная работа на соискание ученой степени доктора технических наук, 2006.

5. Ю. Кочетов, Н. Младенович, П. Хансен Локальный поиск с чередующимися окрестностями. ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ, Январь-июнь 2003. Серия 2. Том 10, № 1, 11-43

6. Ю.А. Кочетов, А.Р. Усманова. Вероятностный поиск с запретами для задач упаковки в контейнеры. Труды Байкальской международной конференции, Иркутск, 2001, т 6, 22-26.

7. Chazelle В. The bottom-left bin packing heuristic: An efficient implementation. IEEE Trans, on Comput. 2(1983). P. 697-707.

8. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions. SIAM J. Comput. 9 (1980). P. 846-855.

9. Daniel D.K.D.B. Sleator A 2.5 times optimal algorithm for packing in two dimensions. Computer Science Department, Stanford University, Stanford, CA 94305, U. S A. Received 6 January 1979; revised version received 13 November 1979

10. Pismger D. Heuristics for the container loading problem. European Journal of Operational Research. 2002. N141. P. 382-392.

11. Норенков И.П., Косачевский О. Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации.

12. Информационные технологии. 1999. №2. С. 2-8.

13. Норенков И. П. Эвристики и их комбинации в генетических методах дискретной оптимизации. Информационные технологии. 1999. N2 1. С.2-7. 69.

14. A.Ахо, Дж.Хопкрофт, Дж.Ульман Построение и анализ вычислительных алгоритмов. М.:Мир 1979, 536 стр.

15. B. В. Псиола. О приближенном решении 3-х мерной задачи об упаковке на основе эвристик. Интеллектуальные системы, 11, вып. 1-4, 2007. С.83-101

16. В.В. Псиола. Особенности программной реализации алгоритма Packer 3d. МГУ им. М.В. Ломоносова Москва, 2009. 16 с. Деп. в ВИНИТИ 01.04.09, № 181-В2009

17. В. В. Псиола. Оценки качества работы алгоритма Packer3d (теория и практика). МГУ им. М.В. Ломоносова Москва, 2009. 35 с. Деп. в ВИНИТИ 01.04.09, № 182-В2009

18. В.В. Псиола. Эвристический алгоритм приближенного решения задачи об упаковке. Нейрокомпьютеры: разработка, применение», №9, 2011.

19. М. Липский Комбинаторика для программистов. М.: Мир, 1988

20. D.S. Johnson, A. Demers, J.D. Ullman, M.R.Garey and R.I. Graham 1974. «Worst-case performance bounds for simple one-dimensional packing algorithms», SIAM. J. Comput. 3, 299-325 (6.1)

21. D.S. Johnson 1973] «Near-Optimal Bin Packing algorithms», Doctorial Thesis, Det of Mathematics, Massachusetts Institute of Technology, Cambridge, MA. (6.1;6.3)

22. S. Sahni 1975] «Approximate algorithm for the 0/1 knapsack problem», J. Assoc. Comput. Mach. 22, 115-124. (6.1)

23. O.H. Ibarra, C.E. Kim 1975a] «Fast approximate algorithm for the knapsack and sum of subset problem», J. Assoc. Comput. Mach. 22, 463-468. (6.1)

24. Т.Ч. Xy, M.T. Шит Комбинаторные алгоритмы. Нижний Новгород: Изд-во Нижегородского госуниверситета им.Н.И.Лобачевского, 2004. 330 с.

25. Darrell Whitley. A genetic algorithm tutorial. Statistics and computing, 4, 65-85, 1994

26. Ф. Харари Теория графов. M.: Изд-во «МИР», 1973, 300 стр.

27. Ананий В. Левитин Алгоритмы: введение в разработку и анализ. М.: «Вильяме», 2006, 576 стр., с ил.; ISBN 5-8459-0987-2, 0-20174395-7.

28. В.В. Псиола Об одном эвристическом алгоритме решения задачи Штейнера. Журнал «Приборостроение».' Выпуск 6. 1997 год. Тематический выпуск «Нейросетевые и параллельные методы обработки информации». Санкт-Петербург.

29. В.В. Псиола. Обзор основных нейросетевых моделей. Интеллектуальные системы, 4, вып. 3-4, 1999. С.139-173

30. Т. Khonen Self-organized formation of topologically correct feature maps. Biological Cybernetics. 1982. 43. P.59-69.

31. T. Khonen Self-organized map. Proc. IEEE. 1990. V. 78. № 9. P. 14641480.

32. В.А.Хаменя, И.В Артельных, В.В. Псиола, И.Д. Хаменя Решение задачи классификации в рамках модели смеси гауссовских распределений. Сборник «Теоретические и прикладные проблемы ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ». 2001 год. Москва.

33. Ф. Уоссермен Нейрокомпьютерная техника. Теория и практика. М. Мир, 1992.

34. H.D. Block The Perseptron: a model for brain function. Review of Modern Physics. 1962. 34. P. 123-135.