Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Теоретическая и прикладная экономика
Правильная ссылка на статью:

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

Кочкаров Азрет Ахматович

кандидат физико-математических наук

доцент, департамент анализа данных и принятия решений, Финансовый университет при Правительстве РФ

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
Другие публикации этого автора
 

 

DOI:

10.25136/2409-8647.2021.1.34965

Дата направления статьи в редакцию:

29-01-2021


Дата публикации:

05-02-2021


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


Ключевые слова:

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

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

Abstract: This article reviews the theoretical-graph approach towards transport and logistic systems, which allows describing key details and processes that take place therein. The question of searching for an effective solution of transport and logistics tasks and dependence of such solutions to throughput of the system and the value of the seepage coefficient. This article offers to use seepage theory as an applied instrument for describing and solving transport and logistics tasks. The indicated approach is innovative and original, which may be very promising in the context of global transport planning and management. The essence of this method, based on adaptation of seepage theory for solution of the typical transport and logistics tasks, is reduced to operation of surface run-off and origin on the graph. The model for assessment of the global throughput of transport and logistics system is developed on the basis of the methods of seepage and multidrain flow models. The author offers a model calculation of the impact of holdups upon transport and logistics systems and the tasks solved thereof. A theoretical-graph model, which reflects the structure of transport and logistics system, describes the objects and processes common to transport and logistics tasks. The toolset of graph theory allows solving the specific transport and logistics tasks, as well examining the structural properties of the system, building predictive models, as well as developing new approaches towards solving of these tasks. The characteristics of graph are correlated with the actual network, system and task, as well as with the characteristics of transport or logistics flows examined for the purpose of optimization of topological structure of the system and solution of other tasks.


Keywords:

transport and logistics systems, solution efficiency, dynamic graph, throughput, seepage ratio, congestion, model, flow planning, structural dynamics, graph-theoretical approach

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Библиография
1. Liu J., Li J., Zhao J. The research on supply chain reliability based on meta-graphs //2003 4th International Conference on Control and Automation Proceedings. – IEEE, 2003. – С. 849-853.
2. Surana A. et al. Supply-chain networks: a complex adaptive systems perspective //International Journal of Production Research. – 2005. – Т. 43. – №. 20. – С. 4235-4265.
3. Тархов С. А. Эволюционная морфология транспортных сетей. – 1989.
4. Lahn N., Mulchandani D., Raghvendra S. A graph theoretic additive approximation of optimal transport //Advances in Neural Information Processing Systems. – 2019. – С. 13836-13846.
5. Wagner S. M., Neshat N. Assessing the vulnerability of supply chains using graph theory //International Journal of Production Economics. – 2010. – Т. 126. – №. 1. – С. 121-129.
6. Kaur A., Kanda A., Deshmukh S. G. A graph theoretic approach for supply chain coordination //international journal of logistics Systems and Management. – 2006. – Т. 2. – №. 4. – С. 321-341.
7. Buslaev A. P., Tatashev A. G. On dynamical systems for transport logistic and communications //Journal of Mathematics Research. – 2016. – Т.8. – №. 4. – С. 195.
8. Guo W. et al. A graph-based cost model for supply chain reconfiguration //Journal of manufacturing systems. – 2018. – Т. 48. – С. 55-63.
9. Тарасевич Ю. Ю. Просачиваемость: теория, приложения, алгоритмы //М.: Едиториал УРСС. – 2002.
10. Bollobás B. Modern graph theory. – Springer Science & Business Media, 2013. – Т. 184.
11. Яцкин Д.В., Кочкаров А.А., Кочкаров Р.А. Моделирование транспортно-логистических систем и исследование их структурной устойчивости. Управленческие науки. 2020;10(1):102-111. https://doi.org/10.26794/2404-022X-2020-10-1-102-11
References
1. Liu J., Li J., Zhao J. The research on supply chain reliability based on meta-graphs //2003 4th International Conference on Control and Automation Proceedings. – IEEE, 2003. – S. 849-853.
2. Surana A. et al. Supply-chain networks: a complex adaptive systems perspective //International Journal of Production Research. – 2005. – T. 43. – №. 20. – S. 4235-4265.
3. Tarkhov S. A. Evolyutsionnaya morfologiya transportnykh setei. – 1989.
4. Lahn N., Mulchandani D., Raghvendra S. A graph theoretic additive approximation of optimal transport //Advances in Neural Information Processing Systems. – 2019. – S. 13836-13846.
5. Wagner S. M., Neshat N. Assessing the vulnerability of supply chains using graph theory //International Journal of Production Economics. – 2010. – T. 126. – №. 1. – S. 121-129.
6. Kaur A., Kanda A., Deshmukh S. G. A graph theoretic approach for supply chain coordination //international journal of logistics Systems and Management. – 2006. – T. 2. – №. 4. – S. 321-341.
7. Buslaev A. P., Tatashev A. G. On dynamical systems for transport logistic and communications //Journal of Mathematics Research. – 2016. – T.8. – №. 4. – S. 195.
8. Guo W. et al. A graph-based cost model for supply chain reconfiguration //Journal of manufacturing systems. – 2018. – T. 48. – S. 55-63.
9. Tarasevich Yu. Yu. Prosachivaemost': teoriya, prilozheniya, algoritmy //M.: Editorial URSS. – 2002.
10. Bollobás B. Modern graph theory. – Springer Science & Business Media, 2013. – T. 184.
11. Yatskin D.V., Kochkarov A.A., Kochkarov R.A. Modelirovanie transportno-logisticheskikh sistem i issledovanie ikh strukturnoi ustoichivosti. Upravlencheskie nauki. 2020;10(1):102-111. https://doi.org/10.26794/2404-022X-2020-10-1-102-11

Результаты процедуры рецензирования статьи

В связи с политикой двойного слепого рецензирования личность рецензента не раскрывается.
Со списком рецензентов издательства можно ознакомиться здесь.

Представленная на рецензирование статья посвящена совершенствованию планирования в транспортных сетях на основе применения методов математического моделирования, потоковых моделей и теории графов для решения классических транспортно-логистических задач.
Методология исследования базируется на теории графов и использовании понятия протекания или просачиваемости применительно к ориентированным графам, категорий «исток» и «сток», которые служат для отражения направленности процессов протекания (просачиваемости) слева-направо либо снизу-вверх. Актуальность работы сомнений не вызывает, поскольку наращивание объемов грузоперевозок и увеличение интенсивности транспортных потоков приводит к необходимости поиска новых подходов к их регулированию. Научная новизна представленного исследования, по мнению рецензента, заключается в реализованной попытке применить частную прикладную теорию просачиваемости в рамках теории графов для решения задач потокового планирования в транспортных сетях с учетом их структурной динамики.
При изложении материала выдержан научный стиль, принятый для журнальных статей. Структурно работа состоит из введения, двух разделов, заключения и библтографии.
Авторы во введении справедливо называют теорию просачиваемости частной прикладной теорией, поскольку в научном обороте термин «просачиваемость» чаще всего используется в рамках теории графов. В этой связи ссылки на источники, в которых упоминается теория просачиваемости представляются необходимыми и вполне уместными.
В разделе «Применение теории просачиваемости в описании процессов транспортно-логистических систем» отмечается, что отраженная в статье попытка использования в качестве прикладного инструмента для описания транспортно-логистических задач теории просачиваемости предпринимается впервые, является пионерной. В этой части статьи рассмотрен понятийный аппарат, дано пояснение категорий «исток», «сток», «потоковый путь», «потоковая цепь», изложен алгоритм расчета коэффициента просачиваемости как отношения количества потоковых путей к количеству потоковых цепей, показано, что эта величина зависит от времени и может изменяться вследствие структурных изменений на графе транспортной системы.
В разделе «Исследование процесса образования заторов» описана схема проведения эксперимента с применением случайно сгенерированной модели связной транспортно-логистической сети со 100 вершинами, при этом нулевые значения пропускной способности отдельных ребер соответствуют формированию заторов; рассмотрены 9900 типовых задач доставки с разными точками отправления и назначения; для каждой задачи определены значения коэффициента просачиваемости и функции эффективности; смоделированы случайные итеративные изменения весов ребер в сторону среднего увеличения (уменьшения пропускной способности), соответствующего образованию затора. В результате моделирования обнаружена корреляция значения средней пропускной способности ребер со значениями коэффициента просачиваемости. Эта зависимость представлена графически на рисунке. По результатам изучения корреляции значений коэффициентов эффективности и коэффициентов просачиваемости также построен график и приведено его описание. Согласно которому значения коэффициента эффективности, на которых достигается плато лежат в границах от 0,615 до 0,72. К сожалению, при загрузке текста статьи в автоматизированную систему издательства квадратные скобки, использованные для обозначения закрытого интервала, восприняты как ссылка на библиографию – этот момент требует корректировки.
В Заключении утверждается, что в статье «разработана математическая модель просачиваемости в динамических сетях, описывающих транспортно-логистические системы», однако, математическая конструкция как таковая в представленном материале не отражена, приведено лишь описание схемы проведения эксперимента.
Представленный библиографический список включает 11 источников – публикации отечественных и иностранных ученых по теме статьи, на каждый из которых в тексте имеется адресная ссылка, что подтвержает наличие аппеляции к оппонентам.
Рецензируемый материал подготовлен на актуальную тему, обладает элементами научной новизны и практической значимости, ориентирован на совершенствование подходов к решению задач потокового планирования в транспортных сетях, может вызвать интерес у читателе журнала, что свидетельствует о целесообразности его публикации в виде статьи после доработки.