Содержание к диссертации
Введение
1 Прогнозирование параметров дорожного движения: современные научные направления, решения и основные задачи 14
1.1 Статическое прогнозирование транспортных потоков 15
1.1.1 Прогнозные модели загрузки транспортной сети 15
1.1.2 Модели динамики транспортных потоков (имитационные модели) 16
1.1.3 Современные программные решения для моделирования транспортных потоков 23
1.2 Динамическое прогнозирование транспортных потоков 25
1.2.1 Оценка динамической матрицы корреспонденции и распределения транспортных потоков по сети на основании прямых измерений 25
1.2.2 Краткосрочное прогнозирование транспортных потоков 26
1.3 Прикладные задачи в транспортных сетях: модели и подходы 30
1.3.1 Модели прогноза событий 30
1.3.2 Навигационные задачи 33
1.3.3 Современные программные решения для решения прикладных задач 36
1.4 Обоснование проектов по модернизации транспортных сетей 37
1.5 Современные мировые тенденции 38
1.6 Место настоящей диссертации в научных исследованиях и основные задачи 41
2 Прогнозирование динамики транспортных потоков в транспортной сети с использованием актуальных и статистических данных 44
2.1 Основные обозначения и постановка задачи 45
2.2 Оценка параметров транспортных потоков по данным GPS/ГЛОНАСС наблюдений 48
2.2.1 Алгоритмы оценки текущего положения ТС на графе дорожной сети з
2.2.2 Оценка параметров транспортных потоков по актуальным данным 52
2.3 Общая схема предлагаемого метода 53
2.3.1 Представление графа сети с использованием подграфов. Вектор признаков подграфа 55
2.3.2 Снижение размерности описания подграфа УДС с учётом пространственной и временной избыточности данных о потоках 57
2.3.3 Алгоритмы прогнозирования транспортных потоков с использованием временных рядов 59
2.3.4 Алгоритмы прогнозирования транспортных потоков с использованием методов машинного обучения 61
2.3.5 Алгоритм адаптивной линейной комбинации элементарных прогнозов 63
2.3.6 Вычислительная процедура расчёта прогнозных параметров транспортных потоков 65
2.3.7 Математическая модель краткосрочной динамики транспортных потоков 65
2.3.8 Численный метод настройки математической модели краткосрочной динамики транспортных потоков 66
2.4 Экспериментальные исследования 70
2.5 Выводы и результаты второго раздела 80
3 Прогнозирование времени прибытия общественного транспорта с использованием адаптивной комбинации элементарных прогнозов 82
3.1 Основные обозначения и постановка задачи 82
3.2 Оценка времени прохождение ОТС конкретного сегмента. Модель адаптивной комбинации элементарных прогнозов 87
3.3 Оценка параметров элементарных алгоритмов прогноза 96
3.4 Численный метод настройки математической модели времени прибытия общественных транспортных средств на остановочные пункты 98
3.5 Экспериментальные исследования 99
3.6 Выводы и результаты третьего раздела 109
4 Архитектура и реализация программного комплекса решения задач краткосрочного прогнозирования динамики транспортных потоков и движения отдельных транспортных средств в транспортных сетях 111
4.1 Требования к программному комплексу 111
4.2 Исходные данные 112
4.3 Формирование модели транспортной системы города 115
4.4 Описание работы программного комплекса 116
4.4.1 Уточнение положения транспортных средств 117
4.4.2 Определение состояния транспортного средства 118
4.4.3 Прогноз времени прибытия 120
4.5 Архитектура программного комплекса 121
4.6 Физическая модель данных программного комплекса 128
4.7 Взаимодействие с клиентскими приложениями 130
4.8 Результаты четвертого раздела 133
Заключение 134
Список литературы
- Современные программные решения для моделирования транспортных потоков
- Оценка параметров транспортных потоков по актуальным данным
- Оценка времени прохождение ОТС конкретного сегмента. Модель адаптивной комбинации элементарных прогнозов
- Определение состояния транспортного средства
Современные программные решения для моделирования транспортных потоков
Модели следования за лидером предполагают, что следующие за лидером водители реагируют на малые изменения в относительной скорости даже при большом расстоянии до впереди идущего ТС. Чтобы исправить эту проблему были использованы исследования психологии восприятия [199]. Первая модель психологического расстояния была представлена в [216]. Были введены пороги восприятия и рассмотрено ограниченное и неограниченное вождение. Кроме того, модель включала маневры изменения полосы движения и обгона. Модели психологического расстояния являются основой целого ряда современных микроскопических имитационных моделей.
Микроскопические имитационные модели позволяют проследить за движением отдельных ТС и их водителей. Поведение водителей обычно описывается большим набором правил «если-то». Положение, скорость и ускорение каждого автомобиля вьшисляются для каждого момента времени в зависимости от поведения водителя и характеристик ТС. В работе [3] было приведено 58 микроскопических имитационных модели, из которых были проанализированы 32. Часть из них моделирует поведение следования за лидером и маневр смены полосы движения для каждого индивидуального транспортного средства в потоке. Как правило, поведение следования за лидером основывается на парадигме моделирования психологического расстояния. Для описания маневра изменения полосы движения в микроскопических моделях обычно выделяют этап формирования решения выполнить перестроение, способ выбора целевой полосы движения и момента перестроения. Примерами микроскопических моделей являются AIMSUN2 [9], FOSIM [208], модель Видемана [216].
Модели клеточных автоматов разбивают дорогу на «ячейки» одинаковой длины, транспортные средства движутся дискретно от ячейки к ячейке. Однополосная модель клеточных автоматов была представлена в [151], ее обобщение для случая многополосных многоклассовых моделей транспортных потоков приведено в [149]. Благодаря простоте вьшислений, модели клеточных автоматов могут использоваться для моделирования движения в транспортных сетях крупных размеров. Классическая модель клеточных автоматов следования за лидером является пространственно ориентированной и носит эвристический характер. В [224] предложена альтернативная многополосная модель клеточных автоматов, использующая временно-ориентированные правила следования за лидером. Эта модель описывает поведение водителей более реалистично, сохраняя при этом все достоинства оригинальной модели.
Модели частиц позволяют выделять и отслеживать индивидуальные транспортные средства; их поведение при этом описывается статистическими уравнениями движения, например, макроскопическими моделями транспортных потоков. Примером модели частиц является модель INTEGRATION [203]. В [84] предложена стохастическая микроскопическая пешеходная имитационная модель, основанная на кинетической модели пешеходных потоков.
Субмикроскопические имитационные модели помимо описания пространственно-временного поведения отдельных субъектов в системе движения описывают функционирование их отдельных частей (например, способы использования тормозной системы, учитывая среди прочего время реакции водителя, время, необходимое для нажатия на тормоз и т.д.). Такие модели хорошо подходят для моделирования воздействия системы помощи водителю на динамику автомобиля и стиль вождения. К примеру субмикроскопическая модель SIMONE [142] описывает действия системы адаптивного круиз-контроля (ICC) при непосредственной близости других транспортных средств. Другими примерами субмикроскопических моделей являются MIXIC [204] и PELOPS [128].
Мезоскопические модели транспортных потоков Мезоскопические модели описывают транспортные потоки на среднем уровне детализации. Движение транспортные средства и поведение водителей описываются в агрегированных терминах (например, с помощью функций распределения вероятностей), однако правила поведения описываются на индивидуальном уровне. Три хорошо известных примера мезоскопических моделей транспортных потоков это так называемые модели распределения интервалов движения, кластерные модели и кинетические модели. Интервал движения определяется как разница во времени прохождения фиксированной точки двумя подряд идущими транспортными средствами. Примерами моделей распределения интервалов движения являются полупуассоновская модель [20] и обобщенная модель очередей [19]. Недостатками моделей является игнорирование роли динамики движения. Более того, в моделях считается, что все транспортные средства являются по факту одинаковыми, т.е. функции распределения вероятностей не зависят от способа передвижения, типа транспортного средства, цели передвижения и т.д. Чтобы исправить эти недостатки, в [83] была разработана модель распределения интервалов движения для многопользовательских транспортных потоков и многопользовательских многополосных транспортных потоков.
В кластерных моделях вводится понятие кластера: группы транспортных средств, имеющих общую особенность. В пределах одного кластера условия движения, например, интервалы движения, различия в скорости, и т.д., считаются одинаковыми - в этом смысле кластеры являются однородными. Как правило, размер кластера является динамическим: кластеры могут расти и распадаться. Обычно кластеры возникают из-за ограничения возможностей обгона, например, запрещения обгона, невозможности обгона из-за взаимодействия с другими транспортными средствами, из-за погодных условий или условий окружающей среды [17].
В моделях, основанных на кинетическом уравнении, вместо описания динамики движения отдельных транспортных средств описывается динамика фазовой плотности потока. Основополагающей моделью данного типа является модель Пригожина [173], который впервые сформулировал кинетическое уравнение для транспортного потока. Модель была усовершенствована в [166]: динамика плотности потока рассматривалась в расширенном фазовом пространстве. Кинетическая модель для описания многополосного движения была представлена в [79,103]. В работах [87,85] были введено обобщение модели для описания движения смешанных (многопользовательских) транспортных потоков, в которых можно выделить классы пользователей, различающиеся типом ТС, правилами поведения водителей и т.д.
Оценка параметров транспортных потоков по актуальным данным
В настоящей работе для построения отдельных элементарных прогнозов и исследования их эффективности были использованы метод опорных векторов и метод потенциальных функций. Их краткое описание представлено ниже.
Регрессия методом опорных векторов (SVR) Метод опорных векторов является методом нелинейной регрессии, основная идея которого заключается в переводе исходных векторов признаков в пространство более высокой размерности и использование в новом пространстве модели линейной регрессии. Часто метод опорных векторов представляют в следующем виде:
Метод является вычислительно сложным из-за большой размерности векторов признаков, поэтому для его использования вместо исходных векторов VMV) В настоящей работе используются вектора описания & \Ч- Тогда метод опорных векторов, определяющий расчёт параметра ТП для конкретного сегмента w, примет вид:
Метод потенциальных функций Метод потенциальных функций позволяет прогнозировать значения параметров ТП с учётом близости векторов описания 3 {f) в разные моменты времени. Общее соотношение, характеризующее вычислительную процедуру получения прогнозного значения, для нашей задачи имеет вид (значение "0" в приводимой ниже формуле соответствует факту, что результат прогноза не определён/отсутствует): :(f + nA) = PFa(k,M,t,nA): m=0 JV-1 /_ _ ч ZRM(t)X(t-mA)) ядро формируемой оценки, монотонно убывающее по мере увеличения расхождения между векторами S (t),S \t-mA). В работе предлагается использовать следующую функцию, которая учитывает близость векторов описания не только в том же подграфе, в котором стоится прогноз, но и в "соседних" к -ому Н подграфах:
Параметр и определяет максимальное расстояние между векторами описания, которые будут использоваться в прогнозе. Варьируя значение параметра, будем получать различные значения прогнозов параметров ТП.
В выбранном варианте использования - с финитным ядром (14)-(15) - метод потенциальных функций имеет специфику: при малых значениях параметра и может быть формально получен результат со значением, обозначенным символом "0", то есть факт отсутствия результата. Такая ситуация возникает, если для текущего состояния сети в исторических данных не окажется ни одного близкого прототипа. В предлагаемом решении эта ситуация используется для построения адаптивной вычислительной процедуры агрегации элементарных прогнозов, описание которой приведено ниже.
Алгоритм адаптивной линейной комбинации элементарных прогнозов применяется для построения окончательного прогноза параметров ТП для каждого из подграфов с использованием адаптивной линейной комбинации полученных элементарных прогнозов. Адаптивность комбинации вводится путём анализа фактов появления неопределённых прогнозных значений в наборе алгоритмов прогнозирования, использующих рассмотренный ранее метод потенциальных функций. Ниже предлагаемый способ построения адаптивной комбинации представлен более формально. различная ситуация, когда отдельные прогнозы дают определённые/неопределённые значения.
Идея метода адаптивной линейной комбинации элементарных прогнозов заключается в построении независимых линейных комбинаций элементарных прогнозов (линейной регрессии элементарных прогнозов) для каждой из (Q + l) возможных ситуаций.
Предлагаемый вариант адаптивной комбинации может быть формально представлен в следующем виде:
Заключительным этапом предлагаемого метода является расчёт прогнозных параметров транспортных потоков для графа всей УДС как линейной комбинации прогнозных данных (16) для подграфов. Данная операция оказывается необходимой, поскольку для некоторых из сегментов, попавших одновременно в несколько подграфов, существует несколько прогнозных значений. Искомое прогнозное значение v(w,t) параметра ТП для сегмента w в момент времени t предлагается вычислять по следующей формуле:
В окончательном виде математическая модель краткосрочного прогнозирования параметров транспортных потоков по актуальным и историческим данным может быть представлена следующим набором формальных преобразований (ниже величина / означает текущий момент времени, a t +пА -момент времени, на который прогноз формируется). Этап 1. Проекция потоков на графе УДС на подграфы по формуле (7): Этап 2. Снижение размерности описания подграфов по формуле (10):
Математическая модель краткосрочного прогнозирования параметров ТП, представленная в предыдущем разделе, определена с точностью до набора параметров. Параметры можно условно разбить на две группы, первая из которых содержит параметры, определяемые пользователем или постановкой задачи. Вторая группа параметров - это параметры модели и входящих в её состав алгоритмов/методов. Принципиальным отличием второй группы параметров от первой является необходимость их определения (идентификации) по историческим данным состояний УДС. Ниже приведены составы указанных групп и для параметров второй группы представлено описание численных методов их идентификации.
Оценки матриц главных компонент основаны на оценках ковариационных матриц векторов признаков подграфов, выражения для которых приведены в (8). Описание метода выбора порядка и настройки параметров модели временных рядов (сезонной ARIMA и векторной VARMA) представлены в монографиях [18,29] и для краткости изложения здесь не приводится. По той же причине опускается описание метода решения задачи идентификации коэффициентов для метода опорных векторов, который детально описан в работе [240] и заключается в решении двойственной задачи математического программирования. Наконец, способ получения коэффициентов адаптивной линейной комбинации сводится к независимому решению задач идентификации коэффициентов для обычной линейной регрессии, выполняемой методом наименьших квадратов (МНК), в количестве ((2 + 1) штук (для каждой из возможных ситуаций, описание которых дано в соответствующем подразделе выше). Каждая из указанных МНК задач сводится в конечном итоге к решению системы нормальных уравнений, явный вид которого известен из теории оценивания и здесь, для краткости изложения, также не приводится.
Существенным моментом при оценивании всех указанных параметров является способ формирования выборочных данных, которые используются в качестве прецедентов обработки в вычислительных процедурах идентификации. Ниже представлены описания способов формирования выборочных данных для различных методов. При описании этих способов используются несколько новых обозначений.
Оценка времени прохождение ОТС конкретного сегмента. Модель адаптивной комбинации элементарных прогнозов
Для реализации элементарных прогнозных функций необходимо оценить их параметры: Атх (область определения ядра), и а - для экспоненциального и рационального ядер. Параметр Атх определяется по минимуму среднеквадратической ошибки элементарной прогнозной функции с треугольным ядром. В качестве обучающей выборки использовалась информация о прохождении всех сегментов сети всеми ОТС за день. На рисунке 17 показан график зависимости СКО от значения параметра Amax. 31,6 31,4 31,2 31
Нужно учесть, что при малых значениях Amx множество прецедентов для составления элементарных прогнозов будет пустым. Для реализации элементарных функций было выбрано значение параметра Amx = 2700 (секунд).
Выбор значения параметра а для экспоненциальной и рациональной функции проводился по минимуму СКО при фиксированном параметре Amx. Зависимость СКО от а для экспоненциальной функции приведено в таблице , для рациональной - в таблице.
Для экспоненциальной функции выбрано а = 2,55, для рациональной -а = 35,9 3.4 Численный метод настройки математической модели времени прибытия общественных транспортных средств на остановочные пункты
Для определения параметров адаптивной комбинации для каждой терминальной вершины конструируемой иерархической регрессии необходимо сформировать обучающую выборку. Ниже представлен предложенный способ её формирования.
Зафиксируем сегмент w, тип ТС s и типодень d . Для этих величин по обучающим данным (дни с выборками) для каждой текущей терминальной вершины иерархической регрессии формируем выборки следующим образом. ЦИКЛ по временам прогноза tc=t — wAt (At = 30c, n = 1,2...) Определяем местоположение ОТС с id в это время. Формируем набор параметров прогнозирования для данного ОТС с моментом построения прогноза tc и моментом прогноза t (= і) для сегмента w: rj(d,tc),tc,y{d,t),pw(d,t),rj(d,t). Формируем набор прецедентов \t — t T(tc),A (О)} » и считаем по ним элементарные прогнозы \Tsw,k (d, t, tc ) =0, )-1,.
По завершению формирования обучающих выборок для каждой терминальной вершины производится оценка параметров адаптивной комбинации по методу минимума СКО. Если размер обучающей выборки терминальной вершины недостаточен для оценки параметров комбинации, используются оценки, полученные на родительской вершине.
Экспериментальные исследования разработанного алгоритма проводились на улично-дорожной сети г. Самары. Дорожная сеть состоит из 3387 сегментов, трамвайная сеть - из 409 сегментов. Количество ОТС, подключённых к системе мониторинга - более 1500, новые координаты положения ОТС поступают с усреднённой периодичностью в 30 секунд. Подробнее система мониторинга движения будет описана в следующем разделе.
При составлении прогнозов проводилась дополнительная фильтрация данных, попадающих в список прецедентов {(/ - tj, Tj (tc), А; (tc))} „( у А именно, не рассматривались ТС, находящиеся на конечных точках маршрута, либо не изменявшие своего положения в течение долгого промежутка времени (больше 5 минут). Проводилось сравнение следующих алгоритмов: - алгоритма адаптивной комбинации с набором из 4-х различных ядер; - алгоритма адаптивной комбинации с набором из 4-х экспоненциальных ядер с разными показателями степени; - алгоритмов элементарных прогнозов Tsw,kyd,tc,t) для каждого типа ядра; - прогноза по статистике T{s)(d,i); - модели линейной регрессии, представленной в работе [2]. Сравнение проводилось по критериям СКО (RMSE), средней абсолютной ошибки {МАЕ) и средней относительной ошибки {МАРЕ):
Сравнение проводилось на данных о движении всех ТС в Самаре за 6 будних дней методом перекрестной проверки. Одна часть выборка состояла из записей за один день.
Сначала было проведено экспериментальное исследование алгоритмов для прогноза прибытия ТС автобусных маршрутов. Размер обучающей выборки составлял около 50 млн. записей, размер контрольной выборки - около 10 млн. записей.
В первую очередь было проведено сравнение элементарных прогнозов fwk(d,tc,t). Графики зависимости средней абсолютной и средней относительной ошибок от горизонтов прогноза показаны на рисунках 18 и 19 соответственно. Все прогнозы показали близкие результаты по выбранным критериям, элементарный алгоритм с прямоугольным ядром показал результат хуже остальных алгоритмов. Это объясняется тем, что алгоритм с прямоугольной функцией ядра не учитывает в прогнозе время получения прецедента. Далее на графиках сравнения алгоритмов будут отображаться только результаты прогнозов элементарных алгоритмов с экспоненциальным ядром.
Зависимость средней относительной ошибки от горизонта прогноза на контрольной выборке для ОТС автобусных маршрутов
Лучшие результаты показала модель адаптивной комбинации с различными ядрами элементарных прогнозов, модель адаптивной комбинации с экспоненциальными ядрами уступает по критерию СКО. В целом и на контрольной выборке модель адаптивной комбинации превосходит остальные алгоритмы.
Далее исследовалось качество модели при прогнозировании времени прибытия ОТС трамвайных маршрутов. Специфика движения ОТС трамвайных маршрутов заключается в том, что многие сегменты трамвайной сети являются обособленными и не так сильно зависят от общей транспортной ситуации в городе. Размер обучающей выборки составлял около 16 млн. записей, размер контрольной выборки - около 3 млн.
Графики зависимости СКО, средней абсолютной ошибки и средней относительной ошибки от горизонта прогноза на обучающей выборке для ОТС трамвайных маршрутов показаны на рисунках 26, 27, 28.
Определение состояния транспортного средства
Предназначена для получения новой порции данных о положениях транспортных средств через подсистема взаимодействия с БД мониторинга. При получении новых данных учитывается время предыдущего запроса, и возвращаются только положения транспортных средств, изменившиеся за период обработки. Новые данные поступают в подсистему определения состояния ТС.
Подсистема определения состояния ТС На первом шаге работы подсистема уточняет координаты и маршрут транспортных средств по транспортной сети города, чтобы уменьшить ошибку позиционирования. Уточнение происходит по текущему и предыдущим положениям ТС и информации о предполагаемых маршрутах ТС. Далее по новому положению и предыдущему состоянию происходит определение нового состояния ТС. Данные о состоянии ТС на маршруте поступают в подсистему формирования прогнозов.
Подсистема формирования прогнозов Подсистема определяет все управляющие параметры алгоритма адаптивной комбинации элементарных прогнозов, рассчитывает элементарные прогнозы и формирует прогноз прибытия ТС на все остановочные пункты на маршруте по ходу движения. Результат прогнозов записывается в базу данных программного комплекса через подсистему взаимодействия.
Обработчик запросов Реализует программный интерфейс для взаимодействия клиентских приложений с программным комплексом. Подробнее описан в разделе 4.7 Взаимодействие с клиентскими приложениями. Графический интерфейс администратора Через браузер предоставляет администратору сервера инструменты по настройке параметров функционирования программного комплекса, обновлению классификаторов маршрутов и остановок, их связи с классификаторами, принятыми в системе мониторинга «АСУ-Навигация».
Программный комплекс в целом представляет собой веб-приложение, поставляемое в формате WAR, написанное на языке программирования Java, предназначенное для развертывания в свободно распространяемом контейнере сервлетов Apache Tomcat 7. Разработанный программный комплекс может быть развернут на операционных системах Windows Server/XP/Vista/7/8.
Физическая модель данных программного комплекса Данные, необходимые для работы программного комплекса, хранятся в отдельной БД на отдельном сервере и не затрагивают работу системы «АСУ-Навигация». В качестве СУБД был выбран Microsoft SQL Server 2008 R2.
На рисунке 43 изображена диаграмма таблиц БД программного комплекса, используемых для хранения информации о транспортных средствах, доступных для мониторинга, и их связи с транспортными средствами в БД «АСУ-Навигация». Частичное дублирование данных необходимо для снижения нагрузки на БД мониторинга, а также для занесения в семантику ТС дополнительной информации, например, доступность для инвалидов.
Диаграмма таблиц, хранящих информацию, необходимую для составления прогнозов в модели адаптивной комбинации элементарных прогнозов, приведена на рисунке 45. Используются следующие таблицы:
Прогнозы прибытия и другая аналитическая информация о движении ОТС должны быть доступны сторонним сервисам для информирования пассажиров, поэтому для взаимодействия сервисов с программным комплексом был разработан программный интерфейс. Обращение к программному интерфейсу происходит с помощью HTTP-протокола. Существование единого программного интерфейса позволяет разрабатывать новые типы клиентских приложений (например, CMC и ICQ-сервисов) без внесения изменений в работу программного комплекса. В программном комплексе реализован интерфейс со следующими методами:
Получение прогнозов для заданной остановки выполняется в отдельном потоке и не затрагивает основной цикл пересчета положений ТС и формирования прогнозов. Состоит из двух шагов:
1. Из хранилища делается выборка прогнозов всех маршрутов, проходящих через остановку.
2. Набор прогнозов сортируется по времени, снабжается дополнительной информацией о прибывающих транспортных средствах (бортовой номер, местонахождение), и в определенном формате записи выдается в ответ на запрос.
В настоящее время программный комплекс используется для отображения информации о движении транспорта на сайте транспортного оператора Самары (рисунок 46), с помощью мобильных приложений (рисунок 47), на карте города (рисунок 48), с помощью электронных табло на остановочных пунктах.
