Применение методов теории ПРОСАЧИВАЕМОСТИ для РЕШЕНИЯ ЗАДАЧ ПОТОКОВОГО ПЛАНИРОВАНИЯ В ТРАНСПОРТНЫХ СЕТЯХ С УЧЕТОМ их СТРУКТУРНОЙ ДИНАМИКИ

Кочкаров Азрет Ахматович кандидат физико-математических наук доцент, департамент анализа данных и принятия решений, Финансовый университет при Правительстве РФ 125993, Россия, г. Москва, Ленинградский пр., 49 Kochkarov Azret Ahmatovich PhD in Physics and Mathematics Docent, the department of Data Analysis and Decision-Making , Financial University under the Government of the Russian Federation 125993, Russia, g. Moscow, Leningradskii pr., 49 akochkar@gmail.com Другие публикации этого автора     Яцкин Данил Владиленович Специалист, АО «Концерн «Радиотехнические и Информационные Системы» 141701, Россия, Московская Область область, г. Долгопрудный, ул. Институтский Переулок, 9 Yatskin Danil Vladilenovich Specialist, JSC "Radio Engineering and Information Systems" 141701, Russia, Moskovskaya Oblast' oblast', g. Dolgoprudnyi, ul. Institutskii Pereulok, 9 danil@frtk.ru

Кочкаров Расул Ахматович кандидат экономических наук доцент, департамент анализа данных и принятия решений, Финансовый университет при Правительстве РФ 125993, Россия, г. Москва, Ленинградский пр., 49 Kochkarov Rasul Ahmatovich PhD in Economics Docent, the department of Data Analysis and Decision-Making, Financial University under the Government of the Russian Federation 125993, Russia, g. Moscow, Leningradskii pr., 49 rasul_kochkarov@mail.ru Другие публикации этого автора

Работа выполнена при поддержке РФФИ (проект КОМФИ № 18-00-01103).

ВВЕДЕНИЕ

Транспортно-логистические системы и соответствующие задачи, рассматриваемые на них, нуждаются в едином инструментарии для описания как в частном, так и в общем виде. Для этих целей подходят терминология и методология теории графов ^[1-4]. В таком случае в роли вершин выступают логистические узлы, а связи между ними можно считать ребрами.

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

Графовая структура, служащая моделью транспортно-логистической системы, описывает все необходимые для определения и задания объекты и процессы, характерные для транспортно-логистических задач ^[5-8]. При этом инструментарий теории графов позволяет как решать конкретные транспортно-логистические задачи, так и изучать структурные свойства системы, строить прогнозные модели и разрабатывать новые подходы для решения задач.

В частности, классической транспортно-логистической задачей является поиск пропускной способности той или иной системы относительно потоков тех или иных товаров, заданных как явным, так и неявным образом. Для описания и изучения ряда процессов может быть использована теория просачиваемости ^[9], являющаяся частной прикладной теорией.

ПРИМЕНЕНИЕ ТЕОРИИ ПРОСАЧИВАЕМОСТИ В ОПИСАНИИ ПРОЦЕССОВ ТРАНСПОРТНО-ЛОГИСТИЧЕСКИХ СИСТЕМ

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

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

Кратчайший путь от истока к стоку при этом называется потоковым путем P(v). Множество потоковых путей V_P, соответствующих произвольно выбранной периферийной вершине, счетно и конечно.

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

Показателем уровня просачиваемости (коэффициентом просачиваемости) k_пр называется отношение количества потоковых путей к количеству потоковых цепей k_пр=|V_P|/|V_S|.

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

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

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

ИССЛЕДОВАНИЕ ПРОЦЕССА ОБРАЗОВАНИЯ ЗАТОРОВ

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

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

На построенной структуре были отдельно рассмотрены 9900 типовых задач (полный набор) доставки товаров (потоков элементов задачи f) с разными точками отправления и назначения. Таким образом для каждой задачи было определено значение функции эффективности P_opt=P(s_opt). Отдельно по описанной ранее методологии был определен k_пр.

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

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

На каждой итерации были рассчитаны значения P(s) для нового оптимального решения целевой задачи и значения k_пр. В качестве результата моделирование было взято соответствующее значение k_эфф=P(s)/P_opt, усредненное по всем решаемым на данной сети задачам.

Была обнаружена корреляция значения средней пропускной способности ребер (по отношению к начальной конфигурации) со значениями k_пр (см. рис.1).

Рис. 1. Зависимость k_пр от нормированной средней пропускной способности ребер n.

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

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

Далее была исследована корреляция значений k_эфф и k_пр для рассматриваемых задач. Такая зависимость, вид которой представлен на рисунке 2, носит более сложный характер.

Рис/ 2. Зависимость коэффициента эффективности решения транспортно-логистической задачи k_эфф от коэффициента просачиваемости транспортно-логистической системы k_пр.

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

Эксперимент был повторен для разных конфигураций параметров исходной задачи и разных графов транспортно-логистических сетей и вид графика повторялся для всех проведенных экспериментов. При этом плато всегда было только одно, что позволяет предположить наличие значения k_эфф, стабильного по отношению к незначительным изменениям просачиваемости системы. При этом значения k_эфф, на которых достигается плато лежат в границах ^{[0.615, 0.72]}, что в совокупности с видом графиков позволяет провести параллель с барьерными значениями коэффициента устойчивости к структурным разрушениям ^[11].

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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