Юрий Паршуков, DATA+
Логистика
В марте 1974 года в Берлине на Первом европейском конгрессе по логистике было сформулировано и принято определение: ЛОГИСТИКА — наука о планировании, управлении и контроле за движением материальных, информационных и финансовых ресурсов в различных системах.
Логистика позволяет минимизировать товарные запасы, сократить время доставки товаров, ускорить процесс получения информации и повысить уровень сервиса. Деятельность в области логистики разнообразна. Она включает управление транспортом, складским хозяйством, запасами, кадрами, организацию информационных систем, коммерческую деятельность и т.д.
С более утилитарных позиций, логистика — это система организации, планирования, управления и контроля материальных и информационных потоков в пространстве и во времени, от поставщиков до конечного потребителя.
Логистика активно пересекает национальные границы, и в Европе в рамках ЕЭС создаются трансконтинентальные логистические системы. Создание объединенного европейского рынка предопределяет построение межнациональных систем логистики.
Для России с ее огромными просторами и ресурсами логистика особенно важна. Для поэта Россия — «страна березового ситца», для транспортников – это 87 тысяч километров магистральных железных дорог с 4 тысячами станций, 84 тысячи километров внутренних водных путей с 43 морскими портами и 2 тысячами речных причалов, 800 тысяч километров авиамаршрутов с 756 аэропортами, 540 тысяч километров автомагистралей. Ноша своя, но, вопреки расхожему выражению, тянет. И масштабностью проблем, стоящих за сухими статистическими выкладками, и широтой задач, которые необходимо решать по возможности рациональным образом.
По сферам объектов система логистики подразделяется на: производство; систему складского хозяйства; систему транспортировки, упаковки и обращения с материалом; информационную систему, включая обработку заказов и систему хранения. Множество логистических цепочек предприятия, поддерживаемых в системах стандарта ERP (планирование ресурсов предприятия), представлено на рис. 1.
Рис. 1. Логистические цепочки предприятия.
Более подробно остановимся на транспортном компоненте логистики. Его важность подтверждается тем, что до 50% всех затрат на логистику связано с транспортными издержками.
Транспортная логистика
Транспортная логистика призвана обеспечить: оптимизацию транспортных систем, выбор видов и типов транспортных средств; определение разноканальных маршрутов доставки и их оптимизацию; технологическое единство транспортно-складского процесса.
Современная транспортная логистическая система должна предоставлять следующие возможности:
- план отправки товара при поступлении заказа
- создание плана перевозок с помощью средств динамического планирования
- построение маршрутов на основе списка рассылки, позволяющих определить кратчайший путь к заказчику
- контроль за перемещением товара на маршруте
- предоставление информации о находящихся в пути товарах
- генерацию погрузочных накладных, упаковочных листов и других требуемых документов.
Составление оптимального плана перевозок — классическая математическая задача. Как известно, усилия, необходимые для ее решения, при увеличении масштаба задачи растут экспоненциально. Поэтому вручную составить план, близкий к оптимальному или хотя бы достаточно экономичный, практически невозможно. Более того, если не использовать средства автоматизации, то при значительных объемах перевозок, при большом количестве клиентов, складов, возможных маршрутов, транспортных средств вообще вряд ли удастся вовремя доставить клиентам заказанные ими товары.
Конечно, реальная ситуация далека от идеальной математической модели. Тем не менее, современные информационные технологии позволяют если и не найти оптимальное решение, поскольку многочисленные случайные обстоятельства исключают возможность существования такого решения в математическом смысле, то значительно сократить транспортные расходы.
Подходы и решения
Классическая транспортная и родственные ей задачи, решаемые методами линейного программирования, часто далеки от реальной жизни. В то же время, решать эти задачи не только необходимо, но и возможно. Опишем кратко задачу оптимальной доставки товаров в том виде, в каком она решается в компании DATA+.
Основная задача транспортной логистики — перемещение требуемого количества товара в нужную точку, оптимальным маршрутом, за требуемое время и с наименьшими издержками.
Картографической основой при решении задачи является связный граф дорог, например Москвы и области. Из произвольной вершины такого графа можно попасть в любую другую вершину. Каждый участок дороги представлен ребром графа, а координаты его начала и конца совпадают, соответственно, с координатами конца предыдущего участка и началом следующего ребра. Направление каждого ребра совпадает с направлением движения по дороге, и каждая дорога представлена двумя наборами ребер, соответствующими двустороннему движению.
Рис. 2. Фрагмент карты Москвы с рассчитанными маршрутами движения автотранспорта.
Все перекрестки, повороты и развороты представлены дополнительными ребрами, отображающими разрешенные маневры на дороге (рис. 2). Данная карта и дополнительные слои (набор «Москва до дома» и др.) распространяются и поддерживаются в актуальном состоянии несколькими столичными компаниями. Естественно, задачу можно решать и на любой другой карте, удовлетворяющей указанным выше условиям. Существуют, например, аналогичные карты Санкт-Петербурга и некоторых крупных городов России.
Кроме собственно графа, хранящегося в формате шейп-файла, неотъемлемой частью графа дорог является файл формата dBase, хранящий характеристики всех ребер этого графа, такие как:
- длина участка дороги
- скорость движения по этому участку
- признак разрешения/запрета движения по участку всем или отдельным видам транспорта (до 10 видов)
- среднее время прохождения участка и время задержки (например, на перекрестке)
- коэффициент, увеличивающий/уменьшающий время движения по участку.
Таким образом, атрибутивная информация хранится независимо от графа дорог. Средства редактирования, предоставляемые пользователю, позволяют создавать различные наборы сетей дорог, отражающие реальные ситуации или время дня (года), и выполнять расчет на той сети, которая наиболее адекватно отражает состояние магистралей.
Для определения точек, откуда автомашины начинают движение и где заканчивают свои маршруты, вводится множество гаражей (баз) со следующими характеристиками:
- адрес гаража (выбирается из точечного слоя домов Москвы/области или проставляется вручную на карте)
- признак (битовая маска), определяющий подмножество автомашин, которые могут обслуживаться базой (не зависит от типа автомашины).
Для перевозки грузов задается множество агентов – автомашин, развозящих товары. Они имеют следующие атрибуты:
- тип автомашины (определяет максимальные вес и объем развозимого товара)
- время начала и окончания работы
- начальная и конечная точки маршрута из множества складов/баз
- признаки (битовая маска), определяющие, какие точки может обслуживать данный агент и какими базами (гаражами) могут обслуживаться разные точки
- признак участия в решении текущего варианта задачи.
Точки обслуживания (магазины, склады и т.п.) – места, куда агенты должны доставить товар. Задаются координатами из точечного слоя зданий города/области или наносятся на карту вручную, имеют следующие характеристики:
- время работы
- тип агента (автомашины), который может обслужить данную точку
- вес и объем груза, который необходимо доставить в данную точку
- время разгрузки автомашины
- признаки (битовая маска), определяющие, какие агенты могут обслуживать данную точку.
Адреса точек обслуживания могут импортироваться из файлов с последующим геокодированием или выбираться из имеющейся базы адресов, которая постоянно обновляется вместе с картой города.
После задания множеств гаражей, агентов, точек обслуживания и их временных характеристик выбирается критерий оптимизации: максимальный вес развозимого груза, минимальное суммарное время доставки, минимальная длина маршрутов, или такие как минимальный набор агентов для решения задачи и, наоборот, равномерность загрузки агентов.
Сложность решения такой задачи усугубляется разнородными ограничениями, которые должны быть учтены:
- ограничения в графе дорог (запрет проезда по некоторым дорогам или, например, по центру города)
- ограничения по весу и объему товара для каждого транспортного средства
- ограничения по времени для агентов и точек обслуживания
- ограничения, связанные с типом используемого автотранспорта (запрет проезда по некоторым дорогам, обслуживание клиентов только указанными типами транспорта)
- другие ограничения, которые могут быть наложены пользователем или моделируют территориальное деление между поставщиками, различные виды товара, дни доставки товара и т.д.
После ввода всех исходных данных в среде ArcGIS решается задача доставки товаров. Эта задача реализована как расширение ArcGIS, добавляющее в стандартный интерфейс дополнительные кнопки и инструменты.
В результате решения получается набор маршрутов, который графически отображается на электронной карте (рис. 2). В документальном виде результаты можно получить в виде файлов Excel, представляющих краткие или подробные маршрутные листы для каждой автомашины. Ввод и вывод данных для программы решения транспортной задачи реализован в VBA (Visual Basic for Applications) – встроенной в ArcGIS среде разработки, поэтому эти процессы могут быть легко адаптированы под нужды заказчика. В частности, реализовано формирование исходных данных путем импорта данных из файла заказов, в котором указаны ассортимент развозимых товаров для каждого клиента и время доставки.
Для ведения базы данных клиентов и автотранспортных средств, хранения маршрутов используются стандартные средства ArcGIS. Эти мощные инструментальные средства позволяют проводить пространственный и статистический анализ решаемых транспортных задач, наглядно отображать получаемые результаты.
Необходимо заметить, что данный программный продукт является открытым (в отличие от продукта ArcLogistics Route компании ESRI, не предназначенного для наших дорожных сетей), он постоянно дорабатывается и совершенствуется. Ряд компаний уже успешно использует его в своей повседневной практике.
Тем, кто сомневается, можно ли оптимизировать транспортные расходы, приведу слова логистика-профессионала:
«Логистика не приносит прибыли, но дает огромную экономию».
