Стрельников Евгений Михайлович,
магистрант
Института инженерных технологий и естественных наук НИУ «БелГУ»,
(Белгород, Россия)
РАЗРАБОТКА АЛГОРИТМА СОСТАВЛЕНИЯ МАРШРУТОВ ПЕРЕДВИЖЕНИЯ ПОЛЬЗОВАТЕЛЕЙ ОБЩЕСТВЕННОГО АВТОТРАНСПОРТА ПО НАИМЕНЬШЕМУ ПУТИ
Аннотация
Данная статья направлена на разработку алгоритма составления маршрутов передвижения пользователей общественного автотранспорта по наименьшему пути.
Ключевые слова
Алгоритм составления маршрутов, общественный транспорт, планирование маршрута, анализ, визуализация, режим онлайн.
На сегодняшний день планирование маршрутов передвижения гражданами, использующими общественный транспорт, становится актуальной задачей. Многие автобусы достигают остановки не по графику, что осложняет расчет времени пользователей. По городу автобусы доходят до остановки через 20 – 25 мин, а за городом это цифра увеличивается с 30 минут и до часу, что существенно увеличивает время ожидания общественного автотранспорта и повышает вероятность опоздать на маршрут.
Для проектирования было использовано draw.io, с помощью которого были разработаны IDEF3-диаграммы. IDEF 3 - способ описания процессов с использованием структурированного метода, позволяющего эксперту в предметной области представить положение вещей как упорядоченную последовательность событий с одновременным описанием объектов, имеющих непосредственное отношение к процессу;
В ходе проектирования алгоритма передвижения пользователей общественного автотранспорта, был построен алгоритм составления маршрутов передвижения по наименьшему пути.
Рисунок 3 – Алгоритм составления маршрутов по наименьшему пути.
Начальный процесс запускает поиск маршрутов по 2 точкам «А» и «Б». Причем, они могут располагаться на любом участке карты и на разном расстоянии. Сам поиск будет осуществляться с определенным радиусом, где центром и есть установленная точка. Далее будут получены остановки, которые попали в зону поиска, где каждая из них будет записана в свой массив. Из первого массива с остановками получаем все общественные автотранспорты и находим их расстояние до остановок. Кроме этого, мы используем данные массивы для составления дерева решений. Получив дерево всех маршрутов, для них устанавливается расстояние и вычисляется время в пути. Далее происходит сортировка маршрутов по времени в пути и вывод пяти маршрутов, которые были найдены по наименьшему расстоянию. Этот алгоритм может запускаться каждый раз, когда происходит изменение координат одной из двух точек «А» или «Б». При этом, предыдущие результаты могут кэшироваться для производительности. К примеру, пользователь может запускать поиск из точки «А» каждый раз в одном месте, а именно дома. В результате поиска, остановки можно будет забирать из базы данных напрямую, чтобы не нагружать систему. Потому что, сам алгоритм поиска ближайших остановок (см. рисунок 4) достаточно ресурсоемкий.
Рисунок 4 – Алгоритм поиска ближайших остановок для установленной точки.
Данный алгоритм начинает свой процесс с установки точки на карте. После этого, от нее сравнивается расстояние до всех остановок, которые были получены из базы данных. Все остановки сортируются по дистанции между выбранной точкой и остановкой. После этого, фильтруются по расстоянию от 500 метров и проверяется количество полученных остановок. Если остановок будет меньше двух, то радиус поиска увеличится в 2 раза относительно установленной точки «А», что составит 1000 метров. Алгоритм поиска ближайших остановок будет выполняться рекурсивно, увеличивая радиус поиска до тех пор, пока не будет найдено более 1 остановки.
Так же будут записываться результаты выполнения для алгоритма «составление дерева решений по остановкам из точки А и Б» (см. рисунок 5).
Рисунок 5 – Алгоритм составления дерева решений по остановкам из точки А и Б.
На первом этапе происходит инициализация дерева решений. Оно заполняется остановками (объектами Point) и проверяется по 2 точкам «А» и «Б». В случае, если найдены маршруты от точки «А» до точки «Б» напрямую, то алгоритм возвращает найденные маршруты. В случае если, маршруты не были найдены, то процесс переходит в следующий этап, а именно в поиск ближайших остановок по найденным маршрутам. Данный этап предусматривает очередность выбора из двух массивов (points, B) объектов, с дальнейшим их сравнением и поиском ближайшей остановки. Найденные остановки добавляются в выбранный объект Point. Далее сам объект передается рекурсивно вниз, до тех пор, пока все его найденные объекты не будут находится вблизи конечных остановок.
Как пример результата данного алгоритма представлен на рисунке 6.
Рисунок 6 – Результат выполнения алгоритма составления дерева решений по двум точкам.
В результате был получен граф, который можно представить в виде таблицы 2, которая отражает все переходы между узлами графа. Узлами графа здесь являются остановки общественного автотранспорта, а ребрами графа являются маршруты с дистанцией между остановками
Таблица 2 – Результат выполнения алгоритма в виде таблицы
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
0
1
1
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
1
1
2
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
6
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
2
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
11
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
12
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
0
0
13
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
14
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
15
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Результат по таблице и итог
Список использованных источников:
1. Node.js событийно-ориентированный язык программирования [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Node.js (дата обращения 05.06.2019)
2. About Node.js [Электронный ресурс] URL: https://nodejs.org/en/about (дата обращения 05.06.2019)
3. Amaksr. 2015. GPS-монитор под андроид «KidsTrack [Электронный ресурс] URL: https://habrahabr.ru/post/257443/ (дата обращения: 05.06.2019).
4. Null 2010. Онлайн-мониторинг транспорта своими руками [Электронный ресурс] URL: https://habrahabr.ru/post/99508/ (дата обращения: 05.06.2019).
1. По ФГОСВсе мероприятия на нашем портале проводятся строго в соответствии с действующим законодательством и ФГОС
2. БыстроРезультаты олимпиад доступны моментально. Результаты участия в творческом конкурсе или публикации статей – в течение 1 рабочего дня
3. ЧестноУчастие в любом конкурсе – бесплатное. Вы оплачиваете изготовление документа только когда знаете результат
