Программные продукты и системы

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

В транспортной инфраструктуре в системах дистрибьюции в основном используется автомобильный и железнодорожный транспорт, причем в региональных перевозках значительно лидируют автоперевозки, что подтверждается статистическими данными по грузообороту и объемам перевозок. Беглый анализ деятельности автотранспортных предприятий показал, что большинство из них имеют хороший потенциал для сокращения удельной стоимости и повышения качества услуг благодаря четкому выделению и оптимизации биз­нес-процессов, в том числе и оптимизации управления грузоперевозками, что вполне в духе многих успешных перевозчиков, использующих стратегию low cost/high value.

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

Построение оптимальной системы распределения продукции является частным случаем задачи маршрутизации [2, 3], которая сводится к оптимизационной задаче на графе. Математическую модель системы маршрутов можно представить как полный взвешенный граф G=(V, E), где вершины V={v0, v1, …, vn}, а дуги E={e0, e1, …, en}. Автотранспортное предприятие, являющееся началом и концом каждого маршрута (базой), – это вершина v0. Другие вершины представляют места реализации, а также промежуточные узлы (склады, перевалочные пункты и пр.). Для каждой дуги (i, j) задана стоимость перевозки, а для каждого места реализации (клиента) – ожидаемый спрос и соответствующая ему вероятность. Также задана грузоподъемность каждого ТС.

Задачу оптимизации управления грузоперевозками можно описать формально как задачу минимизации функционала, описывающего полную стоимость расходов на транспортировку продукции:

при ограничениях

где {Ti} – множество типов ТС, i=1, …, n; {Sj} – ассортимент продукции, j=1, …, m; Ti(l, Sj) – стоимость перевозки j-го типа продукции как функция от расстояния; cp – стоимость p-й перевалки;  – максимальная грузоподъемность ТС Ti типа; mSj – масса j-го типа товара; wSj, lSj, hSj – габариты j-го типа товара;  – общее время эксплуатации i-го ТС; ai – константа, характеризующая степень загруженности i-го ТС (0¸1).

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

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

Шаг 1. Установка начального значения феромона, представляющего собой терм нечеткого множества «значимость» прокладки локального маршрута муравьем для всех ребер графа возможных маршрутов. Центр данного терма можно определить при помощи выражения , где r(i, j) – стоимость перевозки из i-го в j-й узел (точку разгрузки); G – граф маршрутов.

Шаг 2. Пошаговая прокладка маршрутов с использованием набора эвристических правил, определяющих поведение муравья как программного агента.

В начале выполнения данного шага в базу помещаются все муравьи колонии, которые движутся к клиентам, прокладывая множество маршрутов. Достигнув клиента, они с заданной степенью вероятности могут попасть в ситуации, когда спрос либо соответствует ожиданиям, либо ниже или выше ожидаемого значения. В соответствии с ситуацией муравей отправляется к другому клиенту или возвращается на базу. Множество муравьев образуют колонию (которая подчиняется неким поведенческим правилам), определяемую набором нечетких и четких продукционных правил маршрутизации (ППм) при непринадлежности смежной вершины j к списку табу T(m): ППм-1 – выбор направления прокладки локальной трассы из i-й в j-ю вершину графа маршрутов; ППм-2 – разгрузка товара; ППм-3 – возвращение на базу; ППм-4 – смена ТС.

ППм-1: Если «величина » «достаточно большая», ТО «ребро (i, j)» имеет «большой приоритет» И «добавить вершину j в T(m)».

Величина  определяется по следующей эмпирической формуле:

где r(i, j) – стоимость перевозки из i-го в j-й узел; Pj – выручка, которая может быть получена муравьем от продажи товара в узле j; g – некоторая константа;  – стоимость маршрута от узла j до базы: , где z – множество возможных маршрутов от узла j до базы.

Четкие правила ППм-2 имеют вид

а) «ЕСЛИ (zi£pi(k)) И (Q(m)(k)>0) И (Qi(k)³Q(m)(k)), ТО () И (Q(m)(k)=0) И (Qi(k)=Qi(k)– –Q(m)(k))»;

б) «ЕСЛИ (zi£pi(k)) И (Q(m)(k)>0) И (Qi(k)) И (Q(m)(k)=Q(m)(k)–Qi(k)) И (Qi(k)=0)»;

в) «ЕСЛИ (zi>pi(k)) И (Q(m)(k)>0) И ( ´Qi(k)³Q(m)(k)), ТО () И (Q(m)(k)=0) И (Qi(k)=Qi(k)–Q(m)(k))»;

г) «ЕСЛИ (zi>pi(k)) И (Q(m)(k)>0) И ( ´Qi(k)) И (Q(m)(k)=Q(m)(k)–) И (Qi(k)=0)»,

где zi – случайная величина в интервале [0, 1]; pi(k) – вероятность спроса заданного количества k-го типа товара в узле i; Qi(k) – спрос k-го типа товара в i-м узле; Q(m)(k) – количество k-го типа товара у муравья m; Pi(k) – прибыль, полученная муравьем от продажи k-го типа товара в узле i; c(k) – стоимость k-го типа продукции.

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

ППм-3: «ЕСЛИ (смежная вершина j не принадлежит списку табу T(m)) И (Yj(m)+d(I, j)> >Yj(m)+Pj), ТО (муравей перемещается на базу)».

Формализованная запись ППм-3 имеет вид {(i, 0)½ " (i, j), jÏT(m), Yj(m)+r(i, j)>Yj(m)–Pj}, где Pj – выручка, которая может быть получена муравьем от продажи товара в узле j.

ППм-4: «ЕСЛИ (смежная вершина j не принадлежит списку табу T(m)) И (2×cn+r*(i, j)

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

Шаг 3. Обновление концентрации феромонов на всех ребрах графа маршрутов по следующему правилу в типовой схеме метаэвристики муравьиных колоний: ti,j=(1–r)×ti,j+r×Dti,j, где ti,j – переменная, определяющая скорость испарения феромона (0£r£1); Dti,j – приращение концентрации феромонов на очередной итерации алгоритма, вычисляемое по известной формуле

где Q – некоторая константа; cost(St) – стоимость полученной конфигурации маршрута.

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

Шаг 4. Повторение шагов 2 и 3, пока результат распределения продукции по маршрутам не перестанет изменяться.

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

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

Литература

1. Дли М.И., Жилкин И.А. Интервальные модели поддержки принятия решений по развитию предприятий железобетонных изделий // Интеграл. 2009. № 2. С. 108.

2. Ghiani G., Guerriero F., Laporte G. and Musmanno R. Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies / Research Report, Center of Excellence for High Performance Computing, University of Calabria, Arcavacata di Rende, 2003.

3. Усенко И.В. Обзор проблем принятия решений в неопределенных и расплывчатых условиях при решении транспортных задач // Перспективные информационные технологии и интеллектуальные системы. 2008. № 2 (34). С. 37–44.