Ганущак Надежда Константиновна

Факультет: Горно-геологический

Специальность: Геоинформационные системы и технологии (ГИС)

Тема выпускной работы:

«Исследование существующих алгоритмов решения транспортных задач в ГИС»

Руководитель: Гермонова Екатерина Александровна

Реферат

Введение. Цели и задачи работы. Актуальность и новизна

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

Задача нахождения кратчайшего пути постоянно актуальна для водителей скорой медицинской помощи, бригад быстрого реагирования, милиции, спасателей... Перед каждым человеком, отправляющимся в путь, становится проблема выбора оптимального пути.

Иллюстрация процесса нахождения кратчайшего пути представлена на рис.1:

Рисунок 1 - Кратчайший путь от А до В

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

Задачи работы – изучить три алгоритма нахождения кратчайшего пути (алгоритм Дейкстры, алгоритм Уоршелла-Флойда и алгоритм Левита), определить необходимые для их реализации входные данные и реализовать в среде ГИС эти методы нахождения кратчайшего пути. Далее тестировать эти алгоритмы на реальных транспортных сетях при различных ограничениях и условиях, оценить точность и время выполнения алгоритмов при различных условиях. В итоге провести сравнительный анализ результатов и выявить оптимальный метод нахождения кратчайшего пути при заданных параметрах.

Ранее уже выполнялись аналогичные исследования, но в них рассматривались другие алгоритмы. Таким образом, в данной работе впервые выполняется исследование и сравнения работы алгоритмов Уоршелла-Флойда, Дейкстры и Левитта между собой.

Если применить результаты исследований, выполненных в данной работе, при разработке программного обеспечения, можно повысить эффективность, быстродействие и качество программ для решения транспортных задач и анализа сети в ГИС.

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

Обзор существующих исследований и разработок

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

Например, в статье [1] описываются исследования по оценке работы алгоритма Дейкстры, Эвристического и Генетического алгоритмов. В этой работе использовали 6 реальных транспортных сетей для оценки алгоритмов кратчайшего пути. Эти 6 сетей включают в себя Схему транспортных сетей Ирана в масштабах 1:25000 и 1:250000. Эти транспортные сети включают в себя транспортные сети низкой детализации и транспортные сети высокой детализации. Сети низкой детализации состоят из двух видов дорог: автострады и шоссе. Сети высокой детализации состоят из Асфальтовой дороги 1, Асфальтовой дороги 2, Асфальтовой дороги 3 и Грунтовой дороги. Сети были занесены и обработаны в ArcViewGIS, действующей на рабочей станции Pentium 4 (RAM 280 Mb, CPU 1800 MHz) в среде Windows NT. Топологические отношения и длины дуг были определены в Arc/Info и конвертированы в формат ArcView. Алгоритмы были написаны на языках программирования Visual Basic, Visual C++, MapObject. Программы разрабатывались для нахождения группы кратчайших путей типа "от одного к одному", "от одного ко всем" и "от всех ко всем". Алгоритмы были реализованы, используя данные с различным числом узлов и связей.

В результате тестирования получили, что:

1. время выполнения упомянутых алгоритмов зависит от условий задачи и числа узлов в реальных транспортных сетях;
2. когда число узлов и сложность задачи увеличиваются, Эвристический метод работает лучше, чем другие;
3. Для небольшого числа узлов и сложных условий задачи Метаэвристический метод (Генетический алгоритм) работает лучше, чем другие;
4. Для небольшого чиста узлов и легких условий задачи алгоритм Дейкстры применять выгоднее, чем другие.

В работе [2] рассматривались такие алгоритмы кратчайшего пути, как алгоритм Йена, алгоритм Флойда и алгоритм Дейкстры. Эти методы были реализованы в системе управления базами данных FoxPro 6.0. Однако, здесь было принято априори, что алгоритм Дейкстры наилучший для путей между парой вершин сети, Алгоритм Флойда лучший для решения задач оптимизации путей между всеми парами вершин в сети, алгоритм Йена наилучший для нахождения нескольких кратчайших путей между двумя вершинами транспортной сети.

В исследованиях, описанных в статье [3], алгоритмы кратчайших путей были реализованы в Borland Delphi 6. Но здесь не выполнялось обоснование выбора наилучшего алгоритма для нахождения кратчайшего (оптимального) пути на транспортной сети.

Если обратиться к главе "8.7 Задача о кратчайшем пути и ее варианты" из книги И.В. Романовского [4], то здесь рассматриваются для решения задачи о кратчайшем пути алгортмы Беллмана, Уоршелла-Флойда, Дейкстры, Дейкстры-Грибова и Левита. В ходе рассмотрения этих методов были сделаны такие выводы:

1. «...Преимущество алгоритма Уоршелла-Флойда состоит в том, что он годен для большинства графов с ребрами неотрицательной длины, отличный вариант для решения задачи в общем случае, без особых условий. Недостатком алгоритма является необходимость несколько раз анализировать одну и ту же вершину, что приводит к лишним итерациям, а следовательно – к затратам времени и ресурсов ПК. Кроме того, нет проверки на возможность наличия в графе отрицательных ребер, что может привести к затруднениям в программной реализации...»
2. «...Эффективность метода Дейкстры существенно зависит от того, как организован поиск вершины с наименьшим текущим расстоянием...»
3. «...Несмотря на очень высокую эффективность метода Дейкстры-Грибова, в практических задачах с «географической» системой расстояний эще более эффективен метод, принаблежащий Б.Ю.Левиту... В сравнении с методом Дейкстры метод Левита проигрывает на том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М1. Эксперименты показывают, что для графов с «геометрическим» происхождением, т.е. для графов, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым. Он выигрывает и по размеру программы. Метод Левита обладает еще и тем преимуществом перед методом Дейкстры, что он применим в случае отрицательных длин дуг (ведь «длина дуги» - это просто название, которое дает нам полезные ассоциации с реальностью)...»

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

Что касается разработанных программных комплексов для решения задач сетевого анализа с применением ГИС технологий, то хотелось бы уделить внимание нескольким достаточно распространенным программам.

Во-первых, рассмотрим модуль Network Analyst (ESRI) [5], который предлагает дополнительные функции к ArcView GIS для анализа линейных сетевых тем, таких как дороги, линии коммуникаций, городские улицы, реки и др. С помощью Network Analyst решается задача поиска ближайшего пункта обслуживания а также выполняется определение зон обслуживания(доступности).Одной из стандартных функций модуля является выдача маршрутного листа передвижения. Network Analyst удобен и прост в эксплуатации, но решает только несколько задач сетевого анализа и работает только со специально подготовленными данными.

Более широкий набор функций по работе с сетями предоставляет Network Engine от ESRI [6]. Этот программный пакет предназначен для создания функций сетевого моделирования, нахождения пути (маршрута) и отслеживания сетевой топологии. С его помощью можно моделировать любые сети, в том числе абстрактные. Но он оптимизирован для целей задания, сохранения, прокладки и анализа сетей, представляющих собой объекты реального мира, такие как улицы и магистрали, железные дороги, электрические, газовые или телекоммуникационные сети, водопроводы и системы канализационного стока, или обычные водотоки. Подобные географические (то есть имеющие пространственное протяжение и/или привязку) сети обычно рассматриваются как логический граф, основанный на реальных сетевых объектах.

Что касается программных продуктов для решения транспортных задач в среде MapInfo, то следует обратить внимание на ChronoVia – модуль для поиска оптимальных путей в сети, и ChronoMap – модуль для построение зон транспортной доступности. Программы работают практически с любыми данными дорожной сети в векторном формате MapInfo Professional [7]. Кроме того, есть возможность определить правила для сети, что позволяет приблизить математическую модель к реальным дорожным условиям. Чем больше правил позволяет определять программное обеспечение, тем корректней получаемый результат.

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

Построение зон транспортной доступности в ChronoMap обладает большим числом настроек. Зоны могут строиться по одной или многим точкам с минимизацией расстояния, времени или транспортных издержек, с учётом категории транспортных средств и всех характеристик сети. Полезной особенностью является построение зон доступности, как от точки, так и к точке. Имеется широкий выбор настроек для оформления карты.Помимо этого имеется возможность проводить сравнительный анализ двух карт транспортной доступности, в результате которого получается новая карта, выявляющая различия, например, для оценки транспортной доступности, после закрытия дороги. Ещё одна функция может использоваться для таких задач как создание и сравнение различных сценариев доступности определенного пункта с оценкой эффективности каждого варианта.

Хотелось бы отметить особенность ChronoVia и ChronoMap [7]. Большинство программ данного класса оперирует скоростными характеристиками сегментов уличной сети, и как правило это максимальная скорость движения для данного класса дороги. При этом не учитывается, какое транспортное средство передвигается по этой дороге. В данных программных продуктах вводится понятие транспортного средства, имеется библиотека различных транспортных средств. Пользователь может выбрать из библиотеки, которая в случае необходимости может быть расширена, транспортное средство (автомобиль, велосипед, грузовик, трактор и т.д.) для движения по маршруту. Например, трактор будет иметь меньшую скорость по сравнению с автомобилем на одной и той же дороге, а пожарная машина, может пренебрегать некоторыми ограничениями, установленными для других транспортных средств. Параметры каждого транспортного средства могут быть модифицированы: скорость, снижение скорости в час пик и т.п. Также можно изменять физические характеристики вес, высота, ширина и т.д.

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

Таким образом, изучив существующие материалы работ по данной теме можно отметить, что очень мало исследований далют четкий и обоснованный ответ на вопрос «Какой алгоритм лучше при данных условиях на данной сети?».

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

Следующей нерешенной проблемой в данном направлении исследования является выбор языка программирования для программной реализации методов оптимизации затрат транспортной системы. Необходима такая программа, которая занимала бы минимум места на жестком диске ЭВМ, использовала бы минимум ресурсов ЭВМ и была бы максимально эффективной для решения поставленных задач.

Таким образом, можно заметить, что еще есть много нерешенных вопросов при проведении исследований по нахождению кратчайшего пути и решения других задач сетевого анализа с применением ГИС технологий.

Собственные результаты

На данный момент выполнены такие работы:

1. Выполнено изучение теоретических аспектов алгоритмов Дейкстры, Левита и Уоршелла-Флойда.
2. 2. В ArcViewGIS, действующей на рабочей станции Celeron D (RAM 512 Mb, CPU 2,53 GHz) в среде Windows NT, создана сеть дорог на основе карты Ворошиловского р-на г. Донецк в М 1:10 000, включающая 230 вершин (перекрестков) и аналогичная сеть, включающая 510 узлов.
3. Работа алгоритмов на реальных транспортных сетях в ArcView GIS организована путем вызова из скрипта динамической библиотеки, в которой выполняется расчет кратчайшего пути по заданному алгоритму. Dll-библиотеки написаны в среде программирования Borland Delphi 5.
4. Учитывается возможность не включать в расчеты кратчайшего пути «непроходимые» вершины (пробки, ремонт на дорогах), т.е. можно строить минимальные обходные пути.
5. В результате выполнения задания с использованием каждого из трех алгоритмов создается линейная тема - рисуется кратчайший путь, а также атрибутивная таблица, в которой записаны номера начала и конца пути, длина пути в метрах и время выполнения задачи в секундах. Кроме того, в текстовый файл записывается последовательность вершин, по которым проходит полученный путь.

На данный момент результаты таковы:

• подтвердился тезис из [1]о том, что время выполнения задачи с использованием любого из алгоритмов зависит от числа узлов сети и условий (непроходимые точки);
• при нахождении кратчайшего пути между двумя точками алгоритм Уоршелла-Флойда работает медленнее всех, но лучше остальных алгоритмов он работает для определения кратчайших путей между всеми парами вершин в сети;
• при нахождении кратчайшего пути между двумя точками наиболее быстрым является алгоритм Левита;
• в большинстве случаев длина полученного пути и последовательность точек, по которым проходит найденный путь, совпадает, но иногда бывают различия – это предстоит изучить.

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

Заключение

В результате изучения ранее выполненных исследований и разработок в области сетевого анализа можно сделать вывод, что задача нахождения кратчайшего пути очень актуальна во многих областях человеческой деятельности. Кроме того, существует достаточно большой круг вопросов, который предстоит решить по этой теме. В частности нет ясного ответа, какой алгоритм применять для нахождения оптимального пути при заданных условиях.

В работе «Исследование существующих алгоритмов решения транспортных задач в ГИС» выполняется изучение особенностей работы трех алгоритмов нахождения оптимального пути (метод Левита, Дейкстры и Уоршелла-Флойда) на реальных транспортных сетях, в результате которых можно будет определить наилучший алгоритм решения поставленной задачи. На данный момент выполнена только часть исследований, остается много нерешенных вопросов...

Если учесть результаты всех выполненных исследований, систематизировать эту информацию и применить на практике, можно значительно повысить производительность, быстродействие, точность и эффективность программных комплексов, разрабатываемых для решения задач сетевого анализа, и в частности транспортных задач, с применением ГИС технологий.

Перечень ссылок

1. Roozbeh Shad, Hamid Ebadi, Mohsen Ghods. Evaluation of Route Finding Methods in GIS Application. - Dept of Geodesy and Geomatics Eng. K.N.Toosi University of Technology. - http://www.gisdevelopment.net/technology/gis/ma03202pf.htm
   (or articles in library)



2. Королёва Ирина. Кратчайшие пути. - Курсовая работа (осенний семестр 2002/03 уч. года). - http://gip-102irina.narod.ru/List.htm



3. Колодинская Е.В.,Скляренко О.А. Сетевое моделирование:основные методы и программная реализация. - CODE № 1/2003. - http://www.vb.kiev.ua/magazine/2004/01/cm200301_11.pdf



4. Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся на прикладной математике и информатике. — 3-е изд., перераб. и доп. — СПб.: Невский Диалект; БХВ-Петербург, 2003



5. Продукты компании ESRI: Модуль Network Analyst. - http://www.dataplus.ru/Soft/ESRI/ARCVIEW/Network.htm



6. Продукты компании ESRI: NetEngine. - http://www.dataplus.ru/Soft/ESRI/NetEngine/Index.htm



7. Программы фирмы Magellan Ing.: Решение транспортных задач в MapInfo - геоинформационные системы ESTI MAPhttp://www.esti-map.ru/magellan.htm

Вопросы и пожелания направлять по адресу:  : aranelka@mail.ru