Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем
Проблема оптимального раскроя-упаковки объединяет различные по математической и прикладнойостановке задачи. В литературе они встречаются под разными названиями: задачи раскроя, упаковки, размещения, загрузки, распределения ресурсов и т. д. Общим для них является наличие двух групп объектов. К первой группе относятся большие объекты, ко второймалые. Требуется установить соответствие и порядок… Читать ещё >
Содержание
- Глава 1. Задачи одно и двухмерного раскроя-упаковки и методы их решения
- 1. 1. Классификация задач раскроя-упаковки
- 1. 2. Задача одномерной целочисленной упаковки
- 1. 2. 1. Математические модели одномерного раскроя-упаковки
- 1. 2. 2. Методы решения задач линейного раскроя-упаковки, основанные на использовании линейного программирования
- 1. 2. 3. Эвристические методы расчета одномерного раскроя-упаковки
- 1. 2. 4. Точные методы расчета одномерного раскроя-упаковки
- 1. 3. Задача прямоугольной упаковки
- 1. 3. 1. Постановка задачи прямоугольной упаковки
- 1. 3. 2. Эвристические методы решения задачи прямоугольной негильотинной упаковки
- 1. 3. 3. Точные методы решения задачи негильотинного прямоугольного раскроя
- 1. 4. Постановка задачи исследования
- 1. 5. Основные результаты главы
- Глава 2. Задачи одномерного целочисленного раскроя-упаковки: вычислительный эксперимент
- 2. 1. Краткая характеристика исследуемых методов решения одномерного раскроя-упаковки
- 2. 1. 1. Метод первый подходящий с упорядочиванием (FFD)
- 2. 1. 2. Метод последовательного уточнения оценок (SVC)
- 2. 1. 3. Модифицированный метод ветвей и границ (МКК)
- 2. 2. Эксперименты для одномерного раскроя-упаковки с методами SVC и SVCR
- 2. 2. 1. Тестовые задачи
- 2. 2. 2. Результаты эксперимента с методами SVC и ISVCR
- 2. 3. Эксперимент для одномерного раскроя-упаковки с методом МКК
- 2. 3. 1. Тестовые задачи
- 2. 3. 2. Результаты эксперимента с методом МКК
- 2. 1. Краткая характеристика исследуемых методов решения одномерного раскроя-упаковки
Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем (реферат, курсовая, диплом, контрольная)
Проблема оптимального раскроя-упаковки объединяет различные по математической и прикладнойостановке задачи. В литературе они встречаются под разными названиями: задачи раскроя, упаковки, размещения, загрузки, распределения ресурсов и т. д. Общим для них является наличие двух групп объектов. К первой группе относятся большие объекты, ко второймалые. Требуется установить соответствие и порядок назначения между ними так, чтобы некоторая целевая функция достигала минимум при выполнении определенных ограничений.
Диссертационная работа посвящена разработке алгоритмов для решения задач плотной упаковки прямоугольных объектов в прямоугольной области на основе ее линейной аппроксимации. Эта задача является ИР-трудной и отыскание даже псевдополиномиального точного алгоритма для ее решения невозможно. Поэтому наряду с громоздкими точными алгоритмами получили широкое распространение различные эвристики. От эвристических алгоритмов требуется хорошее приближение к точному решению и быстрота исполнения. Этим качеством удовлетворяют алгоритмы, основанные на линейной аппроксимации. Однако, задача линейного раскроя, аппроксимирующая прямоугольную упаковку, так же является ЫР-трудной. В связи с этим выбор подходящего алгоритма для ее решения так же представляет определенные трудности. Этим обстоятельством и объясняется научная актуальность проблемы в целом. Что касается актуальности работы на практике, то ее трудно переоценить. Создание быстрых и достаточно точных алгоритмов позволит решать массу практических задач, связанных, так или иначе, с использованием материальных ресурсов. Что является особенно актуальным на фоне современной тенденции сохранения и сбережения природных ресурсов.
Диссертация посвящена разработке и исследованию эффективности приближенных эвристических алгоритмов для решения задачи прямоугольной упаковки: аппроксимации линейным раскроем с целью получения начального решениясозданию детерминированного и стохастического алгоритмов продолжения и оценки улучшенного решенияпроведению и анализу вычислительных экспериментов.
Научная новизна диссертационной работы заключается в следующем:
• разработаны методы и условия аппроксимации прямоугольной упаковки линейным раскроем;
• предложены нижние границы для оценки полученных решений;
• разработан быстрый детерминированный алгоритм улучшения начального решения с использованием топологических свойств упаковок;
• разработан генетический алгоритм улучшения начального решения;
• исследована эффективность алгоритмов линейного раскроя и прямоугольной упаковки.
Предложенные в диссертации алгоритмы ориентированы на широкий класс прикладных задач. Их адаптация к конкретным производственным условиям не представляет особого труда. Это и составляет практическую значимость работы.
Работа выполнялась по заданию ФЦП «Интеграция», проект 76, а также на завершающем этапе при поддержке Российского Фонда Фундаментальных Исследований, проект 99−01−937.
Результаты работы докладывались и обсуждались: на конференции «Математическое программирование и приложения» в 1997 и 1999 годахинституте математики и механики УрО АН РФ, г. Екатеринбургна международной конференции «Проблемы оптимизации и экономические приложения», в 1997 г. институте математики СО РАН РФ, г. Омскна международной научной конференции «Оптимизация численных методов» в 1998 г. институте математики ИМВЦ УНЦ РАНна международной сибирской конференции по исследованию операций, ИМ СО АН РФ, 1998 г.- на XVIII международной конференции «Исследование операций», г. Брюссельна научных семинарах ИМ БФ АН РФматематического факультета БГУ и кафедры вычислительной математики и кибернетики УГАТУ, кафедры «исследования операций» С. Петербургского государственного университета.
Диссертация состоит из введения, четырех глав, списка цитируемой литературы и приложения.
4.3. Основные результаты и выво л главы 4
1. В рамках проведенных экспериментов была — одтверждена следующая гипотеза: «эффективность алгоритма определяется параметрами задачи по ширине и мало зависит от параметров задачи по ине».
2. Показано, что эффективность разработанных ал горитмов плотной упаковки на базе аппроксимации линейным раскроем, а к jhho детерминированного «перестройка» (REC) и стохастического «генетического» (GEN), значительно выше известных эвр, ических алгоритмов «последовательного уточнения оценок» (SVC) i. < динамического перебора" (DS).
3. Замечено, что эффективность разработанного алгоритма REC возрастает с увеличением заготовок по ширине.
4. Была исследована эффективность различных схем реализации генетического алгоритма, касающаяся процедуры скрещивание. И выявлено, что лучшие результаты дает алгоритм с более простой процеду рой скрещивания.
5. Для эвристических алгоритмов (SVC, DS, R 1 J, GEN) решения задач прямоугольной упаковки выявлены классы al-оч /¦ > трудные, alтрудные и al-легкие.
ЗАКЛЮЧЕНИЕ
1. На базе линейной аппроксимации разработаны два эвристических алгоритма для решения задачи прямоугольной упаковки: REC (перестройка) и GEN (генетический). С этой целью:
1.1. введено понятие прямоугольно ориентированного линейного раскроя (ROLC), сформулированы и доказаны необходимые и достаточные условия для ROLC;
1.2. введены понятия ослабленного (d.ROLC) и сильно ослабленного (e.d.ROLC) прямоугольно ориентированного линейных раскроев, разработаны алгоритмы их построения;
1.3. рассмотрены топологические свойства прямоугольных упаковок, сформулированы и доказаны необходимые и достаточные условия эквивалентности d. ROLC и ROLC;
1.4. предложены новые нижние границы RP, позволившие более точно оценивать эффективность алгоритмов и находить хорошее начальное приближение;
1.5. произведено структурирование d. ROLC и определение генетических элементов: гена, аллели, локуса, хромосомы, особи;
1.6. введены генетические процедуры скрещивания, мутации, селекции.
2. Произведены вычислительные эксперименты с ВРР и RP задачами. Анализ результатов экспериментов позволил сделать следующие выводы:
2.1. алгоритм SVCR для решения задачи линейного раскроя вполне ориентирован на решение задачи d. ROLC: с его помощью определяется приближенная нижняя граница RP и начальное решение, которое принимается в качестве верхней границы;
2.2. алгоритмы REC и GEN полиномиальной сложности превосходят по своей эффективности (трудоемкость и близость к оптимуму) ранее разработанные алгоритмы FFD, SVC и DS;
2.3. генетический алгоритм значительно превосходит по эффективности и трудоемкости все рассмотренные алгоритмы.
Список литературы
- Arenales M.N., Morabito R.N. An AND/OR graph approach to the solution of two-dimensional non-guillotine cutting problems. European Journal of Operational Research. 1995, vol.84, pp.559−617.
- Arenales M.N., Morabito R.N. An AND/OR-graph approach to cutting and packing problems. Decision Making under Conditions of Uncertainty (Cutting -Packing Problems). The International Scientific Collection. Ufa. 1997. p. 207−225.
- Beasley J.E. An exact two-dimensional non-guillotine cutting tree search procedure. Operational Research. 1985, vol.33, pp.49−64.
- Belov G. A modified sequential values correction method for the one-dimensional cutting stock problem. // Decision Making under Conditions of Uncertainty (Cutting-Packing Problems). The International Scientific Collection. Ufa. 1997. p. 41−47.
- Dudzinski K., Walukiewicz S. Exact methods for the knapsack problem and its generalizations. European Journal of Operational Research. 1987. vol.28, pp.3−21.
- Dyckhoff H. A Typology of Cutting and Packing Problems. //European Journal of Operational Research. 1990.v.44.p.l45−159.
- Falkenauer E. The Grouping Genetic Algorithms Widening the Scope of the Gas. JORBEL — Belgian Journal of Operations Research, Statistics and Computer Science, 1993, vol. 33 (1,2), pp. 79−102.
- Falkenauer E. The Grouping Genetic Algorithms for Bin Packing. JORBEL -Belgian Journal of Operations Research, Statistics and Computer Science, 1995, vol. 35, pp. 64−88.
- Galambus G., Van Vliet A. Louwer bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. Computing vol. 52, pp. 281−297.
- Garey M.R., Jonson D.S. Computersand Intractability: A Guide to the Theory of NP-Completeness. // Freeman. San Francisco. CA. 1979.
- Gau T., Wascher G. CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. European J. Oper. Res. 1995, 84, p.572−579.
- Gehring H., Bortfeldt A. A Genetic Algorithm for Solving the Container Loading Problem. // International transactions in operational research. 1997, vol.4, № 5/6, p. 401−418.
- Khan L.R. An exchange heuristic for the bin packing problem. For presentation at the Triennial conference of IFORS. Vancouver, British Columbia, Canada, Juli 812, 1996.
- Marcotte O. The cutting stock problem and integer rounding. Mathematical Programming, 33(1): 82−92,1985
- Martello S., Toth P. Lower Bounds and Reduction Procedures for the Bin Packing Problem. Discrete Applied Mathematics. 1990, vol. 22. North-Holland, Elsevier Science Publishers B.V., pp.59−70.
- Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. John Wiley, Chichester. Ong H.L., Magazine M.J. and Wee T.S. (1984) Probabilistic analysis of bin packing heuristics. // Operations Research. 1990. v. 32. p. 983−998.
- Martello S., Vigo D., Exact solution of two-dimensional finite bin packing problem. Management Science. 1997, vol. 35, pp. 68−74.
- Mukhacheva E.A. One-dimensional bin packing problems. Models and methods. Decision Making under Conditions of Uncertainty (Cutting Packing Problems). The International Scientific Collection. Ufa. 1997. p. 7−14.
- Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems. // International Journal of Software Engineering and Knowledge Engineering. 1993. v. 3. № 4. p. 463−476.
- Richter K. Solving sequential interval cutting problems via dynamic programming. European Journal of Operational Research. 1992, vol.57, pp.332 338.
- Scheithauer G. The solution of packing problems with piece of variable length and additional allocation constraints. Optimization. Vol 34, pp. 81−96.
- Scheithauer G., Terno J. The modified integer round-up property of the one-dimensional cutting stock problem. European J. Oper. Res., 84: 562−571,1995.
- Scheithauer G., Terno J. Theoretical investigation on the modified integer roundup property of the one-dimensional cutting stock problem. Technical report, MATH-NM-23−1995, TU Dresden, 1995.
- Scheithauer G, Terno J. A heuristic approach for solving the multi-pallet packing problem. Decision Making under Conditions of Uncertainty (Cutting Packing Problems). The International Scientific Collection. Ufa.1997. p. 140−155.
- Schwerin P., Wascher G. The Bin-Packing Problem: A problem Generator and
- Some Numerical Experiments with FFD Packing and MTP. // International Transactions in Operational Research. 1997.v. 4. № 5/6. p.337−389.
- Serker B.R., An optimum solution for one-dimensional slitting problems: a dynamic programming approach. European Journal of Operational Research. 1988, vol.39, pp.749−755.
- Simchi-Levi D. New worst-case results for the bin packing problem. Naval Res. Log.Quart. 1994. vol.41, pp. 579−585.
- Sinuany-Stern Z., Weiner I. The one-dimensional cutting stock problem using two objectives. Journal of Operational Research. 1994, vol.45, pp.231−236.
- Stadtler H. A comparison of two optimization procedures for 1- and 1,5-dimensional cutting stock problems. Oper. Res. Spekt. 1988,10, p.97−111.
- Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre prakti-sche Losung. -Leiprig, 1987, p.207.
- Van Driessche R., Piessens R. Load Balancing With Genetic Algorithms. Proceedings of the second Conference on Parallel Problem Solving from Nature (PPSN2), Brussels, Belgium, September 28−30, 1992.
- Vasko F.J., Cregger M.L., Newhhart D.D., Stott K.L. A real-time one-dimensional cutting stock algorithm for balanced cutting patterns. Oper. Res. Lett. 1993, 14, p.275−282.
- Von Laszewski G. Intelligent Structural Operators for the k-way Graph Partitioning Problem. Proceedings of the Fourth International Conference on Genetic Algorithms. San Diego, July 13−16, 1991.
- Wascher G., Gau T. Heuristics for the one-dimensional cutting stock problem: a computational study. Oper. Res. Spekt. 1996,18, p.131−144.
- Аккуратов Г. В., Березнев B.A., Брежнева O.A. О методе решения уравнения с булевыми переменными. Принятие решений в условиях неопределенности: межвуз. научный сб. Уфа, 1990. с. 145−146.
- Батищев Д.И. Генетические алгоритмы решения экстремальных задач. /Под ред. Академика АЕН Я. Е. Львовича: Учеб. Пособие. Воронеж. Гос. Техн. Унт- Нижегородский гос. Ун-т. Воронеж, 1995. 69 с.
- Бронштейн Е.М., Валеева А. Ф., Мухачева Э. А. Линейный способ построения прямоугольной упаковки. Оптимизация, Новосибирск, ИМ СЩ РАН, 1993, вып.51(69). с.34−42.
- Бухвалова В.В. Реализация метода зон Липовецкого для прямоугольного раскроя. Математическое обеспечение рационального раскроя в системахавтоматизированного проектирования. Тезисы докл. всесоюзной конференции. Уфа, 1987, с. 16−17.
- Вайнштейн А.Д. Задачи об упаковки прямоугольников в полосу (обзор) // Управляющие системы, ИМ СОАН СССР, 1984, вып.25.
- Валеева А.Ф. Негильотинный прямоугольный раскрой на базе применения методов математического программирования в автоматизированных системах управления. Диссертация на соискание ученой степени кандидата технических наук. Уфа, 1993 г.
- Валеева А.Ф. Алгоритм прямоугольной упаковки и применение его к задаче фигурного раскроя. // Труды международной конференции по прикладной и индустриальной математике. Новосибирск, ИМ СО РАН, 1997, с.46−56.
- Гери М.П., Джонсон Д. С. Вычислительные машины и трудноразрешимые задачи. -М.- Мир, 1987. -272с.
- Канторович JI.B., Залгаллер В. А. Рациональный раскрой промышленных материанов. -Новосибирск: Наука СО, 1971. -320с.
- Картак В.М. Модели и методы оптимизации упаковки N-мерных параллелепипедов. Диссертация на соискание ученой степени кандидата физико-математических наук. Уфа, 1999 г.
- Кацев C.B. Об одном классе дискретных минимаксных задач. Кибернетика, 3, Киев, 1979,113−118.
- Кофман А. Введение в прикладную комбинаторику. -М. Наука, Гл. ред. физ.-мат. лит., 1975. -447 с.
- Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя. Свердловск: Уро АН СССР, 1988. -50 с.
- Липовецкий А.И. К оптимизации свободного размещения прямоугольников. Автоматизация проектирования в машиностроении. Минск: ИТК АН БССР, 1985. с. 80−87.
- Липовецкий А.И. Алгоритмы негильотинного прямоугольного раскроя. Математическое обеспечение рационального раскроя в САПР: Материалы всесоюзной конференции: Уфа, 1988, с. 72−79.
- Мухаметзянов Р.З. Структурные преобразования прямоугольных упаковок.. //Рук. Деп. в ВИНИТИ. № 53-В99. от 18.01.1999. -15 с.
- Мухачева A.C. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем. // Рук. Деп. в ВИНИТИ. № 53-В99. от 14.01.1999. -18 с.
- Мухачева Э.А. Рациональный раскрой промышленных материалов: Применение АСУ. -М.Машиностроение, 1984. -176с.
- Мухачева Э.А., Верхотуров М. А., Мартынов В. В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа, 1998. -216с.
- Мухачева Э.А., Мухачева A.C. Методы генерации прямоугольной упаковки на базе аппроксимации линейным раскроем. // Информационный бюллетень № 8. Конференция Математическое программирование и приложения (тезисы докладов). Екатеринбург. 1999., 205−206с.
- Мухачева Э.А., Рубинштейн Г. Ш. Математическое программирование. -Новосибирск: Наука. -1987. -274с.110
- ГРАФИК ПОВЕДЕНИЯ АЛГОРИТМА SVCR
- Элементов т = 80- Нижняя граница N0 = 30- Оптимальное решение Nonm = 30
- Итерации N опт = 30, N о = 301. Ширина полосы W=255−1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
- Ми 38 39 39 39 40 41 41 42 43 45 45 45 45 46 46 47 48 48 50 51и 123 58 112 124 70 40 96 100 111 117 114 67 69 82 89 104 39 38 47 1001. АЛГОРИТМ ИКСхо хз 9 15 Х6 б 18 1 г 14 XX 8 4 5 12 Х9 1. X 2 20 7 3
- Метод: Первый подходящий о перестройкой <�сверху вниз) Нижняя граница = 3 08
- Длина = 310 Ширина. = 255 Отн< Ю = Ю1 Вреия (сех/ЮО) = 6Х1. АЛГОРИТМ GEN
- Генетический Алгоритм .А 1трио1од.1×11. Файл Настройки Помощь