Русский
!

Presentations

Investigations of the influence of some modifications of transport networks on the maximal flow value in them

Grigorovitch E.R., Skvortsova M.I.

Moscow Technological University, Institute of Fine Chemical Technology, Russia, 119571, Moscow, Vernadskogo pr., 86, tel.(495)936-88-71, e-mail: skvorivan@mail.ru

Одной из классических задач прикладной теории графов является задача поиска максимального потока в сети (fmax) (см., например, [1,2]). Частным видом сетей являются транспортные сети, представляющие собой математические модели реальных сетей дорог. Наряду с задачей поиска fmax в сети весьма важной является и задача изучения влияния определенных перестроек транспортной сети на величину максимального потока в ней (│fmax│). Актуальность подобного рода задач связана с постоянным увеличением транспортных потоков в крупных городах и, как следствие, возникновением «пробок» на дорогах, что приводит к необходимости искать оптимальные пути модификации уже имеющихся транспортных сетей.

В настоящей работе изучается зависимость величины │fmax│в транспортной сети специальной структуры от определенных перестроек этой сети. Преобразования сети, приводящие к возрастанию величины │fmax│в ней, названы нами «эффективными». Цель работы – выявить эффективные преобразования сети. Рассматриваются перестройки сети следующих двух видов: 1) структурные модификации сети, связанные с удалением (добавлением) в нее новых вершин и дуг; 2) преобразования сети, заключающиеся в увеличении пропускных способностей некоторых дуг исходной сети, без изменения ее структуры. Преобразования первого вида соответствуют строительству эстакад и съездов/въездов на них; преобразования второго вида могут быть связаны, например, с расширением имеющихся участков дорог сети. Очевидно, что │fmax│ является функцией от структуры сети и пропускных способностей ее дуг. Однако получить явное, аналитическое выражение для │fmax│ в зависимости от характеристик сети не представляется возможным. В связи с этим для исследований нами были использованы компьютерный эксперимент и статистические методы. Первоначально были построены 100 исходных однотипных сетей со случайными пропускными способностями дуг; затем для всех сетей были построены их различные модификации и найдены fmax в них. В результате сравнительного анализа были определены эффективные преобразования сетей и степени их эффективности. Установлено, что обеспечить увеличение │fmax│ в сети рассматриваемого вида можно лишь при увеличении пропускных способностей определенных дуг сети.

Литература.

1. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир,1978,432 стр.

2. Бродецкий Г.Л., Гусев Д.А. Экономико-математические методы и модели в логистике. - М.: Академия, 2012, 288 стр.

© 2004 Designed by Lyceum of Informational Technologies №1533