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

1 Разработка, анализ и программная реализация алгоритмов поиска и оптимизации маршрутов движения в улично-дорожной сети города Научный руководитель: профессор, д. т. н.Пимонов Александр Григорьевич Исполнитель: студ. гр. ПИ021Лопатин Артем Алексеевич Дипломная работа

2 2 Цель и задачи работы Цель – создание геоинформационной системы поиска и оптимизации маршрутов движения в улично-дорожной сети города Задачи Выполнить обзор существующих программных реализаций Проанализировать алгоритмы поиска на графах и способы представления графов Провести системный анализ улично-дорожной сети города Спроектировать базу данных Разработать программный комплекс

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

4 4 Геоинформационная система Геоинформационная система (ГИС) – это информационная система, работающая с пространственно- координированными объектами и явлениями

5 5 Применение ГИС Градостроительство, архитектура Землепользование, управление недвижимостью Инженерно-геодезические и инженерно- геологические изыскания Планирование и управление транспортными перевозками Навигация, поиск маршрутов движения

6 6 Программные реализации ГИС ГИС-редактор «City Explorer» Городская информационная система ДубльГИС Городская информационная система «Открытый город» Электронная справочная система г. Калуги Справочник метро «PMetro»

7 7 Представление графов в информационных системах Матрица инциденций Матрица смежности Список пар, соответствующих ребрам Список смежных вершин

8 8 Методы и алгоритмы поиска Генетический алгоритм Поиск в глубину Поиск в ширину Алгоритм Дейкстры Алгоритм обхода препятствий Генетический алгоритм

9 9 ГИС ПИОМ

10 10 Структура базы данных Таблицы БД: Cross – перекрестки NodeBegin – начальные узлы улиц NodeEnd – конечные узлы улиц StreetCaption – названия улиц Street – отрезки улиц

11 11 Редактор схем

12 12 Подсистема поиска и оптимизации Поиск в глубину Поиск в ширину Алгоритм Дейкстры Алгоритм обхода препятствий

13 13 Поиск оптимального маршрута

14 14 Оптимальный многопунктовый маршрут

15 15 Перспективы развития и использования Работа с результатами поиска: формирование и экспорт отчетов, расчет дополнительных данных Добавление дополнительных атрибутов и формирование новых критериев поиска Различные области использования графов

16 16 Результаты работы Разработана ГИС ПИОМ Выступление на VI Всероссийской научно- практической конференции Публикация в сборнике научных трудов «Инновационные недра Кузбасса. IT-технологии» Выступление на 52-й научно-практической конференции КузГТУ Публикация в сборнике докладов студентов и аспирантов КузГТУ

17 Разработка, анализ и программная реализация алгоритмов поиска и оптимизации маршрутов движения в улично-дорожной сети города Дипломная работа Ваши вопросы Научный руководитель: профессор, д.т.н.А. Г. Пимонов Исполнитель: студ. гр. ПИ021А. А. Лопатин