Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Сурначев, Максим Юрьевич

• Сурначев, Максим Юрьевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Сурначев, Максим Юрьевич

Введение.

1. Задачи раскроя-упаковки: аналитический обзор моделей и методов их решения.

1.1 Задача одномерного раскроя-упаковки. w 1.1.1 Методы, использующие математическое программирование.

1.1.2 Комбинаторные методы.

1.1.3 Приближенные и эвристические методы.

1.1.4 Методы локального поиска оптимума.

Введение диссертации (часть автореферата) на тему «Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера»

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

Актуальность проблемы. В научной и производственной деятельности часто встречаются ситуации раскроя и упаковки встречаются очень часто: это задачи раскроя материала на заготовки различных форм и размеров, и задачи размещения совокупности предметов на ограниченной площади или в ограниченном пространстве. Многие другие проблемы также сводятся к ситуациям раскроя и упаковки. Среди многообразия постановок задач раскроя и упаковки самостоятельный интерес представляют задачи упаковки параллелепипедов (3DBPP). К таким задачам относятся, например, оптимизация перевозки и складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка деталей. К рассматриваемым проблемам сводится также и ряд задач планирования и распределения ресурсов. Несмотря на конкретное практическое применение, круг работ по решению задач параллелепипедной упаковки невелик. Это объясняется сложностью задач и высокой трудоемкостью их решения. Поэтому является актуальной разработка, эффективных алгоритмов решения задач раскроя-упаковки параллелепипедов.

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

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

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

Задачи, поставленные для достижения цели работы:

1. Рассмотреть постановки основных задач трехмерной упаковки, описать их математические модели;

2. Разработать блочный способ моделирования трехмерных упаковок. Сформулировать его основные свойства и установить связь с другими способами кодирования;

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

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

5. Разработать программное обеспечение, реализующее предложенные методы и алгоритмы;

6. Провести численный эксперимент с целью исследования эффективности предложенных алгоритмов.

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

1. Блочный способ кодирования трехмерных упаковок.

2. «Блочный декодер» - алгоритм конструирования блочной структуры упаковки по приоритетному списку (перестановке параллелепипедов).

3. Эволюционные методы, работающие с блочным декодером для решения поставленной задачи.

4. Компьютерная программа, реализующая разработанные методы и алгоритмы.

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

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

1. Блочный способ кодирования контейнерных упаковок. Он является методом кодирования и моделирования упаковок. Его преимуществами являются: а) взаимнооднозначное представление упаковка-кодировка; б) легкая модифицируемость; в) учет пустых пространств; г) возможность адаптации для любых постановок задач и ограничений; д) возможность использования для разнообразных методов локального поиска.

2. Блочный декодер конструирования упаковки, использующий блочный способ кодирования на базе простых стратегий следующий подходящий (NF) и первый подходящий (FF). Декодер универсален и может применяться в составе различных методов локального поиска оптимума.

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

4. Адаптация эволюционных алгоритмов - метода случайных перестановок, (J+1J-EA и генетического алгоритма для задач упаковки контейнера на базе блочного декодера.

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

Работа выполнялась при частичной поддержке грантов Российского Фонда фундаментальных исследований (РФФИ), проекты 99-01-000937 и 01-01-000510.

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

1. Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности-2000" (Уфа, 2000).

2. Студенческая научно-теоретическая конференция 2001 (Уфа, 2001)

3. Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (Санкт-Петербург, 2001);

4. CSIT'2001: Computer Science and Informational Technologies (Уфа, 2001);

5. Вторая Всероссийская научно-техническая конференция «Мехатроника, автоматизация, управление - 2005» (Уфа, 2005).

6. Семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 10 работ: 6 статей и 4 трудов конференций.

Содержание диссертации.

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

В первой главе проведен аналитический обзор моделей и методов решения задач раскроя-упаковки.

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

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

В четвертой главе описывается реализация ПО и порядок проведения численного эксперимента.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Сурначев, Максим Юрьевич

Основные результаты диссертационной работы:

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

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

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

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

5. Разработано программное обеспечение полиномиального времени работы, реализующее предложенные алгоритмы. ПО позволяет за 0,5-10 минут находить рациональные упаковки для 20-100 различных ящиков.

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

Заключение

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

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

Список литературы диссертационного исследования кандидат технических наук Сурначев, Максим Юрьевич, 2005 год

1. Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач // учебное пособие под ред. Я.Е.Львовича. Воронеж: Воронежский гос. техн. ун-т; Нижегородский ун-т. 1995. С.96.

2. Булавский В.А., Яковлева М.А. О решении задач оптимального раскроя линейных материалов на ЭВМ // Математические методы в технико-экономических расчетах: Материалы научного совещания, т. IV. М.: АН СССР. 1961. С.83-87.

3. Валеева А.Ф., Гареев И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизорованный метод динамического перебора и метод перебора с усечением. //Информационные технологии. Приложение. 2003. №2. С.24.

4. Валеева А.Ф., Тоцков И.Е., Гареев И.Р. Методы решения трехмерной задачи в интеллектуальной системе раскроя-упаковки // Материалы Республиканской научно-технической конференции "Интеллектуальное управление в сложных системах 99". Уфа, 1999. С.36-38.

5. Гери М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи // М. Мир. С.416.

6. Гимади Э.Х., Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный подход // Известия вузов. Математика. 1997. №12. С.25-33.

7. Гимади Э.Х., Залюбовский В.В., Шарыгин П.И. Задачи упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. Математика. №12(427). 1997. С.34-44.

8. Ермаченко А.И., Сиразетдинов Т.М. Рекурсивный метод для решения задачи гильотинного раскроя // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2000. С.35-39.

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

10. Картак В.М. Оптимальная упаковка N-мерных параллелепипедов в полубесконечность // 12-я Байкальская международная конференция, методы оптимизации и их приложения. Иркутск. 2001. С. 18-22.

11. Кацев С.В. Об одном классе дискретных минимаксных задач: Кибернетика, 1979, №5, С.139-141.

12. Кокотов В.З. Алгоритм плотного размещения разногабаритных элементов на плате // Информационные технологии. 1998. № 11. С.16-21.

13. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций. Сер. 2. 2003, Т. 10, № 1.С. 11-43.

14. Липовецкий А.И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении.Минск. 1985. С.80-87.

15. Мухачева А.С., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. М.: МАИ, 2004, 193 с.

16. Мухачева А.С., Куреленков С.Х., Смагин М.А., Ширгазин P.P. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы // Информационные технологии. 2002. №10. С.26-31.

17. Мухачева А.С., Мухачева Э.А. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя // Информационные технологии. №6, 2002. С.25-30.

18. Мухачева А.С., Сурначев М.Ю. Задача параллелепипедной упаковки: декодер на базе блочных структур // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2005. С.51-55.

19. Мухачева А.С., Ширгазин P.P. Задачи упаковки прямоугольников: рандомизированная эвристика на базе двойственной схемы локального поиска оптимума //Информационные технологии. 2003. №5. С. 18-23.

20. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. -М . Машиностроение. 1984. С. 176.

21. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов // Уфа. УГАТУ. 1998. С.216.

22. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. 2000. №9. С. 15-22.

23. Мухачева Э.А., Мухачева А.С., Чиглинцев А.В. Генетический алгоритм блочной структуры в задачах двумерной упаковки // Информационные технологии. 1999. №11. С. 13-18.

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

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

26. Романовский И.В. Алгоритмы решения экстремальных задач // М.: Наука. 1977. С.168.

27. Романовский И.В. Решение задачи гильотинного раскроя методом переработки списка состояний // Кибернетика. 1969. № 1. С. 102-104.

28. Романовский И.В., Христова Н.П. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. 1973. 13(5). С. 1200-1209.

29. Сборник трудов ВНИИСИ "Модели и методы оптимизации" М., 1980, № 3. С.352.

30. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наукова думка. 1986. 268 с.

31. Сурначев М.Ю. Задача параллелепипедной упаковки в контейнер: обзор методов решения. // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2003. С.208-211.

32. Сурначев М.Ю. Задача целочисленного линейного раскроя: обзор алгоритмов. // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2002. С. 168-171.

33. Сурначев М.Ю. Применение блочных технологий к задаче упаковки контейнера // Мехатроника, автоматизация, управление 2005: Вторая Всероссийская научно-техническая конференция. Сб. тр. Т.2. Уфа: УГАТУ. С.10-12.

34. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм для задачи упаковки. // Моделирование, вычисления, проектирование в условиях неопределенности-2000: Сб.науч.тр. Уфа: УГАТУ, 2000. С.458-459.

35. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм. // Дискретный анализ и исследование операций: Матер, конф. Новосибирск: Изд-во Института математики, 2002. С.237.

36. Сурначев М.Ю., Собко С.Н. Гибридный группирующий генетический алгоритм. // Математическое моделирование в решении научных и технических задач. Выпуск 2. Уфа: Изд-во "Технология", 2001. С.70-75.

37. Тоцков И.Е. Методы решения задачи трехмерной упаковки на базе алгоритма динамического перебора. Рукопись депонирована в ВИНИТИ, № 2589-В99, 1999.

38. Шабрина JI.M. К разработке линейного алгоритма решения задачи трехмерной упаковки// Математическое моделирование в решении научных и технических задач. Уфа, 1994. С.3-5.

39. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization/ // John Wiley&Sons. 1996.

40. Baum S., Trotter Jr.L. Integer rounding for polymatroid and branching optimization problems. // SIAM J. Alg. Disc. Meth. 1981. 2(4). P.416-425.

41. Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of Operational Research. 2002. 141. P.274-294.

42. Bischoff E.E., Marriott M.D. A comparative evaluation of heuristics for container loading // European Journal of Operation Research, 44(1990). P.267-276.

43. Bortfeldt A., Gehring H., Applying tabu search to container loading problems // Operations Research Proceedings 1997, Springer, Berlin, 1998, P.533-538.

44. Bortfeldt A., Gehring H. A hybrid genetic algorithm for the container loading problem. // European Journal of Operation Research, 131(2001). P.143-161.

45. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem // Quaterly Journal of the Belgian, French and Italian Operations Research Societies 2002.

46. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing // CS270 Project Report, Spring 1999.

47. Dykhoff H. A typology of cutting and packing problems // Evropean Journal of Operational research. 1990. Vol. 44. P.145-159.

48. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem // Tech. Rep. 99/13, DIKU, University of Copenhagen, Denmark. Dept. of Computer Science, University of Copenhagen.

49. Folkenauer E. The grouping genetic algorithms for Bin-Packing. JORBEL-Belgian Journal of operations Research, Statistics and Computer Science, 1995. V. 35. P.64-88.

50. Gehring H., Bortfeldt A. Genetic algorithm for solving the container loading problem. // International Transactions in Operation Research 4(5-6). P.401-418.

51. Gilmore P.C. and Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem, Operations Research 9(1961), P.849-859.

52. Gilmore P.C., Gomory R.E. Multistage cutting stock problems of two and more dimensions // Operation Research, 13(1965). P.94-120.

53. Hinxman A. The Trim-Loss and assortment problems: a survey // European Journal of Operational Research. 1980. N11. P.863-888.

54. I.R. Gareev, R.R. Shirgasin, S.N. Sobko, M.Yu. Surnachev. Heurisms for One-Dimensional Bin-Packing Problem // CSIT'2001: Computer Science and Informational Technologies. Ufa: USATU Publishers. - P.263-267.

55. Imahori S., Yaguira M., Ibaraki T. Local Search Heuristics for the Rectangle ' Packing Problem With General Spatial Costs // MIC'2001 4th Metaheuristics International conference. P.471-476.

56. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. // European Journal of Operation Research. 1999. 112. P.413-420.

57. Lodi, S. Martello, D. Vigo. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research 141 (2002). P.410-420.

58. Marcotte O. The cutting stock problem and integer rounding // Math. Program. 1985. 33(1). P.82-92.

59. Martello S. and Toth P. Knapsack problems: Algorithms and Computer Implementations. In: Operations Research. 1990. v. 32. P.983-998.

60. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems // INFOR. 1994. 32(4).

61. Martello S., Pisinger D., Vigo D., The three-dimensional bin packing problem, Operations Research 48 (2000). P.256-267.

62. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. // YOHN WILEY&SONS. Chichester. 1990.

63. Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem // Management Science. 1997. 35. P.64-68.

64. Morabito R., Arenales M., An AND/OR graph approach to the container loading problem // International Transactions in Operational Research 1 (1994). P.59-73.

65. Mukhacheva E., edit. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems)/ The International Scientific Collection. 1997. Ufa. Russia.

66. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V. 3. N4. P.463-476.

67. Pisinger D. Heuristic for the container loading problem // European Journal of Operation Research, 141(2002). P.3 82-392.

68. Rehtenberg I., Evolutionsstrategie: Optimerung Technischer systeme nach Prinzipen der Biologischen Evolution // Stuttgart: Formann-Holzboog Verlag, 1973.

69. Scheithauer G. and Terno J. A Branch-and-Bound Algorithm for Solving One- dimensional Cutting Stock Problems Exactly, Applicationes Mathematicae, 23.2:151-167, 1995.

70. Scheithauer G. and Terno J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. Oper. Res. Proc. 1991, Springer-Verlag, Berlin Heidelberg, P.439-444.

71. Schwerin P., Wascher G. A New Lower Bound for the Bin-Packing Problem and its integration to MTP // Pesquisa Operational. 1999. 19(2). P. 111-131.

72. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.

73. Valeyeva A.F. and Totskov I.E. Developed of Three-Dimensional Methods Decision Making under Conditions of Uncertainty (Cutting-Packing Problems). Ufa, 1998.- P.198-206.

74. Valeyeva A.F., Agliullin M.N. Ant Colony Algorithm for the 2-D Bin-Packing Problem: Numerical Study // Proceedings of the 5th International Workshop on Computer Science and Information Technologies, 2003. P.l 10-114.

75. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional. 2000. V. 20. N2. P.233-247.

76. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999. 19(2).