СТАТИСТИЧЕСКИЕ МЕТОДЫ ОБРАБОТКИ ДАННЫХ ДЛЯ ПРОГНОЗИРОВАНИЯ ТРАНСПОРТНОЙ ЗАГРУЖЕННОСТИ ГОРОДСКИХ ДОРОГ

Вялых Константин Михайлович

аспирант, Московский государственный технический университет им. Н. Э. Баумана, г. Москва

E-mail: 

В статье анализируется проблема предсказания транспортных заторов на дорогах городов. Предлагаются математические модели и алгоритмы, позволяющие решать задачу прогнозирования дорожной обстановки, используя лишь информацию о скорости движения автомобилей, получаемую от портативных спутниковых навигаторов. Особое внимание уделено методам учёта неполноты и зашумлённости исходных данных при построении прогноза. Алгоритмы прогнози­рования успешно апробированы на выборке данных, полученной для дорог Санкт-Петербурга.

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

Наиболее доступным источником первичной информации о скорости транспортного потока являются портативные автомобильные спутниковые навигаторы. Этой информацией располагают компании «Яндекс» [2], «СитиГид» [1] и др. Тем не менее, подобная информация используется ими лишь для отображения на карте текущей (либо характерной для данного времени) дорожной обстановки. Прогноз изменения текущей обстановки пользователям не предоставляется.

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

Критерии качества прогноза. Каждая из рассматриваемых моделей имеет большую или меньшую предсказательную способность при определенных условиях, что требует дополнительных усилий по их выбору и согласованию. При выборе наилучшей модели прогнозирования дорожной обстановки необходимо задаться некоторой численной характеристикой качества прогноза. Тем не менее, в рамках решаемой задачи невозможно предложить единственно верный критерий точности предсказания ввиду сложности процесса и неоднородности требований пользователей к системе. Ни средняя абсолютная ошибка, ни средняя относительная ошибка, ни среднеквадратическая ошибка прогнозирования скорости не совпадают с интуитивным представлением о погрешности прогноза, что легко показать на следующем примере. Пусть при реальной скорости транспортного потока 80 км/ч две сравниваемые математические модели получили прогнозную скорость 140 и 20 км/ч соответственно. Для обеих моделей абсолютные ошибки прогнозирования равны 60 км/ч, относительные ошибки равны 75 %, а среднеквадратические ошибки равны 60 км/ч. Однако, с точки зрения пользователя, эти результаты не являются равноценными, поскольку применение второй модели приводит к принципиально неверному выводу о наличии затора.

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

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

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

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

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

Перечисленным требованиям удовлетворяет метрика вида M(V) = lnV. При расчете параметров моделей и выборе моделей оптимизируется среднеквадратическое отклонение метрики M(V).

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

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

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

Vʹ=V—V_char,

где: Vʹ — отклонение скорости;

V — текущая скорость;

V_char — характерная скорость.

Рассмотрим пару дорог c и d. Предположим, что влияние одной дороги на другую имеет линейный закон и распространяется с некой задержкой τ. Если τ<0, то дорога c влияет на дорогу d. Если τ>0, то дорога d влияет на дорогу c. Если τ близко к нулю, то имеет место как влияние c на d, так и влияние d на c. Таким образом, имеется взаимосвязь вида

V_cʹ(t) = a V_dʹ(t—τ) + ε(t),

где: V_cʹ — отклонение скорости для дороги c;

V_dʹ — отклонение скорости для дороги

d; a — величина взаимосвязи;

ε — остаточное отклонение скорости.

Остаточное отклонение ε(t) состоит из двух составляющих: случайного отклонения, которое затухает при неизменных значениях V_cʹ(t) и V_dʹ(t—τ), и неслучайного отклонения, которое затухает с изменением значений V_cʹ(t) и V_dʹ(t—τ). Априорно разделить эти отклонения не представляется возможным, однако величину взаимосвязи характеризуют скорости затухания этих отклонений. Поэтому вне зависимости от изменения V_cʹ(t) и V_dʹ(t—τ) взаимосвязь характеризуется затуханием величины ε(t). Если принять, что скорость затухания случайного отклонения скорости пропорциональна самому отклонению, то получим выражение

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

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

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

Значение силы взаимосвязи между дорогами µ зависит от значения задержки τ. Оптимальное значение τ не выводится аналитически, поэтому определяется перебором. Выбирается такая величина τ*, при которой взаимосвязь µ максимальна.

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

Прогнозирование на основе характерной скорости движения с учетом отклонений. Для прогнозирования дорожной ситуации на дороге c используется информация о ситуации на смежных дорогах d с силой взаимосвязи µ_c,d больше определенного порога. Величина взаимосвязи a рассчитывается с помощью метода главных компонент [3], использующего сингулярное разложение матрицы Vʹ, содержащей отклонения скоростей от характерной скорости.

После перемножения компонент разложения получим матрицу Vʹ_bal. В ней содержатся отклонения скорости, «сбалансированные» относительно предположения о линейном законе взаимосвязи между дорогами.

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

V_cp (t+θ) = V_cchar(t+θ) + β (θ) Vʹ_cbal(t),

где: V_cp — прогнозная скорость на дороге c;

V_cchar — характерная скорость на дороге c;

Vʹ_cbal — отклонение скорости для дороги c, содержится в строке матрицы Vʹ_bal, соответствующей дороге c;

β(θ) — функция, описывающая влияние «сбалансированного» отклонения скорости от характерной на прогнозную скорость для каждого θ.

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

где: интервал времени Δt показывает, насколько давним является сравниваемый прецедент.

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

где: l — количество пар отсчетов, в которые известно значение скорости для обеих сравниваемых ситуаций;

J_roadk — мера различия двух ситуаций на дороге k;

K — число дорог, имеющих наибольшее влияние на данную дорогу.

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

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

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

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

где: N — количество отсчетов в течение времени T.

Значимость истории S оценивается количеством ситуаций, попавших в группу.

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

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

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

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

• при расчете взаимосвязи между дорогами алгоритму для получения новой информации о взаимосвязи достаточно двух релевантных последовательных измерений на обеих дорогах;
• при прогнозировании на основе характерной скорости движения на небольшом количестве измерений влияние выбросов нивелируется благодаря оценке медианой распределения вместо среднего значения;
• при прогнозировании на основе характерной скорости движения с учетом отклонений можно выявлять множественные взаимосвязи при небольшом количестве измерений;
• при прогнозировании на основе прецедентов при расчете меры схожести между ситуациями нет необходимости иметь информацию о ситуации на всех участках области.
• погрешность разности метрик M(V_p) — M(V_r) не зависит от длины рассматриваемого участка дороги;
• благодаря возможности объединить дороги в группы по силе взаимосвязи и рассматривать группы как единое целое, ошибка прогнозирования уменьшается.

Результаты численного эксперимента. Для оценки качества предсказания производилось сравнение предложенных методов прогно­за с предсказанием при помощи простой экстраполяции средней скорости.

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

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

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

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

Список литературы:

1. Описание системы «СитиГид». URL: http://www.probki.net/news.aspx (дата обращения 01.03.2012).
2. Описание системы «Яндекс Пробки». URL: http://help.yandex.ru/maps/informer.xml (дата обращения 01.03.2012).
3. Jolliffe I. T. Principal Component Analysis, Series: Springer Series in Statistics. 2nd ed. — NY.: Springer, 2002, - 487 p. - P. 64—68.
4. MacQueen J. Some methods for classification and analysis of multivariate observations//Proc. 5th Berkeley Symp. on Math. Statistics and Probability. 1967. Р. 281—297.