Двойственные методы поиска равновесий в смешанных моделях распределения потоков в больших транспортных сетях

В работе изучается задача поиска равновесного распределения потоков в транспортной сети, часть ребер которой характеризуется функциями затрат, а часть ребер характеризуется пропускной способностью и постоянными затратами на прохождение в отсутствие затора. Такие модели (получившие название смешанные модели) возникают, например, при описании грузоперевозок РЖД. Частным случаем смешанной модели является семейство моделей равновесного распределения потоков по путям: BMW-модель (модель Бэкмана), модель стабильной динамики. Поиск равновесия в смешанной модели сводится к решению задачи выпуклой оптимизации. В данной статье строится двойственная задача, которая решается методом зеркального спуска (двойственных усреднений). Приводятся два различных способа восстановления решения исходной (прямой) задачи. Показывается, что предложенные подходы допускают эффективное распараллеливание. Результаты о скорости сходимости предложенных численных методов соответствуют известным нижним оракульным оценкам для данного класса задач (с точностью до мультипликативных констант). Библ. 20.

Ключевые слова

прямо-двойственный метод, равновесное распределение потоков в транспортной сети, метод зеркального спуска, поиск кратчайших путей

Источник финансирования

Работа А.В. Гасникова выполнена при финансовой поддержке РФФИ (код проекта 15-31-70001_а_мос).

Получено

19.12.2018

Дата публикации

19.12.2018

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Гасников А. В. , Гасникова Е. В. , Нестеров Ю. Е. Двойственные методы поиска равновесий в смешанных моделях распределения потоков в больших транспортных сетях // Журнал вычислительной математики и математической физики – 2018. – Tом 58. – Номер 9 C. 1447-1454 [Электронный ресурс]. URL: http://ras.jes.su/zvmmf/s207987840001699-7-1-ru (дата обращения: 29.04.2024). DOI: 10.31857/S004446690002523-6
MLA	Gasnikov, A., Gasnikova, E., Nesterov, Yu "Dual equilibrium search methods in mixed flow distribution models in large transport networks." Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58.9 (2018):1447-1454. DOI: 10.31857/S004446690002523-6
APA	Gasnikov A., Gasnikova E., Nesterov Y. (2018). Dual equilibrium search methods in mixed flow distribution models in large transport networks. Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58(9), pp.1447-1454 DOI: 10.31857/S004446690002523-6

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 957

Оценка читателей: голосов 0

1. Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики // Матем. моделирование. 2016. Т. 28. № 10. С. 40–64. arXiv:1506.00293

2. Patriksson M. The traffic assignment problem. Models and methods. Utrecht, Netherlands: VSP, 1994.

3. Nesterov Y., de Palma A. Stationary dynamic solutions in congested transportation. Networks: Summary and Perspectives // Networks Spatial Econ. 2003. № 3(3). P. 371–395.

4. Гасников А.В., Дорн Ю.В., Нестеров Ю.Е, Шпирко С.В. О трехстадийной версии модели стационарной динамики транспортных потоков // Матем. моделирование. 2014. Т. 26. № 6. C. 34–70. arXiv:1405.7630

5. Ващенко М.П., Гасников А.В., Молчанов Е.Г., Поспелова Л.Я., Шананин А.А. Вычислимые модели и численные методы для анализа тарифной политики железнодорожных грузоперевозок. М.: ВЦ РАН, 2014. arXiv:1501.02205

6. Курош А.Г. К урс высшей алгебры. М.: Наука, 1965.

7. Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013. http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf

8. Duchi J.C., Shalev-Shwartz S., Singer Y., Tewari A. Composite objective mirror descent // COLT. 2010. P. 14–26. http://www.cs.utexas.edu/users/ambuj/research/duchi10composite.pdf

9. Нестеров Ю.Е. Модели равновесных транспортных потоков и алгоритмы их нахождения. Выступление на семинаре “Математическое моделирование транспортных потоков” в МЦНМО 14 апреля 2012 г. http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=6433

10. Nesterov Y. Primal-dual subgradient methods for convex problems // Math. Program. Ser. B. 2009. V. 120(1). P. 261–283.

11. Nesterov Yu. Complexity bounds for primal-dual methods minimizing the model of objective function // CORE Discussion Papers. 2015/03. 2015.

12. Аникин А.С., Гасников А.В., Двуреченский П.Е., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях // Ж. вычисл. матем. и матем. физ. 2017. Т. 57. № 8. С. 1270–1284. arXiv:1602.01686

13. Nemirovski A., Onn S., Rothblum U.G. Accuracy certificates for computational problems with convex structure // Mathematics of Operation Research. 2010. V. 35. № 1. P. 52–78.

14. Nesterov Yu., Shpirko S. Primal-dual subgradient method for huge-scale linear conic problem // SIAM J. Optim. 2014. V. 24. № 3. P. 1444–1457. http://www.optimization-online.org/DB_FILE/2012/08/3590.pdf

15. Гасников А.В., Нестеров Ю.Е. Универсальный метод для задач стохастической композитной оптимизации // Ж. вычисл. матем. и матем. физ. 2018. Т. 58. № 1. С. 52–69. arXiv:1604.05275

16. Ahuja R.K., Magnati T.L., Orlin J.B. Network flows: Theory, algorithms and applications. Prentice Hall, 1993.

17. Bast H., Delling D., Goldberg A., Muller-Hannemann M., Pajor T., Sanders P., Wagner D., Werneck R.F. Route planning in transportation networks // Microsoft Technical Report. 2015. arXiv:1504.05140

18. https://github.com/vikalijko/transport

19. https://github.com/leonshting/traffic_equilibrium.git

20. https://github.com/bstabler/TransportationNetworks