English
!

Доклады

Исследование влияния некоторых перестроек транспортных сетей на величину максимального потока в них

Григорович Е.Р., Скворцова М.И.

Московский технологический университет, Институт тонких химических технологий им. М.В. Ломоносова, каф. Высшей и прикладной математики, Россия, 119571, г. Москва, пр-т Вернадского, 86, тел. (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 Дизайн Лицея Информационных технологий №1533