1. На главную
  2. Электронные версии
  3. Программирование
  4. № 6, 2023

Программирование, 2023, № 6, стр. 36-48

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

Н. А. Ильтяков a, *, М. А. Обозов a, **, И. М. Дышлевский a, ***, Д. В. Ярмошик a, b, ****, М. Б. Кубентаева a, *****, А. В. Гасников a, b, c, ******, Е. В. Гасникова a, *******

a Московский физико-технический институт
141701 г. Долгопрудный, Институтский пер., 9, Россия

b Институт проблем передачи информации РАН
127051 г. Москва, Большой Каретный пер., 19, стр. 1, Россия

c Кавказский математический центр Адыгейского гос. университета
385000 г. Майкоп, Первомайская ул., 208, Россия

* E-mail: iltyakov.nik@gmail.com
** E-mail: obozovmark9@gmail.com
*** E-mail: igordyslevski@gmail.com
**** E-mail: yarmoshik.dv@phystech.edu
***** E-mail: kubentay@gmail.com
****** E-mail: gasnikov@yandex.ru
******* E-mail: egasnikov@yandex.ru

Поступила в редакцию 13.06.2023
После доработки 16.07.2023
Принята к публикации 20.07.2023

Аннотация

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

Список литературы

  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.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Программирование

Архивы выпусков Информация о журнале Отправить рукопись в журнал