Аннотация 2
ВВЕДЕНИЕ 3
1 Постановка задачи 4
1.1 Описание задачи 4
1.2 Описание предметной области 4
1.3 Математическая модель задачи 6
2 Методы решения задачи 20
2.1 Метод размещения прямоугольников на плоскость 21
2.2 Модификация метода размещения прямоугольников на плоскость 26
2.3 Метод, основанный на применении генетического алгоритма 32
2.3.1 Начальный этап работы алгоритма 33
2.3.2 Одноточечный кроссовер порядка 34
2.3.3 Одноточечная мутация порядка 37
2.3.4 Селекция 37
3 Разработка программы, предназначенной для решения задачи оптимальной упаковки
груза в контейнер 39
3.1 Средства разработки программы 39
3.2 Выбор алгоритма нахождения решения задачи 39
3.3 Алгоритм последовательного размещения параллелепипедов в контейнер 40
3.4 Генетический алгоритм нахождения наилучшего порядка размещения
параллелепипедов 42
3.5 Архитектура программы 43
3.5.1 Общий принцип работы программы 43
3.5.2 Описание основных структур данных 44
3.5.3 Описание основных переменных 47
3.5.4 Описание основных функция 48
3.5.5 Правила ввода-вывода 49
3.5.6 Обработка ошибок 50
ЗАКЛЮЧЕНИЕ 54
ЛИТЕРАТУРА 55
ПРИЛОЖЕНИЕ А 58
ПРИЛОЖЕНИЕ Б 61
Работа посвящена созданию программы, которая позволит решить задачу трехмерного размещения набора параллелепипедов в контейнер при наличии ограничений. Реальным примером такого размещения является оптимальное размещение груза в прицеп фуры. Эта задача является важной и актуальной в логистике и транспортной отрасли. Для эффективного ведения транспортного бизнеса необходимо перевозить максимальное количество товара с минимальными издержками. Благодаря алгоритму размещения, пользователь получит возможность оптимально упаковать нужный груз в контейнер для транспортировки, избежать перевеса транспортного средства, потери его устойчивости на дороге. Это позволит уменьшить износ транспортного средства, избежать штрафов за перевес, снизить расходы на транспортировку грузов, а также увеличить безопасность участников дорожного движения.
Решение задачи оптимального размещения груза в прицепе фуры может быть достигнуто с помощью математических моделей и сочетание принципов работы генетических и жадных алгоритмов. Такие модели могут учитывать множество факторов, таких как размеры грузов, вес, форму, характеристики прицепа и дороги.
Актуальность исследования данной темы обуславливается тем, что задача трехмерной упаковки параллелепипедов в контейнер является ЫР-трудной, и не представляется возможным получить для нее детерминированный алгоритм, который бы позволил находить точное решение этой задачи за приемлемое время.
Цель данной работы заключается в разработке прикладной компьютерной программы, предназначенной для получения решения задачи трехмерной упаковки параллелепипедов в контейнер.
Задачами данной работы являются:
1. Изучить предметную область;
2. Составить математическую модель задачи;
3. Определить ограничения задачи;
4. Определить входные данные для решения задачи;
5. Изучить существующие методы последовательного размещения параллелепипедов в контейнер;
6. Модифицировать метод под специфику задачи;
7. Создать интерфейс программы;
8. Создать программу;
В рамках данной работы были изучены существующие методы приближенного решения ЫР-трудной задачи трехмерной упаковки прямоугольников в контейнер, принципы работы генетического алгоритма, создана модификация жадного алгоритма для решения задачи расчета размещения груза в полуприцеп грузового транспортного средства. Впоследствии была спроектирована и реализована прикладная программа для получения приближенного решения этой задачи. Поскольку рассматриваемая задача является ЫР- трудной, исследования в области приближенных методов ее решения не теряют своей актуальности. В качестве реализуемого в программе способа поиска приближенного решения был выбран метод, основанный на сочетании алгоритма размещения прямоугольников в контейнер и генетического алгоритма поиска наилучшего порядка размещения груза в полуприцеп ТС. Выбор обоснован тем, что генетические алгоритмы дают хорошие результаты при решении оптимизационных задач с большим количеством входных данных и, в частности, стойки к сходимости к локальному оптимуму целевой функции [16].
На основе анализа предметной области и существующих решений был сделан вывод о том, что задача размещения груза в полуприцепе является сложной и важной задачей, которая требует комбинаторного подхода и применения различных методов оптимизации.
Программа предоставляет пользователю возможность ввести заранее подготовленные данные, задать различные условия задачи. Кроме того, пользователь может изменять параметры генетического алгоритма для получения наилучшего результата. Это, несомненно, расширяет возможности прикладного использования программы. После введения всех входных данных приложение осуществляет поиск решения, и в случае успеха демонстрирует пользователю найденный наилучший способ размещения груза в полуприцеп ТС, что позволяет быстро и наглядно получить представление о качестве полученного решения. Также приложение может оценивать корректность введенных пользователем данных и выдавать рекомендации по устранению ошибок в работе алгоритма, что, несомненно, упрощает использование приложения при решении прикладных задач.
Продолжение исследований в данной области однозначно имеет смысл, ввиду ЫР- трудности задачи трехмерного размещения параллелепипедов в контейнер, что на данный момент означает невозможность раз и навсегда получить для нее совершенный способ получения наилучшего решения.
