Russian Federation
To quantitatively assess the capacity of road networks, the article considers the use of the auxil-iary graph method with a minimum set of sections, since it is important to take into account the possibilities for redistributing traffic flow in the network in order to use the available capacity reserves
throughput capacity, road network, section method, shortest routes, auxiliary graph
Целью устойчивого развития городского транспорта является оптимизация пропускной способности и эксплуатационной эффективности существующей дорожной сети, избегая при этом расширения магистралей, поскольку это требует больших капиталовложений, либо является невозможным ввиду плотности городской застройки [1-4]. Поэтому исследование, направленное на количественную оценку пропускной способности дорожных сетей, является актуальным и требует нового подхода к решению данной задачи.
Согласно методу сечений общая пропускная способность участков дороги может быть описана минимальным набором сечений. В результате задача сводится к определению наименьшего набора сечений в дорожной сети. Опишем поэтапно алгоритм вспомогательного графа для поиска минимального набора сечений с целью определения пропускной способности дорожной сети [5].
На шаге 1 создается базовая абстрактная сеть G на основе реальных карт дорожной сети городских территорий. Пропускная способность корректируется с учетом ключевых переменных пропускной способности каждого участка дорожной сети G городских территорий.
Шаг 2. Строится вспомогательная карта дорожной сети G поверх исходной G*.
Шаг 3. Используя процедуры компьютерного программирования, определяются кратчайшие пути в G*.
Шаг 4. Фиксируется сегмент улично-дорожной сети, соответствующий кратчайшему контуру в G*, который является минимальным набором сечений.
Шаг 5. Сумма интенсивности движения участков дороги, соответствующих минимальному набору сечений, является пропускной способностью дорожной сети.
Далее опишем алгоритм поиска кратчайших путей между всеми парами вершин графа.
Определяется сеть G={𝑉,𝐸,𝐶}. Согласно теории множеств сечений, известно, что 𝑉 – это множество точек G, 𝐸 – это множество дуг 𝐺, а 𝐶 – правая часть сети. Ребра G рассекают плоскость на несколько областей, каждая из которых называется гранью G. Одна из граней не ограничена и называется внешней, а другая – внутренней. Для сети G, всегда можно выделить область 𝑣𝑠 на левой стороне G и 𝑣𝑡 – на правой стороне G. Предположим, что есть две вертикальные линии, проходящие через точки 𝑣𝑠 и 𝑣𝑡, в которых внешняя часть становится четырьмя частями, называя часть выше G верхом, а часть ниже G низом. Как показано на рисунке 1, 𝐹1 является верхом, а G, 𝐹2 и 𝐹3 – внутренней частью G, 𝐹4 – низом G.
Предположим, что существует подмножество 𝑋 из 𝑉, удовлетворяющее условию 𝑥∈𝑋 и 𝑦∈
=𝑉−𝑋, тогда можно определить (1) – (3):
(1)
(2)
(3)
𝑂(𝑋) является множеством сечений G. Уравнение (4) называется емкостью множества сечений 𝑂(𝑋):
(4)
Рисунок 1 – Схема сети G
𝑂(𝑋) является множеством сечений G. Уравнение (4) называется емкостью множества сечений 𝑂(𝑋):
(4)
Когда два смежных ребра находятся на границе одной и той же стороны, последовательность 𝑒𝑖1, …, 𝑒𝑖𝑘 является набором в сети G. Два ребра 𝑒1 и 𝑒2 в Φ(𝑋) называются связанными с Φ(𝑋) если 𝑒𝑖1=𝑒1 и 𝑒𝑖𝑘=𝑒2. Рассмотрим теорему: если 𝑂(𝑋) – минимальное множество сечений, то любые два ребра в 𝑂(𝑋) соединены с Φ(𝑋). Поскольку кратчайшее сечение имеет двойственность, то множество сечений сети G можно получить, найдя кратчайшее сечение между ее вспомогательным графом и вершиной выхода 𝑣𝑠∗ к вершине входа 𝑣𝑡∗.
Вспомогательный граф G* строится следующим образом: каждая внутренняя грань F имеет вершину 𝑣∗ из G*, соответствующую ей, вершина сети G имеет вершину 𝑣𝑠∗ из G*, соответствующую ей. Когда грани в сети смежные, вершины во вспомогательном графе также являются смежными. Каждая пара смежных вершин G* имеет пару ребер, и их направление определяется следующим способом: пусть 𝑣𝑖∗ и 𝑣𝑗∗ соответствуют граням G*, то существуют направленные ребра 𝑣𝑖∗𝑣𝑗∗ и 𝑣𝑗∗𝑣𝑖∗, 𝑣𝑖∗ и 𝑣𝑗∗. 𝐹𝑖 и 𝐹𝑗, общая граница 𝐹𝑖 и 𝐹𝑗 обозначается как 𝑙𝑖𝑗, и является цепью. Если G* создано на основе G, 𝑣𝑖∗ можно спроецировать на 𝐹𝑖 и 𝑣𝑗∗ в 𝐹𝑗. Когда направление 𝑣𝑖∗𝑣𝑗∗ совпадает с 𝑙𝑖𝑗 называется 𝑙𝑖𝑗 по 𝑣𝑖∗𝑣𝑗∗ направление. Следовательно, также получается, что направление 𝑙𝑖𝑗 определяется направлением 𝑣𝑗∗𝑣𝑖∗, которые противоположны. Формула выглядит следующим образом:
𝑙𝑖0={𝑒|𝑒∈𝑙𝑖𝑗, направление определяемое по 𝑣𝑖∗𝑣𝑗∗}
𝑙0𝑗={𝑒|𝑒∈𝑙𝑖𝑗 направление, противоположное определяемому 𝑣𝑖∗𝑣𝑗∗}.
Укажем 𝑣𝑖∗𝑣𝑗∗ как (5):
(5)
Если 𝑙0𝑗≠Φ, то 𝑊(𝑣𝑖∗𝑣𝑗∗) соответствует множеству ребер 𝑙0𝑗. Если 𝑙0𝑗=Φ, то 𝑙𝑖0={𝑒|𝑒∈𝑙𝑖0 и 𝐶(𝑒)=𝑊(𝑣𝑖∗𝑣𝑗∗)}, аналогично определяя 𝑊(𝑣𝑗∗𝑣𝑖∗).
Для вершины 𝑣𝑖∗ смежной с 𝑣s∗ нужно определить только направленное ребро 𝑣s∗𝑣𝑗∗ и вес 𝑊(𝑣s∗𝑣𝑗∗); для вершины 𝑣𝑗∗ смежной с 𝑣t∗ – направленное ребро 𝑣𝑗∗𝑣t∗ и вес 𝑊(𝑣𝑖∗𝑣𝑗∗). При вычислении кратчайшего пути от 𝑣s∗ до 𝑣t∗ в G длина пути 𝑃 является суммой весов на его верхних ребрах, обозначаемой 𝑊(𝑃), которая выражается следующим образом:
(6)
Вспомогательный граф G* для сети G показан на рисунке 2.
Рисунок 2 – Вспомогательный граф G*
для сети G
Вспомогательный граф G* построен так, что 𝑣𝑖∗𝑣𝑗∗ всегда пересекает ребра в соответствующем множестве Φ(𝑋) в G и их мощности соответствуют друг другу. 𝑣𝑠∗ в 𝑣𝑡∗ также делит вершины G на две части, и кратчайшее сечение во вспомогательном графе G* соответствует наименьшему сечению в сети G. Таким образом, когда все кратчайшие пути во вспомогательном графе найдены, набор минимальных сечений определяется на основе того факта, что ребра во вспомогательном графе соответствуют ребрам в сети G [2, 5].
Применение описанного алгоритма будет давать оптимальные результаты в следующих ситуациях, когда реальная дорожная сеть может быть упрощена до графа, в котором:
– одна вершина является входом, а остальные – выходом из нее;
– односторонняя направленность движения по ребрам.
В большинстве случаев сеть многоначальная и ненаправленная [5-8], поэтому алгоритм кратчайшего пути вспомогательного графа необходимо улучшить следующим образом:
1) Абстракция дорожной сети упрощается до сети без направления: большинство дорог в реальной сети являются двунаправленными; поэтому упрощаем дорожную сеть до ненаправленной сети.
2) Определяем набор вершин входа и выхода. Возможные потоки неориентированных графов отражаются с множественными входами и выходами. Для задачи потока детерминированных сетей необходимо определить данный набор в сети.
3) Добавляются фиктивные вершины 𝑣𝑠 и 𝑣𝑡 в сеть, соединяется каждая вершина входа и выхода с двумя фиктивными вершинами соответственно. Чтобы гарантировать, что измененная сеть соответствует фактической пропускной способности между 𝑣𝑠, 𝑣𝑡 и другими вершинами устанавливается бесконечным значением.
Основной процесс решения пропускной способности дорожной сети с использованием этого алгоритма заключается в построении неориентированной вспомогательной дорожной сети G* из неориентированной G, нахождении кратчайшего пути в G*, а затем определении наименьшего множества сечений в G. Сумма G в сети будет являться общей пропускной способностью.
Построение вспомогательного графа G* можно получить следующим образом: для каждой внутренней грани 𝐹 из G существует вершина 𝑣∗ из G*, соответствующая ей; для вершины G существует вершина 𝑣𝑠∗ из G*, соответствующая ей; для G ниже, есть вершина 𝑣𝑡∗ из G*; и правая часть каждой стороны G* равна правой части соответствующего ребра в G, которое пересекает ее. Все веса ребер G* получаются из G, которые соединены относительно Φ(𝑋).
Метод вспомогательного графа может определить только максимальное значение пропускной способности из набора вершин входа и выхода, он не учитывает распределение объема транспортного потока в промежуточных точках. Поэтому значения, полученные с помощью данного метода, устанавливаются в качестве нижнего предела пропускной способности дорожной сети.
1. Bahirev, I. A. Ocenka usloviy dvizheniya na gorodskih ulicah / I. A. Bahirev, A. Yu. Mihaylov. – Tekst : neposredstvennyy // Gradostroitel'stvo. 2015. № 4 (38). S. 63-68.
2. Siregar, M. L. Median-type adjust-ment factor for road capacity calculation / M. L. Siregar, H. R. Agah, F. A. Arifin // Interna-tional Journal of Technology. 2015. Vol. 5. pp. 762–769.
3. Kripak, M. N. Ocenka sostoyaniya ulichno-dorozhnoy seti krupnogo goroda / M. N. Kripak, O. A. Lebedeva. – Tekst : neposredstvennyy // Sovremennye tehnologii. Sistemnyy analiz. Modelirovanie. 2016. № 3 (51). S. 171-174.
4. Mihaylov, A. Yu. Integral'nyy kriteriy ocenki kachestva funkcionirovaniya ulichno-dorozhnyh setey / A. Yu. Mihaylov. – Tekst : neposredstvennyy // Izvestiya Irkutskoy gosudarstvennoy ekonomicheskoy akademii. 2004. № 2. S. 50-53.
5. Xing, R. A regional road network capacity estimation model for mountainous cities based on auxiliary map / R. Xing, F. Wang, X. Cai, N. Chen, T. Yang, B. Peng // Sustainability. 2023. Vol. 15(14). 11439. 27 p.
6. Poltavskaya, Yu. O. Povyshenie propusknoy sposobnosti po ulice Karla Marksa /Poltavskaya Yu.O., Dragunov A.F., Lyapustin P.K. //Sovremennye tehnologii i nauchno-tehnicheskiy progress. 2014. T. 1. S. 43.
7. Lebedeva, O. A. Analiz proektirovaniya transportnyh zon na osnove modelirovaniya seti / O. A. Lebedeva. – Tekst : neposredstvennyy // Vestnik Angarskogo gosudarstvennogo tehnicheskogo universiteta. 2019. № 13. S. 172-177.
8. Fedotova, A. S. Stepen' ispol'zovaniya propusknoy sposobnosti avtomobil'nyh dorog /Fedotova A.S., Lebedeva O.A.// Sbornik nauchnyh trudov Angarskogo gosudarstvennogo tehnicheskogo universiteta. 2015. T. 1. № 1. S. 270-274.
