РАЗРАБОТКА АЛГОРИТМА ПОИСКА ОПТИМАЛЬНЫХ МАРШРУТОВ С ПОМОЩЬЮ АЛГОРИТМА ФЛОЙДА-УОРШЕЛЛА НА ПРИМЕРЕ ТРАНСПОРТНОЙ СИСТЕМЫ ГОРОДА ЛАНГЕПАС

Аннотация: в данной работе представлена разработка алгоритма поиска оптимальных маршрутов между вершинами графа полученного в предыдущей статье [2, с. 5].

Abstract: this paper presents the development of an algorithm for finding optimal routes between the vertices of the graph obtained in the previous article [2, p. 5].

Ключевые слова: транспортная система, ориентированный граф, оптимальный путь, алгоритм Флойда-Уоршелла.

Keywords: transport system, directed graph, optimal path, Floyd-Warshell algorithm.

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

1. повышение уровня информирования населения о работе автомобильного транспорта, осуществляющего регулярную перевозку пассажиров и багажа в городе [1, с. 2];
2. повышение привлекательности использования транспорта общего пользования населением города [1, с. 2];
3. обеспечение возможности повышения качества обслуживания маршрутов регулярных перевозок пассажиров и багажа за счет получения объективной информации о движении транспортных средств, обслуживающих маршруты [1, с. 2];
4. снижение количества личного автомобильного транспорта на дорогах города за счет увеличения количества перевозимых пассажиров [1, с. 2].

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

Цель: разработать алгоритм поиска оптимальных маршрутов между вершинами графа города Лангепас [2, с. 5] для дальнейшей его реализации с помощью языка программирования.

Объект исследования: графическая модель города Лангепас представленная в виде ориентированного графа.

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

Для исследования модели с помощью метода нахождения оптимальных путей Флойда – Уоршелла нужно сформировать матрицу смежности для графа. Матрицы смежности представляются двумерным массивом размера n x n, где n – число вершин графа. В нашем случае вершин в графе 34, соответственно матрица для транспортной системы города Лангепас будет размером 34 x 34.

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

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

Рисунок 1. Блок схема алгоритма предварительного заполнения матрицы расстояний

Более подробно рассмотрим две основные функции в этом алгоритме: функция, которая связывает остановки с помощью маршрута, и функция, которая связывает смежные остановки пешеходными маршрутами.

Функция связывания остановок с помощью маршрута. Данная функция обходит все остановки маршрута и заполняет ячейку матрицы, если из одной остановки можно доехать в другую без пересадок. Для этого запускается цикл, который бежит по всем остановкам в том порядке, который указан в маршруте. Первая остановка заносится в массив, который хранит все рассмотренные остановки, так как из одной остановки путь никуда не построить. Начиная со второй остановки алгоритм перебирает в цикле каждую рассмотренную ранее остановку и строит до рассматриваемой на данный момент остановки путь. Если между этими остановками в матрице уже есть путь, то алгоритм сравнивает этот путь с новым, и если этот путь отличается, то добавляет его к существующему пути как новый вариант пути. Если в матрице между этими остановками пути не было, то новый путь без проверки заносится в матрицу. После того как все элементы массива с рассмотренными ранее остановками закончились, рассмотренную остановку заносим в этот массив и переходим к следующей остановке в маршруте. Главный цикл закончит свою работу, как только все остановки маршрута будут рассмотрены. Блок схема описанного алгоритма приведена на рисунке 2.

Рисунок 2. Блок схема алгоритма связывания остановок с помощью маршрута

Функция связывания смежных остановок пешеходными маршрутами. Данная функция связывает вершины графа, соответствующие смежным остановкам пешеходными маршрутами. Для этого получаем список всех смежных остановок для рассматриваемой остановки и циклом пробегаемся по каждой из них. В цикле между рассматриваемыми остановками создаем пешеходный маршрут и помещаем его в матрицу. Цикл работает до тех пор, пока не будут рассмотрены все смежные остановки в массиве. Блок схема алгоритма приведена на рисунке 3.

Рисунок 3. Блок схема алгоритма связывания смежных остановок пешеходными маршрутами

На этом предварительное заполнение матрицы завершено.

После того, как матрица маршрутов заполнена начальными значениями, к ней можно применить алгоритм нахождения оптимальных маршрутов Флойда – Уоршелла. Алгоритм реализуется в три цикла for, внешний выбирает вершину, через которую мы пробуем найти лучший путь, внутренние два перебирают пары вершин, между которыми мы ищем оптимальный путь. Во внутреннем цикле, если между остановками существует путь и он не содержит пересадок (прямой путь), то оставляем его и переходим к следующей конечной вершине, иначе происходит расчет сложности маршрутов и их сравнение. Если новый путь через промежуточную остановку по сложности такой же, как и существующий, то добавляем его как новый вариант пути, если лучше, то заменяем им существующий путь, если хуже, то оставляем старый путь. Если существующего пути между двумя рассматриваемыми остановками нет, то создаем новый путь через промежуточную остановку и помещаем в матрицу. Блок схема алгоритма приведена на рисунке 4.

Рисунок 4. Блок схема алгоритма нахождения оптимальных маршрутов Флойда-Уоршелла

Формула расчета сложности маршрута. Чтобы определить какой маршрут наиболее оптимальный, рассчитывается сложность существующего и нового маршрутов.  Для этого была выведена следующая формула расчета сложности маршрута, которая представлена ниже:

complexity = countBus + countWalking / 3,                         (1)

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

countWalking – количество сегментов маршрута которые необходимо пройти пешком.

CountWalking делим на три, потому что считаем, что два сегмента пользователь может пройти пешком, а если их больше, то увеличиваем сложность маршрута. Блок схема алгоритма расчета сложности маршрутов приведена на рисунке 5.

Рисунок 5.  Блок схема алгоритма расчета и сравнения сложности маршрутов

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

 Список литературы:

1. Постановление Правительства Ханты-Мансийского автономного округа – Югры от 02.03.2018 N 51-п " О единой региональной информационной системе управления транспортом Ханты-Мансийского автономного округа - Югры" // http://docs.cntd.ru/document/543546499
2. Князев С.М. Построение модели транспортной системы города Лангепас // Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ: сб. ст. по мат. XLII междунар. студ. науч.-практ. конф. № 7(42). URL: https://sibac.info/archive/meghdis/7(42).pdf – статья в интернете (дата обращения: 17.06.2018).