Adviss logistics - портал по логистике  

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

Основными условиями задачи являются следующие:

1)       Поставщик или дистрибьютор располагает одним или несколькими складами, с которых осуществляется доставка товаров клиентам.

2)       Склады являются многономенклатурными по ассортименту продукции, т.е. заказ клиента может быть полностью удовлетворен поставкой с любого склада.

3)       Складские и транспортные мощности достаточны для выполнения заказов клиентов, то есть, гарантировано отсутствие дефицита.

4)       Мы рассматриваем «заказную» систему поставок, то есть дистрибьютор только должен выполнить заказы клиентов в определенном объеме, и он располагает ресурсами для этого. В данном случае мы не рассматриваем задачу, связанную с запасами и хранением товаров, в которой дистрибьютор должен учитывать запасы товаров, как у себя, так и у клиентов, которые составляют «мертвый» капитал и, кроме того, возникают расходы с его хранением.

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

6)       Доставка осуществляется клиентам со складов автомобилями различной грузоподъемности. При этом практикуется следующая схема маршрутизации. Каждый автомобиль выполняет только один рейс от одного склада по принципу «один ко многим», то есть за один рейс автомобиль может обеспечить доставку нескольким клиентам, но клиент должен быть обслужен одним автомобилем. Суммарные заказы клиентов по маршруту автомобиля не должны превосходить его грузоподъемность.

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

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

В настоящее время для формирования маршрутов движения транспортных средств (ТС) широко используется специализированное программное обеспечение ГИС-класса. Сегодня на российском рынке представлено достаточно много фирм, предлагающих свои программные продукты для решения задач транспортной логистики. Наибольшим успехом на российском рынке пользуются Деловая карта (разработчик ООО «Фирма «ИНГИТ», Санкт-Петербург, Россия) и Top-Logistic (разработчик «Компания «TopPlan», Санкт-Петербург, Россия). Функциональные возможности этих и подобных им программных продуктов очень близки. Продажная цена одной лицензии для установки программы на локальном компьютере колеблется от 500 до 2000 долларов США. Окупаются эти программные продукты, по мнению разработчиков, за два-три месяца. Основными недостатками этих программных продуктов является невозможность сформировать маршруты в автоматическом режиме, если имеется несколько грузоотправителей для данного количества грузополучателей и если число формируемы маршрутов велико, например, для Top-Logistic свыше 100. Как правило, в дистрибутивных сетях крупных компаний решаются задачи именно такого масштаба и сложности. Поскольку «в лоб» решить данную задачу не представляется возможным, предлагается проводить декомпозицию общей задачи маршрутизации мелкопартионных грузов.

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

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

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

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

На основе полученной информации определяется транспортно-технологическая система (ТТС) доставки грузов (блок 2). Предлагается выделять две ТТС доставки грузов: глобальную и локальную. Локальная система доставки определена выше.

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

Во-вторых, предлагается для проведения разбиения всех клиентов на группы по признаку территориального расположения использовать процедуру кластерного анализа методом k-средних (блок 4). Метод k-средних принадлежит к группе итеративных методов кластерного анализа. Сущность их заключается в том, что процесс классификации начинается с задания некоторых начальных условий (количество образуемых кластеров, порог завершения процесса классификации и т.д.). Метод k-средних удобен для обработки больших статистических совокупностей, так как его вычислительный алгоритм является быстродействующим. Метод k-средних реализован в таких популярных пакетах статистического анализа, как STATISTICA^® и SPSS^®.

Затем, с использованием упомянутых выше или аналогичные программные продукты ГИС-класса решается задача маршрутизации движения ТС (блок 5) для каждой группы клиентов.

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

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

/А.А. Бочкарев

Санкт-Петербургский государственный инженерно-экономический университет/