Реферат по теме выпускной работы

Содержание

• Введение


• 1. Актуальность темы


• 2. Цель и задачи исследования, планируемые результаты


• 3. Обзор исследований и разработок


• 3.1 Обзор международных источников


• 3.2 Обзор национальных источников


• 3.3 Обзор локальных источников


• 4. Анализ аналогичных систем


• 5. Математическая постановка задачи трёхмерной упаковки


• Выводы


• Список источников

Введение

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

1. Актуальность темы

Упаковка коробок в контейнер, кузов транспортного средства или на паллету является одной из самых сложных проблем упаковки из-за ограничений, которые возникают в реальном мире. [10] Было установлено, что эта задача является NP-полной. Все точные алгоритмы, решающие задачу об упаковке, используют полный перебор всех возможных решений. В следствии чего, даже при небольшом количестве грузов, программа будет работать неприемлемо большое количество времени. Так же проблемой является набор дополнительных ограничений, которые должны быть выполнены при расстановке груза в заданном объеме. Таким образом, создание приближенных алгоритмов, которые за приемлемое время находят решение, близкое к оптимальному, с учетом дополнительных ограничений является актуальной задачей.

2. Цель и задачи исследования, планируемые результаты

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

Планируется решить следующие задачи:

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

2. Разработать математическую модель размещения груза с условием ограничений;

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

4. Экспериментально проверить эффективность работы алгоритма.

Объектом исследования является процесс погрузки товаров в транспортное средство.

Предметом исследования является определение оптимального размещения грузов внутри заданного объема транспортного средства.

3. Обзор исследований и разработок

В ходе анализа работ, посвященных созданию моделей и алгоритмов трёхмерной упаковки определено, что для решения подобных задач используют, в основном, эвристические подходы. В литературе наиболее часто упоминаются следующие эвристические алгоритмы: итерационный локальный поиск (Iterative Local Search, ILS); направленный локальный поиск (Guided Local Search, GLS); поиск с переменной окрестностью (Variable Neighborhood Search, VNS); вероятностный жадный алгоритм (GRASP); эволюционный алгоритм (Evolutionary Algorithm, EA); генетический алгоритм (Genetic Algorithms, GA); алгоритм оптимизации муравьиной колонии (Ant Colony Optimization, ACO); имитация отжига (Simulated Annealing, SA); поиск с запретами (Tabu Search, TS). [9] По сравнению с числом всевозможных эвристик, количество точных алгоритмов решения трехмерной задачи упаковки в контейнер ограничено. Одна из причин этого заключается в сложности представления вероятной упаковки и введения ограничений из реальных задач. Даже если такой метод решения найден, остается сложность в формулировке решения, зачастую являющимся большим из-за числа коробок и контейнеров. [10]

Большинство из них базируется на декомпозиции исходной задачи и сведению ее к задачам меньшей размерности путём разбиения на слои и заполнением каждого слоя какой-либо эвристикой. Некоторые алгоритмы используют двухфазные процедуры. На первой фазе происходит упаковка коробок в слои, на второй – процесс обмена коробок внутри слоя для улучшения локального решения. [1]

3.1 Обзор международных источников

В работах зарубежных авторов решение проблемы размещения грузов внутри транспортного средства встречается совместно с решением проблемы построения маршрутов, так называемая задача коммивояжёра. При решении транспортной задачи выделяется 2L-CVRP и 3L-CVRP. Задачи класса 2LCVRP рассматривают двумерное размещение объектов, 3L-CVRP (Three-Dimensional Loading Capacitated Vehicle Routing Problem) соответственно трехмерное.

Например, в работах [4] и [5] используется гибридный алгоритм решения 3L-CVRP, состоящий из алгоритма поиска с запретами для составления маршрутов транспортных средств и алгоритма подчиненного дерева поиска для загрузки ящиков всех клиентов в грузовое пространство автомобиля.

3.2 Обзор национальных источников

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

1. Данные для укладки (список ящиков) передаются алгоритму комбинирования ящиков в блоки;

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

3. Сформированный набор блоков передается в алгоритм 3-x мерной укладки, который состоит из 3 частей:

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

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

в) третья часть является применением алгоритма 2-х мерной укладки к выбранной плоскости и допустимому набору блоков для укладки в эту плоскость;

4. Алгоритм 3-х мерной укладки выполняется до тех пор, пока не уложены все ящики заказа и в ТС остается свободный объем для укладки ящиков;

5. После того как все ящики уложены или объем полностью заполнен, расчет оптимальной укладки ящиков в ТС считается завершенным. [2]

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

Абсолютно иной подход к этой задаче предлагается в работе «Применение генетического алгоритма решения задачи трехмерной упаковки» авторами которой являются В.В. Курейчик, Д.В. Заруба, Д.Ю. Запорожец. Предложенный алгоритм упаковывает грузы не послойно. Это предложенное решение позволяет размещать все грузы внутри контейнера вместе. Достигается это путем того, что используется модифицированный генетический алгоритм, который позволяет работать с закодированным решением (хромосомой), которая соответствует размещению ящиков внутри контейнеров. То есть каждая хромосома хранит информацию по расположению и размерам всех блоков, что позволяет в ходе работы алгоритма искать оптимальное расположение грузов внутри ТС. [3] Таким образом длина хромосомы равна количеству грузов.

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

Так же для решения задач такого плана известен метод плоскостей, представленный в работе О.В. Корчевской.

Особенностями этого метода являются:

- непосредственное решение задач, а не сведение их к задачам меньшей размерности;

- использование как слойной, так и бесслойной стратегий;

- заполнение по, так называемым, приоритетным осям;

- анализ пустот и рассмотрение способов их объединения;

- допускается использование не одного, а нескольких параллелепипедов.

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

3.3 Обзор локальных источников

В Донецком национальном техническом университете вопросами оптимизации погрузки товаров занимался Трубачев Д.С. Он занимался задачей распределения грузов внутри воздушного транспортного средства. В его работе рассматривалась проблема погрузки с ограничениями грузоподъемности самолета. Были предложены 4 метода для решения данной задачи: полный перебор, метод ветвей и границ, метод динамического программирования, генетический алгоритм. [8]

4. Анализ аналогичных систем

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

Так же похожим функционалом обладает сервис расчета загрузки на сайте www.searates.com. Это портал, посвященный морским грузоперевозкам. На нем имеется калькулятор загрузки, который позволяет получить приближённо оптимальное расположение грузов внутри контейнера.

5. Математическая постановка задачи трёхмерной упаковки

Дана область трехмерного пространства шириной W, длиной L и высотой H – контейнер для погрузки с открывающийся сзади частью размерами H×W для загрузки и разгрузки товаров и грузоподъемностью D. Также дано множество блоков N. Все множество блоков разбито на множество типов T. Каждый тип определяет геометрические параметры, вес, ценность и ряд других параметров блоков. Требуется рассчитать точное положение блоков в заданном объеме таким образом, чтобы его заполнение было допустимым и эффективным, то есть суммарный объем поместившихся блоков должен быть максимален. Допустимым положением блока считается такое, когда все упакованные блоки находятся внутри заданного объема, не пересекаются и опираются на дно и стенки других блоков.

Ограничениями могут служить:

1. Суммарный объем элементов не должен превышать объема транспортного средства.

2. Ни один элемент не может выходить за границы заданного объема.

3. Занимаемый вес не может превышать грузоподъёмность транспортного средства.

4. Коробки могут размещаться только таким образом, чтобы их грани были параллельны стенам контейнера.

5. Коробки не должны пересекаться друг с другом.

Целевая функция:

F = (x_max - x_min) * (y_max - y_min) * (z_max - z_min) , F →min,

где точки (x_min, y_min, z_min) и (x_max, y_max, z_max) – точки, определяющие описывающий параллелепипед блоков.

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

1. Блоки могут иметь только форму параллелепипеда

2. Заполнение объема ТС блоками происходит от дальней стенки к ближней.

3. Упакованы могут быть только те блоки, которые проходят в дверной проем транспортного средства шириной W1 и высотой H1.

4. Упакованы могут быть только те блоки, которые полностью помещаются в контейнере.

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

- ограничение на хрупкость предметов: нехрупкие предметы не могут быть размещены сверху хрупких;

- ограничение на ориентацию и повороты коробок;

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

Для реализации данной задачи в ходе анализа методов был выбран модифицированный генетический алгоритм.

Выводы

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

Замечания

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

Список источников

1. Корчевская О.В. Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов, Диссертация // СГТУ, 2009 г. – 147с.
2. Псиола В.В. Об одном приближении плотной упаковки, Диссертация // МГУ имени М.В. Ломоносова, 2011 г. – 143с.
3. Курейчик В.В., Заруба Д.В., Запорожец Д.Ю. Применение генетического алгоритма решения задачи трехмерной упаковки // Известия ЮФУ. Технические науки, 2012 г. - 264с.
4. Bortfeldt A. A hybrid algorithm for the capacitated vehicle routing problem with threeв dimensional loading constraints // — Режим доступа:ftp.fernuni-hagen.de/pub/fachb/wiwi/winf/forschng/publi/DBFakWiWI460.pdf
5. Ruan Q., Ruo Q., Woghiren K., Miao L. A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints //  — Режим доступа: ntl.bts.gov/lib/37000/37900/37921/A_hybrid_genetic_algorithm_for_the_vehicle_routing_problem_with_three-dimensional_loading_constraints.pdf
6. Сайт компании Packer3d // — Режим доступа: packer3d.ru
7. Сайт компании Searates // — Режим доступа: searates.com
8. Трубачев Д. С. Система формирования динамического расписания рейсов, с учетом воздушных ресурсов авиакомпании // — Режим доступа: masters.donntu.ru/2013/fknt/trubachev/
9. Кощеев И.С. Оптимизация доставки груза потребителям с учетом его размещения внутри транспортных средств на основе эвристических методов. Диссертация // — Режим доступа: www.ugatu.ac.ru/assets/files/documents/dissov/03/2014/KoshcheevIS/diss.pdf
10. Юдаков П.В. Задача о трехмерной упаковке и методы ее решения. Обзор // Инженерный вестник № 06, июнь 2015 г.
11. Лобкова А.А., Секирин А.И. Алгоритмы оптимизации загрузки транспортных средств // Международная научно-техническая конференция студентов и молодых учёных Компьютерная и программная инженерия, декабрь 2015 г.