RAS MathematicsПрограммирование Programming and Computer Software

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

On Accelerated Coordinate Descent Methods for Searching Equilibria in Two-Stage Transportation Equilibrium Traffic Flow Distribution Model

PII
10.31857/S0132347423060055-1
DOI
10.31857/S0132347423060055
Publication type
Status
Published
Authors
Volume/ Edition
Volume / Issue number 6
Pages
36-48
Abstract
The search for equilibrium in a two-stage traffic flow model reduces to the solution of a special nonsmooth convex optimization problem with two groups of different variables. For numerical solution of this problem, the paper proposes to use the accelerated block-coordinate Nesterov-Stich method with a special choice of block probabilities at each iteration. Theoretical estimates of the complexity of this approach can markedly improve the estimates of previously used approaches. However, in the general case they do not guarantee faster convergence. Numerical experiments with the proposed algorithms are carried out in the paper.
Keywords
Date of publication
17.09.2025
Year of publication
2025
Number of purchasers
0
Views
19

References

  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
Translate

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

Scopus

Scopus

Scopus

Crossref

Scopus

Higher Attestation Commission

At the Ministry of Education and Science of the Russian Federation

Scopus

Scientific Electronic Library