Том 23, номер 2, 2016 г., Стр. 63-87

УДК 519.8
Крылатов А. Ю.
Распределение потока в сети как задача поиска неподвижной точки

Аннотация:
Статья посвящена проблемам поиска конкурентного равновесия (распределение потоков с равным временем перемещения по альтернативным маршрутам) и системного оптимума (распределение потоков с минимальным средним временем перемещения) в сети из параллельных каналов с одной парой исток-сток. Время перемещения по каналам моделируется произвольными гладкими неубывающими функциями. Доказано, что задача поиска равновесного и оптимального потоков для данной сети может быть сведена к задаче поиска неподвижной точки, выраженной в явном виде. Разработан метод поиска равновесного и оптимального распределений потоков в виде процедуры простой итерации. Доказана сходимость метода со скоростью геометрической прогрессии, а при дополнительных достаточно естественных условиях доказана квадратичная сходимость метода.
Библиогр. 30.

Ключевые слова: конкурентное равновесие, системный оптимум, неподвижная точка, потоки в сети.

DOI: 10.17377/daio.2016.23.503

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

Статья поступила 31 июля 2015 г.
Исправленный вариант — 24 ноября 2015 г.

Литература

[1] Вержбицкий В. М. Основы численных методов. М.: Высш. шк., 2002. 840 с.

[2] Захаров В. В., Крылатов А. Ю. Системное равновесие транспортных потоков в мегаполисе и стратегии навигаторов: теоретико-игровой подход // Мат. теория игр и её прил. 2012. Т. 4, № 4. С. 23–44.

[3] Захаров В. В., Крылатов А. Ю. Конкурентная маршрутизация транспортных потоков поставщиками услуг навигации // Упр. большими системами. 2014. Т. 49. С. 129–147.

[4] Захаров В. В., Крылатов А. Ю. Конкурентное равновесие Вардроп на транспортной сети из параллельных неоднородных маршрутов // Процессы упр. и устойчивость: Тр. XLV Междунар. науч. конф. аспирантов и студентов (СПб, 1–4 апреля 2014 г.). Т. 1. СПб: Изд. дом Федоровой Г. В., 2014. С. 476–481.

[5] Зоркальцев В. И., Киселёва М. А. Равновесие Нэша в транспортной модели с квадратичными затратами // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 3. С. 31–42.

[6] Крылатов А. Ю. Оптимальные стратегии управления транспортными потоками на сети из параллельных каналов // Вестн. СПбГУ. Сер. 10. Прикл. математика. Информатика. Процессы упр. 2014. № 2. С. 121–130.

[7] Мазалов В. В. Математическая теория игр и приложения. СПб.: Лань, 2010. 448 с.

[8] Швецов В. И. Математическое моделирование транспортных потоков // Автомататика и телемеханика. 2003. № 11. P. 3–46.

[9] Altman E., Combes R., Altman Z., Sorin S. Routing games in the many players regime // Proc. 5th Int. ICST Conf. Performance Evaluation Methodologies and Tools (Paris, May 16–20, 2011). Brussels: ICST, 2011. P. 525–527.

[10] Altman E., Wynter L. Eguilibrium, games, and pricing in transportation and telecommunication networks // Netw. Spatial Econ. 2004. Vol. 4, No. 1. P. 7–21.

[11] Beckmann M. J., McGuire C. B., Winsten C. B. Studies in the economics of transportation. New Haven, CT: Yale Univ. Press, 1956. 359 p.

[12] Chen R.-J., Meyer R. R. Parallel optimization for traffic assignment // Math. Program. 1988. Vol. 42, No. 1–3. P. 327–345.

[13] Chiou S.-W. Optimization of robust area traffic control with equilibrium flow under demand uncertainty // Comput. Oper. Res. 2014. Vol. 41. P. 399–411.

[14] Chiu Y.-C., Bottom J., Mahut M., Paz A., Balakrishna R., Waller T., Hicks J. Dynamic traffic assignment // Transp. Res. Circular. Vol. E–C153. Washington, DC: Transp. Res. Board, 2011. 62 p.

[15] Farahani R. Z., Miandoabchi E., Szeto W. Y., Rashidi H. A review of urban transportation network design problems // Eur. J. Oper. Res. 2013. Vol. 229, No. 2. P. 281–302.

[16] Fisk C. A nonlinear equation framework for solving network equilibrium problems // Environ. Plan. Ser. A. 1984. Vol. 16, No. 1. P. 67–80.

[17] Fisk C., Nguyen S. A unified approach for the solution of network equilibrium problems // Montreal: Univ. Montreal, 1980. (Publ. Centre Rech. Transp.; Vol. 169).

[18] Hollander Y., Prashker J. N. The applicability of non-cooperative game theory in transport analysis // Transp. 2006. Vol. 33, No. 5. P. 481–496.

[19] Mazalov V. Wardrop equilibrium for network with parallel channels and the BPR latency function // Int. Game Theory Rev. 2016 (to appear).

[20] Patriksson M. Sensitivity analysis of traffic equilibria // Transp. Sci. 2004. Vol. 38, No. 3. P. 258–281.

[21] Patriksson M. A unified description of iterative algorithms for traffic equilibria // Eur. J. Oper. Res. 1993. Vol. 71, No. 2. P. 154–176.

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

[23] Sheffi Y. Urban transportation networks: equilibrium analysis with mathematical programming methods. Englewood Cliffs, NJ: Prentice-Hall, 1985. 416 p.

[24] Wardrop J. G. Some theoretical aspects of road traffic research // Proc. Inst. Civil Eng. 1952. Vol. 1, No. 3. P. 325–362.

[25] Yang H., Huang H.-J. The multi-class, multi-criteria traffic network equilibrium and systems optimum problem // Transp. Res. Part B. 2004. Vol. 38, No. 1. P. 1–15.

[26] Zakharov V. V., Krylatov A. Yu. Equilibrium assignments in competitive and cooperative traffic flow routing // IFIP Adv. Inf. Commun. Technol. 2014. Vol. 434. P. 641–648.

[27] Zakharov V. V., Krylatov A. Yu. Transist network design for green vehicles routing // Adv. Intelligent Syst. Comput. 2015. Vol. 360. P. 449–458.

[28] Zakharov V. V., Krylatov A. Yu. Competitive green-vehicle assignment on a transportation network // Game Theoretic Models Math. Ecology. New York: Nova Sci. Publ., 2015. P. 205–234.

[29] Zakharov V. V., Krylatov A. Yu., Ivanov D. A. Equilibrium traffic flow assignment in case of two navigation providers // IFIP Adv. Inf. Commun. Technol. 2013. Vol. 408. P. 156–163.

[30] Zheng H., Chiu Y.-C. A network flow algorithm for the cell-based single-destination system optimal dynamic traffic assignment problem // Transp. Sci. 2011. Vol. 45, No. 1. P. 121–137.