Дискретная математическая модель сети автомобильных дорог г.Москвы и анализ ее пропускной способности
Московский энергетический институт (технический университет),
кафедра теоретической механики
Кирсанов М.Н.
Проблема оптимизации транспортной сети столицы является в последнее время актуальной. Развитие транспорта, увеличение числа автомобилей одновременно с увеличением темпов развития промышленности и связанная с этим увеличение требуемых скоростей перевозок дают основание полагать, что задачи интенсификации городского транспорта в дальнейшем будут еще более неотложными.
Создание математической модели сети автомобильных дорог позволит теоретически проанализировать скрытые резервы сети и возможности ее развития. Воспользуемся аппаратом дискретной математики. Представим сеть дорог в виде взвешенного неориентированного графа с вершинами в перекрестках и с ребрами- дорогами. Вес ребер (пропускная способность) зададим условно равным числу полос с некоторым поправочным коэффициентом, зависящим от качества покрытия, числа светофоров, развязок, интенсивности движения и др. Точные значения пропускных способностей отдельных дорог выясняются из регулярных наблюдений и не являются предметом настоящего исследования. Решим задачу насыщения сети. Используем систему компьютерной алгебры Maple. Обычно под сетью понимается граф с одним стоком и одним истоком и вычисляется максимальная пропускная способность сети от истока до стока методом Форда-Фалкерсона. Из всего множества задач, которые можно поставить для анализа сети дорог Москвы рассмотрим для примера одну – определения максимального потока на въезд в центр. В качестве истока возьмем некоторый фиктивный узел 0, соединенный фиктивными дорогами со всеми въездами в город (32 вершины на МКАД). Эту операцию выполним в цикле
for i to 32 do addedge({0,i},weights=40,G):od:
Аналогично введем сток, соединенный дорогами заведомо большой пропускной способностью (в 10 раз больше реальной) с 11 вершинами Садового кольца. Таким образом модель будет оценивать пропускную способность дорог города, а не подъездов к нему.
Представим упрощенную схему, включающую только наиболее значимые дороги. Всего возьмем 70 узлов (перекрестков). Маршруты внутри Садового кольца для поставленной задачи можно не принимать во внимание. Увеличение числа дорог, входящих в модель не составит принципиальных трудностей. Время счета также увеличится незначительно.
МКАД содержит вершины 1-32 с нумерацией по часовой стрелке (нумерация в общем произвольная). Садовое кольцо – вершины 41- 51. Ленинградское шоссе – вершины 31-51. Вершина 51 – площадь Маяковского. Маршрут 23-62-60-64-65-47 — Ленинский проспект. На рисунке отмечен также километраж МКАД (мелким шрифтом). Несмотря на соответствие реальным трассам, данная модель является отладочной и может давать практические результаты после внесения в нее всех возможных дорог с указанием их пропускной способности. Заметим также, что пропускная способность зависит от времени суток, а некоторые пути являются односторонними. Ниже приведен полный текст программы в задаче на въезд в город. Счет показывает, что пропускная способность равна 52 единицам. Те дороги, по которым пропускная способность совпала с потоком (насыщенные ребра) дает оператор eset. На рисунке эти дороги выделены пунктиром. Интересно отметить, что западная часть МКАД при этом осталась недогруженной. Недогруженной осталась Профсоюзная улица и еще ряд других дорог.
> restart:
> with(networks):
Создаем граф
> new(G):
72 вершины, включая исток 0 и сток 71
> addvertex({seq(i,i=0..71)},G):
Исток
> for i to 32 do addedge({0,i},weights=40,G): od:
Сток
> for i from 41 to 51 do addedge({i,71},weights=40,G):od:
МКАД
> for i to 31 do addedge({i,i+1},weights=6,G): od:
> addedge({32,1},weights=6,G):
Садовое кольцо
> for i from 41 to 50 do addedge([i,i+1],weights=3,G):od:
> addedge({51,41},weights=3,G): addedge({1,33},weights=4,G):
> addedge({33,41},weights=4,G): addedge({2,35},weights=4,G):
> addedge({35,36},weights=4,G): addedge({35,38},weights=4,G):
> addedge({3,37},weights=4,G): addedge({37,38},weights=4,G):
> addedge({38,39},weights=4,G): addedge({39,42},weights=4,G):
> addedge({4,37},weights=4,G): addedge({6,34},weights=4,G):
> addedge({34,43},weights=4,G): addedge({7,44},weights=4,G):
> addedge({11,45},weights=4,G): addedge({12,40},weights=4,G):
> addedge({11,45},weights=4,G): addedge({40,45},weights=4,G):
> addedge({16,70},weights=4,G): addedge({70,69},weights=4,G):
> addedge({69,46},weights=4,G): addedge({19,68},weights=4,G):
> addedge({68,67},weights=4,G): addedge({67,69},weights=4,G):
> addedge({22,61},weights=4,G): addedge({61,66},weights=4,G):
> addedge({66,65},weights=4,G): addedge({65,47},weights=4,G):
> addedge({23,62},weights=4,G): addedge({62,60},weights=4,G):
> addedge({60,64},weights=4,G): addedge({64,65},weights=4,G):
> addedge({62,59},weights=4,G): addedge({59,63},weights=4,G):
> addedge({63,48},weights=4,G): addedge({24,58},weights=4,G):
> addedge({25,55},weights=4,G): addedge({55,56},weights=4,G):
> addedge({56,49},weights=4,G): addedge({57,50},weights=4,G):
> addedge({29,54},weights=4,G): addedge({54,53},weights=4,G):
> addedge({53,52},weights=4,G): addedge({52,51},weights=4,G):
> addedge({30,54},weights=4,G): addedge({31,53},weights=4,G):
> addedge({27,55},weights=3,G): addedge({55,58},weights=3,G):
> addedge({58,59},weights=3,G): addedge({59,60},weights=3,G):
> addedge({60,61},weights=3,G): addedge({61,68},weights=3,G):
> addedge({67,66},weights=3,G): addedge({66,64},weights=3,G):
> addedge({64,63},weights=3,G): addedge({63,56},weights=3,G):
> addedge({56,57},weights=3,G): addedge({57,52},weights=3,G):
> addedge({52,33},weights=3,G): addedge({33,36},weights=3,G):
> addedge({36,39},weights=3,G): addedge({39,34},weights=3,G):
> addedge({70,40},weights=3,G):
flow(G,0,71,eset,comp);
> eset;
Для анализа модели на выезд изменим оператор
flow(G,71,0,eset,comp);
Число насыщенных путей (вычисляется оператором nops(eset)) уменьшится с 60 до 39, а максимальный поток останется прежним – 52. Приведем список насыщенных дорог. Именно на них возможно образование «пробок»:
Рис. 1