GLOBAL OPTIMUM SEARCH IN THE NETWORK DESIGN PROBLEM

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The global optimum search in the network design problem for the case of networks with disjoint paths is considered. In the considered formulation of the problem, the manager of a network invests in the capacities of its elements, seeking to minimize the total delay arising from the equilibrium flow assignment. It is proven that the solution to the problem under study must necessarily solve a certain minimax problem. Optimality conditions for solutions of the minimax problem are found under fairly natural assumptions. Based on the results, a new algorithm is developed for optimizing the topology of a network with disjoint paths.

About the authors

A. Yu Krylatov

St. Petersburg State University; Institute of Transport Problems

Email: a.krylatov@spbu.ru
Saint Petersburg; Saint Petersburg

References

  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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences