ПОИСК ГЛОБАЛЬНОГО ОПТИМУМА В ЗАДАЧЕ ОПТИМИЗАЦИИ ТОПОЛОГИИ СЕТИ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Статья посвящена проблеме поиска глобального оптимума в задаче оптимизации топологии сети для случая сетей с непересекающимися путями. В рассматриваемой постановке задачи менеджер сети инвестирует в пропускные способности ее элементов, стремясь минимизировать общую задержку, возникающую в результате равновесного распределения потоков. Доказано, что решение исследуемой задачи с необходимостью должно разрешать определенную задачу минимакса. При этом получены условия оптимальности решений возникающей задачи минимакса при достаточно естественных допущениях. На основе полученных результатов разработан новый алгоритм решения задачи оптимизации топологии сети с непересекающимися путями. Библ. 20. Фиг. 3. Табл. 2.

Об авторах

А. Ю Крылатов

СПбГУ; Институт проблем транспорта

Email: a.krylatov@spbu.ru
Санкт-Петербург; Санкт-Петербург

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

  1. Stackelberg H.V. Marktform und Gleichgewicht. Berlin: Springer, 1934 (English Translated: The Theory of the Market Economy. Oxford: Oxford Univer. Press, 1952).
  2. Migdalas A. Bilevel programming in traffic planning: Models, methods and challenge // J. Global Optimizat. 1995. V. 7. P. 381–405.
  3. Krylatov A.Y., Zakharov V.V., Malygin I.G. Competitive traffic assignment in road networks // Transport and Telecommunicat. 2016. V. 17. № 3. P 212–221.
  4. Krylatov A., Raevskaya A. Freight flow assignment in the intermodal logistics network // Transportat. Res. Procedia. 2023. V. 68C. P. 492–498.
  5. Xing C., Jing Y., Wang S., Ma S., Poor H.V. New viewpoint and algorithms for Wwater-filling solutions in wireless communications // IEEE Transact. on Signal Proces. 2020. V. 68. P. 1618–1634.
  6. Suh S., Kim T. Solving nonlinear bilevel programming models of the equilibrium network design problem: a comparative review // Ann. Operat. Res. 1992. V. 34. № 1. P. 203–218.
  7. Yang H., Bell M.G.H. Models and algorithms for road network design: a review and some new developments // Transport Rev. 1998. V. 18. № 3. P. 257–278.
  8. Abdulaal M., LeBlanc L. J. Continuous equilibrium network design models // Transportat. Res. Part B. 1979. V. 13. № 1. P. 19–32.
  9. Marcotte P. Network optimization with continuous control parameters // Transportat. Sci. 1983. V. 17. № 2. P. 181– 197.
  10. Marcotte P., Marquis G. Efficient implementation of heuristics for the continuous network design problem // Ann. Operat. Res. 1992. V. 34. № 1. P. 163–176.
  11. Suwansirikul C., Friesz T.L., Tobin R.L. Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem // Transportat. Sci. 1987. V. 21. № 4. P. 227–292.
  12. Tobin R. L., Friesz T. L. Sensitivity analysis for equilibrium network Fflow // Transportat. Sci. 1988. V. 22. № 4. P. 231–293.
  13. Tobin R. L. Sensitivity analysis for variational inequalities // J. Optimizat. Theory and Appl. 1986. V. 48. № 1. P. 191–204.
  14. Chiou S. Bilevel programming for the continuous transport network design problem // Transportat. Res. Part B. 2005. V. 39. № 4. P. 361–383.
  15. Friesz T.L., Cho H.-J., Mehta N.J., Tobin R.L., Anandalingam G. A simulated annealing approach to the network design problem with variational inequality constraints // Transportat. Sci. 1992. V. 26. № 1. P. 1–68.
  16. Meng Q., Yang H., Bell M.G.H. An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem // Transportat. Res. B. 2001. V. 35. P. 83–105.
  17. Li C., Yang H., Zhu D., Meng Q. A global optimization method for continuous network design problems // Transportat. Res. Part B. 2012. V. 46. № 9. P. 1144–1158.
  18. Крылатов А. Ю. Распределение потока в сети как задача поиска неподвижной точки // Дискретный анализ и исслед. операций. 2016. T. 23. № 2. C. 63–87 (English Translated: Krylatov A.Yu. Network flow assignment as a fixed point problem // J. Appl. and Industrial Math. 2016. V. 10. № 2. P. 243–256.)
  19. Schmeidler D. Equilibrium points of nonatomic games // J. Stat. Phys. 1973. V. 7. № 4. P. 295–300.
  20. Milchtaich I. Internalization of social cost in congestion games // Economic Theory. 2021. V. 71. P. 717–760.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024