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

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

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.

Sobre autores

N. Iltyakov

Moscow Institute of Physics and Technology

Autor responsável pela correspondência
Email: iltyakov.nik@gmail.com
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9

M. Obozov

Moscow Institute of Physics and Technology

Autor responsável pela correspondência
Email: obozovmark9@gmail.com
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9

I. Dyshlevski

Moscow Institute of Physics and Technology

Autor responsável pela correspondência
Email: igordyslevski@gmail.com
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9

D. Yarmoshik

Moscow Institute of Physics and Technology
; Institute for Information Transmission Problems of the RAS (Kharkevich Institute)

Autor responsável pela correspondência
Email: yarmoshik.dv@phystech.edu
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9; Russia, 127051, Moscow, Bolshoi Karetny lane, 19, build. 1

M. Kubentaeva

Moscow Institute of Physics and Technology

Autor responsável pela correspondência
Email: kubentay@gmail.com
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9

A. Gasnikov

Moscow Institute of Physics and Technology
; Institute for Information Transmission Problems of the RAS (Kharkevich Institute); Caucasian Mathematical Center of the Adyghe State University

Autor responsável pela correspondência
Email: gasnikov@yandex.ru
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9; Russia, 127051, Moscow, Bolshoi Karetny lane, 19, build. 1; Republic of Adygea, 385016, Maykop, st. Pervomaiskaya, 208

E. Gasnikova

Moscow Institute of Physics and Technology

Autor responsável pela correspondência
Email: egasnikov@yandex.ru
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9

Bibliografia

  1. Ortúzar J.D., Willumsen L.G. Modelling transport. John Wiley and Sons. West Sussex, England. 2002.
  2. Boyles S.D., Lownes N.E., Unnikrishnan A. Transportation network analysis. Volume I: Static and Dynamic Traffic Assignment, 2020.
  3. Гасников А.В., Гасникова Е.В. Модели равновесного распределения потоков в больших сетях. М.: УРСС, 2023.
  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. Гасников А.В. и др. О трехстадийной версии модели стационарной динамики транспортных потоков // Математическое моделирование. 2014. Т. 26. № 6. С. 34–70.
  6. Gasnikova E. et al. An evolutionary view on equilibrium models of transport flows // Mathematics. 2023. V. 11. № 4. P. 858.
  7. Котлярова Е.В. и др. Поиск равновесий в двухстадийных моделях распределения транспортных потоков по сети // Компьютерные исследования и моделирование. 2021. Т. 13. № 2. С. 365–379.
  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. 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. Баймурзина Д.Р. и др. Универсальный метод поиска равновесий и стохастических равновесий в транспортных сетях // Журнал вычислительной математики и математической физики. 2019. Т. 59. № 1. С. 21–36.
  11. Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов // Труды Московского физико-технического института. 2016. Т. 8. № 2 (30). С. 67–100.
  12. Gasnikova E. et al. Sufficient conditions for multi-stages traffic assignment model to be the convex optimization problem. arXiv:2305.09069.
  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. Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова с приложениями М.Л. Бланка, К.В. Воронцова и Ю.В. Чеховича, Е.В. Гасниковой, А.А. Замятина и В.А. Малышева, А.В. Колесникова, Ю.Е. Нестерова и С.В. Шпирко, А.М. Райгородского, с предисловием руководителя департамента транспорта г. Москвы М.С. Ликсутова. М.: МЦНМО, 2013. 427 с., 2-е изд.
  15. Patriksson M. The traffic assignment problem: models and methods. Courier Dover Publications, 2015.
  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. 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. Котлярова Е.В. и др. Обоснование связи модели Бэкмана с вырождающимися функциями затрат с моделью стабильной динамики // Компьютерные исследования и моделирование. 2022. Т. 14 : 2. С. 335–342.
  19. Вильсон А.Дж. Энтропийные методы моделирования сложных систем. М.: Наука, 1978.
  20. Гасников А.В. и др. Эволюционные выводы энтропийной модели расчета матрицы корреспонденций // Математическое моделирование. 2016. Т. 28. № 4. С. 111–124.
  21. Nesterov Y. Smoothing technique and its applications in semidefinite optimization //Mathematical Programming. 2007. V. 110. № 2. P. 245–259.
  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. Guminov S. et al. Accelerated alternating minimization // ICML 2021.
  24. Tupitsa N. et al. Numerical Methods for Large-Scale Optimal Transport. arXiv:2210.11368.
  25. Nesterov Y. Universal gradient methods for convex optimization problems // Mathematical Programming. 2015. V. 152. № 1–2. P. 381–404.
  26. Гасников А.В., Нестеров Ю.Е. Универсальный метод для задач стохастической композитной оптимизации // Журнал вычислительной математики и математической физики. 2018. Т. 58. № 1. С. 51–68.
  27. Kovalev D., Gasnikov A., Malinovsky G. An Optimal Algorithm for Strongly Convex Min-min Optimization. arXiv:2212.14439.
  28. Gasnikov–Nesterov A universal method for stochastic problems composite optimization. arxiv preprint arXiv:1604.05275. 2016
  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. Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов. arxiv preprint arXiv:1508.02182. 2015.
  31. Алиев А.С., Мазурин Д.С., Максимова Д.А., Швецов В.И. Структура комплексной модели транспортной системы г. Москвы // Труды Института системного анализа Российской академии наук. 2015. Т. 65 (1). С. 3–15.
  32. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. arXiv:1711.00394.
  33. Ссылка на репозиторий с исходным кодом вычислительных экспериментов https://github.com/Lareton/transport_network_optimization
  34. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.
  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. 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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar
2.

Baixar (157KB)
Metadados
3.

Baixar (176KB)
Metadados
4.

Baixar (158KB)
Metadados

Declaração de direitos autorais © Н.А. Ильтяков, М.А. Обозов, И.М. Дышлевский, Д.В. Ярмошик, М.Б. Кубентаева, А.В. Гасников, Е.В. Гасникова, 2023

Este site utiliza cookies

Ao continuar usando nosso site, você concorda com o procedimento de cookies que mantêm o site funcionando normalmente.

Informação sobre cookies