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

На правах рукописи

Агафонов Антон Александрович

Математические модели и адаптивные методы краткосрочного прогнозирования

параметров дорожного движения

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание учёной степени кандидата технических наук

3 0 ОКТ 2014

САМАРА-2014

005553845

005553845

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)»" на кафедре геоинформатики и информационной безопасности и в федеральном государственном бюджетном учреждении науки Институте систем обработки изображений Российской академии наук.

Науч н ый руководитель: доктор физико-математических наук, доцент Мясников Владислав Валерьевич

Официальные оппоненты:

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

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

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт системного анализа Российской академии наук, г. Москва.

Защита состоится "12" декабря 2014 г. в 10 часов на заседании диссертационного совета Д 212.215.05, созданного на базе федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)», по адресу: 443086, г. Самара, Московское лиоссе, 34.

С диссертацией можно ознакомиться в библиотеке и на сайте федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)», http://www.ssau.ru.

Автореферат разослан "10" октября 2014 г.

Учёный секретарь

диссертационного совета Д 212.215.05 доктор технических наук, доцент

С.В. Востокин

" Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика СП. Королева {национальный исследовательский университет)» переименовано в федеральное государственное автономное образовательное учреждение высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)», приказ Минобрнауки России от 10 июля 2014 г., 738.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы

Развитие и повсеместное активное использование современных систем электронных коммуникаций, глобальных навигационных систем, систем компьютерного зрения, активных и пассивных датчиков различного типа и назначения привело к появлению возможности решения чрезвычайно сложных проблем, сама постановка которых два десятилетия назад казалась невозможной. К числу таких проблем, несомненно, относятся проблемы создания "умных городов" и интеллектуальных транспортных систем. Рассматриваемая в рамках диссертационной работы задача построения краткосрочного (в пределах часа) прогноза параметров транспортных потоков и движения отдельных транспортных средств в крупных городах является одной из многих задач, которые приходится решать на пути полного и эффективного разрешения указанных проблем. В настоящем же времени решение указанных задач оказывается также полезно, что наглядно демонстрируют известные компании Яндекс, Google и др., предоставляющие различные интернет-сервисы и/или мобильные приложения, которые позволяют участникам дорожного движения визуально анализировать развитие транспортной ситуации а своём городе и планировать свои перемещения. С ростом реального трафика популярность таких сервисов только увеличивается.

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

Собственно задачам краткосрочного прогнозирования транспортных потоков и прогноза событий в мировой печати посвящено огромное количество работ, однако на русском языке публикации практически отсутствуют. Наиболее популярными моделями и методами решения этих задач являются: модели на основе архивных данных (Smith В., 1993); линейные регрессионные модели (Rice, 2004; Sun H., 2007); модели временных рядов ARIMA (Williams В., 2003; Fambro D., 2007), VARMA (Stathopoulos А., 2003), ST-ARMA (Kamarianakis I., 2002); нейронные сети (Chen H., 2001; Guorong G., 2010); модели на основе фильтрации Калмана (Okutani I., 1984; Ojeda, 2013); методы непараметрической регрессии (Zhang Т., 2010); метод опорных векторов для задач регрессии (Wu С., 2003; Zhang X., 2007); гибридные модели (Tan M., 2009; Sun г., 2013). В последнее время усилия исследователей сосредоточены на разработке гибридных моделей.

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

- имеют «локальный» характер: прогноз вычисляется для конкретного сегмента или перекрестка транспортной сети;

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

- игнорируют дополнительную информацию, влияющую на величину прогноза.

Учитывая все изложенные выше тезисы, можно говорить о безусловной актуальности как

темы диссертационной работы в целом, так и отдельных выбранных направлений исследований в частности.

нрль и задачи исследований

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

Для достижения поставленной цели в диссертации решаются следующие задачи:

1. Оценка современного состояния задач прогнозирования в транспортных сетях.

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

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

4. Разработка и реализация программного комплекса решения задач прогнозирования динамики транспортных потоков и движения отдельных транспортных средств в транспортных сетях. Постановка экспериментов на натурных данных (полученных в транспортной сети города Самара), анализ результатов и сравнение с существующими решениями. Поставленные задачи определяют структуру работы и содержание её разделов. Методы исследований

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

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

2. Разработаны оригинальные алгоритмы оценки текущего положения транспортных средств на графе дорожной сети по данным СРБ/ГЛОНАСС наблюдений.

3. Разработан оригинальный численный метод настройки (определения параметров) предложенной математической модели краткосрочной динамики транспортных потоков с использованием актуальных и статистических данных о движении транспортных средств.

4. Предложена математическая модель времени прибытия общественных транспортных средств на остановочные пункты, использующая комбинацию алгоритмов прогнозирования, адаптивную по отношению к состоянию движения транспорта и ряду внешних факторов (освещение, погодные условия).

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

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

Теоретическая значимость работы

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

Практическая значимость работы

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

в г. Самара посредством сайта транспортного оператора Самары (tosamara.ru) и мобильного приложения "Прибывалка-63", что подтверждается актом внедрения ОАО «Самара-Информспутник». Реализация результатов работы

Результаты диссертации использованы при выполнении ряда госбюджетных и хоздоговорных НИР в ИСОИ РАН, ОАО «Самара-Информспутник», проекта РФФИ № 13-07-12103-офи-м «Анализ и прогнозирование транспортных потоков на основе комплексного использования космической навигационной информации, данных дистанционного зондирования Земли и систем видеонаблюдения», программы фундаментальных исследований Президиума РАН «Фундаментальные проблемы информатики и информационных технологий» (проект 2.12), работ по договору для Министерства образования и науки Российской Федерации (в рамках постановления Правительства Российской Федерации от 09.04.2010 г. № 218: договор N3 02.Г36.31.0001 от 12.02.2013). Апробация работы

Основные результаты диссертации были представлены на двух научных конференциях: международной молодежной конференции «XII Королёвские чтения» (Самара, 2013); 11-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» («РОАИ», Самара, 2013). Публикации

По теме диссертации опубликовано 5 работ. Из них 3 работы опубликованы в изданиях, определённых в перечне ведущих рецензируемых научных журналов и изданий ВАК Министерства образования и науки РФ.

Структура диссертации

Диссертация состоит из четырёх разделов, заключения, списка использованных источников из 255 наименований; изложена на 164 страницах машинописного текста, содержит 48 рисунков, 7 таблиц, 2 приложения.

На защиту выносятся

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

2. Алгоритмы оценки текущего положения транспортных средств на графе дорожной сети по данным GPS/ГЛОНАСС наблюдений и численный метод настройки (определения параметров) предложенной математической модели краткосрочной динамики транспортных потоков с использованием актуальных и статистических данных о движении транспортных средств.

3. Математическая модель времени прибытия общественных транспортных средств на остановочные пункты, использующая комбинацию алгоритмов прогнозирования, адаптивную по отношению к состоянию движения транспорта и ряду внешних факторов (освещение, погодные условия).

4. Численный метод настройки предложенной математической модели времени прибытия общественных транспортных средств на остановочные пункты.

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

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ В первом разделе диссертации приводится оценка современного состояния задач прогнозирования в транспортных системах. Приведена классификация задач, рассмотрены подзадачи, включающие в себя:

— статическое прогнозирование матриц корреспонденции и распределения транспортных потоков, решаемое методами прогнозного и имитационного моделирования (Гасников A.B., Швецов В.И., Hoogendoorn S.P., Ortuzar J.);

- динамическое прогнозирование транспортных потоков, включающее оценку матриц корреспонденции и распределение потоков в течение дня, э также краткосрочное прогнозирование (Wu}., Sherali H., Bolshinsky E., Vlahogianni E.);

- прогноз событий и навигационные задачи, включающие задачи прогноза прибытия ОТС на остановочные пункты (Lin S., Altinkaya M.), прогноза дорожных заторов (Liu) и другие.

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

Во втором разделе диссертации решается задача оценки и краткосрочного прогнозирования динамики транспортных потоков.

Примем в качестве математической модели улично-дорожной сети (УДС) ориентированный граф, дуги we W которого соответствуют реальным участкам (сегментам) УДС, а вершины представляют собой разделяющие участки дорог узлы. Направление дуги определяет направление движения транспортного средства (ТС) на соответствующем участке сети, а параметр транспортного потока (ТП) на конкретном участке сети определим как функцию v: WxT -> R, которая в конкретный момент времени /еТ для конкретной дуги we W определяет его значение v{w,i).

В настоящей работе исходными данными для оценок параметров ТП выступают данные GPS/ГЛОНАСС измерений, которые поступают с различных ТС как актуальная информация. Формально, эти данные могут быть представлены как последовательность пар физических координат следующего вида:

(1)

где 3 с N - определяет множество условных номеров ТС, которые поставляют GPS/ГЛОНАСС -данные о своём местоположении; j - задаёт порядковый номер поступившего сигнала.

Формальная постановка задачи получения краткосрочного прогноза для заданного параметра ТП УДС может быть сделана следующим образом: имея заданный граф УДС с множеством рёбер W и множеством маршрутов {Wm }„sn и актуальные (и исторические} данные о положении ТС в виде (1), рассчитать оценку (спрогнозировать) параметров ТП v{w,r) для всех iveW и

t=t'+n& (л = 1 ,N).

В приведённой формулировке N-число формируемых прогнозов, расположенных регулярно с временным интервалом Д, величина /' - текущий момент времени. Прогнозный горизонт в этом случае определяется величиной N&, которая для интересующего нас краткосрочного прогноза имеет порядок одного часа.

Предварительным, но необходимым этапом предлагаемого метода, является преобразование исходных данных к виду, удобному для обработки. Суть такого преобразования - переход от набора данных (1), косвенно характеризующих параметры ТП в сети в конкретные моменты времени (прошлого), к собственно значениям параметров ТП в эти моменты:

\{w,t\ we W, t = t'-nA{n = 0X~) W

Предлагаемый способ построения актуальных оценок параметров транспортных потоков (2) по данным GPS/ГЛОНАСС наблюдений (1) состоит из двух этапов:

- построение оценок местоположений ТС 8 конкретные моменты времени, для которых учитываются ограничения, налагаемые геометрическим положением сегмента УДС и поступательным и/или маршрутным движением отдельных ТС;

- расчёт величин (2) по полученным оценкам местоположений.

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

- алгоритм 1 для случая единственного маршрута ОТС;

- алгоритм 2 для случая двух маршрутов ОТС, различающихся направлением движения;

- алгоритм 3 для случая произвольного ТС, определяющий наиболее «вероятное» местоположение ТС с учетом истории движения.

Алгоритмы 1 и 2 определяют местоположение ОТС на сегменте маршрута с учетом условия поступательного движения, либо снитают положение неопределенным, если ОТС находится не на маршруте.

Предлагаемый метод краткосрочного прогнозирования параметров ТП состоит из следующих этапов (ниже каждый из этих этапов представлен подробнее):

1) Разбиение графа УДС на пересекающиеся подграфы по территориальному признаку и формирование вектора признаков (значений параметров потоков) по каждому из них.

2) Снижение размерности вектора признаков для каждого подграфа путём устранения пространственно-временной зависимости значений параметров потоков.

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

4) Агрегация элементарных прогнозов, построенных для каждого из подграфов УДС, с использованием адаптивной линейной комбинации полученных элементарных прогнозов. Адаптивность вводится путём учёта дополнительной (управляющей) информации, возникающей при невозможности построения отдельных элементарных прогнозов для метода потенциальных функций - в этом случае линейная комбинация элементарных прогнозов формируется для сокращённого набора построенных прогнозов.

5) Расчёт окончательных значений прогнозных параметров транспортных потоков всей УДС в виде линейной комбинации прогнозов для всех подграфов УДС. В данном случае изменениям (усреднениям) подвергаются только те параметры, которые соответствуют сегментам УДС (рёбрам графа), попавшим одновременно в несколько подграфов.

Предлагается следующий способ представления графа УДС с использованием подграфов: выбирается число формируемых подграфов в количестве АГ0 • Л",, и в подграф с номером к =к0К\ +£, {ка = О,А"0 — = О,К1 -1), обозначаемый ниже \У,, относятся те дуги из множества \У, координаты одной из вершин которых попадают в прямоугольную область П, , : ™11Л(„, х"'(0) = П(оЛ V *"(1)е },

Л и» ™

= ГГШ

г + к° (-с --С")

«о Л1)

*Г = тах лгГ (с1 з- = 0,1 .

Каждый получаемый подграф \У, УДС для дальнейшей обработки представляется в виде своего описания - вектора признаков, характеризующего потоки подграфа в конкретный момент времени. Формирование указанного вектора признаков производится следующим образом.

Пусть {< - набор рёбер конкретного выбранного подграфа в количестве 5* штук, упорядоченный определённым образом (способ упорядочивания значения не имеет). Тогда вектор признаков, используемый в качестве описателя этого подграфа, имеет вид:

V,(() = (Ки.„. Д.... 1-МА\. ,./)... / - Л/Л»7" (3)

здесь М> 1 - число используемых в векторе признаков архивных значений параметров ТП для каждого сегмента сети. Для удобства дальнейшего изложения, процесс получения описания для конкретного подграфа запишем в виде операции проекции:

* = (4)

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

Предлагаемый способ снижения размерности заключается в переходе от исходного представления (3) к сокращённому представлению с использованием небольшого числа компонент, получаемых с использованием метода главных компонент (РСА) по оценке ковариационной матрицы векторов признаков ?£(/). Результатом работы метода снижения размерности оказывается вектор &'(/), состоящий из компонент, которые совокупно характеризуют текущее состояние (с предысторией на Л/отсчётов по времени) подграфа Wi УДС в конкретный момент времени Полученный вектор описания Щ, (г) вместе с исходным описанием подграфа УДС используются для построения набора элементарных прогнозов.

Далее рассмотрим используемые в работе алгоритмы элементарных прогнозов.

Из моделей временных рядов в диссертации были использованы сезонная модель АИ1МА и векторная модель УАЯМА. Результат прогнозирования, получаемый при применении метода прогнозирования временных рядов для всех сегментов в конкретном к-ом подграфе сети, будем в дальнейшем обозначать (/ + лд)= 75(<г,Л/,г,пЛ).

Метод опорных векторов является методом нелинейной регрессии, основная идея которого заключается в переводе исходных векторов признаков в пространство более высокой размерности и использование в новом пространстве модели линейной регрессии. Результат прогнозирования, получаемый в результате применения метода БУИ, будем обозначать у0'(/ + лд)=5га(£,л/,ллд)

Метод потенциальных функций позволяет прогнозировать значения параметров ТП с учётом близости векторов описания в разные моменты времени. Общее соотношение, характеризующее вычислительную процедуру получения прогнозного значения, для нашей задачи имеет вид (значение "0" в приводимой ниже формуле соответствует факту, что результат прогноза не определён/отсутствует):

V,; (г +- пД) = РР„ (к, м,и лД)з

0, 1>Л^(<Ш/-тл))=о.

где Яа(5,$ ядро формируемой оценки, монотонно убывающее по мере увеличения

расхождения между векторами В работе предлагается использовать следующую

функцию, которая учитывает близость векторов описания не только в том же подграфе, в котором стоится прогноз, но и в "соседних" к к-ому Н подграфах:

[о, р > 4а. (6)

Г*

Параметр а определяет максимальное расстояние между векторами описания, которые будут использоваться в прогнозе. Варьируя значение параметра, будем получать различные значения прогнозов параметров ТП.

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

Пусть ^ (er, eR,) монотонно убывающая последовательность чисел:

а", > crqtl [q = 0,0-2). Тогда при Q выбранных для метода потенциальных функций ядер с различными {с,]^ возможна всего (Q +1) различная ситуация, когда отдельные прогнозы дают

определённые/неопределённые значения. Идея метода адаптивной линейной комбинации элементарных прогнозов заключается в построении независимых линейных комбинаций элементарных прогнозов (линейной регрессии элементарных прогнозов) для каждой из (Q +1) возможных ситуаций. Предлагаемый вариант адаптивной комбинации может быть формально представлен в следующем виде:

anJS(k,M,l,n&)+a"SVR(kM,t,n&\ PF^(k,MJM) = 0. Га'(/ + иДН (7)

(k,M,t,n&\ q = 1 + arg maix_(PF„ (к.М,!,пЛ) Ф 0). ,,о ' «-ö.e-i *

В представленной адаптивной линейной комбинации настройка требуется для следующего набора вещественных коэффициентов {ar* jj-o.^. Для настройки коэффициентов используется оригинальный численный метод с использованием актуальных и статистических данных о движении транспортных средств.

Заключительным этапом предлагаемого метода является расчёт прогнозных параметров транспортных потоков для графа всей УДС как линейной комбинации прогнозных данных (7) для подграфов. Данная операция оказывается необходимой, поскольку для некоторых из сегментов, попавших одновременно в несколько подграфов, существует несколько прогнозных значений. Искомое прогнозное значение v(n.',f) параметра ТП для сегмента w в момент времени t предлагается вычислять по следующей формуле:

*М = Й--(8)

где ?„'(()| - значение параметра ТП на конкретном сегменте w, полученное для к-го подграфа, i7» (f| играет роль индикатора вхождения сегмента в конкретный подграф:

[О, иначе. [0, иначе.

В окончательном виде математическая модель краткосрочного прогнозирования параметров транспортных потоков по актуальным и историческим данным может быть представлена следующим набором формальных преобразований (ниже величина /* означаеттекущий момент времени, а t + пА - момент времени, на который прогноз формируется).

Этап 1. Проекция потоков на графе УДС на подграфы по формуле (4):

¡Й'МЛ'Х . k-ÖJTК

Этап 2. Снижение размерности описания подграфов.

Этап 3. Расчёт набора элементарных прогнозов для состояния сети в будущий момент времени ?„*(/*+лд) с использованием метода прогнозирования временных рядов 7х(*,ЛЛ<'.пд), метода опорных векторов $Ув{к,М/м) и метода потенциальных функций РРа{к,М,<,пД) (л =

Этап 4. Построение адаптивной линейной комбинации элементарных прогнозов, полученных на предыдущем шаге, и получение набора прогнозов для отдельных подграфов {?,}(/ + иа)}4„0 ■ Формальное выражение для адаптивной линейной комбинации приведено в формуле (7).

Этап 5. Расчёт прогнозных параметров транспортных потоков для графа всей УДС по формуле

(8). „

Экспериментальное исследование разработанной модели и алгоритма адаптивнои комоина-ции проводилось на УДС г. Самара. Графики зависимости средней абсолютной ошибки (в секундах) и средней относительной ошибки от горизонта прогноза (в минутах) показаны на рисунках 1а и 16 соответственно.

140 0.25

Рисунок 1. Зависимость ошибок от горизонта прогноза.

Модель адаптивной комбинации показала лучшие результаты по сравнению с элементарными прогнозами.

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

Введём обозначения:

- V/-конкретный сегмент сети;

- 5 - тип (сорт) ТС/ общественного ТС (ОТС);

- т - номер маршрута ТС/ОТС;

. щ _ множество сегментов сети, соответствующих конкретному маршруту ОТС (5, т);

- Ю - уникальный идентификатор ОТС.

- с/- день, однозначно идентифицируемый набором (год, день); всё множество дней обозначим Ч> О/еУ);

- {Ч'„Ч'21..,Ч', } = Ф -разбиение всего множества дней ¥ (¿еЧ") на эквивалентные классы (например, дни недели). Дополнительно определим функцию Ф, которая выдаёт класс/тип конкретного дня, называемые далее "типодень";

- 1С -текущий момент времени (момент, на который составляется прогноз).

Положение произвольного объекта на транспортной сети задаётся парой (сегмент, относительное положение в сегменте) - («г, д), где Д е [ОД].

Постановка задачи: пусть в конкретный момент г, конкретное /-ое ОТС находится в положении Д0). Необходимо определить время, через которое оно будет находиться в заданном положении (остановки) (и-,;,ДЛ.).

Считаем, что маршрут между двумя положениями (\у0,Д0) и (и^,ДА.) включает в себя следующие сегменты из множества ¡V,т ->и'2 ->...-»и>,._, при этом следующие положения считаются равными (н,<,1)=(н,К|,0).

Тогда

*=I

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

Т,о'(¿.'гА '>!, (9)

Конструируемая оценка (9) должна учитывать следующие специфики. Во-первых, эта величина характеризует время прохождения сегмента и^ совершенно конкретным транспортным средством с идентификатором Ш. При этом на том же сегменте может выполняться движение других транспортных средств, в частности: ОТС того же маршрута ОТС того же типа .5; ОТС других типов и другие ТС.

Замена прогнозного времени для конкретного ОТС на величину прогнозного времени другого ОТС того же типа или ТС другого типа сопровождается, с одной стороны, потенциальным увеличением используемых в построении оценки (9) числа ТС, и, с другой стороны, игнорированием в конструируемой оценке специфики движения, присутствующей у конкретного ОТС, конкретного маршрута и т.д. Для учета этой специфики в модель введены мультипликативные коэффициенты.

Тогда искомой величиной является величина Т'(<1,1Г,1), которая определяет прогнозное время прохождения конкретного сегмента ОТС типа 5 в момент времени г дня А при условии, что прогноз вычисляется в момент времени 1Г. Перечислим состав информации, которая (неочевидным образом и в неочевидной степени) оказывает влияние назначение Т"'(с!, г). Для удобства введём индекс "последнего" по порядку ОТС на сегменте и- конкретного типа 5: к"(¿/,<с).

Тогда состав искомой информации может быть определён следующим образом:

1) - диапазон времени, прошедший с момента прохождения сегмента последним ОТС того же типа (на момент построения прогноза);

2) 1-1с -требуемый горизонт прогноза;

3) Тг.Ы1 ((/с) - время нахождения на сегменте последнего (на момент построения прогноза)

ОТС;

4) Т.,^ ((гг) = | - "наивная" оценка времени прохождения сегмента ОТС с

порядковым номером /с"{(1,1с), совпадающая с реальным временем нахождения указанного ОТС на сегменте в случае, если ОТС уже оказалось на другом сегменте, и элементарным образом экстраполирующая время прохождения сегмента в противном случае;

5) То^О/.О - нормативное время прохождения сегмента и' ОТС того же типа 5;

6) Тэд^'— статистическое время прохождения сегмента м/ ОТС того же типа 5;

— предположительное время прохождения сегмента с учётом средней скорости

конкретного ОТС;

~ множество прецедентов, отражающих моменты и время прохождения сегмента различными ОТС к моменту прогноза ;

9) ^(</,/)е[0,1] - условное значение, интегрально характеризующее на момент прогноза I сложность вождения при данном освещении и при данных погодных условиях;

11

10) р*(</,г)е[0Д] - условное значение, характеризующее плотность потока транспортных средств на участке сети в конкретное время;

11) 7(</,() - параметр, характеризующий динамику движения ТС;

12) 5-типОТС.

Указанные величины несут различную содержательную информацию, влияющую на способ её использования. А именно, величины 3-8 отражают отдельные или статистически агрегированные "прецеденты" временных затрат. Указанные величины могут быть использованы (вместе или отдельно, напрямую или косвенно) при построении искомой оценки как некоторые реализации искомой оценки (неискажённые или искажённые заранее определённым образом).

Величины 1-2 и 9-12 непосредственно оказывают влияние на искомую величину. Однако, ни одна из этих величин не может быть рассмотрена как прецедент временных затрат. Как следствие, указанные величины можно рассматривать как управляющие, характеризующие способ комбинации и/или его параметры.

Учитывая сделанные замечания, величину 77(й*(,«) целесообразно рассматривать как некоторую функцию следующего вида:

Выбор конкретного вида этой функции - это вопрос выбора соответствующей математической модели, с последующим решением вопросов идентификации и верификации. В данной работе предлагается следующий вид функции, основанный на комбинации алгоритмов, выполняющих элементарные прогнозы для каждого типа ОТС (рисунок 2):

5=0

Алгоритм 0

Алгоритм К-1

/Л*')

7=ч«:-!

'о

5-1-1, м.Н '

Алгоритм 0

Алгоритм А*- /

Агрегирующая функция

I

I кК -1 ^ ^ параметры 8.

тГСл)

уМ р'(*0

гЛ^'с-О

Рисунок 2. Схематический вид модели комбинации элементарных прогнозов Алгоритмы элементарных прогнозов реализуют отображения множества прецедентов {(/-г^гД/Дд/г,))}.^.^ ( в различные оценки средних Г/'г). В качестве подобных отображений в работе предлагается использовать следующие:

(О _

г.«*(</,,„,)= !. _ \ , К* М=

к = О.ЛМ

Предлагаемые оценки относятся к классу ядерных, при этом различия в алгоритмах заключаются в используемых ядрах ык (1). В диссертации используются 4 ядра: прямоугольное, треугольное, экспоненциальное и рациональное. Дополнительно следует заметить, что в целом предлагаемая модель допускает использование произвольного набора алгоритмов оценки среднего, не обязательно совпадающих с выбранными.

Алгоритм комбинации элементарных прогнозов реализует отображение набора оценок средних и величин Г.^,в итоговую

оценку с учётом значений управляющих параметров

■5,г"(г/,/Д< —Представляется целесообразным, чтобы этот алгоритм удовлетворял следующим двум основным требованиям: был адаптивен по отношению к изменениям дорожной ситуации, был адаптивен по отношению к значению параметров.

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

Предлагается в качестве агрегирующей функции использовать следующее выражение:

/

(И)

л -1 . .

1 И + а2 +а] +а4" +а';

Определение параметров в формуле (11) производится с использованием оригинального численного метода. В рамках этого метода параметры {а* {и^*,,^,,^,,^,,«,',} определяются отдельно для каждого типа .т ОТС и подобластей параметров г"/Д (- ,/(г/,Г), р"(с/. 1\г/{с1л) алгоритма агрегации. Определение областей осуществляется автоматически в процессе конструирования иерархической регрессионной конструкции, подобной дереву регрессии. Отличием от известного дерева регрессии в данном случае является то, что значения параметров, по которым производится иерархическое разбиение, не используются в расчёте функции регрессии (11).

Экспериментальные исследования предложенной модели и алгоритма прогнозирования проводились на улично-дорожной сети г. Самары. Графики зависимости средней абсолютной ошибки (в секундах) и средней относительной ошибки от горизонта прогноза (в минутах) показаны на рисунках За и 36 соответственно. Модель адаптивной комбинации показала лучшие результаты.

- Статистика

- Экспоненциальное ядро

- Адаптивный прогноз

а)

0,35 0,3 0,25 0,2 0,15 0,1 0,05 0

— — - Статистика

-Экспоненциальное ядро

Адаптивный прогноз

б)

Рисунок 3. Зависимость ошибок от горизонта прогноза

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

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

- должны использоваться данные глонасс-мониторинга общественного транспорта по территории г.о. Самара;

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

- время обработки по всем транспортным средствам и остановкам должно быть гарантированно меньше периода обновления данных в 30 секунд.

В соответствии с приведенными требованиями была определена схема взаимодействия разрабатываемого программного комплекса с другими компонентами системы и спроектирована его архитектура, показанная на_рисунке4.

Сервер информационного табло

Подсистема взаимодействия с БД мониторинга

Подсистема взаимодействия с сокетным сервером

--Г —

Подсистема взаимодействия с БД сервера

Сокетный сервер (служба)

Модуль трансформации координат (еИ1)

Рисунок 4. Архитектура программного комплекса

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

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

заключение

Основные результаты диссертационной работы:

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

2. Разработаны оригинальные алгоритмы оценки текущего положения транспортных средств на графе дорожной сети по данным GPS/ГЛОНАСС наблюдений.

3. Разработан оригинальный численный мето'д настройки (определения параметров) предложенной математической модели краткосрочной динамики транспортных потоков с использованием актуальных и статистических данных о движении транспортных средств.

4. Предложена математическая модель времени прибытия общественных транспортных средств на остановочные пункты, использующая комбинацию алгоритмов прогнозирования, адаптивную по отношению к состоянию движения транспорта и ряду внешних факторов (освещение, погодные условия).

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

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

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

Публикации по теме диссертации

Статьи в изданиях, входящих в перечень ВАН:

1. Агафонов A.A. Прогнозирование параметров движения городского пассажирского транспорта по данным спутникового мониторинга / A.A. Агафонов, A.B. Сергеев, A.B. Чернов // Компьютерная оптика. - 2012. -Т. 36. №3. - С 453-458.

2. Агафонов A.A. Алгоритм оценки времени прибытия общественного транспорта с использованием адаптивной композиции элементарных прогнозов / A.A. Агафонов, В.В. Мясников // Компьютерная оптика. - 2014. - Т. 38. №2. - С. 356-369.

3. Агафонов A.A. Оценка и прогнозирование параметров транспортных потоков с использованием композиции методов машинного обучения и моделей прогнозирования временных рядов / A.A. Агафонов, В.В. Мясников // Компьютерная оптика. - 2014. - Т. 38. N93. - С. 539-549.

Материалы и тезисы конферениий, статьи в сборниках:

1. Агафонов A.A. Прогнозирование параметров движения городского пассажирского транспорта по данным спутникового мониторинга и статистическим данным / A.A. Агафонов // XII Королёвские чтения: Международная молодёжная научная конференция. - Самара. - 2013. - Том 2. - С 172.

2. Agafonov A.A. City transport motion parameters forecasting by satellite monitoring data and statistics / A.A. Agafonov, A.V. Chernov, A.V. Sergeyev // Proceedings of the 11th International Conference on Pattern Recognition and Image Analysis: new information technologies (PRIA-11-2013). - Samara. - 2013. -Vol. 2.-pp. 489-491

Подписано в печать 26.09.2014. Формат 60 х 84/16. Бумага ксероксная. Печать оперативная. Объем - 1,0 усл. п. л. Тираж 100 экз. Заказ № 29.

Отпечатано в типографии ООО «Инсома-пресс» 443080, г. Самара, ул. Сапфировой, 110 А: тел.: 222-92-40