НАУКА и ОБРАЗОВАНИЕ

УДК. 004.021

Россия, МГТУ им. Н.Э. Баумана

kostyoskol@mail.ru

pavlov@bmstu.ru

mari-na-bzzz@yandex.ru

Введение

Загруженность автомобильных дорог стала в настоящее время глобальной проблемой. Особенно остро она ощущается в мегаполисах.

Данная статья посвящена разработке системы прогнозирования дорожной обстановки, которая будет предоставлять информацию о характерной загруженности дорог, наиболее вероятной дорожной ситуации в текущий момент времени, а также строить прогноз изменения дорожной ситуации.

В разрабатываемой системе прогнозирования в качестве источника первичной информации используются данные о передвижении автомобилей, полученные от портативных спутниковых навигаторов. Информация включает данные о маршруте следования автомобиля и времени пересечения им узлов на графе дорог.

Сейчас в России основным источником информации о загруженности дорог являются системы, которые отображают текущую дорожную обстановку и характерную загрузку дорог [1].

За рубежом существует ряд систем, которые предоставляют прогноз изменения дорожной обстановки на основе известной предыстории и данных о текущей ситуации, используя информацию с датчиков, установленных под дорожным полотном или у обочины. Поэтому таким системам доступна полная информация о числе и скорости движения автомобилей на каждом участке трассы. Одной из самых известных разработок является система Traffic Prediction Tool (TPT) корпорации IBM [2].

Разрабатываемая авторами статьи система, в отличие от существующих зарубежных аналогов, строит прогноз изменения дорожной ситуации на основе зашумленных и неполных данных о скорости движения автотранспорта. Неполнота данных обусловлена тем, что мы знаем дорожную ситуацию только на тех дорогах, где находятся автомобили, оборудованные портативными спутниковыми навигаторами. А зашумленность обусловлена ошибками измерения местоположения и скорости движения этих автомобилей. В отличие от известных российских разработок, при построении прогноза учитываются не только исторические данные о скоростях, но и ситуация, сложившаяся в городе в данный момент.

Система использует ряд математических моделей, каждая из которых имеет большую или меньшую предсказательную способность при определенных условиях. Ниже описаны модели и критерии, на основе которых происходит выбор наиболее эффективной модели для сложившейся ситуации.

Научная новизна работы заключается в разработке алгоритма прогнозирования дорожной ситуации, который показал себя лучше аналогов в условиях неполноты и зашумленности исходных данных.

1.    Количественные характеристики дорожных ситуаций

Дорожной ситуацией будем называть совокупность местоположений, скоростей и габаритных размеров всех транспортных средств на рассматриваемой дороге. Однако используемый тип датчиков позволяет получить информацию только о средней скорости движения. Дорожную ситуацию будем характеризовать метрикой ­– непрерывно дифференцируемой функцией M(V), зависящей от скорости движения транспортного потока Vи выбранной так, чтобы разность значений метрики, соответствующих двум ситуациям на дороге, несла информацию о различии этих ситуаций. Метрика должна обладать свойствами.

1. Так как водителей интересует относительная погрешность прогнозирования времени движения T, вычисляемая по соотношению

где индексами p и rобозначены соответственно прогнозируемые и реальные величины, то разность метрик M (V_p) – M (V_r)  должна быть пропорциональна отношению V_p / V_r.

2. Так как на разгруженной дороге скорости зависят в большей степени от характера вождения и типа транспортного средства, чем от дорожной ситуации, то чувствительность метрики к скорости должна быть тем меньше, чем больше значение самой скорости, то есть

3. Абсолютная погрешность разности метрик M (V_p) – M (V_r), обусловленная погрешностью измерения времени движения T, не должна зависеть от длины рассматриваемого участка дороги.

Перечисленные требования оставляют некоторую свободу в выборе конкретного вида функции M (V), однако среди основных элементарных функций им удовлетворяет только логарифмическая метрика вида M (V) = lnV.

Меру различия J некоторых дорожных ситуаций 1 и 2, относящихся к группе дорог и отстоящих по времени на интервал Δt, будем оценивать средним квадратом разности их метрик:

где N – число измерений, I – число рассматриваемых дорог, t_beg и t_end – начало и конец временного интервала, на котором производятся измерения. Время t меняется дискретно с постоянным шагом дискретизации.

При оптимизации прогнозирующих моделей необходимо сравнивать прогнозируемую и фактическую ситуацию за один и тот же интервал времени, то есть исследовать величину

где V ⁱ_r – реальная скорость на дороге i; V ⁱ_p – прогнозная скорость на дороге i.

2.    Взаимосвязь между дорогами

Заторы на одних улицах провоцируют заторы на других. При этом от структуры развязок и схемы организации движения будет зависеть и скорость транспортного потока, и величина взаимовлияния. Для повышения точности прогноза нужно учитывать эти связи между дорогами.

 Поскольку на скорость движения потока влияют такие факторы, как часы пик, праздники и т.д., то чтобы минимизировать это влияние, требуется исследовать отклонения скорости от ее характерной величины для данного времени суток, дня недели и времени года

U= V– V_char,

где U– отклонение скорости, V– текущая скорость, V_char– характерная скорость (п. 3).

Примем, что взаимное влияние отклонений скорости движения транспорта на двух дорогах cи d имеет линейный закон. Любую ситуацию, отвечающую этому линейному закону, будем называть равновесной. Всякое отклонение скорости от равновесной скорости, связанное с изменением дорожной ситуации, на одной из дорог распространится на другие дороги с некоторым запаздыванием τ, тем самым обеспечив восстановление равновесия, но уже при иных величинах скоростей. Таким образом, математическая модель взаимосвязи имеет вид

U_c (t) = a U_d (t – τ) + ε (t ),

где a ­– коэффициент взаимосвязи, ε– остаточное отклонение скорости.

Всякое отклонение скорости от равновесной скорости, не связанное с изменением дорожной ситуации, не будет влиять на скорость движения на других дорогах, однако с течением времени будет убывать и тем самым восстанавливать равновесие при тех же величинах скоростей, которые были изначально. Если принять, что скорость затухания случайного отклонения скорости пропорциональна самому отклонению, то получим выражение

ε (t) – ε (t– 1) = bε (t– 1) + δ (t– 1).

Физически осмысленным является лишь случай b< 0, поскольку в противном случае уравнение описывает неограниченное возрастание отклонения ε. Если в расчёте получено положительное значение b, то это может быть объяснено недостаточностью накопленных статистических данных.

Силу взаимосвязи µ_c,d между дорогой c и дорогой d оцениваем отношением коэффициента затухания b к стандартной ошибке определения этого коэффициента SE_b. Стандартная ошибка определения коэффициента линейной регрессии вычисляется как отношение среднеквадратичного отклонения остатка к среднеквадратичному отклонению фактора, следовательно

где σ(∙) – среднеквадратичное отклонение.

Для каждого значения τ из определенного интервала рассчитывается значение величины µ_c,d . Затем отыскивается такая величина τ*, при которой взаимосвязь µ_c,d максимальна. Если τ* < 0, то дорога cвлияет на дорогу d, при τ* > 0 дорога d влияет на дорогу c. В случае τ*, близкого к нулю, имеет место как влияние cна d, так и влияние d на c.

Скорость движения при отсутствии заторов зависит не столько от дорожной ситуации, сколько от характера вождения и вида транспортного средства. Поэтому в расчете параметров aи b участвуют только те отсчеты, в которых скорости на обеих дорогах ниже определенного порога.

3.    Прогнозирование на основе характерной скорости движения

В основе предлагаемой модели прогнозирования лежит расчет медианной скорости движения с учетом цикличности действия внешних факторов на дорожную обстановку по времени суток, дням недели и времени года. Эту скорость будем называть характерной скоростью.

Экстраполяция характерной скорости может использоваться как самостоятельный инструмент прогнозирования. Однако в этом случае никак не учитывается дорожная ситуация, сложившаяся в городе на момент построения прогноза, поэтому точность такого прогноза невелика (п. 6). Вычисление характерной скорости может выступать и в качестве составной части более сложных моделей прогнозирования, рассмотренных ниже.

4. Прогнозирование на основе характерной скорости движения с учетом отклонений

При построении прогноза было бы некорректно рассматривать пару взаимосвязанных дорог изолированно от дорожной сети всего города. Между дорогами существуют множественные связи, и их учёт необходим для корректного предсказания дорожной обстановки. На одних дорогах текущая скорость может быть выше характерной, а на других ниже, но из-за влияния дорог друг на друга транспортный поток будет перераспределяться: скорости на недогруженных дорогах будут падать, а на перегруженных расти.

Обобщая линейный закон взаимосвязи отклонений скоростей от характерной скорости (п. 2) на случай нескольких дорог c, d,… y, z, можем записать его в виде

U_c (t) = a_c,d U_d (t – τ_c,d ) + a_c,eU_e(t – τ_c,e ) +…+ a_c,z U_z (t – τ_c,z ) + ε_c (t ),

U_d (t ) = a_d,c U_d (t – τ_d,c ) + a_d,e U_e(t – τ_d,e ) +…+ a_d,z U_z (t – τ_d,z ) + ε_d (t ),

…

U_z (t ) = a_z,c U_c (t – τ_z,c ) + a_z,d U_d (t – τ_z,d ) +…+ a_z,y U_y (t – τ_z,y ) + ε_z (t ).

В построенную многомерную модель включаются лишь те дороги, для которых характеристика взаимосвязи µ оказывается выше определённого порога.

Поиск коэффициентов взаимосвязи a_i,j осуществляется с помощью метода главных компонент [3], использующего сингулярное разложение матрицы данных.

На вход алгоритма подается матрица, содержащая отклонения скоростей от характерной скорости для всех дорог, включённых в модель, с соответствующими смещениями по времени τ :

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

Сингулярное разложение позволяет представить матрицу U  в виде

U = LSP^T,

где L – матрица собственных векторов, S – матрица квадратов собственных чисел, P – матрица поворота. Величины, обратные к собственным числам матрицы U, характеризуют рассеяние данных в направлениях, задаваемых матрицей поворота. Благодаря этому они могут использоваться для выявления главных и второстепенных факторов, определяющих рассеяние данных. Это, в свою очередь, позволяет выделить среди коэффициентов взаимосвязи дорог a_i,j лишь те, которые существенны для построения прогноза.

Число главных компонент определяется экспериментально. Собственные числа, соответствующие остальным компонентам, в матрице Sобнуляются. После перемножения матриц L, S и P^T, содержащих только главные компоненты, получим матрицу U_bal . В ней содержатся отклонения скорости, «сбалансированные» относительно предположения о линейном законе взаимосвязи между дорогами.

Прогнозная скорость V ^c_p для дороги c через время θ рассчитывается с помощью уравнения вида

V ^c_p (t +θ ) = V ^c_char (t +θ ) + β (θ ) U ^c_bal (t ),

где V ^c_char– характерная скорость на дороге c; U ^c_bal – «сбалансированное» отклонение скорости для дороги c; β (θ ) – функция, описывающая влияние «сбалансированного» отклонения скорости от характерной на прогнозную скорость для каждого θ.

Функция β (θ ) принимается равной единице при θ = 0 и равной нулю при больших значениях θ. Последнее означает, что на длительных интервалах прогнозирования нивелируется любое начальное отклонение скорости и, следовательно, прогноз строится исходя из одной лишь характерной скорости движения. Для всех промежуточных значений θ величина β (θ )рассчитывается из условия минимизации меры J  (п. 1).

5. Прогнозирование на основе значимости и определенности истории

В основе этого метода лежит предположение, что если разделить все дорожные ситуации на группы со схожей историей, то у всех ситуаций внутри группы будет схожее развитие [4]. В качестве метода кластеризации может быть выбран метод k ближайших соседей [5]. В качестве «расстояния»  может выступить мера различия двух ситуаций на дороге

Мера различия ситуаций, вычисленная по множеству дорог, имеющих наибольшее влияние на данную дорогу, равна сумме мер различия для всех дорог этого множества с весами, равными силе взаимосвязи дорог:

Здесь l– число пар отсчетов, в которые известно значение скорости для обеих сравниваемых ситуаций, J ⁱ_road - мера различия двух ситуаций на дороге I ; I– число дорог, имеющих наибольшее влияние на данную дорогу.

Мера схожести ситуаций является величиной, обратной мере их различия

В случайном процессе V (t ) присутствует явная цикличность по времени суток, по дню недели и по времени года. Будем искать схожие ситуации с различным шагом цикличности ρ.

Ситуации подразделяются на группы с помощью метода k ближайших соседей по метрике J_area , рассчитанной на интервале [(t – T – nρ), (t – nρ)], где n– целое число. Кластеризации подлежат только ситуации, для которых выполнен ряд условий: полнота истории, значимость истории и определенность истории.

Полнота истории P оценивается числом измерений и равна

где N – число отсчетов в течение времени T. Значимость истории S оценивается числом ситуаций, попавших в группу. Определенность истории D оценивается близостью развития ситуации внутри группы и равна дисперсии величины J_area[(t – T – nρ), (t – nρ)] по множеству ситуаций в группе.

Прогнозная скорость вычисляется как взвешенная сумма экстраполированных характерных скоростей с весами W_area :

6. Результаты численного эксперимента

Для экспериментального исследования точности предсказания скорости транспортных потоков был разработан программный комплекс, реализующий описанные в статье прогнозирующие модели. Исходный код программного комплекса написан на интерпретируемом языке Python [6]. Код состоит из 15 функционально замкнутых модулей и соответствующих модульных тестов. Для первоначальной отладки прототипов всех прогнозирующих моделей использовался специализированный язык математического моделирования R[7].

В качестве исходных данных была использована информация о скорости движения транспорта по наиболее загруженным дорогам Санкт-Петербурга за сентябрь-октябрь 2010 года по данным компании «СитиГИД» [8].

Абсолютные значения меры погрешности прогноза J (п. 1) лишь опосредованно характеризуют точность предсказания скорости, но позволяют сравнивать применяемые прогнозирующие модели между собой. В табл. 1 приведены значения меры Jи соответствующие им оценки относительной погрешности расчёта времени движения  δTдля прогноза скорости согласно описанным в статье моделям.

Таблица 1.

Погрешности прогнозирования

Из табл. 1 видно, что использование характерной (медианной) скорости движения (п. 3) вместо средней позволяет повысить точность прогноза за счёт устранения влияния случайных выбросов скорости на получаемые предсказания. Тем не менее, дальнейшее увеличение достоверности прогноза обеспечивается лишь использованием более сложных математических моделей, учитывающих «сбалансированные» отклонения скорости от характерной (п. 4) либо использующих сравнение дорожной обстановки с аналогичными ситуациями в прошлом (п. 5). Последняя прогнозирующая модель является наиболее точной, однако предъявляет самые жёсткие требования к полноте истории и, следовательно, применима лишь для наиболее загруженных дорог города.

Заключение

Сравнение полученных результатов позволяет сделать вывод, что предложенные в статье математические модели прогноза обеспечивают в среднем более высокую точность, чем методы, основанные на экстраполяции средней или характерной скорости движения.

В дальнейшем планируется продолжить разработку новых моделей и протестировать уже существующие модели на большем интервале времени. Также планируется проверить работоспособность системы на данных, полученных в Москве и других городах.

Литература

1. Как работают Яндекс.Пробки. URL: http://company.yandex.ru/technologies/yaprobki/ (дата обращения: 01.03.2012)

2. IBMTrafficPredictionTool. URL: http://www.ibm.com/smarterplanet/us/en/traffic_congestion/nextsteps/index.html (дата обращения: 01.03.2012)

3. Jolliffe I.T. Principal Component Analysis, Series: Springer Series in Statistics, 2nd ed., Springer, NY, 2002, - 487 p. - P. 64–68.

4. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989. – 587 с. - С. 282-291.

5. MacQueen J. Some methods for classification and analysis of multivariate observations.In Proc. 5th Berkeley Symp.on Math. StatisticsandProbability, 1967, p. 281-297.

6. Python Programming Language – Official Website.  URL: http://www.python.org/(дата обращения: 01.03.2012).

7. The R Project for Statistical Computing. URL: http://www.r-project.org/ (дата обращения: 01.03.2012).

8. СитиГИД. Навигационная служба. URL: http://www.probki.net/news.aspx  (дата обращения: 01.03.2012).