ОМНПрограммирование Programming and Computer Software

  • ISSN (Print) 0132-3474
  • ISSN (Online) 3034-5847

ОБ УСКОРЕННЫХ ПОКОМПОНЕНТНЫХ МЕТОДАХ ПОИСКА РАВНОВЕСИЙ В ДВУХСТАДИЙНОЙ МОДЕЛИ РАВНОВЕСНОГО РАСПРЕДЕЛЕНИЯ ТРАНСПОРТНЫХ ПОТОКОВ

Код статьи
10.31857/S0132347423060055-1
DOI
10.31857/S0132347423060055
Тип публикации
Статус публикации
Опубликовано
Авторы
Том/ Выпуск
Том / Номер выпуска 6
Страницы
36-48
Аннотация
Поиск равновесия в двухстадийной модели транспортных потоков сводится к решению специальной негладкой задачи выпуклой оптимизации с двумя группами разных переменных. Для численного решения данной задачи в статье предложено использовать ускоренный блочно-покомпонентный метод Нестерова–Стиха со специальным выбором вероятностей блоков на каждой итерации (одного из двух). Теоретические оценки сложности такого подхода могут заметно улучшать оценки используемых ранее подходов. Однако в общем случае не гарантируют более быстрой сходимости. В статье проведены численные эксперименты с предложенными алгоритмами.
Ключевые слова
Дата публикации
17.09.2025
Год выхода
2025
Всего подписок
0
Всего просмотров
17

Библиография

  1. 1. Ortúzar J.D., Willumsen L.G. Modelling transport. John Wiley and Sons. West Sussex, England. 2002.
  2. 2. Boyles S.D., Lownes N.E., Unnikrishnan A. Transportation network analysis. Volume I: Static and Dynamic Traffic Assignment, 2020.
  3. 3. Гасников А.В., Гасникова Е.В. Модели равновесного распределения потоков в больших сетях. М.: УРСС, 2023.
  4. 4. Evans S.P. Derivation and analysis of some models for combining trip distribution and assignment // Transportation Research. 1976. V. 10 (1). P. 37–57.
  5. 5. Гасников А.В. и др. О трехстадийной версии модели стационарной динамики транспортных потоков // Математическое моделирование. 2014. Т. 26. № 6. С. 34–70.
  6. 6. Gasnikova E. et al. An evolutionary view on equilibrium models of transport flows // Mathematics. 2023. V. 11. № 4. P. 858.
  7. 7. Котлярова Е.В. и др. Поиск равновесий в двухстадийных моделях распределения транспортных потоков по сети // Компьютерные исследования и моделирование. 2021. Т. 13. № 2. С. 365–379.
  8. 8. Kubentaeva M. et al. Primal-Dual Gradient Methods for Searching Network Equilibria in Combined Models with Nested Choice Structure and Capacity Constraints. arXive:2307.00427
  9. 9. Nesterov Y., Stich S. Efficiency of the accelerated coordinate descent method on structured optimization problems // SIAM Journal on Optimization. 2017. V. 27. № 1. P. 110–123.
  10. 10. Баймурзина Д.Р. и др. Универсальный метод поиска равновесий и стохастических равновесий в транспортных сетях // Журнал вычислительной математики и математической физики. 2019. Т. 59. № 1. С. 21–36.
  11. 11. Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов // Труды Московского физико-технического института. 2016. Т. 8. № 2 (30). С. 67–100.
  12. 12. Gasnikova E. et al. Sufficient conditions for multi-stages traffic assignment model to be the convex optimization problem. arXiv:2305.09069.
  13. 13. Allen-Zhu Z. et al. Even faster accelerated coordinate descent using non-uniform sampling // International Conference on Machine Learning. PMLR. 2016. V. 1110–1119.
  14. 14. Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова с приложениями М.Л. Бланка, К.В. Воронцова и Ю.В. Чеховича, Е.В. Гасниковой, А.А. Замятина и В.А. Малышева, А.В. Колесникова, Ю.Е. Нестерова и С.В. Шпирко, А.М. Райгородского, с предисловием руководителя департамента транспорта г. Москвы М.С. Ликсутова. М.: МЦНМО, 2013. 427 с., 2-е изд.
  15. 15. Patriksson M. The traffic assignment problem: models and methods. Courier Dover Publications, 2015.
  16. 16. Stabler B., Bar-Gera H., Sall E. Transportation Networks for Research Core Team. Transportation Networks for Research. Accessed Month, Day, Year. [Electronic resource]: https://github.com/bstabler/TransportationNetworks (accessed 16.02.2021).
  17. 17. Nesterov Y., De Palma A. Stationary dynamic solutions in congested transportation networks: summary and perspectives // Networks and spatial economics. 2003. T. 3. № 3. P. 371–395.
  18. 18. Котлярова Е.В. и др. Обоснование связи модели Бэкмана с вырождающимися функциями затрат с моделью стабильной динамики // Компьютерные исследования и моделирование. 2022. Т. 14 : 2. С. 335–342.
  19. 19. Вильсон А.Дж. Энтропийные методы моделирования сложных систем. М.: Наука, 1978.
  20. 20. Гасников А.В. и др. Эволюционные выводы энтропийной модели расчета матрицы корреспонденций // Математическое моделирование. 2016. Т. 28. № 4. С. 111–124.
  21. 21. Nesterov Y. Smoothing technique and its applications in semidefinite optimization //Mathematical Programming. 2007. V. 110. № 2. P. 245–259.
  22. 22. Peyré G., Cuturi M. Computational Optimal Transport: With Applications to Data Science // Foundations and Trends® in Machine Learning. 2019. V. 11. № 5–6. P. 355–607.
  23. 23. Guminov S. et al. Accelerated alternating minimization // ICML 2021.
  24. 24. Tupitsa N. et al. Numerical Methods for Large-Scale Optimal Transport. arXiv:2210.11368.
  25. 25. Nesterov Y. Universal gradient methods for convex optimization problems // Mathematical Programming. 2015. V. 152. № 1–2. P. 381–404.
  26. 26. Гасников А.В., Нестеров Ю.Е. Универсальный метод для задач стохастической композитной оптимизации // Журнал вычислительной математики и математической физики. 2018. Т. 58. № 1. С. 51–68.
  27. 27. Kovalev D., Gasnikov A., Malinovsky G. An Optimal Algorithm for Strongly Convex Min-min Optimization. arXiv:2212.14439.
  28. 28. Gasnikov–Nesterov A universal method for stochastic problems composite optimization. arxiv preprint arXiv:1604.05275. 2016
  29. 29. Meruza Kubentayeva et al. Primal-Dual Gradient Methods for Searching Network Equilibria in Combined Models with Nested Choice Structure and Capacity Constraints. arXiv:2307.00427.
  30. 30. Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов. arxiv preprint arXiv:1508.02182. 2015.
  31. 31. Алиев А.С., Мазурин Д.С., Максимова Д.А., Швецов В.И. Структура комплексной модели транспортной системы г. Москвы // Труды Института системного анализа Российской академии наук. 2015. Т. 65 (1). С. 3–15.
  32. 32. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. arXiv:1711.00394.
  33. 33. Ссылка на репозиторий с исходным кодом вычислительных экспериментов https://github.com/Lareton/transport_network_optimization
  34. 34. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.
  35. 35. Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM Journal on Optimization. 2012. V. 22. № 2. P. 341–362.
  36. 36. De Cea J., Fernandez J. E., Dekock V., Soto A. Solving network equilibrium problems on multimodal urban transportation networks with multiple user classes // Transport Reviews. 2005. V. 25(3). P. 293–317.
QR
Перевести

Индексирование

Scopus

Scopus

Scopus

Crossref

Scopus

Высшая аттестационная комиссия

При Министерстве образования и науки Российской Федерации

Scopus

Научная электронная библиотека