EN|RU
Свободный доступ к полным текстам предоставляется после 1 июля года, следующего за годом публикации. Полный текст этой статьи можно приобрести на сайте elibrary.ru.

Том 27, номер 1, 2020 г., Стр. 43–60

УДК 519.8
Коннов И. В., Лайтинен Э., Пинягина О. В.
Приближенные методы частичной линеаризации для задач потокового равновесия

Аннотация:
Предлагаются упрощённые модификации метода частичной линеаризации для задачи потокового равновесия со смешанным спросом. В этих модификациях вспомогательная задача поиска направления решается приближённо. Для предложенных модификаций сохраняются основные свойства сходимости исходного метода, а неточное решение вспомогательных задач позволяет сократить вычислительные затраты. Предварительные численные тесты показали преимущество и эффективность предложенного подхода по сравнению с точным вариантом метода.
Табл. 3, ил. 2, библиогр. 17.

Ключевые слова: задача потокового равновесия, метод частичной линеаризации, направление спуска, приближённое решение

DOI: 10.33048/daio.2020.27.658

Коннов Игорь Васильевич 1
Лайтинен Эркки 2
Пинягина Ольга Владиславовна 1
1. Казанский федеральный университет,
ул. Кремлёвская, 18, 420008 Казань, Россия
2. Университет Оулу,
ул. Пентти Кайтеран, 1, 90014 Оулу, Финляндия
e-mail: konn-igor@ya.ru, erkki.laitinen@oulu.fi, olga.piniaguina@kpfu.ru

Статья поступила 23 апреля 2019 г.
После доработки — 5 ноября 2019 г.
Принята к публикации 27 ноября 2019 г

Литература

[1] Dafermos S. Traffic equilibrium and variational inequalities // Transp. Sci. 1980. Vol. 14, No. 1. P. 42–54.

[2] Dafermos S. The general multimodal network equilibrium problem with elastic demand // Networks. 1982. Vol. 12, No. 1. P. 57–72.

[3] Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Acad. Publ., 1999. 444 p.

[4] Patriksson M. The traffic assignment problem: models and methods. Mineola, NY: Dover Publ., 2015. 240 p.

[5] Magnanti T. L. Models and algorithms for predicting urban traffic equilibria // Transportation Planning Models. Amsterdam: North–Holland, 1984. P. 153–185.

[6] Konnov I. V., Pinyagina O. V. Partial linearization method for network equilibrium problems with elastic demands // Discrete Optimization and Operations Research (DOOR 2016). Proc. 9th Int. Conf. (Vladivostok, Russia, Sep. 19–23, 2016). Heidelberg: Springer, 2016. P. 418–429. (Lect. Notes Comput. Sci.; Vol. 9869).

[7] Konnov I. V. Simplified versions of the conditional gradient method // Optimization. 2018. Vol. 67, No. 12. P. 2275–2290.

[8] Mine H., Fukushima M. A minimization method for the sum of a convex function and a continuously differentiable function // J. Optim. Theor. Appl. 1981. Vol. 33. P. 9–23.

[9] Patriksson M. Cost approximation: a unified framework of descent algorithms for nonlinear programs // SIAM J. Optim. 1998. Vol. 8. P. 561–582.

[10] Patriksson M. Nonlinear programming and variational inequality problems: A unified approach. Dordrecht: Kluwer, 1999. 348 p.

[11] Bredies K., Lorenz D. A., Maass P. A generalized conditional gradient method and its connection to an iterative shrinkage method // Comput. Optim. Appl. 2009. Vol. 42. P. 173–193.

[12] Scutari G., Facchinei F., Song P., Palomar D. P., Pang J.-S. Decomposition by partial linearization: Parallel optimization of multi-agent systems // IEEE Trans. Signal Process. 2014. Vol. 62. P. 641–656.

[13] Konnov I. V. On auction equilibrium models with network applications // NETNOMICS: Economic Research and Electronic Networking. 2015. Vol. 16, No. 1. P. 107–125.

[14] Pinyagina O. V. On a network equilibrium problem with mixed demand // Discrete Optimization and Operations Research (DOOR 2016). Proc. 9th Int. Conf. (Vladivostok, Russia, Sep. 19–23, 2016). Heidelberg: Springer, 2016. P. 578–583. (Lect. Notes Comput. Sci.; Vol. 9869).

[15] Пинягина О. В. Задача потокового равновесия со смешанным спросом // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 4. С. 77–94.

[16] Bertsekas D. P., Gafni E. M. Projection methods for variational inequalities with application to the traffic assignment problem // Nondifferential and Variational Techniques in Optimization. Heidelberg: Springer, 1982. P. 139–159.

[17] Nagurney A. B. Comparative tests of multimodal traffic equilibrium methods // Transp. Res., Part B: Methodological. 1984. Vol. 18, No. 1. P. 469–485.

 © Институт математики им. С. Л. Соболева, 2015