Достаточность в задаче оптимизации топологии сети

Достаточность в задаче оптимизации топологии сети

Крылатов А. Ю.
Дискретный анализ и исследование операций, 33, 1, 91-113 (2026)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2026.33.831

Аннотация:

Статья посвящена изучению условий достаточности в двухуровневой задаче оптимизации топологии сети. В рассматриваемой постановке задачи менеджер сети инвестирует в пропускные способности маршрутов, стремясь минимизировать общую задержку, возникающую в результате равновесного распределения потоков. Основной массив статей, исследующих соответствующую задачу, посвящён разработке алгоритмов поиска решений на основе необходимых условий оптимальности. В настоящей статье доказывается ряд утверждений, позволяющих проверять множество активных переменных на достаточность при поиске глобального оптимума в задаче оптимизации топологии сети с непересекающимися маршрутами. С практической точки зрения в случае рассматриваемого типа сетей появляется возможность построения множества переменных, достаточного для поиска глобального оптимума посредством работы с переменными только из этого множества. 

Табл. 3, ил. 2, библиогр. 34.

Литература:
  1. Cieslik D. Network design problems // Encyclopedia of optimization. Boston, MA: Springer, 2008.
     
  2. Von Stackelberg H. F. Marktform und Gleichgewicht. Berlin: Springer, 1934. [German].
     
  3. Migdalas A. Bilevel programming in traffic planning: Models, methods and challenge // J. Global Optim. 1995. V. 7. P. 381–405.
     
  4. Samani A. R., Shetab-Boushehri S.-N., Mahmoudi R. Reliable urban transportation network design problem considering recurrent traffic congestions // Adv. Ind. Eng. 2021. V. 55, No. 1. P. 69–89.
     
  5. Zweers B. G., van der Mei R. D. Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings // Eur. J. Oper. Res. 2022. V. 300, No. 1. P. 178–188.
     
  6. Xing C., Jing Y., Wang S., Ma S., Poor H. V. New viewpoint and algorithms for water-filling solutions in wireless communications // IEEE Trans. Signal Proces. 2020. V. 68. P. 1618–1634.
     
  7. Xu X., Chen A., Yang C. A review of sustainable network design for road networks // KSCE J. Civil Eng. 2016. V. 20. P. 1084–1098.
     
  8. Yang H., Bell M. G. H. Models and algorithms for road network design: A review and some new developments // Transp. Rev. 1998. V. 18, No. 3. P. 257–278.
     
  9. Крылатов А. Ю. Распределение потока в сети как задача поиска неподвижной точки // Дискрет. анализ и исслед. операций. 2016. T. 23, № 2. C. 63–87.
     
  10. Magnanti T. L., Wong R. T. Network design and transportation planning: Models and algorithms // Transp. Sci. 1984. V. 18. P. 1–55.
     
  11. Wong S. C., Yang H. Reserve capacity of a signal-controlled road network // Transp. Res. Pt. B. 1997. V. 31. P. 397–402.
     
  12. Gao Z. Y., Wu J. J., Sun H. J. Solution algorithm for the bi-level discrete network design problem // Transp. Res. Pt. B. 2005. V. 39. P. 479–495.
     
  13. Chen A., Zhou Z., Chootinan P., Ryu S., Yang C., Wong S. C. Transport network design problem under uncertainty: A review and new developments // Transp. Rev. 2011. V. 31, No. 6. P. 743–768.
     
  14. Dafermos S. C. Traffic assignment and resource allocation in transportation networks: PhD thesis. Baltimore, MD, 1968.
     
  15. Dantzig G. B., Harvey R. P., Lansdowne Z. F., Robinson D.W., Maier S. F. Formulating and solving the network design problem by decomposition // Transp. Res. Pt. B. 1979. V. 13, No. 1. P. 5–17.
     
  16. Abdulaal M., LeBlanc L. J. Continuous equilibrium network design models // Transp. Res. Pt. B. 1979. V. 13, No. 1. P. 19–32.
     
  17. Tan H. N., Gershwin S. B., Athans M. Hybrid optimization in urban traffic networks. Rep. DOT-TSC-RSPA-79-7. Cambridge, MA: MIT, 1979. 106 p.
     
  18. Friesz T. L. An equivalent optimization problem with combined multiclass distribution assignment and modal split which obviates symmetry restriction // Transp. Res. Pt. B. 1981. V. 15. P. 361–369.
     
  19. Friesz T. L., Anandalingam G., Mehta N. J., Nam K., Shah S. J., Tobin R. L. The multiobjective equilibrium network design problem revisited: A simulated annealing approach // Eur. J. Oper. Res. 1993. V. 65. P. 44–57.
     
  20. Dafermos S. Traffic equilibria and variational inequalities // Transp. Sci. 1980. V. 14. P. 42–54.
     
  21. Marcotte P. Network optimization with continuous control parameters // Transp. Sci. 1983. V. 17, No. 2. P. 181–197.
     
  22. Meng Q., Yang H., Bell M. G. H. An equivalent continuously differentiable model and a locally convergent algorithm for the continuous networks design problem // Transp. Res. Pt. B. 2001. V. 35. P. 83–105.
     
  23. Gao Z., Sun H., Zhang H. A globally convergent algorithm for transportation continuous network design problem // Optim. Eng. 2007. V. 8. P. 241–257.
     
  24. Tobin R. L., Friesz T. L. Sensitivity analysis for equilibrium network flow // Transp. Sci. 1988. V. 22, No. 4. P. 231–293.
     
  25. Tobin R. L. Sensitivity analysis for variational inequalities // J. Optim. Theory Appl. 1986. V. 48, No. 1. P. 191–204.
     
  26. Chiou S. Bilevel programming for the continuous transport network design problem // Transp. Res. Pt. B. 2005. V. 39, No. 4. P. 361–383.
     
  27. Meng Q., Yang H., Bell M. G. H. An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem // Transp. Res. Pt. B. 2001. V. 35. P. 83–105.
     
  28. Suwansirikul C., Friesz T. L., Tobin R. L. Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem // Transp. Sci. 1987. V. 21, No. 4. P. 227–292.
     
  29. Li C., Yang H., Zhu D., Meng Q. A global optimization method for continuous network design problems // Transp. Res. Pt. B. 2012. V. 46, No. 9. P. 1144–1158.
     
  30. Du B., Wang D. Z. W. Solving continuous network design problem with generalized geometric programming approach // Transp. Res. Record. 2016. V. 2567, No. 1. P. 38–46.
     
  31. Gairing M., Harks T., Klimm M. Complexity and approximation of the continuous network design problem // SIAM J. Optim. 2017. V. 27, No. 3. P. 1554–1582.
     
  32. Крылатов А. Ю. Поиск глобального оптимума в задаче оптимизации топологии сети // Журн. вычисл. математики и мат. физики. 2024. Т. 64, № 10. С. 1851–1867.
     
  33. Schmeidler D. Equilibrium points of nonatomic games // J. Stat. Phys. 1973. V. 7, No. 4. P. 295–300.
     
  34. Zhou Z., Yang M., Sun F., Wang Z., Wang B. A continuous transportation network design problem with the consideration of road congestion charging // Sustainability. 2021. V. 13. P. 7008.

Исследование выполнено за счёт Санкт-Петербургского гос. университета (проект № 116814048). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Крылатов Александр Юрьевич
  1. Санкт-Петербургский гос. университет, 
    Университетская наб., 7/9, 199034 Санкт-Петербург, Россия
  2. Институт проблем транспорта, 
    12-я линия, 13, В. О., 199178 Санкт-Петербург, Россия

E-mail: a.krylatov@spbu.ru, aykrylatov@yandex.ru 

Статья поступила 25 марта 2025 г.
После доработки — 30 июля 2025 г.
Принята к публикации 22 декабря 2025 г.

Abstract:

The paper is devoted to the global optimum search in the network design problem with non-interfering routes. Within this paper, we assume that the network manager invests in capacity of the network to minimize overall delay caused by equilibrium flow assignment. We prove that solving the network design problem can be reduced to the subset of routes search, which gives the minimum value of goal function in a finite set of minimax problems. Moreover, we establish how such a subset should be generated in order to ensure that the corresponding value decreases. Eventually, under fairly natural assumptions, we obtain optimality conditions for solutions to emerging minimax problems. For demonstration purposes, we apply the obtained results to a concrete example. 

Tab. 3, illust. 2, bibliogr. 34.

References:
  1. D. Cieslik, Network design problems, in Encyclopedia of Optimization (Springer, Boston, MA, 2008).
     
  2. H. F. Von Stackelberg, Marktform und Gleichgewicht (Springer, Berlin, 1934) [German].
     
  3. A. Migdalas, Bilevel programming in traffic planning: Models, methods and challenge, J. Global Optim. 7, 381–405 (1995).
     
  4. A. R. Samani, S.-N. Shetab-Boushehri, and R. Mahmoudi, Reliable urban transportation network design problem considering recurrent traffic congestions, Adv. Ind. Eng. 55 (1), 69–89 (2021).
     
  5. B. G. Zweers, and R. D. van der Mei, Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings, Eur. J. Oper. Res. 300 (1), 178–188 (2022).
     
  6. C. Xing, Y. Jing, S. Wang, S. Ma, and H. V. Poor, New viewpoint and algorithms for water-filling solutions in wireless communications, IEEE Trans. Signal Proces. 68, 1618–1634 (2020).
     
  7. X. Xu, A. Chen, and C. Yang, A review of sustainable network design for road networks, KSCE J. Civil Eng. 20, 1084–1098 (2016).
     
  8. H. Yang and M. G. H. Bell, Models and algorithms for road network design: A review and some new developments, Transp. Rev. 18 (3), 257–278 (1998).
     
  9. A. Yu. Krylatov, Network flow assignment as a fixed point problem, Diskretn. Anal. Issled. Oper. 23 (2), 63–87 (2016) [J. Appl. Ind. Math. 10 (2), 243–256 (2016)].
     
  10. T. L. Magnanti and R. T. Wong, Network design and transportation planning: Models and algorithms, Transp. Sci. 18, 1–55 (1984).
     
  11. S. C. Wong and H. Yang, Reserve capacity of a signal-controlled road network, Transp. Res., Pt. B, 31, 397–402 (1997).
     
  12. Z. Y. Gao, J. J. Wu, and H. J. Sun, Solution algorithm for the bi-level discrete network design problem, Transp. Res., Pt. B, 39, 479–495 (2005).
     
  13. A. Chen, Z. Zhou, P. Chootinan, S. Ryu, C. Yang, and S. C. Wong, Transport network design problem under uncertainty: A review and new developments, Transp. Rev. 31 (6), 743–768 (2011).
     
  14. S. C. Dafermos, Traffic assignment and resource allocation in transportation networks, PhD Thesis (Baltimore, MD, 1968).
     
  15. G. B. Dantzig, R. P. Harvey, Z. F. Lansdowne, D. W. Robinson, S. F. Maier, Formulating and solving the network design problem by decomposition, Transp. Res., Pt. B, 13 (1), 5–17 (1979).
     
  16. M. Abdulaal and L. J. LeBlanc, Continuous equilibrium network design models, Transp. Res., Pt. B, 13 (1), 19–32 (1979).
     
  17. H. N. Tan, S. B. Gershwin, and M. Athans, Hybrid optimization in urban traffic networks, Rep. DOT-TSC-RSPA-79-7 (MIT, Cambridge, MA, 1979).
     
  18. T. L. Friesz, An equivalent optimization problem with combined multiclass distribution assignment and modal split which obviates symmetry restriction, Transp. Res., Pt. B, 15, 361–369 (1981).
     
  19. T. L. Friesz, G. Anandalingam, N. J. Mehta, K. Nam, S. J. Shah, and R. L. Tobin, The multiobjective equilibrium network design problem revisited: A simulated annealing approach, Eur. J. Oper. Res. 65, 44–57 (1993).
     
  20. S. Dafermos, Traffic equilibria and variational inequalities, Transp. Sci. 14, 42–54 (1980).
     
  21. P. Marcotte, Network optimization with continuous control parameters, Transp. Sci. 17 (2), 181–197 (1983).
     
  22. Q. Meng, H. Yang, and M. G. H. Bell, An equivalent continuously differentiable model and a locally convergent algorithm for the continuous networks design problem, Transp. Res., Pt. B, 35, 83–105 (2001).
     
  23. Z. Gao, H. Sun, and H. Zhang, A globally convergent algorithm for transportation continuous network design problem, Optim. Eng. 8, 241–257 (2007).
     
  24. R. L. Tobin and T. L. Friesz, Sensitivity analysis for equilibrium network flow, Transp. Sci. 22 (4), 231–293 (1988). 
     
  25. R. L. Tobin, Sensitivity analysis for variational inequalities, J. Optim. Theory Appl. 48 (1), 191–204 (1986).
     
  26. S. Chiou, Bilevel programming for the continuous transport network design problem, Transp. Res., Pt. B, 39 (4), 361–383 (2005).
     
  27. Q. Meng, H. Yang, and M. G. H. Bell, An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem, Transp. Res., Pt. B, 35, 83–105 (2001).
     
  28. C. Suwansirikul, T. L. Friesz, and R. L. Tobin, Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem, Transp. Sci. 21 (4), 227–292 (1987).
     
  29. C. Li, H. Yang, D. Zhu, and Q. Meng, A global optimization method for continuous network design problems, Transp. Res., Pt. B, 46 (9), 1144–1158 (2012).
     
  30. B. Du and D. Z. W. Wang, Solving continuous network design problem with generalized geometric programming approach, Transp. Res. Record. 2567 (1), 38–46 (2016).
     
  31. M. Gairing, T. Harks, and M. Klimm, Complexity and approximation of the continuous network design problem, SIAM J. Optim. 27 (3), 1554–1582 (2017).
     
  32. A. Yu. Krylatov, Global optimum search in the network design problem, Zh. Vychisl. Mat. Mat. Fiz. 64 (10), 1851–1867 (2024) [Russian] [Comput. Math. Math. Phys. 64 (10), 2238–2255 (2024)].
     
  33. D. Schmeidler, Equilibrium points of nonatomic games, J. Stat. Phys. 7 (4), 295–300 (1973).
     
  34. Z. Zhou, M. Yang, F. Sun, Z. Wang, and B. Wang, A continuous transportation network design problem with the consideration of road congestion charging, Sustainability 13, 7008 (2021).