Любая перевозка начинается с упаковки того, что мы хотим везти, в то, на чем мы собираемся ехать. Хорошо упаковать — это значит максимально заполнить полезным грузом ограниченный объем. Но идеальной упаковке всегда что-то мешает: то грузы не совмещаются, то окна не совпадают, то по времени везде не успеть… Получается, что при относительно малых объемах грузов и при наличии более строгих ограничений, проблема утилизация транспорта отходит на второй план. Но сегодня мы обратимся к случаю, когда именно грамотный выбор подвижного состава и правильная укладка являются главным фактором оптимизации.
Вот и классическая научная постановка подсказывает нам, что Задача маршрутизации транспорта (Vehicle Routing Problems, VRP) представляет собой пересечение двух изолированных задач:
- Задача коммивояжера (Traveling Salesman Problem, TSP), где нужно обойти все заданные точки кратчайшим путем без ограничений по вместимости транспортного средства.
- Задача об упаковке рюкзака (Bin Packing Problem, BPP), где нужно упаковать разнородные по весу и ценности грузы в ограниченный по вместимости рюкзак.
При чем обе эти задачи предполагают «мульти»-вариант постановки, то есть в общем виде маршрутов с кратчайшим путем у каждого будет более одного и доступных транспортных средств тоже несколько и они могут быть разной вместимости.
Итак, упаковка в контексте задачи маршрутизации — это объединение грузов для совместной перевозки. При чем ОТМ здесь оперирует именно грузовыми местами, а не заказами в целом. Это означает, что для более оптимальной загрузки ОТМ может разбить один заказ кратно грузовым местам по нескольким разным машинам, если это даст выигрыш в утилизации. Утилизация подвижного состава рассчитывается по двум измерениям: по весу и объему грузовых мест. В общем виде ОТМ стремится использовать максимально большие машины из доступных и максимально их утилизировать, чтобы сократить общее количество рейсов. Конечная цель оптимизации — это минимальная стоимость перевозки единицы груза при условии соблюдения всех других неденежных ограничений.
Для того, чтобы точно рассчитать утилизацию машин нужна детальная информация о грузе. В идеале нужны точные вес, объем и размеры по каждому месту. Это может стать большой проблемой при условии, что обычно у нас на входе заказы, из строк которых можно узнать только номенклатуру и количество. Но есть хорошая новость: ОТМ поддерживает вложенную упаковку и автоматический расчет грузовых мест. В ОТМ могут задаваться параметры первичной и вторичной упаковки для каждой номенклатурной позиции. Есть возможность вести варианты укладки товара на паллету в виде количества слоев и количества коробов в слое, а также есть функция формирования смешанных паллет. Это все может показаться лишним и даже может вызвать возмущение тех, кто давно выстрадал все нюансы упаковки в WMS, а им тут предлагают упрощенную версию того же самого. Но не спешите критиковать, ведь в данном случае ОТМ претендует только на примерный расчет грузовых мест, достаточный для заказа транспорта. После фактической сборки складом информацию о местах в ОТМ можно обновить и проверить загрузку машин еще раз. При должной настройке отклонений в духе «плюс минус машина» быть не должно.
Предположим, что о грузах все известно, и можно, наконец, заняться укладкой в машины. Мы будем разбирать ситуацию, когда доступны машины побольше и поменьше. Напомню, что цель оптимизации — это минимальная общая стоимость решения, поэтому в нашу модель еще нужно ввести понятие тарифа за перевозку для каждого типа машины. Тут, конечно, есть варианты. Если машины собственные, то тариф будет скорее всего приведен к километру пробега и стоимость для бОльшей машины будет больше за счет бОльшего расхода топлива. Если машины наемные, то может быть фиксированный тариф за день/за рейс независимо от пробега. В обоих случаях чем больше будет загрузка, тем меньше расходов ляжет на каждую единицу груза в каждой машине.
А теперь эксперименты!
Чтобы исключить влияние маршрута на утилизацию, то есть свести все к задаче упаковки рюкзака, мы возьмем один заказ с большим количеством одинаковых грузовых мест, которые полностью ни в одну из доступных машин не входят. При различных тарифах посмотрим какие машины выберет ОТМ и как распределит по ним эти грузовые места. Утилизацию будем рассматривать только по весу.
Исходные данные: Заказ на перевозку 11 тонн, с грузовыми местами по 100 кг. Два типа машин грузоподъемностью 10 тонн и 4 тонны в неограниченном количестве.
Пример №1. Тарифы за рейс: машина 10т — 10 000 руб.; машина 4т — 4 000 руб.
С приоритетом на пробег возможно решение из двух рейсов, а с приоритетом на стоимости ОТМ выбирает решение из трех рейсов с более низкой общей стоимостью и бОльшей утилизацией машин.
| Количество рейсов | 2 | 3 |
| Типы машин | 10т + 4т | 4т + 4т + 4т |
| Общая стоимость | 14 000 руб. | 12 000 руб. |
| Общий пробег | 13,7 км | 20,5 км |
| Средняя утилизация | 78% | 92% |
| Утилизация по машинам | 100 / 25 | 100 / 100 / 75 |
Пример №2. Тарифы за рейс: машина 10т — 10 000 руб.; машина 4т — 5 000 руб.
После изменения тарифа для машины 4т общая стоимость по обеим комбинациям машин совпадает и равна 15 000 руб. В этом случае начинает действовать приоритет по пробегу / минимизации количества машин и ОТМ выбирает решение из двух рейсов с меньшим общим пробегом.
| Количество рейсов | 2 | 3 |
| Типы машин | 10т + 4т | 4т + 4т + 4т |
| Общая стоимость | 15 000 руб. | 15 000 руб. |
| Общий пробег | 13,7 км | 20,5 км |
| Средняя утилизация | 78% | 92% |
| Утилизация по машинам | 100 / 25 | 100 / 100 / 75 |
Более сложную картину можно увидеть при загрузке машин разнородными грузами: легкими/объемными и тяжелыми/компактными. Например, овсяные хлопья в коробках и сахар в мешках. В этом случае важна оптимизация загрузки по весу и по объему именно в сочетании, что может позволить сократить количество необходимых машин за счет правильной комбинации разных грузов в каждой машине. Но этот интригующий пример, а также тонкости моделирования загрузки машины в 3D я оставлю для следующей статьи.