Математическое моделирование процесса перемещения мобильных объектов в транспортных сетях для задач планирования оптимального маршрута движения Трубаков Евгений Олегович

Содержание к диссертации

Введение

ГЛАВА 1. Анализ подходов к математическому и компьютерному моделированию перемещения объектов в транспортных сетях с планированием маршрута передвижения 10

1.1. Анализ проблем математического и компьютерного моделирования мобильных объектов 11

1.1.1. Проблема объемов информации при сохранении истории изменения 12

1.1.2. Проблема получения актуальной информации в высоконагруженных системах 15

1.1.3. Проблема прогнозирования пространственного положения объекта 17

1.1.4. Поддержка специализированных запросов

1.2. Задачи систем мониторинга мобильных объектов 20

1.3. Анализ методов пространственно-временного моделирования

1.3.1. Анализ методов моделирования дорожных сетей 25

1.3.2. Анализ методов организации данных в ГИС 27

1.3.3. Анализ методов организации пространственных данных 28

1.3.4. Анализ методов организации пространственно-временных данных 35

1.4. Анализ методов поиска оптимального маршрута с учетом пространственно-временных параметров 42

1.5. Анализ математических методов актуализации данных в высоконагруженных системах мониторинга мобильных объектов 49

1.6. Метод построения прогноза изменения пространственного положения мобильных объектов 52

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

1.8. Постановка задачи диссертационного исследования 57

ГЛАВА 2. Математическая модель пространственно временных данных для позиционирования и прогнозирования положения мобильных объектов 58

2.1. Общие принципы построения пространственно-временной модели 59

2.2. Модель топологии транспортной сети 64

2.3. Методы сокращения размерности графа транспортной сети 65

2.4. Методы представления пространственно-временных данных

2.4.1. Метод представления топологии транспортной сети 69

2.4.2. Методы представления характеристик транспортной сети 72

2.4.3. Методы представления характеристик мобильных объектов 78

2.4.4. Математическое моделирование пространственно-временного перемещения мобильных объектов для разработки планов 83

2.5. Математический метод увеличения скорости обновления данных в высоко нагруженных системах мониторинга мобильных объектов 85

2.5.1. Алгоритм обновления значений динамических характеристик сегментов сети 85

2.5.2. Алгоритм обновления значения динамических характеристик мобильных объектов 87 2.6. Математический метод повышения эффективности занимаемого дискового пространства хранением истории изменения характеристик пространственно-временного моделирования 89

2.6.1. Алгоритм свертки значений динамических характеристик сегментов транспортной сети 89

2.6.2. Алгоритм свертки значений динамических характеристик мобильных объектов 90

2.7. Выводы 91

ГЛАВА 3. Математическое моделирование перемещения мобильных объектов для поиска оптимального пути 93

3.1. Алгоритм пространственно-временного моделирования перемещения мобильных объектов 93

3.2. Алгоритм поиска выбранного сегмента 94

3.3. Численный метод поиска оптимального маршрута 97

3.4. Численный метод определения веса сегмента транспортной сети 101

3.5. Алгоритм увеличения релевантности планового маршрутов 106

3.6. Выводы 109

глава 4. Программный комплекс пространственно временного моделирования мобильных объектов и экспериментальные исследования эффективности разработанных методов 111

4.1. Программный комплекс пространственно-временного моделирования мобильных объектов в дорожных сетях с прогнозированием и планированием 111

4.1.1. Назначение и особенности реализации программного комплекса 112

4.1.2. Этапы разработки программного комплекса 113

4.1.3. Инструментальные требования к программному комплексу 114

4.1.4. Функциональная схема программного комплекса 116

4.1.5. Структурная схема программного комплекса 120

4.1.6. Принципиальная схема работы системы мониторинга процесса перемещения мобильных объектов в транспортных сетях 123

4.1.7. Метод получения динамических характеристик мобильных объектов 125

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

4.1.9. Выбор и обоснование языка, средств разработки и используемой СУБД 131

4.2. Экспериментальные исследования эффективности разработанных методов моделирования 132

4.2.1. Описание тестовых данных 132

4.2.2. Оценка эффективности поиск оптимального маршрута 133

4.2.3. Оценка прогнозирование пропускной способности сегментов дорожной сети 135

4.2.4. Оценка адекватности построенного маршрута 136

Выводы 137

Заключение 139

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

• Проблема прогнозирования пространственного положения объекта
• Методы представления пространственно-временных данных
• Алгоритм поиска выбранного сегмента
• Принципиальная схема работы системы мониторинга процесса перемещения мобильных объектов в транспортных сетях

Введение к работе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Соответствие диссертации паспорту специальности. Работа соответствует паспорту специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»:

п. 1 – разработка новых математических методов моделирования объектов и явлений.

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

п. 4 – реализация эффективных численных методов и алгоритмов в виде
комплексов проблемно-ориентированных программ для проведения

вычислительного эксперимента.

п. 6 – разработка новых математических методов и алгоритмов проверки адекватности математических моделей объектов на основе данных натурного эксперимента.

Научная новизна работы состоит в следующем:

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

2. Предложена пространственно-временная структура данных на основе усеченного агрегированного R*-дерева для представления транспортной сети.

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

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

Практическую ценность работы составляют следующие положения.

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

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

Практическое применение. Предложенные методы моделирования пространственно-временного перемещения мобильных объектов легли в основу программного комплекса мониторинга и планирования перемещения мобильных объектов «ГИСМО+», внедренного в логистический отдел ОАО МП «Совтрансавто-Брянск-Холдинг», занимающегося грузоперевозками по всей России и в другие государства. Комплекс «ГИСМО+» использовался для мониторинга положения автотранспорта компании и планирования маршрутов его перемещения.

На защиту выносятся следующие положения:

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

4. Методы агрегирования сегментов транспортной сети, на основе усеченного R*-дерева с агрегированными виртуальными узлами второго рода для повышения эффективности численных методов поиска оптимального пути движения.

5. Методы прогнозирования изменения динамических характеристик транспортной сети.

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

7. Математические методы и алгоритмы пространственно-временного моделирования процесса перемещения мобильных объектов на основе предложенной модели.

8. Метод контроля за релевантностью планового маршрута движения мобильного объекта в транспортной сети.

9. Архитектура и функциональные характеристики разработанного проблемно-ориентированного программного комплекса «ГИСМО+».

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

Апробация результатов работы. Результаты диссертации были представлены

на 15 конференциях различных уровней: международной научно-технической конференции «Информационные технологии, энергетика и экономика» (г. Смоленск, 2011); III Всероссийской конференции «Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях» (г. Иркутск, 2013); международной научно-практической конференции «Fundamental science and technology» (г. Москва, 2013); всероссийской научной конференции с международным участием «Геодезия, картография и маркшейдерия» (г. Казань, 2014) и др.

Публикации. По теме диссертации опубликовано 15 печатных работ, в том числе 1 монография и 4 статьи в научных журналах, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, четырёх глав, заключения, библиографического списка, содержащего 143 наименования и приложения. Работа изложена на 154 страницах, содержит 32 рисунка, 2 таблицы. Общий объем работы составляет 156 страниц.

Проблема прогнозирования пространственного положения объекта

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

На фоне развития систем мониторинга происходит развитие компьютерных технологий. Например, удешевление объемов памяти, увеличение дискового пространства. Это приводит к тому, что остро встает вопрос не хранения, а обработки всех накопленных данных и использование её в дальнейшем планировании. Именно для этого и разрабатываются новые эффективные математические модели хранения и обработки пространственно-временных данных.

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

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

На данный момент однозначного решения проблемы объемов данных нет. В разных математических моделях используются различные приемы для сокращения поступающей в систему информации. Наибольшее распространение среди таких работ получили [57, 63, 74, 94, 114, 124, 131, 136, 141, 143]. Рассмотрим наиболее типичные подхода минимизации данных.

В реальных системах для человека временная ось считается непрерывной, поэтому и в системе мобильных объектов она также непрерывна. Из-за этого возникает масса проблем с неуправляемым ростом данных. Для того что бы выйти из сложившийся ситуации принимают распространение временной оси дискретным. То есть разбивает её на равные интервалы времени, в которые могут приходить данные от объектов. По своей сути эти интервалы указывают возможную частоту обновления данных. То есть в конце каждого интервала объект собирает со своих датчиков информацию и отправляет её на серверную часть системы мониторинга. Поступающая информация считается многомерной точкой в пространстве характеристик объекта. Для получения траектории изменения характеристики полученные точки интерполируются. Данная кривая является неким приближенным аналогом действительного изменения. Так как изменения характеристик происходит всё же в непрерывном распределении оси времени. Точность совпадения, полученного и действительного треков, задается при помощи сокращения частоты получения данных (шага дискретности оси времени). Но следует учитывать тот факт, что чем чаще система получает данные, тем их будет больше. Таким образом, появляется обратная взаимосвязь между объёмом данных и точностью траектории их изменения. Пусть Rr будет показателем реального маршрута, а Rd будет отображаемым маршрутом. Тогда среднее значение разницы между маршрутами: где n - количество полученных показаний, а Vi - объем данных получаемый каждый интервал времени. Тогда точность прямо пропорциональна шагу дискретности и обратно пропорциональна объемам информации. Иначе говоря, чем ниже шаг, тем выше точность и выше объемы данных, а чем выше шаг, тем ниже точность и ниже объемы данных.

Другим приемом в пространственно-временном моделировании является признание факта определенного закона изменения характеристик объекта (например, пусть движение объекта описывается прямолинейно). Тогда, зная начальное положение объекта и его вектор движения, всегда можно определить его положение на траектории. Поэтому отпадает необходимость в хранении точек прямой движения объекта. В моделировании при данном подходе происходит сохранения ключевых точек, то есть тех точек, в которых произошло изменение вектора движения. Таким образом, дискретный шаг обновления данных в системе равен интервалу изменения вектора движения в реальном мире. Поэтому частота обновления данных в системе зависит от некоторого порогового значения изменения данных (от погрешности изменения, меньше которой считается движения без изменения). Как и в первом приеме так и во втором объём данных зависит от их точности. То есть чем меньше пороговое значение изменения данных, тем они точнее и тем большие объемы поступают в систему.

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

Проблема минимизации объёмов исторической информации, и её обработка являются самыми существенными, стоящими перед разработчиками систем мониторинга мобильных объектов. Во многом именно тут появляются нюансы различного пространственно-временного моделирования данных [10].

Методы представления пространственно-временных данных

Листовая же вершина данной структуры представляется в виде набора следующих данных: L = IDMO, IDSeg, T1, T2, PStart, PEnd, Past, PointData , где IDMO – идентификатор движущегося объекта, IDSeg – идентификатор сегмента сети, интервал (PStart, PEnd) – начальная и конечная пространственная метка на сегменте, т.е. часть сегмента, на которой происходило движение в интервале времени (T1, T2), Past – указатель на листовой узел с прошлым участком движения объекта (указатель может быть направлен на узлы любого дерева из набора Rs), PointData – указатель на ячейку структуры второго уровня.

Эти и многие другие модели пространственно-временных данных были разработаны для потребностей организации данных. Мониторинг мобильных объектов – является одной из ключевых задач в системах мониторинга, но не единственной. Рассмотренные модели не отвечают широкому кругу задач систем, поэтому необходимо производить их расширение, либо на структурном уровне, либо на функциональном. Наибольшую эффективность системы получат при расширении на структурном уровне. Поэтому во второй главе предложена новая математическая пространственно-временная модель данных, которая учитывает достоинства существующих моделей, но имеет значительные расширения по сравнению с ними. 1.4. Анализ методов поиска оптимального маршрута с учетом пространственно-временных параметров

Вся транспортная сеть разбивается на сегменты. Точки соединения этих сегментов можно принять как вершины графа, тогда сами сегменты станут ребрами графа. Таким образом сеть можно представить в виде графа G: где u – начальная вершина ребра, а v – конечная вершина дуги. То есть можно сказать, что дуга (сегмент сети) ведет от вершины u к вершину v [44]. Маршрутом (путем) называется последовательность дуг графа такая, что начальная вершина дуги является конечной вершиной для соседней дуги. M = (a1, a2, …), где a1 и a2 такие что v1 = u2.

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

Весом ребра в графе может быть любая характеристика, подставленная в числовом виде. Поэтому введем дополнительную функцию w, с помощью которой происходит вычисление числового значения веса из значения характеристики. Вес всего пути р определяется как сумма весов сегментов этого пути: р = (wo, wi, ..., wk).

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

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

Алгоритм Дейкстры. Алгоритм Дейкстры находит кратчайший путь от заданной вершины графа до всех остальных. Работает для графов без отрицательных весов [62].

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

Алгоритм Дейкстры-Грибова. Алгоритм Дейкстры–Грибова заключается в модификации алгоритма Дейкстры. Изменения базового алгоритма заключается в разбиении множества вершин на подмножества с близкими значениями кратчайшего пути в текущую вершину на данном шаге. Значения принимаются как близкие, если их разница меньше либо равна минимальной длины дуги. На каждом шаге при поиске вершины берется не пустое подмножество, соответствующее минимальному значению расстояния [27].

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

Алгоритм Левита. Алгоритм Левита похож на алгоритм Дейкстры. Отличие заключается в том, что при изменении метки вершины на более меньшую, эта вершина помечается как не проверенная и для неё снова запускается алгоритм. Второе отличие заключается в возможности работы с отрицательными весами ребер [20]. Сложность алгоритма рассчитывается по формуле: O(n m).

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

Алгоритм Йена. Алгоритм Йена предназначен для поиска нескольких оптимальных путей во взвешенном графе между двумя вершинами. Его суть заключается в том, что после нахождения оптимального пути мы можем из него выкинуть какое-либо ребро и взамен ему достроить путь [23].

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

Алгоритм Беллмана- Форда. Алгоритм Беллмана-Форда так же, как и алгоритм Дейкстры решает задачу по поиску кратчайших путей из заданной вершины до всех остальных вершин графа. Данный алгоритм отличается от алгоритма Дейкстры, тем, что вес дуг в графе может быть отрицательным. Так же этот алгоритм проверяет наличие отрицательных циклов. Если в графе нет таковых, то алгоритм находит кратчайшие пути [51, 73]. Время работы алгоритма рассчитывается по формуле:

Алгоритм поиска выбранного сегмента

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

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

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

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

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

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

Математический метод повышения эффективности занимаемого дискового пространства хранением истории изменения характеристик пространственно-временного моделирования

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

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

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

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

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

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

Так как с течением времени количество маршрутов будет только увеличиваться, то производить их обработку будет затруднительно. Поэтому организуется отдельное TCB+-дерево в листовых вершинах, которого сохраняются указатели на структуры маршрутов. Благодаря такой организации увеличивается скорость поиска необходимого маршрута.

Принципиальная схема работы системы мониторинга процесса перемещения мобильных объектов в транспортных сетях

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

Уровень прогнозирования. Данный уровень содержит набор правил, по которым происходит приблизительный расчет изменения конкретных параметров в будущем следующим образом. Из хранилища выбирается определенная группа данных. Например, данные конкретного объекта о его уровне топлива за последние 5 часов. Далее с помощью соответствующих алгоритмов происходит расчет дальнейшего изменения параметра на определенный срок в будущем. Например, пусть будет алгоритм расчета расхода топлива следующим: находится среднестатистическое значение расхода в час, далее полученное значение принимается постоянным и на основе этого значения можно предположить с определенной долей вероятности расход топлива за последующий час.

На основе выдвинутых требований и функциональной схемы системы мониторинга построим для неё структурную схему (см. рис. 26). С её помощью можно выделить приоритетные элементы для анализа, отследить зависимость между модулями и произвести начальное планирование [31].

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

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

Дорожная сеть. Тип данных дорожная сеть представляет собой статические данные дорожной сети, загружаемые в систему в векторном виде. По сути это набор векторов и пространственные отношения между ними [65].

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

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

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

Все данные системы попадают на уровень хранения. На уровне хранения находятся модули предобработки данных, загружаемых в систему и модули её хранения (см. рис. 27).

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

Следующим уровнем является базовый уровень. В этом блоке находятся основные функции для обработки запросов по дорожной сети, слоям, работы с мобильными объектами (см. рис. 28).

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

Еще выше находятся интерфейсы взаимодействия пользователей и других систем с системой мониторинга.

Началом работы с системой мониторинга процесса перемещения мобильных объектов в транспортных сетях является загрузка начальных данных (пространственные данные окружающей среды, статичные данные мобильных объектов, транспортную сеть (топологию и статические характеристики сегментов сети)). Загрузку данных в систему осуществляется администратором-менеджером.

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

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

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

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