logo
Теория логистика КАИ

Обоснование транспортных схем доставки запасов

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

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

Подходы и решения

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

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

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

Рис. 2. Фрагмент карты Москвы с рассчитанными маршрутами движения автотранспорта.

Все перекрестки, повороты и развороты представлены дополнительными ребрами, отображающими разрешенные маневры на дороге (рис. 2). Данная карта и дополнительные слои (набор «Москва до дома» и др.) распространяются и поддерживаются в актуальном состоянии несколькими столичными компаниями. Естественно, задачу можно решать и на любой другой карте, удовлетворяющей указанным выше условиям. Существуют, например, аналогичные карты Санкт-Петербурга и некоторых крупных городов России.

Кроме собственно графа, хранящегося в формате шейп-файла, неотъемлемой частью графа дорог является файл формата dBase, хранящий характеристики всех ребер этого графа, такие как:

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

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

Для перевозки грузов задается множество агентов – автомашин, развозящих товары. Они имеют следующие атрибуты:

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

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

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

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

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

В результате решения получается набор маршрутов, который графически отображается на электронной карте (рис. 2). В документальном виде результаты можно получить в виде файлов Excel, представляющих краткие или подробные маршрутные листы для каждой автомашины. Ввод и вывод данных для программы решения транспортной задачи реализован в VBA (Visual Basic for Applications) – встроенной в ArcGIS среде разработки, поэтому эти процессы могут быть легко адаптированы под нужды заказчика. В частности, реализовано формирование исходных данных путем импорта данных из файла заказов, в котором указаны ассортимент развозимых товаров для каждого клиента и время доставки.

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

Необходимо заметить, что данный программный продукт является открытым (в отличие от продукта ArcLogistics Route компании ESRI, не предназначенного для наших дорожных сетей), он постоянно дорабатывается и совершенствуется. Ряд компаний уже успешно использует его в своей повседневной практике.

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