Разработка, анализ и программная реализация алгоритмов поиска и оптимизации маршрутов движения в улично-дорожной сети города Научный руководитель: профессор, д. т. н.Пимонов Александр Григорьевич Исполнитель: студ. гр. ПИ021Лопатин Артем Алексеевич Дипломная работа
2 Цель и задачи работы Цель – создание геоинформационной системы поиска и оптимизации маршрутов движения в улично-дорожной сети города Задачи Выполнить обзор существующих программных реализаций Проанализировать алгоритмы поиска на графах и способы представления графов Провести системный анализ улично-дорожной сети города Спроектировать базу данных Разработать программный комплекс
3 Актуальность разработки высокая стоимость строительства; медленная скорость строительства; высокая плотность застройки города; наличие культурно-исторических достопримечательностей. Проблемы строительства новых дорог в городе:
4 Геоинформационная система Геоинформационная система (ГИС) – это информационная система, работающая с пространственно- координированными объектами и явлениями
5 Применение ГИС Градостроительство, архитектура Землепользование, управление недвижимостью Инженерно-геодезические и инженерно- геологические изыскания Планирование и управление транспортными перевозками Навигация, поиск маршрутов движения
6 Программные реализации ГИС ГИС-редактор «City Explorer» Городская информационная система ДубльГИС Городская информационная система «Открытый город» Электронная справочная система г. Калуги Справочник метро «PMetro»
7 Представление графов в информационных системах Матрица инциденций Матрица смежности Список пар, соответствующих ребрам Список смежных вершин
8 Методы и алгоритмы поиска Генетический алгоритм Поиск в глубину Поиск в ширину Алгоритм Дейкстры Алгоритм обхода препятствий Генетический алгоритм
9 ГИС ПИОМ
10 Структура базы данных Таблицы БД: Cross – перекрестки NodeBegin – начальные узлы улиц NodeEnd – конечные узлы улиц StreetCaption – названия улиц Street – отрезки улиц
11 Редактор схем
12 Подсистема поиска и оптимизации Поиск в глубину Поиск в ширину Алгоритм Дейкстры Алгоритм обхода препятствий
13 Поиск оптимального маршрута
14 Оптимальный многопунктовый маршрут
15 Перспективы развития и использования Работа с результатами поиска: формирование и экспорт отчетов, расчет дополнительных данных Добавление дополнительных атрибутов и формирование новых критериев поиска Различные области использования графов
16 Результаты работы Разработана ГИС ПИОМ Выступление на VI Всероссийской научно- практической конференции Публикация в сборнике научных трудов «Инновационные недра Кузбасса. IT-технологии» Выступление на 52-й научно-практической конференции КузГТУ Публикация в сборнике докладов студентов и аспирантов КузГТУ
Разработка, анализ и программная реализация алгоритмов поиска и оптимизации маршрутов движения в улично-дорожной сети города Дипломная работа Ваши вопросы Научный руководитель: профессор, д.т.н.А. Г. Пимонов Исполнитель: студ. гр. ПИ021А. А. Лопатин