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

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

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

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

Самым простым из направлений дальнейшего развития ГИС ПИОМ является уве-

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

расчет дополнительных параметров, формирование отчетов и их экспорт в различные

форматы для дальнейшей обработки.

Например, для водителей-экспедиторов и бухгалтеров можно на основании длины

найденного маршрута и заданных норм расхода топлива рассчитывать объем горючего,

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

же рассчитать и финансовые затраты на него. Если указать месячное количество поездок

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

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

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

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

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

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

тия и применения ГИС ПИОМ. Можно рассмотреть несколько вариантов дополнительных

атрибутов.

1) Качество дорожного полотна и количество полос движения. При определении

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

роге с покрытием или нет, но и по возможности оценить качество дорожного покрытия. В

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

покрытия не всегда находится на должном уровне. С определением количества полос

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

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

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

создают еще одну левую полосу движения специально для поворота налево. Таким обра-

зом, на основании этих атрибутов определяется такой маршрут движения, длина которого

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

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

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

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

крытием не желателен.

2) Удобство передвижения по участку дороги. Этот параметр можно оценить толь-

ко экспертным методом. Не секрет, что каждый водитель имеет свои «хитрые» пути дви-

жения. На их выбор влияет несколько факторов: плотность движения и загруженность

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

Учитывая все это, можно получить удобный маршрут. При выборе этого критерия поиск

маршрута ведется на основании экспертных оценок об «удобстве» проезда по участкам

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

3) Время движения. Этот критерий аналогичен критерию длины пути. Однако дли-

на отрезка дороги и среднее время проезда по нему не всегда пропорциональны. Есть уча-

сти дорог с ограниченной скоростью движения, есть участки, где движение затруднено

плотным потоком и постоянно возникающими пробками. А бывает и наоборот – строят

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

ской скорости [17].

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

Если абстрагироваться от того, что графы в этой работе – это представление улич-

но-дорожной сети города, то можно предложить множество применений созданной гео-

информационной системы.

Сеть горных выработок подземного горнодобывающего предприятия (шахты) мо-

жет быть представлена в виде графа. В этом случае ГИС ПИОМ можно использовать для

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

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

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

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

из нее непригодные для движения (разрушенные, затопленные и т. п.) участки. Это осо-

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

работающих в сложных горно-геологических условиях.

Или, если представить что узлы – это города, а ребра графа – это линии авиапере-

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

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

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

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

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

ко. Ведь в критерий оптимальности могут входить достаточного много параметров: стои-

мость перелета, время полета, время ожидания следующего рейса, компания-

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

шенной комфортности), качество пересадочного пункта и другие. Разработанная ГИС

ПИОМ (при незначительной модификации и добавлении требуемых исходных данных)

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

заданному критерию результат.

Можно найти еще множество вариантов практического применения разработанной

ГИС ПИОМ при небольшой модификации в каждом конкретном случае.

ЗАКЛЮЧЕНИЕ

В результате проведенного исследования создана геоинформационная система по-

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

двух основных подсистем. Первая – подсистема ввода, редактирования и управления гра-

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

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

таблицы связанных с ними баз данных. Во второй – подсистеме поиска и оптимизации

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

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

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

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

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

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

авиаперелетов, пассажирских и грузовых автоперевозок.

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

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

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

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

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

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

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

Отдельные результаты работы были опубликованы в сборнике научных трудов [17],

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

«Инновационные недра Кузбасса. IT-технологии», проходившей в марте 2007 года в

г. Кемерово.

Результаты исследования были представлены на апрельской 52-й научно-

практической конференции и опубликованы в «Сборнике докладов студентов и аспиран-

тов Кузбасского государственного технического университета» [18].

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

1 Скворцов А. В. Геоинформатика: Учеб. пособие. – Томск: Изд-во Том. ун-та, 2006. –

336 с.

2 Бойков В. Н., Федотов Г. А., Пуркин В. И. Автоматизированное проектирование авто-

мобильных дорог (на примере IndorCAD/Road). – М.: Изд-во МАДИ (ГТУ), 2005. –

223 с.

3 Скворцов А. В., Поспелов П. И., Крысин С. П. Геоинформатика в дорожной отрасли

(на примере IndorGIS). – М.: Изд-во МАДИ, 2005. – 389 с.

4 ООО «ДАТА Ист». City Explorer [Электронный ресурс]. – Режим доступа:

http://www.dataeast.ru/Rus/Sales/cityexplorer.asp, свободный.

5 Проект ДубльГИС [Электронный ресурс]. – Режим доступа: http://www.2gis.ru, сво-

бодный.

6 Открытый город. Электронный деловой справочник [Электронный ресурс]. – Режим

доступа: http://www.open-city.ru, свободный.

7 Электронная справочная система города Калуги [Электронный ресурс]. – Режим дос-

тупа: http://users.kaluga.ru/is/programm.htm, свободный.

8 Справочник метро «PMetro» [Электронный ресурс]. – Режим доступа:

http://www.pmetro.nm.ru, свободный.

9 INTUIT.ru: Учебный курс – Графы и алгоритмы [Электронный ресурс]. – Режим дос-

тупа: http://www.intuit.ru/department/algorithms/gaa/, свободный.

10 INTUIT.ru: Учебный курс – Графы и их применение [Электронный ресурс]. – Режим

доступа: http://www.intuit.ru/department/algorithms/graphsuse/, свободный.

11 Липский В. Комбинаторика для программистов. Пер. с англ./ В. А. Евстигнеева, О. А.

Логинова, под ред. Ершова А. П. – М.: Мир, 1988. – 200 с.

12 Седжвик Роберт. Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер. с

англ./Роберт Седжвик. – СПб: ООО «ДиаСофтЮП», 2002. – 496 с.

13 Компьютерра [Электронный ресурс]. – Режим доступа:

http://www.computerra.ru, сво-

бодный.

14 DelphiWorld 6.0 [Электронный ресурс]. – Режим доступа: http://delphiworld.narod.ru,

свободный.

15 Delphi Russian Knowledge Base from Vit [Электронный ресурс]. – Режим доступа:

http://www.drkb.ru, свободный.

16 Нейронные сети и генетические алгоритмы [Электронный ресурс]. – Режим доступа:

http://www.neuroproject.org, свободный.

17 Лопатин А. А. Комплекс программ поиска оптимального маршрута движения в до-

рожно-транспортной сети города // Инновационные недра Кузбасса. IT-технологии:

сборник научных трудов. – Кемерово: ИНТ, 2007. – С. 392–393.

18 Лопатин А.А. Представление графов в информационных системах // Сборник докладов

студентов и аспирантов Кузбасского государственного технического университета.

Том 2. По результатам докладов 52-й научно-практической конференции, 16-20 апреля

2007 г. – Кемерово: ГУ КузГТУ, 2007. – С. 154–155.

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

Каталоги и файлы Описание

KEMEROVO папка с примером проекта для ГИС ПИОМ

KEMEROVO\lCross.* файлы таблицы БД с данными о перекрестках

KEMEROVO\lNodeBegin.* файлы таблицы БД с данными о начальных узлах

KEMEROVO\lNodeEnd.* файлы таблицы БД с данными о конечных узлах

KEMEROVO\lStreet.* файлы таблицы БД с данными об отрезках улиц

KEMEROVO\lStreetCaption.* файлы таблицы БД с данными о перекрестках

KEMEROVO\mapdata.ini файл инициализации проекта

KEMEROVO\sourcemap.bmp bmp-файл с картой-источником

SOURCE папка с исходными кодами разработанной программы

SOURCE\gis_piom.dpr файл проекта Delphi

SOURCE\gis_piom.res файл ресурсов

SOURCE\*.dfm файлы форм

SOURCE\*.pas файлы модулей форм

SOURCE\uCross.pas файл модуля работы с перекрестками

SOURCE\uFind.pas файл модуля работы с алгоритмами поиска

SOURCE\uMap.pas файл модуля работы с картой

SOURCE\uStreet.pas файл модуля работы с улицами

diplom.doc файл с текстом дипломной работы

diplom.ppt файл презентации дипломной работы

gis_piom.exe исполняемый файл разработанной ГИС ПИОМ