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



Шестаков Николай Александрович

Алгоритмическое и программное обеспечение геоинформационной системы для мониторинга мобильных объектов в дорожной сети

05.13.11— Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

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

- 9 ЛЕН 2010

Томск —2010

004615949

Работа выполнена на кафедре вычислительной техники ГОУ ВПО Национальный исследовательский Томский политехнический университет

Научный руководитель:

доктор технических наук, профессор, Заслуженный деятель науки РФ Марков Николай Григорьевич

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

доктор технических наук, профессор Бойков Владимир Николаевич

кандидат технических наук, доцент Останин Сергей Александрович

Ведущая организация:

Томский государственный

университет систем управления и радиоэлектроники, г. Томск

Защита состоится 22 декабря 2010 г. в 17 часов на заседании Совета по защите докторских и кандидатских диссертаций Д 212.269.06 при Национальном исследовательском Томском политехническом университете по адресу: 634034, г. Томск, ул. Советская, 84/3, Институт кибернетики ТПУ, ауд. 214.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского Томского политехнического университета по адресу: 634034, г. Томск, ул. Белинского, 55.

Автореферат разослан «2<3> ноября 2010 г.

Ученый секретарь Совета по защите докто"~"""г и кандидатских диссертаций Д 212.269.06

кандидат технических наук, доцент

Общая характеристика работы

Актуальность темы. В последние годы, особенно с развёртыванием отечественной спутниковой навигационной системы ГЛОНАСС, наблюдается взрывное развитие технологий позиционирования объектов. Появляется всё больше доступных цифровых карт, дешевеет навигационное оборудование. Это даёт толчок к массовому распространению информационных систем, основанных на использовании данных о местоположениях мобильных объектов (МО), а также ведёт к появлению вокруг этих систем инфраструктуры сервисов, основанных на местоположении МО (location-based services или LBS-услуг). К таким системам относятся персональные автонавигаторы, работающие с одним МО, системы мониторинга и диспетчеризации автотранспорта (СМиДА), которые получают информацию о перемещениях многих МО, интернет-сервисы, собирающие данные о перемещениях большого числа МО («ТогаТот», «Яндекс-Пробки», «Пробковорот», «СитиГИД» и другие). Активно развиваются интеллектуальные транспортные системы. Все эти классы систем можно отнести к категории систем мониторинга мобильных объектов (СММО), которые объединяет то, что МО перемещаются в дорожной сети (ДС).

Параллельно с развитием СММО идёт развитие геоинформационных систем (ГИС), традиционно решающих сложные и серьёзные задачи в области обработки пространственной информации, в том числе и данных о перемещениях МО. Универсальные ГИС, такие как ArcGIS или Maplnfo, обладают средствами, позволяющими решать сложные транспортные задачи, но для навигационных систем и СМиДА их функционал избыточен, скорость работы невысока, а стоимость слишком велика. Поэтому эти продукты занимают нишу, в которой от систем требуется сложный пространственный анализ и моделирование, но не требуется работа в реальном времени.

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

Таким образом, можно сделать вывод об актуальности разработки СММО, имеющих функционал «интеллектуальной» обработки данных о перемещениях МО в ДС, характерный для ГИС, но в то же время способных обрабатывать данные о местоположениях МО в реальном времени.

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

1. На основе анализа существующих СММО и универсальных ГИС определить набор функций ГИСММО и ряд требований к ней.

3 4

2. Разработать принципы построения и структуру ГИСММО.

3. Создать математическое обеспечение ГИСММО. Решение этой задачи предполагает анализ существующих моделей ДС, адаптацию и модификацию таких моделей под функционал ГИСММО, разработку алгоритмов обработки данных о перемещениях МО в ДС и алгоритмов выполнения запросов к пространственным базам данных (БД). Необходимо провести исследование эффективности предложенных алгоритмов.

4. Разработать программное обеспечение (ПО) ГИСММО с учётом имеющихся программных средств современных векторных ГИС и универсальных СУБД. Созданные в результате программные средства системы должны реализовать разработанные модели и алгоритмы и удовлетворять сформулированным принципам и структурным особенностям ГИСММО.

5. Апробировать ГИСММО путём создания на её основе инструментальных и проблемно-ориентированных систем, позволяющих решать практически значимые задачи.

Методы исследований. В работе использованы методы математического моделирования, теории графов, математической статистики, объектно-ориентированного проектирования ПО и проектирования БД.

Научную новизну полученных в работе результатов определяют:

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

2. Предложенные оригинальные показатели эффективности алгоритмов позиционирования МО в ДС в реальном времени.

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

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

Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, алгоритмы и программные средства, использованные в различных инструментальных и проблемно-ориентированных ГИСММО. Объем исходного кода разработанных программных средств составляет более 18 ООО строк на языке С# и Delphi. Разработанный набор библиотек ArdaMap, предназначенный для обработки данных перемещений МО в ДС в реальном времени, реализует предложенную модель ДС, маршрутный алгоритм позиционирования МО в ДС в реальном времени, средства хранения данных ДС в БД и средства импорта данных ДС. ArdaMap является важной составляющей инструментальных ГИСММО, реализованных на программных платформах .NET Compact Framework (внедрена в проекте StreamSpin на мобильных устройствах) и .NET (внедрена в системе мониторинга и диспетчерского управления городского пассажирского транспорта в ООО «ИНКОМ» и в серверной части StreamSpin). Модули об-

работки и хранения ПД, реализующие алгоритмы выполнения пространственных запросов и написанные на языке Delphi, внедрены в подсистеме работы с картами и технологическими схемами корпоративной геоинформационной системы управления производством «Магистраль-Восток» в ОАО «Вос-токгазпром» и ОАО «Томскгазпром».

Результаты внедрения подтверждены 3 актами о внедрении.

Основные положсшш, выносимые на защиту:

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

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

3. Разработанный алгоритм квадрантного разбиения области пространства (используемый в методах Z- и XZ-индексирования пространственных объектов) обеспечивает меньшую ошибку аппроксимации при заданном ограничении количества квадрантов, чем аналогичные алгоритмы.

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

5. Разработанное алгоритмическое и программное обеспечение инструментальных ГИСММО позволяет создавать проблемно-ориентированные ГИСММО и тем самым эффективно решать ряд практически значимых задач по обработке данных о перемещениях МО в ДС.

Апробацпя работы. Основные результаты работы докладывались и обсуждались на II, VI и VII Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных «Молодёжь и современные информационные технологии» (Томск, 2004 г.; Томск, 2008 г.; Томск, 2009 г.), X, XI, XII, XV, XVI Международной научно-практической конференции студентов, аспирантов и молодых учёных «Современная техника и технологии» (Томск, 2004 г.; Томск, 2005 г.; Томск, 2006 г.; Томск, 2009 г.; Томск, 2010 г.), VII Международном российско-корейском симпозиуме по науке и технологиям KORUS'2004 (Томск, 2004 г.), VI Всероссийской научной конференции молодых ученых «Наука. Технологии. Инновации» (Новосибирск, 2006 г.), III, VI, VII Всероссийской конференции «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2006 г.; Томск, 2009 г.; Томск, 2010 г.), 25th Urban Data Management Symposium (Дания, Ольборг, 2006 г.), Международной научно-практической конференции «Интеллектуальные информационно-телекоммуникационные системы для подвижных и труднодоступных объектов» (Томск, 2010 г.)

По результатам исследований опубликовано 17 работ, в том числе 16 статей (2 статьи в изданиях, рекомендованных ВАК).

Личный вклад:

1. Постановка задач диссертационного исследования и разработка концепции ГИСММО, постановки задачи исследования эффективности предложенных автором алгоритмов выполнены совместно с Н.Г.Марковым.

2. Концептуальная структура ГИСММО и структуры И-ГИСММО разработаны автором совместно с Н.Г.Марковым.

3. Модель ДС и реализующие её алгоритмы разработаны автором.

4. Ядро инструментальных ГИСММО (в том числе алгоритм позиционирования МО в ДС), алгоритмы хранения и индексирования ПД, схемы базы данных ДС и маршрутов разработаны автором.

5. Численные эксперименты по исследованию эффективности алгоритма квадрантного разбиения, алгоритмов пространственного индексирования и алгоритма позиционирования МО в ДС проведены автором.

6. Корпоративная ГИС управления производством «Магистраль-Восток», в состав которой было включено ПО ГИСММО в части хранения и обработки ПД, разработана сотрудниками лаборатории геоинформационных систем Института кибернетики ТПУ Кудиновым А.В, Ковиным Р.В., Мирошниченко Е.А. и др. Интеграция модулей пространственного индексирования ГИСММО с ГИС «Магистраль-Восток» была осуществлена автором.

7. Платформа StreamSpin была разработана в исследовательском центре DAISY (университет Ольборга, Дания). Интеграция разработанного ПО инструментальных ГИСММО с платформой осуществлена автором совместно с аспирантом R. Wind и профессором C.S.Jensen этого университета.

8. Система мониторинга и диспетчерского управления городского пассажирского транспорта была разработана ООО «ИНКОМ». Интеграция ПО инструментальной ГИСММО для мониторинга и диспетчеризации автотранспорта (ГИСММО МиДА) с этой системой была осуществлена при участии автора.

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

Содержание работы

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

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

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

На основе анализа функций современных универсальных ГИС и их структуры показано, что многие функции по анализу данных перемещений МО в ДС присутствуют в тех или иных ГИС-продуктах, но использовать такие продукты в качестве СММО зачастую затруднительно или невозможно.

Сделан вывод об актуальности разработки некоторой СММО, в которой бы присутствовали более развитые функции, характерные для ГИС, но реализованные с учётом специфики задач мониторинга МО в ДС.

Рассмотрены модели ДС, используемые в настоящее время, проанализирована возможность их применения в СММО. Проведён анализ существующих алгоритмов позиционирования МО в ДС. Рассмотрены методы и алгоритмы хранения и индексирования пространственных данных, которыми оперируют ГИС и СММО.

На основе результатов проведённого анализа проблемы мониторинга МО в ДС формулируются цель исследования и задачи, решаемые в диссертационной работе.

Вторая глава посвящена концепции создания ГИСММО.

Сформулированы основные требования к ГИСММО:

1. Данные о местоположениях МО должны обрабатываться этой системой в режиме реального времени.

2. ГИСММО должна учитывать тот факт, что МО перемещаются в ДС по маршрутам. Это должно вести к реализации в системе аппарата теории графов, решению транспортной задачи л необходимости подсчёта статистик перемещений МО по маршрутам.

3. ГИСММО должны быть нацелены на решение широкого круга задач, обычно решаемых раздельно уже существующими СММО и ГИС.

4. Разрабатываемые программные средства должны позволять дорабатывать существующие СММО, реализуя в них функции ГИСММО.

На основе изложенных требований предложена концепция создания ГИСММО. Она выражается, в первую очередь, в виде ряда принципов:

1. Структура ГИСММО описывается на трёх уровнях абстракции: концептуальном, инструментальном и проблемно-ориентированном.

2. На основе концептуальной структуры ГИСММО разрабатывается ряд структур инструментальных ГИСММО, их программные средства.

3. ПО каждой из инструментальных ГИСММО позволяет решать класс задач в той или иной предметной области.

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

5. Инструментальные и проблемно-ориентированные ГИСММО должны, по возможности, включать в качестве компонентов универсальные продукты, имеющиеся на рынке (для хранения данных — универсальные СУБД, для оперирования картографическими данными — векторные ГИС).

... . - Данные о местоположениях

ФМ - функциональным модуль ПД - пространственные данные /\ ^ МО, позиционированные в ДС

^ ц Информационный обмен _ ДС-дорожная сеть МО-мобильные объекты ¿Гл Исходные данные о

местоположениях МО

Рис. 1. Концептуальная функциональная структура ГИСММО

На концептуальном уровне абстракции предложена функциональная структура системы (рис. 1), отражающая деление её на функциональные модули и функции без привязки к программным платформам и технологиям, на которых возможна реализация системы. В этой структуре функции ГИСММО, в свою очередь, разделяются на уровни. Функции доступа к данным отвечают за хранение и работу с данными системы. Уровень ядра реализует базовые функции ГИСММО: работа с ДС, с картой, учётными записями пользователей, первоначальная обработка данных о местоположении МО, позиционирование МО в ДС. На функциональном уровне расположены специализированные с учётом особенностей предметной области функции системы: работа с маршрутами, картографические запросы, управление учетны-

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

Кроме базовых функций ДС, карты, учётных записей и подписок, характерных именно для ГИСММО, система может содержать и другой функционал (прочие базовые функции и функциональные модули), который зависит от области применения системы. Для таких функций также характерно распределение по уровням.

На инструментальном уровне абстракции концептуальная структура ГИСММО трансформируется в виде ряда структур инструментальных ГИСММО. Разные инструментальные ГИСММО имеют общий набор базовых функций, но различные ФМ. Предложены и описаны структуры инструментальных ГИСММО МиДА, персональной автомобильной навигации и LBS-услуг.

В третьей главе описаны разработанные модель ДС и алгоритм позиционирования МО в ДС в реальном времени. Проведено исследование эффективности предложенного алгоритма.

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

Топология ДС описывается направленным мультиграфом, в котором узлы представляют пересечения дорог на одном уровне, а рёбра — участки дорог между пересечениями. Участки дорог с двусторонним движением могут быть представлены одним ребром графа. Направление рёбер графа необходимо для того, чтобы отсчитывать расстояние вдоль участка ДС, а также указывать направление движения, если оно одностороннее. Каждому ребру графа сопоставлен признак одностороннего движения («да» или «нет»).

Геометрия ДС описывается множеством полилиний. Каждая полилиния состоит из последовательности точек с известными координатами. Каждой полилинии сопоставлена дуга графа ДС. Каждой точке полилинии сопоставлено расстояние (обозначаемое как measure), которое требуется пройти вдоль полилинии до этой точки (для первой точки полилинии measure = 0, а для последней — равно длине полилинии). Сегментом ДС обозначим ребро графа вместе с соответствующей ему полилинией и атрибутами.

Местоположение точечного объекта в ДС задаётся его позицией р = {5, measure, dir}, где S — ребро графа ДС, measure — расстояние, отсчитываемое вдоль сегмента от начала ребра до положения объекта на ребре, dir — направление движения объекта вдоль ребра, принимающее одно из возмож-

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

Особенностью предлагаемой модели ДС является возможность позиционировать не только точечные объекты, но и площадные. В географической системе координат такому объекту сопоставлена некоторая область, которую нужно отобразить на ДС. Местоположение площадного объекта в ДС будем задавать множеством позиций Е = {pi, р2, ... р„), которые будем называть позициями выхода из области, сопоставленной с этим объектом. Направление движенияpt всегда устанавливается из внутренней области объекта наружу. Зная позиции выхода объекта, возможно осуществлять маршрутизацию до этого объекта по графу ДС и определять моменты пересечения МО границы области.

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

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

а б

Рис.2. Позиции выхода объекта-здания

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

2. Когда позицию МО нельзя определить уверенно (например, на развилке дорог), АПРВ не выполняет позиционирование и сообщает устаревшие позицию и маршрутный путь (плохие динамические свойства АПРВ).

В этой связи для использования в ГИСММО был разработан маршрутный АПРВ, названный БРИТМ, и свободный от указанных недостатков.

Рис.3. Общая схема выполнения маршрутного АПРВ

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

Определение позиции МО происходит по следующему алгоритму.

Начало

Шаг 1. В окрестности местоположения МО выбрать сегменты дорожной сети, называемые сегментами-кандидатами. Проекции местоположения МО на сегменты-кандидаты дадут множество позиций-кандидатов.

Шаг 2. Для каждой позиции-кандидата рассчитать значение некоторой суммарной эвристической функции (СЭФ).

Шаг 3. Из всех позиций-кандидатов выбрать позицию с наибольшим значением СЭФ.

Конец

Работа СЭФ основана на оценке весов отдельных эвристических функций (ЭФ), которые рассчитываются на основе некоторых эмпирических пра-

вил, называемых эвристиками (принятый англоязычный термин — heuristics). Примеры таких эвристик: эвристика расстояния (выбираем сегмент, который ближе), эвристика направления движения (вероятнее сегмент, параллельный движению МО), топологическая эвристика (вероятнее позиции-кандидаты, которые можно соединить с предыдущими позициями). В АПРВ БРИТМ СЭФ Н() рассчитывается по формуле: Н = /сгЯь где Н — значение г-й ЭФ, значения которой лежат в диапазоне [-1...1], ki — удельный весовой коэффициент г-й эвристики. Каждая ЭФ Hi формализует соответствующую эвристику.

Одной из собенностей АПРВ БРИТМ является реализация топологической ЭФ, которая учитывает способность алгоритма корректировать маршрутный путь МО.

Коррекция маршрутного пути алгоритмом БРИТМ. Алгоритм способен корректировать ошибки построения маршрутного пути МО в реальном времени. Это позволяет АПРВ достичь эффективности оффлайновых АП по

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

\..> •• свойства. Работа АПРВ с ле"

а ■■ коррекцией пути показана

г ' на рис. 4. Ошибка пози-

, ционирования (рис. 4 а) не

¡j,. •**"*"/ приводит к отмене построения всего маршрут-

• в ного пути МО. Алгоритм

а - в сложной ситуации алгоритмом ошибочно выбран верхний сегмент Отменяет Предыдущие ре-6 - алгоритмом выбран нижний сегмент, путь скорректирован зуЛЬТЭТЫ ПОЗИЦИОНИрОВЗ-

в - становится очевидной верность выбора нижнего сегмента НИЯ И удаляет пеправИЛЬ-

Рис.4. Коррекция маршрутного пути ную часть построенного

ранее пути (рис. 4 б).

Коррекция пути в АПРВ БРИТМ основана на модифицированном алгоритме Дейкстры, названном DijkstraMod. Этот алгоритм соединяет новую позициюро МО с одной из позиций текущего маршрутного путир/-рп (рис. 5).

Таким образом, обновлённый маршрутный путь может быть продолжением старого, если DijkstraMod соединяет р„ с pi (рис. 5 а), либо часть старого пути удаляется, как ошибочная, если DijkstraMod соединил рп с позицией, отличной от pi (рис. 5 б, рис. 5 в, рис. 5 г). Алгоритм Дейкстры в данном случае не подходит, поскольку ближайшая позиция, входящая в путь, не обязательно последняя верная позиция пути (например, р7 на рис. 5 в). Поэтому алгоритм DijkstraMod для вершин, соответствующих позициям маршрутного пути, вводит штрафные веса {penalty), которые «удлиняют» растояние до этих вершин. Размер штрафа устанавливается равным расстоянию от вершины до последней позиции пути /;,, измеренному вдоль пути.

PiU

а - исходный путь продлевается без удаления части исходного пути

б - из исходного пути удаляется р,

в - из исходного пути удаляется р,

г - из исходного пути удаляются

Рь Р2, Рз

Ро

а

6

в

Рис.5. Коррекция пути в соответствии с алгоритмом DijkstraMocl

Исследование эффективности ЛПРВ БРИТМ. Для оценки количества глобальных ошибок позиционирования предложен показатель QR-Giobai = NCm/NTu!, где NCor — количество треков, для которых маршрутный путь построен успешно, NTo, — общее количество обработанных треков.

Прежде чем вводить показатель эффективности АПРВ, характеризующий его динамические свойства, сделаем несколько пояснений. Интервалом отставания L(t) обозначим расстояние между истинной позицией МО на пути и позицией, рассчитанной АПРВ, в момент времени t. Поскольку на перекрёстках L(t), как правило, монотонно возрастает при движении мимо перекрёстка, а при покидании перекрёстка резко уменьшается до нуля, то имеет смысл рассчитывать пиковые интерваты отставания LP, которые представляют собой локальные максимумы L(t). Суммарным пиковым интервалом отставания LPSum обозначим сумму всех пиковых интервалов отставания, полученных для одного трека МО. Очевидно, что величина LPSum будет определяться не только свойствами АПРВ, но и длиной трека. Поэтому для подсчёта интегрального показателя нужно усреднять LPs,m. Поскольку экспериментально была выявлена линейная корреляция между LPSlim и количеством перекрёстков в пути, в качестве итогового показателя эффективности АПРВ предложен усреднённый пиковый интервал отставания LPAvg, который равен сумме всех пиковых интервалов отставания (по всем трекам), делённой на количество пройденных перекрёстков (также по всем трекам).

Численный эксперимент проведён на реальных треках МО. Данные взяты из проекта «Spar раа farten» и содержат треки частных автомобилей в г. Ольборг (Дания) и его окрестностях (всего более 1500 треков). Поскольку отсутствует информация о реальных маршрутах МО, не представляется возможным оценить абсолютное значение Q^Giobai- Поэтому за эталон маршрутных путей были взяты пути, рассчитанные АПРВ БРИТМ. После чего функция коррекции пути в алгоритме БРИТМ была заменена на ЭФ из маршрутного АП Брилингайте (обозначим полученный алгоритм как Б*) и был измерен параметр 6я-е/оы Для алгоритма Б* относительно алгоритма БРИТМ. Для алгоритма Б* варьировался параметр величины зоны перекрёстка (CR), ис-

пользуемый в ЭФ алгоритма Брилингайте (в оригинальном алгоритме Бри-лингайте CR = 30 м).

Результаты исследований приведены в табл. 1. Можно сделать вывод, что алгоритм коррекции маршрутного пути значительно улучшил показатель LPM.S с 10-70 м/пере-крёсток (Б*) до 2,8 м/перекрёсток (БРИТМ). При этом, из тех треков, на которых предложенный АПРВ БРИТМ удачно построил маршрутный путь, для более 15% треков (QR-Ghbai < 0,85) алгоритм Б* не смог выполнить построение маршрутного пути. Если же уменьшить CR до 1 м (этим практически исключив влияние эвристики зоны перекрёстка), то LPAVg для алгоритма Б* уменьшается до приемлемой величины в 4,6 м, но Qr.gim падает до 0,75. Этим подтверждается более высокая эффективность предложенного АПРВ БРИТМ по обоим показателям QR-Global И LPAvg.

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

Поскольку для управления данными в ГИСММО используются универсальные СУБД, возникает проблема эффективного поиска ПД, т.к. многие из таких СУБД не предоставляют встроенных средств для построения пространственных индексов. Описаны результаты исследования нескольких методов индексирования ПД, реализуемые на основе стандартных индексов, использующих В-деревья и присутствующих практически во всех СУБД. Под управлением СУБД Microsoft SQL Server 2000/2005 были реализованы методы независимых индексов, Z-индексирования и XZ-индексирования.

При реализации методов Z-индексирования и XZ-индексирования возникает задача получения квадрантного разбиения области пространства (рис. 6) с заданным ограничением на количество квадрантов Nmax и минимальной ошибкой аппроксимации <т = 1 — S/^Sq, где S — площадь объекта, — суммарная площадь квадрантов, которыми представлен объект. Известен алгоритм рекурсивного разбиения (РА) с ограничением глубины рекурсии, но он не дает оптимального разбиения. Предложен жадный эвристический алгоритм (ЭА) разбиения области на квадранты, который тоже не оптимален, но даёт меньшую ошибку аппроксимации, чем РА.

Процесс разбиения области в ЭА регулируется эвристической функцией H(q), которая определяет, какой квадрант в текущем разбиении нужно дро-

Таблица 1. Показатели эффективности алгоритмов БРИТМ и Б*_

Алгоритм LpAvgl м/пере- крёсток QR-Chbal

БРИТМ 2,8±0,8 1

Б* (СД= 1 м) 4,6±0,8 0,75±0,12

Б* (СД= 5 м) 10,5±0,7 0,76±0,10

Б* (CR= 15 м) 26,7±1,3 0,82±0,08

Б* (Сй=30 м) 50,5±2,6 0,83±0,08

Б* (CR=45 м) 70,1 ±5,2 0,84±0,08

Б*(CR=60 м) 81,6±6,0 0,81±0,06

бить в следующую очередь. Входными параметрами алгоритма являются: Л^тах — максимально допустимое число квадрантов в разбиении; ЯесЬ — прямоугольная область, которую необходимо разбить на квадранты. Выходным параметром алгоритма является — список квадрантов.

Начало

Шаг 1. Для квадранта с\ установить максимальный размер, равный размеру всего пространства.

Шаг 2. Поместить ц в цНн1. Шаг 3. Если длина (¡Их! равна Л'„и,, то перейти на Конец.

Шаг 4. Если в нет квадрантов, которые можно разбить без переполнения (¡Н.ч1, то перейти на Конец.

Шаг 5. Выбрать из (¡4x1 квадрант q с максимальным значением Н(ц).

Шаг 6. Разбить <у на подквадранты и поместить полученные подквадранты, которые пересекают область Лес/, в д/иЛ

Таблица 2. Ошибка аппроксимации ст для РА и ЭА

Рис.6. Пример оптимального разбиения прямоугольной области на квадранты, ./Чпах=10

Шаг 7. Перейти на Шаг 3.

Конец

//(¡^рассчитывает площадь уменьшаемого пространства при разбиении квадранта, отнесенную к числу квадрантов, на которое увеличится разбиение: Н(д)=с{3/(М5Ж—\). Для каждого квадранта подсчитывается число под-

квадрантов Ытс, на которое нужно разбить исходный квадрант до достижения первого «удачного» разбиения (приводящего к уменьшению ошибки). Например, для квадранта 1 (рис. 6) Л^„с=6, а для квадранта 2 Л^,с=2. Также подсчитывается само это уменьшение с!Б (в абсолютных единицах площади). Но при этом не должно превышать разницу между текущим количеством квадрантов и максимальным (условие переполнения Если несколько квадрантов имеют одинаковое значение Н(ц), то выбор происходит по максимальной площади пустого пространства квадранта: 8етр0,=5д-Б(дгЯес1), где Я,, — площадь квадранта, 8(цгЛес() — площадь пересечения квадранта и разбиваемой области.

Показано, что для квадрантов, которые пересекаются границей области вертикально (как квадранты 2 и 3 на рис. 6) или горизонтально (как квадрант 1), величина Ы5ис зависит от величины зазора между границей области и внешней границей квадранта (зазор соответствует пустому пространству квадранта). Если нормировать сторону квадранта единицей и принять ¿1 — величина зазора, то можно получить, что Ышс=2/-2и'{'1)-2, где 1Ь(сГ) — позиция

/V а, РА а, ЭА

4 3,5 2,4

6 2,8 1,2

8 2,7 0,9

400 0,035 0,019

600 0,024 0,012

800 0,015 0,009

первого единичного бита в двоичном представлении d (например, /Ь(0.1101)=1; /¿>(0.001 )=3), При этом dS=Sql2lb, где S,,— площадь квадранта.

Для угловых квадрантов в качестве d берется максимальная величина зазора.

Для разных значений Nam была подсчитана средняя ошибка аппроксимации ст, получающаяся в результате работы рекурсивного алгоритма (РА) и предложенного эвристического алгоритма (ЭА). Величина NmM была взята из двух диапазонов: от 4 до 8 (характерные значения при построении Z-индексов объектов) и от 400 до 800 (характерные значения при разбиении области запроса для формирования интервалов Z-значений). ЭА дает меньшую (от 1,5 до 3 раз) ошибку аппроксимации (табл. 2). Эта разница существенна для небольших значений N„m, когда само значение ошибки достаточно велико.

Пределы применимости алгоритмов индексирования ПД в универсальной СУБД определены экспериментально на примере выполнения оконных запросов к модельным данным. Варьировался размер объектов (3 размера), их количество (3 варианта), а также размер окна запроса (в условиях эксперимента равный селективности запроса, 5 вариантов). Результаты эксперимента для объектов среднего размера приведены на рис.7. Они показывают, что при селективности запроса меньше 1% и при количестве объектов, исчисляющихся сотнями тысяч, применение XZ-индексирования оправдано при использовании непространственной СУБД.

В пятой главе рассматривается разработанное ПО инструментальных ГИСММО и апробация этих систем при решении практических задач.

Подробно описано ПО трёх реализованных инструментальных ГИСММО: инструментальной ГИСММО МиДА, инструментальной ГИСММО для персональной навигации и инструментальной ГИСММО для оказания LBS-услуг. Основное внимание уделяется набору библиотек ArdaMap, являющемуся основой этого ПО. Библиотеки ArdaMap реализованы на платформе .NET (использованы в инструментальных ГИСММО МиДА и оказания LBS-услуг) и перенесены на платформу .NET Compact Framework (использованы в инструментальной ГИСММО для персональной навигации). ПО указанных инструментальных ГИСММО внедрено в составе следующих систем.

Система мониторинга и диспетчерского управления городского пассажирского транспорта (разработана ООО «ИНКОМ»). ПО инструментальной ГИСММО МиДА было использовано в этой системе для обеспечения

600 тысяч объектов ;

0,01% 0,04% 0,20% 1,00% 5,00% Размер окна [селективность! запроса

I — ♦ — Незэвис индекс * Х2- индекс " 2- индекс!

Рис. 7. Зависимость времени выполнения оконного запроса от размера окна запроса

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

Платформа мобильных сервисов «Б^еатБрт» (университет г. Ольборга, Дания). Инструментальная ГИСММО ддя персональной навигации была использована в составе клиентского ПО этой платформы, инструментальная ГИСММО для оказания ЫЗБ-услуг — в составе серверного ПО. Внедрённое ПО позволило выполнять функции предсказания маршрута движения водителя и использования предсказанного маршрута в качестве контекста мобильных иЗБ-услуг.

Корпоративная геоинформационпая система управления производством «Магистраль-Восток» (функционирует в ОАО «Востокгазпром», ОАО «Томскгазпром»), В состав подсистемы работы с картами, технологическими схемами, мнемосхемами этой системы были интегрированы программные модули ГИСММО по управлению пространственными данными.

Результаты внедрений подтверждают эффективность разработанных моделей, алгоритмов и программ ГИСММО и их практическую значимость.

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

В приложение вынесены акты о внедрении полученных результатов.

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

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

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

2. Разработана концепция построения ГИСММО, предложена концептуальная структура ГИСММО и структуры инструментальных ГИСММО.

3. Разработана модель ДС, учитывающая особенности задач позиционирования и обработки маршрутов МО в реальном времени.

4. Предложены показатели эффективности маршрутных АПРВ.

5. Разработаны алгоритмы функционирования ГИСММО. К ним, в первую очередь, относятся алгоритмы позиционирования МО в ДС и алгоритмы индексирования ПД. В результате исследований, проведённых на модельных и реальных данных, показана высокая эффективность этих алгоритмов.

6. Разработано ПО трёх инструментальных ГИСММО, позволяющих решать различные классы задач. Разработанные инструментальные ГИСММО используются для создания проблемно-ориентированных систем.

7. Осуществлено внедрение разработанного алгоритмического и программного обеспечения инструментальных ГИСММО на трёх предприятиях (получены соответствующие акты) и в университете г. Ольборга (Дания). Ре-

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

Основные публикации по теме диссертации

Статьи, опубликованные в изданиях из перечня ВАК:

1. Шестаков Н.А. Индексирование пространственных данных в СУБД Microsoft SQL Server 2000 //Известия Томского политехнического университета.—2006,—Т.309,—№4.-С. 157-162

2. Шестаков Н.А. и др. Расширение контекста мобильного сервиса маршрутом пользователя в платформе StreaniSpin /Н.А. Шестаков, C.S. Jensen //Известия Томского политехнического университета.—2009.—Т.314.—№5— С. 170-175

Статьи, тезисы докладов на междунар. и всеросс. конференциях:

3. Шестаков Н.А. и др. Исследование эффективности запросов к СУБД SQL Server в задачах пространственной индексации / Н.А. Шестаков, Н.Г. Марков //Доклады II Всероссийской научно-практической конференции студентов и молодых учёных «Молодежь и современные информационные технологии». — Томск: Изд-во. ТПУ. — 2004. — С.37-39

4. Шестаков Н.А. Исследование методов индексирования пространственных данных в среде СУБД SQL Server // Современные техника и технологии: Труды X Юбилейной Международной научно-практической конференции студентов, аспирантов и молодых учёных. — Томск: Изд-во ТПУ. — 2004. — Т. 2. — С. 226-228

5. Shestakov N.A. Increase of Efficiency of Spatial Z-Indexing Algorithms //Сборник докладов XI Международной научно-практической конференции студентов, аспирантов и молодых ученых «Современные техника и технологии».— Томск: Изд-во ТПУ. — 2005. — С. 136-138

6. Designing production management systems of oil-and-gas holding companies /R.V. Kovin, M.V. Kopnov, A.V. Kudinov, N.G. Markov, E.A. Miroslini-chenko, P.M. Ostrast, V.S. Sherstnyov, N.A. Shestakov// Proceedings of KORUS 2004: 8th Korea-Russia International Symposium of Science and Technology. — Tomsk: TPU. — 2004 — V. I. — pp. 91-95

7. Корпоративная система управления производством нефтегазодобывающих предприятий /Ковин Р.В., Копнов М.В., Кудинов А.В., Марков Н.Г., Мирошниченко Е.А., Острасть П.М., Шерстнев B.C., Шестаков Н.А. // Проблемы и перспективы развития минерально-сырьевого комплекса и производительных сил Томской области: Материалы научно-практической конференции. — Новосибирск: Изд-во СНИИГГиМС, 2004. — С. 260-261

8. Шестаков Н.А. Обобщенная схема хранения хронологических данных в Microsoft SQL Server 2000 //Тез. докл. конференции «Технологии Microsoft в теории и практике программирования». — Новосибирск: Изд-во ИСИ. — 2006. — С. 142-144

9. Шестаков Н.А. Схема хранения хронологических данных в СУБД Microsoft SQL Server 2000 // Современные техника и технологии: Труды XII

Международной научно-практической конференции студентов и молодых ученых — Томск: Изд-во ТПУ. — 2006 — Т. 2. — С. 220-222

lO.Shestakov N.A. et al. Access of Spatíal Data Using Microsoft SQL Server 2000 / N.A.Shestakov, N.G.Markov // Proceedings of 25th Urban Data Management Symposium (UDMS'06). — Aalborg, Denmark. — 2006. —pp. 301-312

П.Шестаков H.A. Индексирование пространственных данных методом R-дерева в СУБД Microsoft SQL Server 2005 //Материалы VI всероссийской научной конференции молодых ученых «Наука. Технологии. Инновации». — Новосибирск: Изд-во НГТУ,— Часть 1. — 2006. — С. 176-178

12.Шестаков Н.А. Использование предсказанного маршрута пользователя в качестве контекста для сервисов местоположения // Молодежь и современные информационные технологии: Сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. — Томск: Изд-во СПб Графике. — 2008. — С. 488-489

13.Шестаков Н.А. Использование открытых источников геоданных на примере сервиса OpenStreetMap // Молодежь и современные информационные технологии: Сборник трудов VII Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. — Томск. — 25-27 февраля 2009. — Томск: Изд-во СПБ Графике. — 2009 — Т. 2. — С. 285-286

14.Шестаков Н.А. Предсказание маршрута пользователя: реализация в системе «StreamSpin» //Сборник трудов VI Всероссийской научно-практической конференции «Технологии Microsoft в теории и практике программирования». — Томск: Изд-во ТПУ. — 2009. — С. 115-117

15.Шестаков Н.А. Проект картографического сервиса как платформы для создания мобильных сервисов //Сборник трудов XV Международной научно-практической конференции студентов, аспирантов и молодых учёных «Современные техника и технологии».— Томск: Изд-во ТПУ.— 2009. — Т.2. — С.326-328

16.Шестаков Н.А. Особенности решения задач на графах дорожных сетей с запретами поворотов //Сборник трудов XVI Международной научно-практической конференции студентов, аспирантов и молодых учёных «Современные техника и технологии».— Томск: Изд-во ТПУ.— 2010. — Т.2 — С.412-414

П.Шестаков Н.А. Разработка картографического сервера в составе картографического сервиса «ARDA» //Сборник трудов VII Всероссийской научно-практической конференции «Технологии Microsoft в теории и практике программирования». — Томск: Изд-во ТПУ.— 2010. — С. 63-65

Подгисано к печати 18.11.2010. Формат 60x84/16. Бумага «Снегурочка».

Печать XEROX. Усл.печ.л. 1,14. Уч.-изд.л. 0,96. _Заказ 1950-10 Тираж 100 экз._

Национальный исследовательский Томский политехнический университет Система менеджмента качества Томского политехнического университета сертифицирована NATIONAL QUALITY ASSURANCE по стандарту ISO 9001:2008

ISO 9001 lllllllllll

гадгаьствоwiny. 634050, г. Томск, пр. Ленина, 30 Тел./факс: 8(3822)56-35-35, vww.tpu.ru

ВВЕДЕНИЕ.

ГЛАВА 1. ПРОБЛЕМА МОНИТОРИНГА МОБИЛЬНЫХ ОБЪЕКТОВ В ДОРОЖНОЙ СЕТИ.

1.1. Классификация систем мониторинга мобильных объектов и решаемые с их помощью задачи.

1.1.1. Автомобильные навигационные системы.

1.1.2. Системы мониторинга и диспетчеризации автотранспорта.

1.1.3. ЬВ8-услуги.

1.1.4. Интеллектуальные транспортные системы.

1.2. ГИС для решения транспортных задач.

1.3. Модели дорожных сетей.

1.4. Необходимость разработки ГИС мониторинга МО.

1.5. Теоретический базис ГИС и СММО. Состояние проблемы.

1.5.1. Пространственные базы данных и пространственные СУБД.

1.5.2. Индексирование пространственных данных.

1.5.3. Базы данных мобильных объектов.

1.5.4. Алгоритмы позиционирования МО.

1.6. Цель и задачи диссертационного исследования.

В последние годы, особенно с развёртыванием отечественной спутниковой навигационной системы ГЛОНАСС, наблюдается взрывное развитие технологий позиционирования объектов. Появляется всё больше доступных цифровых карт, дешевеет навигационное оборудование. Это даёт толчок к массовому распространению информационных систем, основанных на использовании данных о местоположениях мобильных объектов (МО), а также ведёт к появлению вокруг этих систем инфраструктуры сервисов, основанных на местоположении МО (location-based services или LBS-услуг). К таким системам относятся персональные автонавигаторы, работающие с одним МО, системы мониторинга и диспетчеризации автотранспорта (СМиДА), которые получают информацию о перемещениях многих МО, интернет-сервисы, собирающие данные о перемещениях большого числа МО («ТошТот», «Яндекс-Пробки», «Пробковорот», «СитиГИД» и другие). Активно развиваются интеллектуальные транспортные системы. Все эти классы систем можно отнести к категории систем мониторинга мобильных объектов (СММО), которые объединяет то, что МО перемещаются в дорожной сети

ДС).

Параллельно с развитием СММО идёт развитие геоинформационных систем (ГИС), традиционно решающих сложные и серьёзные задачи в области обработки пространственной информации, в том числе и данных о перемещениях МО. Универсальные ГИС, такие как ArcGIS или Maplnfo, обладают средствами, позволяющими решать сложные транспортные задачи, но для навигационных систем и СМиДА их функционал избыточен, скорость работы невысока, а стоимость слишком велика. Поэтому эти продукты занимают нишу, в которой от систем требуется сложный пространственный анализ и моделирование, но не требуется работа в реальном времени.

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

Таким образом, можно сделать вывод об актуальности разработки систем мониторинга МО, имеющих функционал «интеллектуальной» обработки данных о перемещениях МО в ДС, характерный для ГИС, но в то же время способных обрабатывать данные о местоположениях этих МО в реальном времени.

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

1. На основе анализа существующих СММО и универсальных ГИС определить набор функций ГИСММО и ряд требований к ней.

2. Разработать принципы построения и структуру ГИСММО.

3. Создать математическое обеспечение ГИСММО. Решение этой задачи предполагает анализ существующих моделей ДС, адаптацию и модификацию таких моделей под функционал ГИСММО, разработку алгоритмов обработки данных о перемещениях МО в ДС и алгоритмов выполнения запросов к пространственным базам данных (БД). Необходимо провести исследование эффективности предложенных алгоритмов.

4. Разработать программное обеспечение (ПО) ГИСММО с учётом имеющихся программных средств современных векторных ГИС и универсальных СУБД. Созданные в результате программные средства системы должны реализовать разработанные модели и алгоритмы и удовлетворять сформулированным принципам и структурным особенностям ГИСММО.

5. Апробировать ГИСММО путём создания на её основе инструментальных и проблемно-ориентированных систем, позволяющих решать практически значимые задачи.

Методы исследований. В работе использованы методы математического моделирования, теории графов, математической статистики, объектно-ориентированного проектирования ПО и проектирования БД.

Апробация работы. Основные результаты работы докладывались и обсуждались на II, VI и VII Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных «Молодёжь и современные информационные технологии» (Томск, 2004 г.; Томск, 2008 г.; Томск, 2009 г.), X, XI, XII, XV, XVI Международной научно-практической конференции студентов, аспирантов и молодых учёных «Современная техника и технологии» (Томск, 2004 г.; Томск, 2005 г.; Томск, 2006 г.; Томск, 2009 г.; Томск, 2010 г.), VII Международном российско-корейском симпозиуме по науке и технологиям KORUS'2004 (Томск, 2004 г.), VI Всероссийской научной конференции молодых ученых «Наука. Технологии. Инновации» (Новосибирск, 2006 г.), III, VI, VII Всероссийской конференции «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2006 г.; Томск, 2009 г.; Томск, 2010 г.), 25th Urban Data Management Symposmm (Дания, Ольборг, 2006 г.), Международной научно-практической конференции «Интеллектуальные информационно-телекоммуникационные системы для подвижных и труднодоступных объектов» (Томск, 2010 г.)

По результатам исследований опубликовано 17 работ, в том числе 16 статей (2 статьи в изданиях, рекомендованных ВАК).

Кратко изложим основное содержание работы.

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

На основе анализа функций современных универсальных ГИС и их структуры показано, что многие функции по анализу данных перемещений МО в ДС присутствуют в тех или иных ГИС-продуктах, но использовать такие продукты в качестве СММО зачастую затруднительно или невозможно.

Рассмотрены модели ДС, используемые в настоящее время, проанализирована возможность их применения в СММО. Проведён анализ существующих алгоритмов позиционирования МО в ДС. Рассмотрены методы и алгоритмы хранения и индексирования пространственных данных, которыми оперируют ГИС и СММО.

Сделан вывод об актуальности разработки некоторой СММО, в которой бы присутствовали более развитые функции, характерные для ГИС, но реализованные с учётом специфики задач мониторинга МО в ДС.

На основе результатов проведённого анализа проблемы мониторинга МО в ДС формулируются цель исследования и задачи, решаемые в диссертационной работе.

Вторая глава посвящена концепции создания ГИСММО.

Сформулированы основные требования к ГИСММО. На основе этих требований предложена концепция создания ГИСММО. Согласно этой концепции структура ГИСММО описывается на трёх уровнях абстракции: концептуальном, инструментальном и проблемно-ориентированном. Предложена концептуальная функциональная структура ГИСММО. На инструментальном уровне эта структура трансформируется в виде ряда структур инструментальных ГИСММО. Разные инструментальные ГИСММО имеют общий набор базовых функций, но различный набор функциональных модулей. Предложены и описаны структуры инструментальных ГИСММО МиДА, персональной автонавигации и для оказания LBS-услуг.

В третьей главе описаны разработанные модель ДС и алгоритм позиционирования МО в ДС в реальном времени. Проведено исследование эффективности предложенного алгоритма.

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

Дано определение позиционирования (англ. map-matching) МО в ДС. Позиционирование необходимо для того, чтобы перейти от географических координат МО к его координатам в ДС. Алгоритм, выполняющий такой переход, называется алгоритмом позиционирования (АП). Известные маршрутные АПРВ обладают определёнными недостатками: большим количеством глобальных ошибок позиционирования и плохими динамическими v свойствами.

В этой связи для использования в ГИСММО был разработан маршрутный АПРВ, названный БРИТМ, и свободный от указанных недостатков. Алгоритм способен корректировать ошибки построения маршрутного пути МО в реальном времени. Это позволяет АПРВ достичь эффективности оффлайновых АП по глобальным ошибкам позиционирования, при этом не ухудшая динамические свойства.

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

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

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

Поскольку для управления данными в ГИСММО используются универсальные СУБД, возникает проблема эффективного поиска ПД, т.к. многие из таких СУБД не предоставляют встроенных средств для построения пространственных индексов. Описаны результаты исследования нескольких методов индексирования ПД, реализуемые на основе стандартных индексов, использующих B-деревья и присутствующих практически во всех СУБД. Под управлением СУБД Microsoft SQL Server 2000/2005 были реализованы методы независимых индексов, Z-индексирования и XZ-индексирования.

При реализации методов Z-индексирования и XZ-индексирования возникает задача получения квадрантного разбиения области пространства с заданным ограничением на количество квадрантов и минимальной ошибкой аппроксимации. Известен алгоритм рекурсивного разбиения (РА) с ограничением глубины рекурсии, но он не дает оптимального разбиения. Предложен жадный эвристический алгоритм (ЭА) разбиения области на квадранты, который тоже не оптимален, но даёт меньшую ошибку аппроксимации, чем РА, что подтверждено численным экспериментом.

Пределы применимости алгоритмов индексирования ПД в универсальной СУБД определены экспериментально на примере выполнения оконных запросов к модельным данным. Варьировался размер объектов, их количество, а также размер окна запроса (в условиях эксперимента равный селективности запроса). Результаты эксперимента показали, что при селективности запроса меньше 1% и при количестве объектов, исчисляющихся сотнями тысяч, применение XZ-индексирования оправдано при использовании непространственной СУБД.

В пятой главе рассматривается разработанное ПО инструментальных ГИСММО и апробация этих систем при решении практических задач.

Подробно описано ПО трёх реализованных инструментальных ГИСММО: инструментальной ГИСММО МиДА, инструментальной ГИСММО для персональной автонавигации и инструментальной ГИСММО для оказания LBS-услуг. Основное внимание уделяется набору библиотек ArdaMap, являющемуся основой этого ПО. Библиотеки ArdaMap реализованы на платформе .NET (использованы в инструментальных ГИСММО МиДА и оказания LBS-услуг) и перенесены на платформу .NET Compact Framework (использованы в инструментальной ГИСММО для персональной автонавигации). ПО указанных инструментальных ГИСММО внедрено в составе следующих систем.

Система мониторинга и диспетчерского управления городского пассажирского транспорта (разработана ООО «ИНКОМ»), ПО инструментальной ГИСММО МиДА было использовано в этой системе для обеспечения функций контроля следования транспортного средства (ТС) по маршруту, оперативного предсказания времени прибытия ТС на остановки общественного транспорта, накопления статистики передвижений ТС по маршрутам и использования этой статистики для формирования отчётов.

Платформа мобильных сервисов «StreamSpin» (университет г. Ольборга, Дания). Инструментальная ГИСММО для персональной автонавигации была использована в составе клиентского ПО этой платформы, инструментальная ГИСММО для оказания LBS-услуг —• в составе серверного ПО. Внедрённое ПО позволило выполнять функции предсказания маршрута движения водителя и использования предсказанного маршрута в качестве контекста мобильных LBS-услуг.

Корпоративная геоинформационная система управления производством «Магистраль-Восток» (функционирует в ОАО «Востокгазпром», ОАО «Томскгазпром»). В состав подсистемы работы с картами, технологическими схемами, мнемосхемами этой системы были интегрированы программные модули ГИСММО по управлению пространственными данными.

Результаты внедрений подтверждают эффективность разработанных моделей, алгоритмов и программ ГИСММО и их практическую значимость.

Научную новизну полученных в работе результатов определяют:

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

2. Предложенные оригинальные показатели эффективности алгоритмов позиционирования МО в ДС в реальном времени.

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

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

Практическая ценность и реализация результатов работы.

Практически значимыми являются созданные модели, алгоритмы и программные средства, использованные в различных инструментальных и проблемно-ориентированных ГИСММО. Объем исходного кода разработанных программных средств составляет более 18 ООО строк на языке С# и Delphi. Разработанный набор библиотек ArdaMap, предназначенный для обработки данных перемещений МО в ДС в реальном времени, реализует предложенную модель ДС, маршрутный алгоритм позиционирования МО в ДС в реальном времени, средства хранения данных ДС в БД и средства импорта данных ДС. ArdaMap является важной составляющей инструментальных ГИСММО, реализованных на программных платформах .NET Compact Framework (внедрена в проекте StreamSpin на мобильных устройствах) и .NET (внедрена в системе мониторинга и диспетчерского управления городского пассажирского транспорта в ООО «ИНКОМ» и в серверной части StreamSpin). Модули обработки и хранения ПД, реализующие алгоритмы выполнения пространственных запросов и написанные на языке Delphi, внедрены в подсистеме работы с картами и технологическими схемами корпоративной геоинформационной системы управления производством «Магистраль-Восток» в ОАО «Востокгазпром» и ОАО «Томскгазпром».

Результаты внедрения подтверждены 3 актами о внедрении.

Личный вклад:

1. Постановка задач диссертационного исследования и разработка концепции ГИСММО, постановки задачи исследования эффективности предложенных автором алгоритмов выполнены совместно с Н.Г.Марковым.

2. Концептуальная структура ГИСММО и структуры И-ГИСММО разработаны автором совместно с Н.Г.Марковым.

3. Модель ДС и реализующие её алгоритмы разработаны автором.

4. Ядро инструментальных ГИСММО (в том числе алгоритм позиционирования МО в ДС), алгоритмы хранения и индексирования ПД, схемы базы данных ДС и маршрутов разработаны автором.

5. Численные эксперименты по исследованию эффективности алгоритма квадрантного разбиения, алгоритмов пространственного индексирования и алгоритма позиционирования МО в ДС проведены автором.

6. Корпоративная ГИС управления производством «Магистраль-Восток», в состав которой было включено ПО ГИСММО в части хранения и обработки ПД, разработана сотрудниками лаборатории геоинформационных систем Института кибернетики ТПУ Кудиновым А.В, Ковиным Р.В., Мирошниченко Е.А. и др. Интеграция модулей пространственного индексирования ГИСММО с ГИС «Магистраль-Восток» была осуществлена автором.

7. Платформа StreamSpin была разработана в исследовательском центре DAISY (университет Ольборга, Дания). Интеграция разработанного ПО инструментальных ГИСММО с платформой осуществлена автором совместно с аспирантом R. Wind и профессором C.S Jensen этого университета.

8. Система мониторинга и диспетчерского управления городского пассажирского транспорта была разработана ООО «ИНКОМ». Интеграция ПО инструментальной ГИСММО для мониторинга и диспетчеризации автотранспорта (ГИСММО МиДА) с этой системой была осуществлена при участии автора.

Основные положения, выносимые на защиту:

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

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

3. Разработанный алгоритм квадрантного разбиения области пространства (используемый в методах Z- и XZ-индексирования пространственных объектов) обеспечивает меньшую ошибку аппроксимации при заданном ограничении количества квадрантов, чем аналогичные алгоритмы.

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

5. Разработанное алгоритмическое и программное обеспечение инструментальных ГИСММО позволяет создавать проблемно-ориентированные ГИСММО и тем самым эффективно решать ряд практически значимых задач по обработке данных о перемещениях МО в ДС.

Автор выражает глубокую благодарность научному руководителю — доктору технических наук, профессору, Заслуженному деятелю науки РФ Н.Г.Маркову за помощь в подготовке диссертационной работы. Автор также благодарит за плодотворные дискуссии доцентов кафедры Вычислительной техники Е.А. Мирошниченко, Р.В. Ковина, A.B. Кудинова, программистов кафедры М.В. Копнова, С.А. Богдана, профессора университета г. Ольборга (Дания) К. Йенсена, аспиранта университета г. Ольборга Р.Винда.

5.8. Основные результаты и выводы по главе

1. Предложена структура ПО трёх инструментальных ГИСММО: инструментальной ГИСММО мониторинга и диспетчеризации автотранспорта, инструментальной ГИСММО для персональной автонавигации и инструментальной ГИСММО для оказания LBS-услуг.

2. Разработано ПО инструментальной ГИСММО мониторинга и диспетчеризации автотранспорта на платформе .NET.

3. Разработано ПО инструментальной ГИСММО для персональной автонавигации на платформе .NET Compact Framework.

4. Разработано ПО инструментальной ГИСММО для оказания LBS-услуг на платформе .NET.

5. ПО инструментальной ГИСММО для мониторинга и диспетчеризации автотранспорта внедрено в Систему мониторинга и диспетчерского управления городского пассажирского транспорта (разработана ООО «ИНКОМ»).

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

7. Осуществлено внедрение ПО инструментальной ГИСММО для оказания LBS-услуг в серверную часть платформы StreamSpin.

8. Осуществлено внедрение программных модулей инструментальной ГИСММО для мониторинга и диспетчеризации автотранспорта, управляющих пространственными данными, в корпоративную геоинформационную систему управления производством «Магистраль-Восток» (функционирует в ОАО «Востокгазпром», ОАО «Томскгазпром»).

9. Предложена архитектура проблемно-ориентированной ГИСММО для мониторинга и диспетчеризации автотранспорта, реализуемой на основе инструментальной ГИСММО для мониторинга и диспетчеризации автотранспорта.

10. Результаты этих внедрений и апробации разработанного ПО подтверждают эффективность предложенной концепции построения ГИСММО и разработанных моделей ДС, алгоритмов и программ.

ЗАКЛЮЧЕНИЕ

Диссертационная работа посвящена созданию алгоритмического и программного обеспечения ГИС для мониторинга МО в ДС. В ходе выполнения диссертационной работы были получены следующие основные научные и практические результаты.

1. Проведён анализ проблемы мониторинга МО в ДС, решаемой с помощью существующих СММО и ГИС. По результатам анализа поставлена цель создания системы мониторинга в реальном времени мобильных объектов в дорожной сети, в которой бы присутствовали «интеллектуальные» функции, характерные для ГИС. Сформулированы общие требования к такой системе, названной ГИСММО.

2. Разработана концепция построения ГИСММО, предложена концептуальная структура ГИСММО и структуры ряда инструментальных ГИСММО.

3. Разработана модель ДС, учитывающая особенности задач позиционирования и обработки маршрутов МО в реальном времени.

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

5. Разработаны алгоритмы функционирования ГИСММО. К ним, в первую очередь, относятся оригинальный маршрутный алгоритм позиционирования мобильных объектов в дорожной сети и оригинальные алгоритмы индексирования пространственных данных. В результате исследований, проведённых на модельных и реальных данных, показана высокая эффективность этих алгоритмов.

6. Разработано ПО трёх инструментальных ГИСММО, позволяющих решать классы задач персональной автонавигации, мониторинга и диспетчеризации автотранспорта и оказания ЬВ Б-услуг. Разработанные инструментальные ГИСММО используются для создания проблемно-ориентированных систем и функционируют на платформах .NET и .NET Compact Framework.

7. Разработана архитектура проблемно-ориентированной ГИСММО для диспетчеризации автомобилей такси. Предложена структура платформы мобильных LBS-услуг как проблемно-ориентированной ГИСММО.

8. Осуществлено внедрение разработанного алгоритмического и программного обеспечения инструментальных ГИСММО на трёх предприятиях (ОАО «Востокгазпром», ОАО «Томскгазпром» и ООО «ИНКОМ»), о чём получены соответствующие акты, и в университете г. Ольборга (Дания). Результаты внедрения подтверждают эффективность разработанной модели дорожной сети и созданных алгоритмов и программ для индексирования пространственных данных и мониторинга мобильных объектов в дорожной сети.

1. Андрианов В.Ю. Применение геоинформационных систем на транспорте // Информационные системы. — №4, 2008. — С. 42-45

2. Блинкин М. Транспорт в городе, удобном для жизни. // Публичные лекции Полит.ру (стенограмма лекции). — URL: http://www.polit.ru/lectures/2010/10/14/transportprint.html. Дата обращения: 20.10.2010

3. Вислобоков В. GIS-Lab: Руководство по PostGIS: 4.5. Построение индексов — URL: http://postgresql.ru.net/postgis/ch045.html. Дата обращения: 10.10.2010

4. Геоинформационные системы и технологии: учебник /Р.В. Ковин, Н.Г. Марков. — Томск: Изд-во ТПУ, 2009. — 267 С.

5. Добрин П.С. и др. Автомобильные навигационные системы: классификация устройств, обзор состояния мирового и российского рынка. /П.С. Добрин, К.П. Чачин// Мобильные телекоммуникации. — №8, 2008 г. — С. 20-24.

6. Ехлаков Ю.П. и др. Принципы построения Web-ориентированной ГИС промышленного предприятия / Ю.П. Ехлаков, О.И. Жуковский, Н.Б. Рыбалов // Известия Томского политехнического университета. — 2006. — Т. 309, №7. —С. 146-152.

7. Жуковский О.И. и др. Архитектура корпоративной WEB-ориентированной ГИС / О.И. Жуковский, Н.Б. Рыбалов // Доклады Томского государственного университета систем управления и радиоэлектроники. — 2008. — №2 (18), ч.2. — С.65-69.

8. Интеллектуальная транспортная система города Дубны //URL: http://its-dubna.ru. Дата обращения: 10.10.2010

9. Корпоративная система управления производством нефтегазодобывающих предприятий / Р.В. Ковин, М.В. Копнов, A.B. Кудинов, Н.Г. Марков, Е.А. Мирошниченко, П.М. Острасть, B.C. Шерстнев, H.A.

10. Шестаков // Проблемы и перспективы развития минерально-сырьевого комплекса и производительных сил Томской области: Материалы научно-практической конференции. — Н.: СНИИГГиМС, 2004. — С. 260-261

11. Официальный сайт компании «Garmin»//URL: www.garmin.ru. Дата обращения: 10.10.2010

12. Официальный сайт компании «MiTAC»//URL: www.miohome.ru. Дата обращения: 10.10.2010

13. Официальный сайт компании «TomTom»//URL: www.tomtom.com. Дата обращения:10.10.2010

14. Официальный сайт проекта «OpenStreetMap — свободная вики-карта мира»//1ЖЬ: www.openstreetmap.org. Дата обращения: 10.10.2010

15. Ривкин М.Н. Тенденции развития универсальных коммерческих СУБД. // URL: http://citforum.ru/database/articles/trends. Дата обращения: 10.10.2010

16. Российская Интеллектуальная Транспортная Система // URL: http://www. fcp-pbdd.ru/techobdd/experience/detail.php ?BLOCK=8 8&ID=14947. Дата обращения: 10.10.2010

17. Сарычев Д.С. и др. Создание информационных моделей автомобильных дорог и информационной системы на их основе /Д.С. Сарычев, С.П. Крысин, A.B. Скворцов // Вестник Томского государственного университета. — 2003. —Т.280.— С.362-369

18. Спутниковый мониторинг транспорта (материал из Википедии) //URL: http://m.wikipedia.org/wild/CnyTHHKOBbiiiMOHHTopiiHrTpaHcnopTa. Дата обращения: 10.10.2010

19. Теория вероятностей и математическая статистика: Учебник для вузов. /А. Андронов, Е. Копытов, Л. Гринглаз. — М.: Юнити-Дана. — 2010. — 464 с.

20. Уоррен Г., мл. Алгоритмические трюки для программистов. — пер. с англ. М.: «Вильяме». — 2003

21. Шестаков Н.А. и др. Расширение контекста мобильного сервиса маршрутом пользователя в платформе StreamSpin /Н.А. Шестаков, C.S. Jensen //Известия Томского политехнического университета.—2009.—Т.314.—№5— С. 170-175

22. Шестаков Н.А. Индексирование пространственных данных в СУБД Microsoft SQL Server 2000. //Известия Томского политехнического университета. — 2006. — Т.309. — №4. — С. 157-162

23. Томск: Изд-во СПб Графике. — 2008. — С. 488^89

24. Шестаков Н.А. Обобщенная схема хранения хронологических данных в Microsoft SQL Server 2000 //Тез. докл. конференции «Технологии Microsoft в теории и практике программирования». — Новосибирск: Изд-во ИСИ. — 2006.1. С. 142-144

25. Шестаков Н.А. Предсказание маршрута пользователя: реализация в системе «StreamSpin» //Сборник трудов VI Всероссийской научно-практической конференции «Технологии Microsoft в теории и практике программирования». — Томск: Изд-во ТПУ. — 2009. — С. 115-117

26. Ashbrook D. Learning significant locations and predicting user movement with GPS / D. Ashbrook, T. Starner// Proc. of the 6th International Symposium on Wearable Computers. — 2002. — P.101—109.

27. Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, В. The R*-tree: An efficient and robust access method for points and rectangles. // Proceedings of ACM SIGMOD International Conference on Management of Data. —1990. — pp. 322-331

28. Dijkstra, E.W. A note on two problems in connexion with graphs //Numerische Mathematik. — №1, 1959. — p.269-271

29. Doran J. An Approach to Automatic Problem-Solving //Machine Intelligence. — №1,1967. — p.105-127

30. Faloutsos C., Kamel I. Beyond uniformity and independence: Analysis of R-trees using the concept of fractal dimension. //Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. — 1994. —pp. 4-13.

31. Faloutsos C., Kamel I. Hilbert R-Tree: An Improved R-Tree Using Fractals. // Department of CS, University of Maryland, Technical Research Report TR-93-19.

32. Faloutsos C., Kamel I. Packed R-Trees Using Fractals. // Department of CS, University of Maryland, Technical Research Report TR-93-1.

33. Faloutsos C., Rong Y. DOT: A Spatial Access Method Using Fractals.th

34. Proceeding of the 7 IEEE International Conference on Data Engineering, pp. 152159

35. Gaîede V. et al. Multidimensional Access Methods / V. Gaede, О. Gunter// ACM Computing Surveys. — Vol. 30, №2. — 1998. —p. 170-231

36. Gazis D. Traffic Theory. //Springer. — 2002. — 280 p.

37. Goldberg A. et al. Reach for A*: Efficient Point-to-Point Shortest Path Algorithms / A. Goldberg, H. Kaplan, R. Werneck // Workshop on Algorithm Engineering & Experiments. — 2006. — pp. 129-143.

38. Google Static Maps API: Руководство разработчика API статических карт // URL: http://code.google.com/intl/ru/apis/maps/documentation/staticmaps. Дата обращения : 10.10.2010.

39. Greenfield J. Matching GPS Observations to Locations on a Digital Map // New Jersey Institute of Technology, Newark, NJ 07102 (Technical Report). — URL: http://www.njtide.org/reports/TRB2002-greenfeld.pdf. Дата обращения: 10.10.2010

40. Grush В. The Case Against Map-Matching / B. Grush // European Journal of Navigation. — 2008. — V.6 (3). — pp. 2-5

41. Guting R.H. An Introduction to Spatial Database Systems // Special Issue on Spatial Database Systems of the VLDB Journal. — 1994. — vol. 3, № 4. — pp. 357-399

42. Guttman A., R-trees: A dynamic index structure for spatial searching. //Proceedings of the ACM SIGMOD International Conference on Management of Data. — 1984. — pp. 47-54.

43. Hart P.E. et al. A Formal Basis for the Heuristic Determination of Minimum Cost Paths /Р. E. Hart, N. J. Nilsson, B. Raphael //IEEE Transactions on System Science and Cybernetics. — Vol. 4(2). —1968. — pp. 100-107

44. Henrich A., Six H., Widmayer P. The LSD tree: spatial access to multidimensional point and non-point objects. // Proceedings of the Fifteenth International Conference on Very Large Data Bases. — 1989. — pp. 45-53

45. Hornammer M. et al. Spatial indexing With A Scale Dimension / M. Hornammer, M. Freeston // URL: http://alexandria.sdc.ucsb.edu /~freeston/papers/ssd99.pdf. Дата обращения: 10.10.2010

46. Jensen С. S. TransDB — GPS Data Management with Applications in Collective Transport / C. S. Jensen, D.Tiesyte // Proc of the 1st International Workshop on Computational Transportation Science. — Dublin, Ireland. — 2008.

47. Jiang J. Modelling Turning Restrictions In Traffic Network For Vehicle Navigation System / J. Jiang, G. Han, J. Chen. // Proc. of Symposium on Geospatial Theory, Processing and Applications. — 2002.

48. Kriegel H.-P., Brinkhoff T., Schneider R. Efficient Spatial Query Processing in Geographic Database Systems // IEEE Data Eng. Bull. — 1993. — vol. 16(3).—pp. 10-15

49. Krumm J. A Markov Model for Driver Route Prediction / J. Krumm // • Society of Automotive Engineers (SAE) World Congress. — 2008

50. Krumm J. Map Matching with Travel Time Constraints / Krumm et al. // SAE World Congress. —2007

51. Krumm J. Route Prediction from Trip Observations / J. Krumm, J. Froehlich// Society of Automotive Engineers (SAE). — 2008

52. Küpper, A. Location-based services: fundamentals and operation // John Wiley & Sons Ltd. — 2005 — 386 p.

53. Li Xiang et al. A trajectory-oriented carriageway-based road network data model, part 1: Background / Li Xiang, Lin Hui.//Geo-Spatial Information Science. — Vol. 9„ No 1 — 2006. — pp. 65-70

54. Maplnfo MapX. //URL: http://www.esti-map.ru/ ITporpaMMHoeo6ecne4eHHe/PBMapInfo/MapInfoMapX/tabid/54/Default.aspx. Дата обращения: 10.10.2010

55. MapServer: официальный сайт //URL: http://www.mapserver.org. Дата обращения: 10.10.2010

56. Miller H.J. et al. Geographic Information Systems for Transportation — Principles and Applications / H.J.Miller, S.Shaw // Oxford University Press, USA. — 480 p.

57. OpenGIS Simple Features Implementation Specification For SQL Rev. 1.1, // Open GIS Consortium. — 1999. — OpenGIS Project Document 99-049

58. OpenGIS Web Map Service (WMS) Implementation Specification //URL: http://www.opengeospatial.org/standards/wms. Дата обращения: 10.10.2010

59. OpenLayers: официальный сайт //URL: http://openlayers.org. Дата обращения: 10.10.2010

60. Oracle Spatial User's Guide and Reference. Release 9.0.1. Spatial Concepts. — URL: http://download.oracle.com/docs/html/A8880501/sdointr.htm. Дата обращения: 10.10.2010

61. Oracle Spatial User's Guide and Reference. Release 9.2. Linear Referencing System. — URL: http://download.oracle.com/docs/html/A8880501/sdointr.htm. Дата обращения: 10.10.2010

62. Papadias D., Theodoridis T. Spatial Relations, Minimum Bounding Rectangles and Spatial Data Structures. // International Journal of Geographical Information Science. — Vol. 11, Issue 2. — 1997. — pp. 111-138

63. Pereira F.C. An Off line Map-Matching Algorithm for Incomplete Map Databases / F.C. Pereira, H. Costa, N.M. Pereira // European Transport Research Review. —2009.—VI (3).— P. 107—124.

64. Quddus M. A general map matching algorithm for transport telematics applications / Quddus, Noland, Ochieng, Zhao // GPS Solutions. — 2003.— pp.157—167.

65. Quddus M. The Effects of Navigation Sensors and Spatial Road Network Data Quality on the Performance of Map Matching Algorithms / Quddus, Noland, Ochieng. // Geoinformatica. — 2009. — V.13(l). — P.85—108.

66. Quddus. Current map-matching algorithms for transport applications: State—of—the art and future research directions / Quddus, Ochieng, Noland // ScienceDirect. Transportation Research Part C. — 2007. — V.15. — P.312—328.

67. Route Ware RW NetServer 3: официальный сайт // URL: http://www.routeware.dk/rwnetsei*ver/rwnetserver.php. Дата обращения: 10.10.2010

68. Saltenis S et al. Indexing of the Current and Near-Future Positions of Moving Objects/ S. Saltenis, C.S. Jensen // Encyclopedia of Database Systems. — Springer, 2008. — pp. 1458-1463

69. Sanders P. Engineering Fast Route Planning Algorithms / P.Sanders, D.Schultes // Lecture Notes on Computer Science. WEA. —2007. — V.4525. — P.23—36.

70. Scheider S. et al. Specifying Essential Features of Street Networks / S. Scheider, D. Schulz// COSIT'07 Proceedings of the 8th international conference on Spatial information theory. — 2007. — pp. 169-185

71. Schrader С. Reacting In Real Time Using Historical and Real-Time Information in Forecasting Link Travel Times: Thesis / Schrader Chris. — Princeton University, 2003. — 136 p.

72. Seeger В., Kriegel H.-P. The buddy-tree: An efficient and robust access method for spatial data base systems. // Proceedings of the Sixteenth International Conference on Very Large Data Bases. — 1990. — p. 590-601.

73. Sellis Т., Roussopoulos N., Faloutsos C. The R+ Tree A Dynamic Index For Multidimensional Objects. // Proc. 13th International Conference on VLDB. — 1987. —p. 507-518

74. Shestakov N.A. et al. Access of Spatial Data Using Microsoft SQL Server 2000 / N.A.Shestakov, N.G.Markov // Proceedings of 25th Urban Data Management Symposium (UDMS'06). — Aalborg, Denmark. — 2006. — pp. 301-312

75. Sommarskog Е. Arrays and Lists in SQL Server // URL: http://www.sommarskog.se/arrays-in-sql.html. Дата обращения: 10.10.2010

76. Speicys L. et al. Enabling Location-based Services — Multi-Graph Representation of Transportation Networks / L. Speicys, C.S. Jensen// Geoinformatica. — Vol. 12 Issue 2 . — 2008. — pp. 219-253

77. StreamSpin: официальный сайт // URL: www.streamspin.com. Дата обращения: 10.10.2010

78. Sung Т. К. A Path Planning Method for Road Networks Having Turn Prohibitions / Т. K. Sung, S. Y. Myoung // Journal of Intelligent Transportation Systems. — 2001. — V6 (02). — P.125—139.

79. The Official Microsoft ASP.NET Site //URL: http://www.asp.net. Дата обращения: 10.10.2010

80. The Official Microsoft IIS Site //URL: http://www.iis.net. Дата обращения: 10.10.2010

81. Towards an Analisys of Range Query Performance in Spatial Data Structures / Pagel B.-U., Six H.-W., Toben H., Widmayer P. // Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. — 1993. — pp. 214-221

82. Tradisauskas N. Map Matching / Tradisauskas N., Jensen C.S. // Encyclopedia of Database Systems. — Springer, 2008. — pp. 1692-1696.

83. Tradisauskas N. Map Matching for Intelligent Speed Adaptation / N. Tradisauskas, J. Juhl, H. Lahrmann, C.S. Jensen // Intelligent Transport Systems. — Vol.3(l). — 2009. — pp. 57-66

84. Winter M. et al. A Modular Neural Network Approach to Improve Map -Matched GPS Positioning / M.Winter, G.Taylor // Lecture Notes in Computer Science. Web and Wireless Geographical Information Systems. — 2006. — Vol. 4295. —pp.76-89.

85. Wunderlich Karl E. et al. Link Travel Time Prediction for Decentralized Route Guidance Architectures / Karl E. Wunderlich, David E. Kaufman, Robert L. Smith // IEEE Transactions On Intelligent Transportation Systems. — 2000. — Vol. 1(1).—pp. 4-14

86. Yongjian Y. Self-adaptive Fuzzy Decision Map Matching Algorithm Based on GIS Buffer in LCS / Yongjian Yang, Xu Yang, Chijun Zhang //IFIP International Federation for Information Processing . — 2008. — V. 258. — pp. 487—494.

87. Yue et al. Road Network Model for Vehicle Navigation using Traffic Direction Approach / Yang Yue, Anthony Gar-On Yeh, Qingquan Li // Lecture Notes in Geoinformation and Cartography. — Springer, 2008. — pp. 613-629