Дипломная работа - Анализ, разработка и программа реализации алгоритмов поиска и оптимизации маршрутов движения в улично-дорожной сети города

Подождите немного. Документ загружается.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Инженерно-экономический факультет

Кафедра вычислительной техники и информационных технологий

ДОПУСТИТЬ К ЗАЩИТЕ В ГАК

Зав. кафедрой, профессор, д.т.н.

А. Г. Пимонов

« » 2007 г.

Лопатин Артем Алексеевич

РАЗРАБОТКА, АНАЛИЗ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

АЛГОРИТМОВ ПОИСКА И ОПТИМИЗАЦИИ МАРШРУТОВ

ДВИЖЕНИЯ В УЛИЧНО-ДОРОЖНОЙ СЕТИ ГОРОДА

Дипломная работа

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

профессор, д.т.н. А. Г. Пимонов

Исполнитель,

студ. гр. ПИ021 А. А. Лопатин

Электронная версия дипломной работы помещена в электронную библиотеку

Файл:

Администратор:

Кемерово – 2007

РЕФЕРАТ

Дипломная работа, 35 стр., 24 рис., 18 источников, 1 приложение.

АЛГОРИТМЫ НА ГРАФАХ, ПОИСК ПУТЕЙ, ОПТИМИЗАЦИЯ, БАЗА ДАННЫХ,

ПРОГРАММИРОВАНИЕ, ГЕОИНФОРМАЦИОННАЯ СИСТЕМА.

Объект исследования – алгоритмы поиска путей на графах.

Цель работы – создание геоинформационной системы поиска и оптимизации

маршрутов движения в улично-дорожной сети города.

Методы и технологии разработки – анализ алгоритмов поиска на графах, систем-

ный анализ улично-дорожной сети города; технология автоматизированных баз данных,

визуальное и объектно-ориентированное программирование.

Результаты работы – выполнен обзор существующих программных реализаций

геоинформационных систем, проведен анализ алгоритмов поиска на графах и способов

представления графов и информационных системах.

Разработана геоинформационная система поиска и оптимизации маршрутов дви-

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

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

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

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

второй – подсистеме поиска и оптимизации маршрутов движения реализованы следую-

щие алгоритмы: поиск в глубину, поиск в ширину, алгоритм Дейкстры, алгоритм обхода

препятствий, генетический алгоритм.

Область применения – разработанная геоинформационная система может быть

использована для поиска и оптимизации маршрутов движения (в том числе и многопунк-

товых) в улично-дорожной сети города; для поиска допустимых и оптимальных маршру-

тов передвижения в сети горных выработок в случае возникновения аварийных ситуаций;

для оптимизации маршрутов авиаперелетов, пассажирских и грузовых автоперевозок.

Дальнейшее расширение возможностей геоинформационной системы может быть

осуществлено за счет реализации работы с результатами поиска (формирование и экспорт

в различные форматы найденных маршрутов движения, расчет затрат на горюче-

смазочные материалы и техническое обслуживание транспортных средств при постоян-

ных автоперевозках по найденным маршрутам), добавления дополнительных атрибутов

дорог и формирования на их основе новых критериев поиска (качество дорожного

полотна и количество полос движения; удобство, время и средняя скорость

передвижения).

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.......................................................................................................................................4

1 ГЕОИНФОРМАЦИОННЫЕ СИСТЕМЫ ...................................................................................5

1.1 Основы геоинформатики ..................................................................................................5

1.2 Классификации ..................................................................................................................6

1.3 Области применения .........................................................................................................7

1.4 Обзор существующих программных реализаций ..........................................................8

1.4.1 ГИС-редактор «City Explorer».................................................................................8

1.4.2 Городская информационная система ДубльГИС ..................................................8

1.4.3 ГИС «Открытый город»...........................................................................................9

1.4.4 Электронная справочная система города Калуги..................................................9

1.4.5 Справочник метро «PMetro» .................................................................................10

2 АЛГОРИТМЫ НА ГРАФАХ......................................................................................................11

2.1 Основы теории графов ....................................................................................................11

2.2 Маршруты, пути, циклы, расстояния ............................................................................12

2.3 Представление графов в информационных системах..................................................13

2.4 Поиск на графах, кратчайшие пути ...............................................................................14

2.4.1 Поиск в глубину......................................................................................................14

2.4.2 Поиск в ширину......................................................................................................15

2.4.3 Кратчайшие пути ....................................................................................................16

2.4.4 Алгоритм Дейкстры поиска кратчайшего пути...................................................17

2.4.5 Алгоритм обхода препятствий А* ........................................................................17

2.5 Генетический алгоритм...................................................................................................18

2.5.1 Естественный отбор в природе .............................................................................18

2.5.2 Понятие и особенности генетического алгоритма..............................................19

2.5.3 Алгоритм решения задачи коммивояжера...........................................................20

3 ГЕОИНФОРМАЦИОННАЯ СИСТЕМА ПОИСКА И ОПТИМИЗАЦИИ МАРШРУТОВ..23

3.1 Среда и средства разработки..........................................................................................23

3.2 Структура данных ...........................................................................................................23

3.3 Программная реализация алгоритмов на графах .........................................................25

3.4 Основные возможности ..................................................................................................26

3.4.1 Начало работы ........................................................................................................26

3.4.2 Создание нового проекта.......................................................................................27

3.4.3 Работа с картой .......................................................................................................28

3.4.4 Поиск оптимального маршрута движения...........................................................30

3.4.5 Поиск оптимального многопунктового маршрута..............................................30

3.5 Перспективы развития и использования.......................................................................31

3.5.1 Работа с результатами поиска ...............................................................................31

3.5.2 Дополнительные критерии оптимизации.............................................................31

3.5.3 Различные области использования графов ..........................................................32

ЗАКЛЮЧЕНИЕ...............................................................................................................................33

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ .....................................................................34

ПРИЛОЖЕНИЕ А СПИСОК ФАЙЛОВ НА КОМПАКТ-ДИСКЕ ............................................35

ВВЕДЕНИЕ

Дорожная отрасль является одной из важнейших отраслей экономики любой про-

мышленно развитой страны. Недаром автомобильные дороги называются «кровеносной

системой» любого государства. Они играют огромную социально-экономическую роль в

жизни современного общества. В Российской Федерации в силу огромной пространствен-

ной протяженности территории транспортные издержки существенно больше среднеми-

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

время и очень рентабельными сооружениями. Известно, что каждый рубль, вложенный в

автомобильные дороги, в перспективе многократно (в 3–5 раз) возвращается в различных

других отраслях экономики за счет снижения транспортных (логистических) издержек,

снижения аварийности, повышения подвижности населения [1].

Низкий уровень развития сети автомобильных дорог России является существен-

ным сдерживающим фактором роста рыночной экономики, при которой автомобильный

транспорт играет доминирующую роль [2]. К сожалению, строительство дорог идет не-

достаточно высокими темпами, и дорожно-транспортные сети города не справляются с

постоянно возрастающей на них нагрузкой. Зачастую строительство дорог ограничено не

только финансовыми рамками и строительными возможностями, но и архитектурой горо-

да. Последнее делает невозможным строительство новых или расширение имеющихся до-

рог в плотно застроенных или исторических местах города. Поэтому высока актуальность

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

дорожно-транспортную сеть города и определять оптимальные с различных точек зрения

маршруты движения.

Таким образом, основной целью данной работы является создание геоинформаци-

онной системы поиска и оптимизации маршрутов движения в улично-дорожной сети го-

рода.

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

1) выполнить обзор существующих программных реализаций геоинформационных

систем;

2) проанализировать алгоритмы поиска на графах и способы представления графов

в информационных системах;

3) провести системный анализ улично-дорожной сети города;

4) спроектировать базу данных для хранения информации об основных элементах

улично-дорожной сети города;

5) разработать программный комплекс, позволяющий создавать и изменять схемы

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

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

Дипломная работа состоит из введения, трех глав, заключения, списка использо-

ванных источников и приложения.

Первая глава работы посвящена общим вопросам геоинформатики и анализу суще-

ствующих программных реализаций геоинформационных систем.

Во второй главе рассмотрены теоретические основы дипломной работы. Проанали-

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

ных системах.

Третья глава является описанием спроектированной базы данных и разработанной

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

дорожной сети города.

1 ГЕОИНФОРМАЦИОННЫЕ СИСТЕМЫ

1.1 Основы геоинформатики

Геоинформационная система (ГИС) – это информационная система, предназна-

ченная для сбора, хранения, обработки, отображения и распространения данных, а также

получения на их основе новой информации и знаний о пространственно-

координированных объектах и явлениях [3]. Основной особенностью ГИС, отличающей

ее от других информационных систем, является то, что все моделируемые в ГИС объекты

и явления имеют пространственную привязку, позволяющую анализировать их во взаимо-

связи с другими пространственно-определенными объектами. ГИС кардинально отлича-

ются от большинства других информационных систем тем, что вся информация в них

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

вые знания.

Первые ГИС появились в 60-х годах ХХ века в Канаде, США и Швеции. Они име-

ли существенные программные и технические ограничения. В течение следующих 20 лет,

вплоть до 80-х годов, проходило становление геоинформатики как науки, отрабатывались

методологические подходы к созданию ГИС, создавался математический аппарат, разра-

батывались модели данных и алгоритмы их обработки. В 80-х годах начинается стреми-

тельное распространение компьютерной техники с одновременным увеличением быстро-

действия и возможностей. Всё это приводит к переходу геоинформатики на новый уро-

вень [2, 3].

Первоначально термин ГИС расшифровывался как географическая информацион-

ная система. Однако сейчас такой термин считается неверным, так как в настоящее время

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

мики.

Главным отличием электронных карт ГИС от бумажных карт является то, что

в ГИС карта не является обычной статической картинкой. Каждый условный знак, изо-

браженный на карте ГИС, соответствует некоторому объекту, который можно

проанализировать, например, получить дополнительную (неграфическую) информацию из

базы данных (БД). То есть, одной из базовых функций ГИС является получение

информации по выбранному на карте объекту. Так, например, в ГИС, выбрав здание на

карте города, можно получить детальную информацию о нем: адрес, этажность и пр.

В основе ГИС лежит концепция послойной организации пространственных данных:

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

ев образует карту. Деление объектов на слои производится так, чтобы объекты одного

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

пологическую структуру и размерность (описание объекта точками, линиями или полиго-

нами). Большое количество слоев создавать нежелательно: нет смысла создавать отдель-

ные слои для дорог с различным типом покрытия, лучше сделать один слой с дорогами, и

у каждого объекта (дороги), указать тип покрытия. В ГИС выделяют несколько основных

слоев, например:

1) Слой рек. На карте города реки обычно представляются в виде многоугольников,

на крупномасштабных картах (картах области, страны) – с помощью ломаных.

2) Слой деревьев. Деревья можно представить в ГИС в виде точечных объектов или

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

3) Слой автомобильных дорог. В зависимости от решаемых задач автомобильные

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

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

ных слоя для осевых линий дорог и для проезжих частей.

4) Слой зданий. Здания представляются в виде многоугольников, описывающих

контур здания на уровне земли. В атрибутах зданий обычно указывают тип здания (жилое,

промышленное, коммерческое), адрес, высоту, количество этажей и пр.

Деление данных на слои позволяет работать в ГИС только с теми данными, кото-

рые необходимы для решения поставленных задач. В самом простом случае можно «вы-

ключить» те слои, которые нам не нужны, и увидеть на карте оставшиеся [1]. Таким обра-

зом, изображение на карте ГИС всегда соответствует некоторому набору данных, храня-

щемуся в БД. При этом всегда можно перейти от условного знака на экране к объекту в

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

рому критерию объект в БД, можно посмотреть его расположение на карте.

1.2 Классификации

В настоящее время геоинформационными системами называют различные инфор-

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

ко классификаций, позволяющих более полно понять сущность ГИС [3].

1) Виды ГИС по пространственному охвату:

• глобальные (планетарные);

• субконтинентальные;

• межнациональные;

• национальные (государственные);

• региональные (областные, краевые, республиканские);

• субрегиональные (районы внутри регионов);

• локальные (городские);

• ультралокальные (отдельные ограниченные территории).

2) Виды ГИС по используемой модели данных:

• векторные ГИС работают с различными моделями данных, а также иногда с

триангуляционными моделями поверхностей;

• растровые ГИС позволяют работать только с растровыми моделями данных;

• гибридные совмещают в себе возможности векторных и растровых ГИС.

3) Виды ГИС по компьютерной платформе, на базе которой они функционируют:

• Настольные ГИС. К этой категории относятся большинство известных ГИС.

Как правило, используемые в них данные сохраняются в локальных файлах.

• Клиент-серверные ГИС. В этих системах пространственные данные хранят-

ся полностью в базе данных сервера. Этот сервер обычно является высоко-

уровневой надстройкой над некоторой промышленной системой управления

базами данных (СУБД типа Microsoft SQL Server, Oracle, DB2, Sybase и др.).

• ГИС для интернета. Такие системы бывают двух видов: а) самостоятельные

программы, обеспечивающее полные функции HTTP-сервера, либо

б) наборы программных компонент (обычно ActiveX-объектов), которые мо-

гут быть интегрированы в существующий Html-код и произвольным обра-

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

кацию карт в интернете, а второй подход более гибок.

Следует заметить, что термином ГИС называются очень многие и разные инфор-

мационные системы. Этим словом описывают как собственно прикладные программы для

различных отраслей, так и сами инструментальные ГИС, на основе которых создаются

конкретные отраслевые системы.

1.3 Области применения

ГИС применяются в различных областях деятельности человека и помогают ре-

шать разнообразные задачи [1, 3]:

• управление (федеральное, региональное, муниципальное, корпоративное);

• землепользование (земельные кадастры, инвентаризация земельных участ-

ков, межевание земель);

• управление недвижимостью (кадастр недвижимости);

• градостроительство (генеральные планы развития, дежурные планы, плани-

рование развития);

• архитектура (проектирование генеральных планов, ландшафтное проекти-

рование);

• бизнес (оценка инвестиций и планирование бизнеса);

• инженерные сети (управление и эксплуатация городских, поселковых и кор-

поративных инженерных сетей: электрических, водопроводных, тепловых,

газовых, телефонных и др.);

• инженерно-геодезические изыскания (ввод и обработка данных геодезиче-

ских изысканий, уравнивание геодезических сетей);

• инженерно-геологические изыскания (ввод и обработка данных по

геологическим колонкам);

• геология (моделирование геологических пластов; обработка данных бурения,

сейсморазведки);

• картография (составление географических и топографических карт);

• проектирование и строительство (проектирование автомобильных и желез-

ных дорог, генеральных планов, электрических и трубопроводных сетей);

• экстренные службы (диспетчеризация выездов милиции, пожарных, скорой

медицинской помощи, службы спасения);

• ГИБДД (управление инженерным обустройством автомобильных дорог:

светофорами, знаками и др.; диспетчеризация выездов);

• транспорт (управление и эксплуатация автомобильных и железных дорог;

управление речными, морскими и воздушными перевозками);

• логистика (планирование и управление транспортными перевозками);

• оборона (планирование войсковых операций, тыловое обеспечение);

• чрезвычайные ситуации (анализ и предсказание чрезвычайных ситуаций,

планирование и осуществление мероприятий по ликвидации последствий);

• экология (оценка и прогнозирование воздействия на окружающую среду);

• метеорология (предсказание погоды, управление сетью метеорологических

пунктов и станций);

• недропользование (управление месторождениями полезных ископаемых);

• природопользование (управление природными ресурсами);

• нефтегазовая отрасль (управление нефтегазодобычей, управление промы-

словыми площадками, управление магистральными трубопроводами);

• демография и статистика (демографический и статистический анализ);

• навигация (навигация на местности и выбор маршрутов движения).

1.4 Обзор существующих программных реализаций

1.4.1 ГИС-редактор «City Explorer»

City Explorer представляет собой профессиональную полнофункциональную ГИС

для создания, редактирования и анализа цифровых карт. Система включает в себя редак-

тор векторной графики, СУБД, редактор условных знаков (для точек, линий и полигонов).

Также среди ее стандартных возможностей – полный набор функций для редактирования

карт и нанесения объектов, различные виды поиска, маршрутизатор, обращение к внеш-

ним БД, встроенный язык VBA, возможность подключения растровых данных и разработ-

ки своих модулей расширения на основе СОМ технологий [4].

Возможности редактирования:

• определение прав отдельных пользователей;

• создание собственных слоев картографических данных;

• редактирование метаданных;

• редактирование объектов данных;

• создание расширений функциональности системы и дополнительных моду-

лей.

City Explorer является платным программным обеспечением (ПО), стоимость одной

лицензии – 16 800 рублей.

1.4.2 Городская информационная система ДубльГИС

Рис. 1.1 – Панорамная карта

г. Кемерово в ДубльГИС

Рис. 1.2 – Схема маршрута

движения в

Ду

бльГИ

Информационная система ДубльГИС – современная замена бумажным картам и

справочным службам. Все версии ДубльГИС выходят ежемесячно и распространяются

бесплатно. Электронные карты городов ДубльГИС

создаются профессиональной картографической

службой по актуальным спутниковым снимкам

(данные дистанционного зондирования спутников

Iconos и Quickbird). Для уточнения карты проводится

объезд территории города [

5] (рис. 1.1).

Возможности ДубльГИС позволяют:

• найти на карте любой из объектов: дом

по адресу, улицу, жилой массив, район,

остановку городского транспорта,

железнодорожную станцию, станцию

метро;

• получить информацию о находящихся в

здании организациях;

• измерить расстояние между объектами

или оценить длину определенного

маршрута;

• распечатать фрагменты карты вместе с

информацией о выбранных зданиях;

• делать собственные пометки на плане

города.

Раздел «Транспорт» в справочниках ДубльГИС

включает информацию по коммерческим и муници-

пальным маршрутам наземного транспорта (автобусы,

троллейбусы, трамваи, маршрутные такси) (рис. 1.2).

Возможности:

• просмотр схемы маршрутов на карте города;

• поиск остановки городского транспорта на карте и просмотр соответствую-

щих номеров маршрутов;

• поиск вариантов проезда между двумя выбранными остановками с учетом

пересадок и пеших переходов между близкорасположенными остановками.

1.4.3 ГИС «Открытый город»

Рис. 1.3 – Карта г. Кемерово

в ГИС «Открытый город»

Рис. 1.4 – Обзор дополнитель-

ной информации об объекте

Открытый город – электронная схема

нескольких городов России, объединенная с

телефонным справочником организаций. Информация

в справочнике, а также схематическая информация

обновляется ежемесячно. Программа распространяется

бесплатно [

6].

Возможности программы «Открытый город»

совпадают с возможностями рассмотренной ранее

программы ДубльГИС. Существуют лишь

незначительные различия в интерфейсе. В ГИС

«Открытый город» заложены карты следующих

городов: Кемерово (рис. 1.3), Новокузнецк, Прокопьевск, Междуреченск, Осинники,

Мыски, Новосибирск, Красноярск, Абакан, Канск, Барнаул, Томск, Омск, Комсомольск-

на-Амуре, Усть-Каменогорск.

1.4.4 Электронная справочная система города Калуги

Эта система имеет много общего с рассмотренными выше программами: Дубль-

ГИС и «Открытый город», однако она значительно превосходит их по предоставляемым

возможностям. К основным положительным моментам электронной справочной системы

города Калуги можно отнести:

• расположение объектов на схеме по

тематическим слоям;

• поиск домов по адресу, предприятий –

по наименованию;

• возможность выбора объекта на карте и

получения информации о нем (рис. 1.4);

• вычисление расстояний и площадей

(рис. 1.5);

• экспорт полученной информации

в MS Excel;

• определение кратчайших транспортных

маршрутов [

7].

Предоставляемые этой программой

возможности позволяют осуществлять с ее помощью

следующие мероприятия:

• контроль за состоянием зданий и

памятников архитектуры;

• контроль за транспортной системой го-

рода;

Рис. 1.5 – Выделение района и

вычисление его площади

• мониторинг социально-экономической обстановки в городе в динамическом

режиме;

• анализ чрезвычайных ситуаций и катастроф;

• экологический мониторинг территории города.

1.4.5 Справочник метро «PMetro»

PMetro – это справочник метро Москвы и других городов. Он отображает схему

метро города (а для некоторых городов и схему электропоездов) и позволяет найти крат-

чайшие пути между станциями [8] (рис. 1.6).

Рис. 1.6 – Кратчайший путь

Отличительные особенности программы:

• наличие схемы метро более 120

городов мира;

• возможность масштабирования,

сглаживания изображения;

• возможность выбора

обязательных и нежелательных

в пути станций;

• наличие дополнительной

информации о наземном

транспорте, проходящем рядом со

станцией метро;

• возможность поиска пути

движения с учетом маршрутов

наземного транспорта (автобусов,

троллейбусов, трамваев,

маршрутных такси), в том числе и

с пересадками между различными

видами транспорта;

Рис. 1.7 – 3D-схема Московского

метрополитена

• отображение зоны покрытия

сотовых операторов;

• наличие многоязыковой

поддержки и транслитерации;

• доступность всех данных для

редактирования пользователем;

• наличие 3D-схемы (рис. 1.7).