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

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

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

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

DOI: 10.33048/daio.2020.27.658

Коннов Игорь Васильевич ¹
Лайтинен Эркки ²
Пинягина Ольга Владиславовна ¹
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.