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

Автор: Сабитов К.А., Новиков Д.Д.

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

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

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

Методы и алгоритмы решения задач загрузки.

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

Задача о рюкзаке является одной из задач комбинаторной оптимизации. Постановка задачи следующая: имеется набор из N предметов, каждый предмет имеет массу W_i и полезность V_i, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W – вместимость рюкзака. Полагают что W_i, V_i, W, P – целые неотрицательные числа, однако могут встречаться и другие условия [1].

Для конечного множества предметов Q={q₁,q₂,…,q_n}, где для каждого q∈Q определена стоимость v_i и вес w_i, нужно найти максимум (1.1) при ограничениях (1.2), где W – вместительность рюкзака, при этом x_i∈(x₁, x₂,…,x_n), где x_i = 1, если предмет был взят в рюкзак, x_i = 0 если нет.

$\sum _{i=1}^n{v}_i*x_i$ (1.1)

$\sum _{i=1}^n{w}_i*x_i\le W$ (1.2)

Задача об упаковке в контейнеры заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими [2].

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

Пусть дано множество объектов A={a_1,a_2,…,a_n}, каждый элемент a_i имеет вес w_i∈(0,1]. Множество контейнеров B={B_1,B_2,…B_m }, объем каждого контейнера Bj равен 1. Найти такое разбиение элементов, что каждая часть множества элементов упакована в один и тот же контейнер с учетом ограничения при этом общее число использованных контейнеров минимизируется.

Могут, рассматриваться различные типы элементов: прямоугольные элементы, 2D элементы, элементы с неправильной формой, элементы различного размера, составные 2D элементы (включая элементы с общими компонентами). 3D элементы, многоразмерные элементы, элементы в виде цилиндров, элементы в виде кругов и др.

Задача трехмерной упаковки, основанной на эвристических процедурах. Для решения задачи рассматриваемым методом возможны два критерия оптимизации:

1. N – число элементов, упакованных в заданный объем.
2. V – объем, требующийся для упаковки всех элементов.
   Создателем метода в постановке задачи приводятся следующие ограничения.
   • Ни один элемент не может выходить за границы заданного объема.
   • Суммарный объем элементов не должен превышать объема области упаковки.
   • Отсутствие пересечений.

Критерием оптимизации является отношение суммы объемов всех элементов к общему объему упаковки [1]. Целевая функция имеет вид (1.3):

$ЦФ=\frac{\sum _{i=1}^n{x}_i*y_i*z_i}{m_x*m_y*m_z}$ (1.3)

Задача трехмерной упаковки, основанной на работе генетического алгоритма.

Генетические алгоритмы предназначены для решения задач оптимизации. Часто они используются при решении NP-трудных задач.

Автор метода выделяет целевую функцию (1.4), однако отмечает, что она не полностью учитывает все критерии задачи трехмерной упаковки. В работе предлагается многокритериальная ЦФ.

$\frac{{\sum }_{i=1}^n{V}_i}{V}*Q^1+P^2*Q^2+P^3*Q^3+P^4+Q^4$ (1.4)

Математическая модель решения задачи загрузки транспортного средства.

Выразим объем V пространства кузова, используя известные параметры:

V = W * H * L (1.5)

Пусть товар, предназначенный для погрузки, задан множеством блоков B = {b₁, b₂, … b_n}, размером N. Каждый блок b_i можно описать следующими параметрами: ширина w_i, высота h_i, длина l_i, вес p_i, стоимость c_i и др. Также можно выразить объем каждого блока, зная его параметры:

V_i = w_i * h_i * l_i (1.6)

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

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

Стоит выделить ограничения, налагаемые на данную задачу:

1. cуммарный объем каждого погруженного блока не должен превышать объема всего кузова ТС:
   ${\sum _{i=0}^n}_i{V}_i \le V$
2. ни один блок не может выходить за границы заданного объема;
3. коробки могут размещаться только таким образом, чтобы их грани были параллельны стенам контейнера;
4. хрупкие предметы не могут быть опорой для тяжеловесных;
5. при укладке должна учитываться возможность поворота коробки по доступным осям

Выводы

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

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