Алгоритмы оптимизации загрузки транспортных средств

Аннотация

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

Общая постановка проблемы

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

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

Анализ методов и алгоритмов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

Список использованной литературы

1. О.В. Корчевская. Диссертация «Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов». СГТУ, 2009г. – 147с.
2. В.В. Псиола. Диссертация «Об одном приближении плотной упаковки». МГУ имени М.В. Ломоносова, 2011г. -143с.
3. В.В. Курейчик, Д.В. Заруба, Д.Ю. Запорожец «Применение генетического алгоритма решения задачи трехмерной упаковки», «Известия ЮФУ. Технические науки»,2012г. - 264с.
4. О.А. Александрова, А.И. Секирин, «Оптимизация грузовых перевозок с использованием генетических алгоритмов», ДонНТУ, 2009г. ¬