Алгоритмическое и программное обеспечение геоинформационной системы для мониторинга мобильных объектов в дорожной сети тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Шестаков, Николай Александрович

• Шестаков, Николай Александрович
• кандидат технических наук
• 2010

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

ВВЕДЕНИЕ.

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

Список литературы диссертационного исследования кандидат технических наук Шестаков, Николай Александрович, 2010 год

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