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

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

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

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

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

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

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

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