Мобильное приложение для поиска оптимального маршрута в университетском городке

Обложка

Цитировать

Полный текст

Аннотация

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

Полный текст

Введение

Крупные университеты имеет сложную архитектурную планировку, поэтому для обучающихся и гостей университета задача поиска нужной аудитории является актуальной. Например, университетский городок Оренбургского государственного университета (ОГУ) состоит из 14 учебных корпусов и сотен различных аудиторий [1].

В настоящее время активно используются навигационные сервисы открытом пространстве во многих сферах деятельности. Всё большую актуальность приобретает навигация, основанная на использовании мобильных приложений (МП), что обусловлено доступностью мобильных устройств [2]. В контексте рассматриваемой проблемы наиболее известны следующие МП для пешей навигации: «Яндекс Карты» [3], 2ГИС [4], Google Maps [5], HERE WeGo [6], Maps.me [7], Sygic GPS Navigation [8], Magic Earth Navigation & Maps [9], iGO Navigation [10], OsmAnd [11], MapFactor Navigation [12].

Результаты проведённого анализа основных характеристик названных МП в виде выявленных достоинств для данной задачи приведены в таблице 1. Среди недостатков некоторых из рассмотренных МП можно отметить: притормаживающий пользовательский интерфейс; устаревшая графика; наличие рекламы; не возможность поиска оптимального пути и др. По информации из открытых источников удалось лишь установить, что в МП [3] для построения маршрутов используется алгоритм Дейкстры.

 

Таблица 1 – Основные характеристики и достоинства МП  

Мобильное приложение

название, разработчик, сайт, платформа

Достоинства

Яндекс. Карты

Яндекс

mobile.yandex.ru/apps/maps

Android; iOS

§ позволяет строить маршруты для пешеходов;

§ знает короткие пути через дворы и проходы между зданиями;

§ показывает входы в здания и включает поэтажные схемы;

§ имеет голосовой помощник «Яндекс. Алиса».

2ГИС

ДубльГИС

info.2gis.com

Android; iOS; Wear OS

§ умеет прокладывать самые короткие пешие маршруты;

§ может работать без подключения к Интернету;

§ отображает поэтажные схемы торговых центров (ТЦ), вокзалов и аэропортов;

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

Google Maps

Google

google.com/maps


Android; iOS

§ позволяет строить пешие маршруты и знает расписание общественного транспорта;

§ поддерживает технологию дополненной реальности (можно видеть подсказки поверх изображения окружающей местности);

§ предоставляет возможность просмотра панорамных снимков и схем, которые помогают ориентироваться в больших зданиях (аэропорты, вокзалы, ТЦ и др.);

§ поддерживает голосовое управление и сохранение карт в памяти устройства с целью последующего использования без подключения к Интернету.

HERE WeGo

Here Technologies

here.com

Android; iOS

§ за считаные секунды подбирает доступные варианты перемещения из начальной точки в конечную, рассчитывает примерное время в пути и позволяет выбрать оптимальный маршрут из списка;

§ при навигации может переключаться в 3D-режим;

§ имеется возможность сохранения карт в памяти мобильного устройства и использования приложения в автономном режиме.

Maps.me

Maps.me Limited

maps.me


Android; iOS

§ построен на основе свободной географической карты OpenStreetMap;

§ картографические данные можно скопировать в память мобильного устройства и пользоваться приложением без подключения к Интернету;

§ умеет строить пешие и велосипедные маршруты.

Sygic GPS Navigation

Sygic

sygic.com/gps-navigation
Android; iOS

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

Magic Earth Navigation & Maps

General Magic

magicearth.com


Android; iOS

§ построен на основе свободной географической карты OpenStreetMap;

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

§ присутствует функция «Что находится рядом», которая выводит список близлежащих объектов.

iGO Navigation

NNG Software Developing and Commercial

igonavigation.com


Android; iOS

§ позволяет строить маршруты для пешеходов и автомобилистов.

OsmAnd

OsmAnd

osmand.net


Android; iOS

§ построен на основе свободной географической карты OpenStreetMap;

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

§ имеет встроенный путеводитель;

§ ведет запись маршрута.

 

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

Целью исследования является разработка МП для поиска оптимального маршрута в университетском городке.

Для достижения поставленной цели необходимо:

  • сформулировать математическую задачу в виде поиска кратчайшего пути в графе;
  • выбрать алгоритм поиска кратчайшего пути в графе;
  • разработать логическую архитектуру программы МП;
  • разработать вспомогательный сервис для добаления новых карт в МП;
  • проверить работоспособность МП.

1. Постановка задачи и метод решения

Задачу поиска оптимального пути от исходной точки  до искомой аудитории можно представить как известную задачу поиска кратчайшего пути в графе [13, 14]. Такой подход используется в рассмотренных МП [3-12].

Пусть задан ортограф G(V, A), каждой дуге которого (u,v) ставится в соответствие число L(u,v) длина дуги. Под длиной дуги маршрута (пути) понимают сумму дуг, составляющих маршрут. Требуется найти длины кратчайших маршрутов и маршруты от выбранной вершины до всех остальных вершин графа vi.

Наиболее известными алгоритмами поиска кратчайшего маршрута в графе являются: алгоритм поиска в ширину, жадный алгоритм поиска кратчайшего пути, алгоритм Дейсктры [15, 16]. В таблице 2 приведены результаты сравнительного анализа указанных алгоритмов.

 

Таблица 2 – Результаты сравнительного анализа алгоритмов отыскания кратчайшего пути в графе

Алгоритм

Достоинства

Недостатки

Алгоритм поиска в ширину

§  сравнительная простота реализации

§  полнота и оптимальность

§  при увеличении пространства поиска производительность поиска снижается по сравнению с другими эвристическими алгоритмами

Жадный алгоритм поиска

§  простота поиска оптимального решения

§  сложность оценки алгоритма

 

Алгоритм Дейкстры

§  сравнительная простота реализации

§  находит кратчайшие пути и их величины только от одной вершины

 

В качестве основы для построения математической модели задачи принят алгоритм Дейкстры. Программная реализация построена на основе UML-шаблонов проектирования [17, 18]. Архитектура программного средства BLoC (компонент бизнес-логики, от англ. Business Logic Component), идея которой заключается в разделении интерфейса (UI-компонента, от англ. User Interface) и бизнес-логики приложения, соответствует единой системы программной документации [19].

Для взаимодействия с пользователем требуются следующие визуальные элементы управления: 

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

Для работы интерфейса требуются классы, в которых реализованы алгоритмы: поиска путей, взаимодействия с базой данных (БД), отображения карт и дополнительной информации, работы с вре́менными данными. Термин «класс» в данном случае используется в контексте объектно-ориентированного программирования и подразумевает собой шаблон для создания объектов, обеспечивающий начальные значения состояний: инициализация полей-переменных и реализация поведения функций или методов. Это позволяет создать универсальный программный продукт для различных карт.

На рисунке 1 представлена вкладка «Навигация» МП. Первый UI-компонент (визуальный элемент интерфейса МП) отвечает за верхнюю часть экрана, в котором расположены наименование вкладки и кнопки, отвечающие за масштаб и ориентацию карты, а также выпадающий список, из которого можно выбрать карты для просмотра. Во второй UI-компонент, имеющий табличную структуру, вложена группа UI-компонентов. В первой строке таблицы расположены два текстовых поля с выпадающим списком, с помощью которых пользователь может выбрать начальную и конечную точки для прокладывания маршрута, и кнопка, отвечающая за расчёт маршрута и его отображение. Во второй строке таблицы расположен UI-компонент, на котором отображается карта и путь, который будет рассчитан МП.

 

Рисунок 1 – Вкладка «Навигация» МП

 

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

Заключительная строка таблицы содержит три кнопки:

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

2. Описание и проверка работоспособности МП

В качестве среды для разработки МП выбрана платформа Android Studio1. Для разработки программного продукта использовался объектно-ориентированный язык Flutter[2]. Выбранный язык является кроссплатформенным языком, что позволяет создавать МП под Android и iOS, а также для решений под Windows, macOS и Linux с использованием языка программирования Dart[3]. В языке Dart нет готового инструмента для отображения карт, но с помощью доступного функционала можно создать новый функционал, отвечающим заданным требованиям.

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

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

 

Рисунок 2 – Шаблон данных

 

На рисунке 3 показан пример шаблона данных МП, принимающего входные данные и отображающего возможные маршруты внутри помещения, с нумерацией аудиторий. Для разработки программного обеспечения выполнена предварительная работа на базе предоставленных  ОГУ документов о планировке корпусов и актуальной  информации о расположении аудиторий и иных помещений. Подготовленный материал форматирован к виду, соответствующему шаблону данных. Полученный результат помещён в БД, которая размещена на удалённом сервере. В интерфейсе поля, отвечающего за выбор начальной и конечной точек маршрута, происходит наполнение информацией из БД, т.е. из полей легенды карты при старте программы. Когда пользователь совершает выбор, то данные записываются во вре́менные переменные, описанные в логической архитектуре, представляющей собой объектно-ориентированную программы, которая содержит слои, классы объектов, пакеты, основные платформы, интерфейсы, подсистемы и их взаимодействия.

 

Рисунок 3 – Пример шаблона данных мобильного приложения

 

На рисунке 4 приведён пример выбора начальной точки маршрута. В интерфейсе предусмотрен выпадающий список, из которого пользователь может выбрать нужную карту для отображения. Результат записывается во врѐменную переменную, описанную в логической архитектуре, и передаётся в класс для отображения. Пример выпадающего списка представлен на рисунке 5.

 

Рисунок 4 – Пример выбора начальной точки маршрута

 

Рисунок 5 – Пример выпадающего списка

 

Рисунок 6 – Карта результата эксперимента

 

Для проверки работоспособности МП проведён эксперимент, согласно которому требуется построить кратчайший путь от 16-го корпуса до аудитории 20119, расположенной в 20-ом корпусе на 1-ом этаже. На рисунке 6 представлена карта результата эксперимента. 

На рисунке 7 приведён построенный МП маршрут, на котором числа означают последовательность точек графа, через которые проходит путь.

 

Рисунок 7 – Построенный мобильным приложением маршрут эксперимента

 

Для упрощения добавления новых карт в БД МП, разработан вспомогательный сервис, написанный на языке программирования PHP4, который преобразует SVG картинку5 в набор данных по созданному шаблону.

SVG-изображение имеет следующую структуру:

  • 1 слой – стены здания;
  • 2 слой – стены внутренней планировки помещений;
  • 3 слой – дороги (возможные маршруты) ;
  • 4 слой – местонахождение точек графа (окружности малого диаметра);
  • 5 слой – местонахождение пронумерованных аудиторий, корпусов и иных помещений (окружности большого диаметра).

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

 

Рисунок 8 – Карта возможных маршрутов

 

Сервис поочерёдно обрабатывает слой и выдаёт данные согласно шаблону, после чего они интегрируются в МП.

На рисунке 9 приведена структура SVG-изображения, полученная за счёт обработки данных о планировке помещений и актуальной информации. На основании слоёв 3 и 4 за счёт работы скрипта PHP генерируется таблица смежности графа, приведённая на рисунке 10. На вход подаются данные, представленные на рисунке 9, вычисляются растояния между точками, на основании бинарных отношений принадлежности точек прямым и пересечений прямых определяются ближашие соседи для всех вершин (рассматривает маршруты, проходящие через окружности из слоя 4 и отыскиваются ближайшие окружности, через которые проходят эти дороги).

 

Рисунок 9 – Структура SVG-изображения

 

Рисунок 10 – Таблица смежности

 

Заключительным этапом работы вспомогательного сервиса является выгрузка конечного результата в БД, которая расположена на удалённом сервере.

Заключение

Разработано МП для поиска оптимального маршрута от начальной точки до точки назначения с функционалом, призванным создать благоприятные условия для удобной навигации в университете. Новизна предложенной разработки заключается в универсальности средств отображения, добавления и редактирования карт. Дальнейшее совершенствование МП возможно в направлении улучшения его точности за счёт объединения алгоритмов поиска путей в графе, а также перевод карт из 2D- в 3D-пространство.

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

1 Android Studio. https://developer.android.com/studio.

2 Flutter. https://flutter.dev/.

3 https://dart.dev/.

4 Lerdorf, Rasmus (June 8, 1995). Announce: Personal Home Page Tools (PHP Tools). Retrieved 7 June 2011.

5 SVG (от Scalable Vector Graphics — масштабируемая векторная графика) — это вид графики, которую создают с помощью математического описания геометрических примитивов, которые и образуют все детали изображения.

×

Об авторах

Слушаш Тугайбаевна Дусакаева

Оренбургский государственный университет

Автор, ответственный за переписку.
Email: slushashdusakaeva@rambler.ru
ORCID iD: 0000-0002-5292-1114

к.т.н., доцент кафедры прикладной математики 

Россия, Оренбург

Виталий Вячеславович Савинов

Оренбургский государственный университет

Email: savinovvet@gmail.com

магистрант института математики и информационных технологий 

Россия, Оренбург

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

  1. Официальный сайт Оренбургского государственного университета. http://www.osu.ru/.
  2. Жаркова С.А. Актуальность разработки мобильных приложений для Android // Научные исследования в современном мире: опыт, проблемы и перспективы развития: сборник научных статей по материалам IX Международной научно-практической конференции, 18 ноября 2022. С.215-220.
  3. Яндекс Карты [Электронный ресурс]. URL: https://mobile.yandex.ru/apps/android/maps.
  4. 2GIS [Электронный ресурс]. URL: https://info.2gis.com/.
  5. Google Maps [Электронный ресурс]. URL: https://bestmaps.ru/google-maps.
  6. HERE WeGo [Электронный ресурс]. URL: https://www.here.com/.
  7. Maps.me [Электронный ресурс]. URL: https://maps.me/.
  8. Sygic GPS Navigation [Электронный ресурс]. URL: https://www.sygic.com/.
  9. Magic Earth Navigation & Maps [Электронный ресурс]. URL: https://www.amazon.com/Magic-Earth-Navigation-and-Maps/dp/B077XTY4F9.
  10. iGO Navigation [Электронный ресурс]. URL: https://www.malavida.com/en/soft/igo-navigation/android/.
  11. OsmAnd [Электронный ресурс]. URL: https://osmand.net/.
  12. MapFactor Navigation [Электронный ресурс]. URL: https://navigatorfree.mapfactor.com/en/.
  13. Алексеев В.Б. Дискретная математика. Москва: ИНФРА-М, 2023. 133 с.
  14. Редькин Н.П. Дискретная математика. Москва: ФИЗМАТЛИТ, 2009. 264 с.
  15. Плотников О.А., Подвальный Е.С. Решение задачи поиска оптимального пути между двумя точками на графе с нерегулярным весом ребер // Вестник ВГТУ. 2012. № 6. С. 22-26.
  16. Бойков В.А. О применении жадных алгоритмов в некоторых задачах дискретной математики // Программные продукты и системы. 2019. №1. С. 55-62.
  17. Ларкман К. Применение UML и шаблонов проектирования М. Издательский дом «Вильямс», 2004. 624 с.
  18. Самуйлов С.В. Объектно-ориентированное моделирование на основе UML. Саратов: Вузовское образование, 2016. 137 c.
  19. ГОСТ 701-90 (ИСО 5807-85) Единая система программной документации (ЕСПД). Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения. М.: Стандартинформ, 2010. 23 с.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2. Рисунок 1 – Вкладка «Навигация» МП

Скачать (135KB)
3. Рисунок 2 – Шаблон данных

Скачать (46KB)
4. Рисунок 3 – Пример шаблона данных мобильного приложения

Скачать (100KB)
5. Рисунок 4 – Пример выбора начальной точки маршрута

Скачать (200KB)
6. Рисунок 5 – Пример выпадающего списка

Скачать (146KB)
7. Рисунок 6 – Карта результата эксперимента

Скачать (336KB)
8. Рисунок 7 – Построенный мобильным приложением маршрут эксперимента

Скачать (217KB)
9. Рисунок 8 – Карта возможных маршрутов

Скачать (198KB)
10. Рисунок 9 – Структура SVG-изображения

11. Рисунок 10 – Таблица смежности

Скачать (867KB)

© Дусакаева С.Т., Савинов В.В., 2023

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ФС 77 - 70157 от 16.06.2017.

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах