The article presents a study of the influence of the accuracy of measuring the flow count on the road network on the quality of distribution. With a high quality of counting the flow on the links, its preservation on each node was not achieved. Therefore, the flows passing through the nodes had to be «balanced». In this article, we will look at methods developed for thread balancing
traffic flow, flow distribution on a link, balancing algorithms
Исследования влияния изменений на улично-дорожной сети начинаются со сбора данных о транспортных потоках [1, 2]. Несмотря на тщательный подсчет звеньев, сохранение потока на каждом узле не соблюдается, но потоки через узлы должны быть «сбалансированы». В исследовании рассматриваются методы, разработанные для балансировки сети. Методы делятся на две категории: алгоритмы и формулировки математического программирования. Очевидным, что решение для балансировки узлов зависит от критериев, выбранных для оценки.
Несмотря на все усилия учетчиков, направленные на точную регистрацию наблюдаемых потоков, при обработке информации в модели отмечено, что зарегистрированные потоки на большинстве перекрестков нарушали требование сохранения потока, то есть сумма входящих потоков должна быть равна сумме исходящих потоков. Другими словами, некоторые узлы пересечения были «несбалансированы» по отношению к зарегистрированным потокам.
Модели оценки матриц отправления-назначения (OD) и распределения потока требуют сбалансированного подсчета на звеньях, для этого рассмотрим алгоритмы способные повысить качество, чтобы восстановить сохранение потока на всех узлах.
Рассмотрим первый алгоритм – метод балансировки узлов [3, 4].
В приведенных ниже шагах u — несбалансированный узел; 
— величина дисбаланса в узле u, 
. На любой итерации 
узел u считается приблизительно сбалансированным, если абсолютное значение 
либо меньше или равно 1 (а), либо находится в пределах 1 процента от 
(b).
Шаг 0. 
Шаг 1. 
. Определение всех узлов j в сети, которые не являются центроидами отправления / назначения, но имеют несбалансированные потоки, и помещение их в набор несбалансированных узлов 
в порядке их исходных номеров. Если все узлы сбалансированы, перейти к шагу 4.
Шаг 2. Если множество
пусто, перейти к шагу 1. В противном случае удалить первый узел множества 
и назвать его «
– узлом».
Шаг 3. Для случая a — если
уменьшить каждый поток на 
где 
— доля всех потоков, поступающих в узел по звену 
Аналогично, каждый исходящий поток будет увеличиваться на 
— доля исходящих потоков, которые отправляются из узла по звену 
. Для случая b — если 
, добавить — к каждому входящему звену 
и вычесть — 
из каждого исходящего звена 
Для случая с — если какая-либо из корректировок приведет к тому, что поток звена станет отрицательным, то он остается без изменений и происходит переопределение 
или 
среди оставшихся путей. Для случая d — перейти к шагу 2.
Шаг 4. Для случая a — определить те нецентроидные узлы , которые неточно сбалансированы. Для случая b — если 
, найти ближайший к и центроиды Z. Если Z — исходный центроид, вычесть из каждого кратчайшего пути между 
и 
Если является центроидом назначения, добавить к каждой связи между и . Для случая c — если , найти центроид , ближайший к . Если является центроидом начала координат, добавить — к каждой связи между и . Если является центроидом пункта назначения, вычесть — из каждой связи между и . Для случая d — остановка итеративного процесса.
Метод балансировки потока на звеньях показывает достаточно грубые результаты, но его достоинством является легкость программирования.
Рассмотрим второй метод – «вес минимального пути». Для этого метода вводится вес звена, определяемый как разница между исходными наблюдаемыми потоками звена 
и потоками на звене 
. Для каждого звена 
:
, (1)
где 
— очень маленькое число.
Второй член в выражении необходим для предотвращения 
на всех звеньях в начале процесса и на любом звене, которые еще не подвергались обработке. По мере корректировки потока на звеньях первое слагаемое начинает доминировать над вторым.
Алгоритм метод «веса минимального пути» состоит из семи шагов.
Шаг 1. Определяются все узлы 
в сети, которые не являются центроидами отправления или назначения, но имеют несбалансированные потоки, и размещаются в набор несбалансированных узлов 
.
Шаг 2. Если множество пусто, происходит остановка, в противном случае удаляется первый узел в наборе 
и ему присваивается название « -узел».
Шаг 3. Расчет веса звена 
для каждого звена в сети.
Шаг 4. Используя соответствующий алгоритм поиска кратчайшего пути (3) и веса звена , находится минимум от текущего -узла ко всем центроидам. Все звенья – двусторонние, независимо от их действительной направленности.
Шаг 5. Определяется центроида , имеющая наименьший вес звена от -узла (путь от до Z имеет наименьшую сумму разностей).
Шаг 6. Одна единица потока направляется по пути 
Эта единица потока будет положительной или отрицательной, в зависимости от знака
, ориентации каждого звена на пути от того, является ли центроида Z исходным пунктом (P) или пунктом назначения (A). Производится обновление так, чтобы 
Шаг 7. Если 
, переход к шагу 2, в противном случае к шагу 3.
Рассмотрим особенности этого метода. Как только -узел сбалансирован, он не претерпевает изменений. При отправке потоков через сеть от текущего -узла к центроиду в соответствии с шагом 6 каждый промежуточный узел i (некоторые из которых, возможно, уже были сбалансированы) сохраняет свое значение 
неизменным. Алгоритм «посещает» каждый -узел только один раз, уравновешивает его и переходит к следующему -узлу. Это эффективная система регулирования объемов потоков на звене таким образом, чтобы нарушить как можно меньшее количество потоков, и в первую очередь тех, значения которых все еще близки к их значениям .
Неэффективно использование метода в тех случаях, когда может приближаться к 100 — большой дисбаланс в сети, вероятно, будет вызван ошибкой сбора или обработки данных — разумнее использовать большую корректировку потока.
Рассмотрим третий метод – минимаксная вариация.
Минимаксный вариационный метод предназначен для обработки d-веса на некоторых отдельных звеньях на путях с минимальным весом от -узла к центроидам. Идея метода состоит в том, чтобы изменить потоки на звеньях, которые корректировались в процессе балансировки. Метод является вариацией предыдущего за исключением пятого шага.
Рассмотрим четвертый метод – минимизации звеньев d-весом. Потоки на звене с минимальным d-весом, найденные на шаге 2, модифицируются, чтобы найти путь между текущим -узлом и каждым центроидом, который имеет связи с d-весами как можно меньшего размера. Алгоритм разрешает изменять путь с минимальным d-весом, если звено на этом пути может быть заменено звеном с меньшим d-весом. Это достигается за счет адаптации «тройной операции», используемой в алгоритме поиска кратчайшего пути Флойда. Подпуть 
заменяется
подпутем
, если 
, где 
— это текущая наименьшая стоимость или расстояние от узла
до узла
. Метод заменяет звено 
на пути с минимальным d-весом на подпуть
, если 
. Эта процедура модифицирует минимальный d – вес пути, чтобы выбрать путь, избежав вовлечение звена, которые уже имеют большие значения 
Шаги 1-4. Такие же, как в вышеприведенных методах.
Шаг 5. Вдоль каждого пути с минимальным d-весом от текущего -узла ко всем центроидам заменить звено на подпуть , если
.
Шаги 6 и 7. Те же, что и в вышеприведенных методах
Все четыре метода демонстрируют адекватную универсальность при тестировании, но каждый из рассмотренных, сформулирован для конкретного критерия, что обеспечивает оптимальное решение, если размер задачи не превышен.
1. Kripak, M. N. Ocenka sostoyaniya ulichno-dorozhnoy seti krupnogo goroda / M. N. Kripak, O. A. Lebedeva // Sovremennye tehnologii. Sistemnyy analiz. Modelirovanie. 2016. № 3 (51). S. 171-174.
2. Poltavskaya, Yu. O. Modelirovanie prodolzhitel'nosti dvizheniya po marshrutu s uchetom harakteristik ulichno-dorozhnoy seti / Yu. O. Poltavskaya, O. A. Lebedeva // V knige: Novye informacionnye tehnologii v issledovanii slozhnyh struktur. materialy Trinadcatoy Mezhdunarodnoy konferencii. Tomskiy gosudarstvennyy universitet. Tomsk, 2020. S. 101-102.
3. Barbour, R. Balancing link counts at nodes using a variety of criteria: an ap-plication in local area traffic assignment / R. Barbour // Strand Associates, Inc., 910 West Wingra Drive, Madison, Wis. 53715. J. D. Fricker, School of Civil Engineering, Purdue University, West Lafayette, Ind. 47907.
4. Zuylen, H. J. The most likely trip matrix estimated from traffic counts / H. J. Zuylen, L. G. Willumsen // Transportation Research B, Vol. 14B, 1980, pp. 281-293.
