Разработка и исследование математических моделей и программ нахождения равновесия транспортных потоков и оптимизации транспортной сети на примере Петрозаводска

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 22-11-20015

НазваниеРазработка и исследование математических моделей и программ нахождения равновесия транспортных потоков и оптимизации транспортной сети на примере Петрозаводска

Руководитель Мазалов Владимир Викторович, Доктор физико-математических наук

Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Федеральный исследовательский центр "Карельский научный центр Российской академии наук" , Республика Карелия

Конкурс №66 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами» (региональный конкурс)

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-203 - Теория оптимизации и исследование операций

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

Код ГРНТИ27.47.19

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Проект направлен на развитие теоретико-игровых подходов к исследованию транспортной системы города и анализу поведения участников транспортной системы. В основе исследования лежит принцип равновесия транспортных потоков, которое достигается при равномерном заполнении всех сегментов транспортной сети. В рассмотрение будут включены внешние факторы, которые представляют собой элементы централизованного управления, которое, как правило, глобально невозможно, но элементы которого можно использовать при организации транспортных потоков. Для дорожного движения к таким внешним факторам относятся: движение по полосам, ширина и количество полос, расположение светофоров, наличие в потоке самоуправляемых транспортных средств; для пассажирских перевозок – вместимость автобусов, расписание движения, влияние муниципального транспорта на социальный оптимум и другие внешние факторы. Кроме того, в исследование данной проблемы будут включены элементы поведения участников процесса – пассажиров и обслуживающих компаний. В этом случае будет использоваться модифицированный принцип Вардропа, разработанный ранее участниками проекта, когда на пассажирские потоки влияют цены на билет, интенсивность и качество обслуживания пассажиров. Соотношение затрат конкурентного и социально-оптимального сценариев описывается “ценой анархии”. В работе будет исследован вопрос как "цена анархии" зависит от внешних факторов и размеров транспортных потоков. Результаты исследований предполагается апробировать на транспортной сети города Петрозаводск. Будет создана программная система, которая позволит моделировать транспортную ситуацию в городе в реальном времени. Полученные результаты позволят дать рекомендации по совершенствованию управления конкретными транспортными потоками, которые помогут улучшить ситуацию на дорогах.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Чиркова Ю.В., Мазалов В.В. Optimal Arrivals to Preemptive Queueing System Lecture Notes in Computer Science, Vol. 13367, pp. 169–181 (год публикации - 2022)
10.1007/978-3-031-09607-5_12

2. Никитина Н.Н., Мазалов В.В. Network Centralities Based on Non-additive Measures Communications in Computer and Information Science, Vol. 1661, pp. 260–271 (год публикации - 2022)
10.1007/978-3-031-16224-4_18

3. Крылатов А.Ю, Раевская А.П. Построение допустимой области значений спроса на перемещение в загруженной улично-дорожной сети Математическая Теория Игр и её Приложения, Т. 14, в. 3, с. 22–44 (год публикации - 2022)

4. Ермолин Н.А., Хитрая В.А., Хитрый А.В., Мазалов В.В., Никитина Н.Н. Modeling of the city’s transport network using game-theoretic methods on the example of Petrozavodsk Contributions to Game Theory and Management (год публикации - 2022)

5. Крылатов А.Ю, Раевская А.П., Цзяньронг Ли Equilibrium Supply-Demand Allocation in a Single-Commodity Network Contributions to Game Theory and Management (год публикации - 2022)

6. Никитина Н.Н., Ивашко Е.Е. Расчет центральности в анализе загруженности городских дорог на примере г. Петрозаводск Математическая теория игр и ее приложения, Т. 15, в. 3, с. 41-63 (год публикации - 2023)

7. Чиркова Ю.В., Мазалов В.В. Equilibrium Arrivals to Preemptive Queueing System with Fixed and Random Population Size Journal of the Operations Research Society of China, P. 1-16 (год публикации - 2023)
10.1007/s40305-023-00461-9

8. Чиркова Ю.В. Equilibrium Arrivals to Preemptive Queueing System with Fixed Reward for Completing Request Lecture Notes in Computer Science, Vol. 13930, p. 241–254 (год публикации - 2023)
10.1007/978-3-031-35305-5_16

9. Чиркова Ю.В. Сетевые игры: равновесное и оптимальное поведение дис. ... д-ра физ.-мат. наук, дис. ... д-ра физ.-мат. наук. Петрозаводск, 2022. 352 с. (год публикации - 2023)

10. Бородина А.В., Мазалов В.В. On the Equilibrium in a Queuing System with Retrials and Strategic Arrivals Mathematics, 11(16), 3535 (год публикации - 2023)
10.3390/math11163535

11. Мазалов В.В., Хитрая В.А. Ранжирование вершин графа с использованием абсолютных потенциалов узлов электрической цепи Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, Т. 19, №2, с. 233-250 (год публикации - 2023)
10.21638/11701/spbu10.2023.209

12. Хитрая В.А., Мазалов В.В. Теоретико-игровая центральность вершин ориентированного графа Математическая теория игр и ее приложения, Т. 15, №3, с. 64-87 (год публикации - 2023)

13. Хитрая В.А., Хитрый А.В. Веб-сервис для визуализации дорожной сети города Петрозаводска Труды Карельского научного центра РАН. Серия «Математическое моделирование и информационные технологии», № 4, с. 54-63 (год публикации - 2023)
10.17076/mat1780

14. Никитина Н.Н., Ивашко Е.Е. High-throughput computing approach to modeling of public transport routes Lecture Notes in Networks and Systems (год публикации - 2024)

15. Крылатов А.Ю, Раевская А.П. Competitive resource allocation among urban congestion areas in a modern big city Journal of the Operations Research Society of China (год публикации - 2024)

16. Чиркова Ю.В. Потенциальная игра в параллельной транспортной сети с симметричными экстерналиями Математическая теория игр и ее приложения, Т. 15, №4, с. 94-105 (год публикации - 2023)

17. Никитина Н.Н., Мазалов В.В. Потенциал в игре заполнения с разными типами транспорта Математическая теория игр и ее приложения, Т. 15, в. 4, с. 79-93 (год публикации - 2023)

18. Крылатов А.Ю., Раевская А.П., Мурзин И. Multi-output regression for travel demand estimation in an urban road network Lecture Notes in Computer Science (год публикации - 2025)

19. Мазалов В.В., Яшин В.В. A Multi-Step Model for Pie Cutting with Random Offers Mathematics, 12(8), 1150 (год публикации - 2024)
10.3390/math12081150

20. Хитрая В.А., Мазалов В.В. Game-Theoretic Centrality of Directed Graph Vertices Automation and Remote Control, Vol. 85, No. 2. P. 245–258. (год публикации - 2024)
10.1134/S0005117924020061

21. Никитина Н.Н., Ивашко Е.Е. Centrality Analysis of a City Road Network Trends in Mathematics, In: Petrosyan, L.A., Mazalov, V., Zenkevich, N.A. (eds) Frontiers of Dynamic Games. GTA 2022. Trends in Mathematics. Vol. Pp. 141–152. Birkhäuser, Cham. (год публикации - 2024)
10.1007/978-3-031-66379-6_10

22. Мазалов В.В., Коновальчикова Е.Н. Равновесие в модели ценообразования на рынке пассажирских перевозок Труды Института математики и механики УрО РАН, Т. 30, № 3. С. 182-190. (год публикации - 2024)
10.21538/0134-4889-2024-30-3-182-190

23. Реттиева А.Н. Кооперативные многокритериальные динамические игры: применение в транспортных задачах Математическая теория игр и её приложения, Т. 16, вып. 3, с. 58-76 (год публикации - 2024)
10.17076/mgta_2024_3_80

24. Никитина Н.Н., Мазалов В.В. Potential in congestion game with different types of vehicles Doklady Mathematics (год публикации - 2025)

25. Никитина Н.Н., Ивашко Е.Е. Calculation of Centrality in the Analysis of Congestion of City Roads on the Example of Petrozavodsk Automation and Remote Control, Vol. 85, pp. 213–224 (год публикации - 2024)
10.1134/S0005117924020085

26. Никитина Н.Н., Ивашко Е.Е. Edge Ranking in a Transport Graph of Petrozavodsk Basing on Equilibrium Flows Contributions to Game Theory and Management (год публикации - 2024)

27. Мазалов В.В., Чжоу Дж. Dynamic stability of coalition formation in dynamic games Operations Research Letters, Vol. 55, 107138 (год публикации - 2024)
10.1016/j.orl.2024.107138

28. Чиркова Ю.В. Potential Game in General Transport Network with Symmetric Externalities Mathematical Optimization Theory and Operations Research. MOTOR 2024. Lecture Notes in Computer Science, vol 14766. Springer, Cham, vol. 14766, pp. 231-242 (год публикации - 2024)
10.1007/978-3-031-62792-7_16

29. Чиркова Ю.В. Анализ транспортных потоков на дорожном графе Петрозаводска XIV ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ (ВСПУ-2024): сборник научных трудов. 17-20 июня 2024 г., Москва / Под общ. ред. Д.А. Новикова; Ин-т Проблем упр. им. В.А. Трапезникова Рос. акад. наук, XIV ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ (ВСПУ-2024): сборник научных трудов. 17-20 июня 2024 г., Москва / Под общ. ред. Д.А. Новикова; Ин-т Проблем упр. им. В.А. Трапезникова Рос. акад. наук, 2024. C. 3990-3994 (год публикации - 2024)

30. Чиркова Ю.В. Исследование вычислительной сложности алгоритма нахождения равновесного по Вардропу распределения транспортных потоков Математическая теория игр и ее приложения, т. 16, в. 4, с. 95-109 (год публикации - 2024)
10.17076/mgta_2024_4_82

31. Крылатов А.Ю., Король М.М., Раевская А.П. Equilibration Operators for Accurate Traffic Flow Assignment in Urban Road Networks Lecture Notes in Networks and Systems, In: Silhavy, R., Silhavy, P. (eds) Cybernetics and Control Theory in Systems. CSOC 2024. Lecture Notes in Networks and Systems, vol 1119. Pp. 526–535. Springer, Cham. (год публикации - 2024)
10.1007/978-3-031-70300-3_39

32. Хитрая В.А. Теоретико-игровые меры центральности в сетях и приложения Диссертация на соискание ученой степени кандидата физико-математических наук, Диссертация на соискание ученой степени кандидата физико-математических наук. Петрозаводск, 2024. 129 с. (год публикации - 2024)

33. Реттиева А.Н. Cooperation in Dynamic Multicriteria Game on Transport Network Международная конференция «Динамические системы: устойчивость, управление, дифференциальные игры» (SCDG2024), посвященная 100-летию со дня рождения академика Н.Н. Красовского. Материалы (год публикации - 2024)

Публикации

19. Мазалов В.В., Яшин В.В. A Multi-Step Model for Pie Cutting with Random Offers Mathematics, 12(8), 1150 (год публикации - 2024)
10.3390/math12081150

24. Никитина Н.Н., Мазалов В.В. Potential in congestion game with different types of vehicles Doklady Mathematics (год публикации - 2025)

Аннотация результатов, полученных в 2024 году
Разработана теоретико-игровая модель ценообразования на дуопольном рынке транспортных услуг, в которой игроками являются транспортные компании, а пассажиры выбирают маршруты, руководствуясь их функцией полезности, которая определена с помощью спецификации Хотеллинга с учетом сетевого эффекта. Для игры ценообразования найдены равновесные ценовые стратегии и проведено численное моделирование на примере транспортной системы г. Петрозаводска. Исследована многокритериальная динамическая транспортная задача, где центр распределяет маршруты между транспортными компаниями и наказывает участников, отклоняющихся от кооперативного поведения. Проведено численное моделирование с использованием данных об общественном транспорте г. Петрозаводска. Разработана процедура ранжирования ребер транспортного графа, результат которой способствует ускорению вычисления фактического равновесного распределения транспортных потоков. Разработана процедура ранжирования ребер транспортного графа, результат которой способствует прогнозированию последствий краткосрочных модификаций транспортного графа, таких как ДТП. Исследована теоретико-игровая модель маршрутизации со сложными игроками, в которой транспортные компании распределяют свои транспортные средства между существующими маршрутами, стремясь минимизировать затраты. Доказано существование равновесия по Нэшу для ряда случаев с нелинейными функциями задержек. Рассмотрен теоретико-игровой подход к вычислению значения центральности вершин ориентированного графа, основанный на числе появления вершин в путях фиксированной длины. Предложено определять центральность вершины как решение кооперативной игры, где характеристическая функция задается как число простых путей фиксированной длины в подграфах, соответствующих коалициям. Введено понятие интегральной центральности как значения определенного интеграла от функции дележа. Доказано, что данная мера центральности удовлетворяет аксиомам Boldi-Vigna. Исследована устойчивость коалиционных структур в динамических коалиционных играх. Введена концепция динамически устойчивого коалиционного разбиения по Нэшу для динамических игр. Найдены условия, при которых возникает динамическая устойчивость, с использованием согласованной во времени процедуры условного распределения для распределения выигрышей по оптимальным траекториям. Для модели Вардропа на графе произвольной топологии и BPR-функциями задержки с попарно симметричными линейными экстерналиями доказано, что игра является потенциальной, имеет единственное равновесие по Вардропу, а значение цены анархии ограничено величиной 4/3. Получено математическое выражение оператора уравновешивания, которое возвращает распределение потоков, обеспечивающих равное время движения на использованных маршрутах между каждой парой узлов отправления-прибытия. Реализован соответствующий оператор и исследованы ключевые особенности его применения на практике. Показано, что оператор ведет себя в соответствии с алгоритмически реализованными аналогами, однако основным преимуществом явной формы оператора является высокая точность решения. Разработан инструмент оценки спроса на перемещение в улично-дорожной сети на основе технологии искусственного интеллекта. Задача поиска спроса на поездки сформулирована как обратная к распределению потоков. Разработаны модели регрессии с несколькими выходами для оценки значений спроса на поездку для улично-дорожной сети с множеством пар узлов отправления-прибытия. Для создания данных для обучения и тестовых выборок использованы решения нелинейной задачи оптимизации равновесного распределения потоков. Обновлена и актуализирована информация о состоянии транспортного графа города Петрозаводска (1587 вершин, 3903 дуги). Доработана и зарегистрирована программная система на языке Python для расчета и визуализации равновесных по Вардропу транспортных потоков на транспортном графе большой размерности (граф г. Петрозаводска). Проведены численные эксперименты по нахождению и сравнению равновесных и оптимальных для системы распределений транспортных потоков для текущего состояния обновленного дорожного графа города Петрозаводска. Проведены численные эксперименты по исследованию вычислительной сложности алгоритма нахождения равновесного по Вардропу распределения транспортных потоков в зависимости от размерности модели. Анализ результатов проведенных экспериментов для исследованных моделей с числом вершин от 40 до 120 показывает близкий к кубическому рост среднего времени выполнения программы с квадратичным ростом числа итераций.

Публикации

19. Мазалов В.В., Яшин В.В. A Multi-Step Model for Pie Cutting with Random Offers Mathematics, 12(8), 1150 (год публикации - 2024)
10.3390/math12081150

24. Никитина Н.Н., Мазалов В.В. Potential in congestion game with different types of vehicles Doklady Mathematics (год публикации - 2025)

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