Комбінований підхід для побудови оптимального індивідуального туристичного маршруту у мобільному застосунку

Abstract

Висвітлено розв’язання задачі побудови оптимальних маршрутів під час планування індивідуальних подорожей в умовах впливу багатьох факторів і можливих змін вхідних параметрів (погодних умов, заторів на дорогах тощо). Проаналізовано чотири класи алгоритмів для розв’язання задачі комівояжера та оцінено їхню доцільність для використання у мобільному туристичному застосунку. Форма мобільного застосунку зумовлена тим, що туристи переважно не беруть у мандри техніку, важчу за смартфон. Вказано недоліки еври- стичних і метаевристичних методів, зокрема, високу чутливість до початкових налаштувань, негарантовані оптимальні розв’язки та ризик зациклення у локальних оптимумах. Відкинуто точні методи як непридатні в контексті поставленого завдання внаслідок високої обчислювальної складності. На підставі проведених досліджень запропоновано комбінований підхід, за якого як глобальну стратегію використано генетичний алгоритм, а для покращення знайдених розв’язків – алгоритм локального пошуку в його чотирьох варіаціях (Relocation, 2- opt, 3–permute і Link swap). Описано архітектуру та технологічний стек розробленого мобільного застосунку. Окреслено перспективу подальших досліджень, зокрема, пошук роз- в’язку задачі групового комівояжера, який дасть можливість усім учасникам групи манд- рівників спільно редагувати план подорожі, та задачі багатоагентної маршрутизації.

The paper deals with building optimal routes for individual trips under the influence of many factors and possible changes in the input parameters (such as weather conditions, traffic congestion, etc). We have analyzed four classes of algorithms for solving the traveling salesperson problem and evaluated their applicability in a tourist mobile application. The software should be a mobile application since only a few travelers take computers or laptops but most of them carry smartphones. The disadvantages of heuristic and metaheuristic algorithms have been considered. These include the dependence on the initial parameters, nonguaranteed optimal solutions, and the risks of being stuck in local optima. The exact methods have been discarded as unaffordable in mobile applications because of their computational complexity. Upon the conducted research, we propose a combined approach that uses the genetic algorithm as a global strategy and the four variations of the local search algorithm (Relocation, 2-opt, 3-permute, and Link swap) for refining the found solutions. The architecture and technology stack for the developed mobile application have been given, too. The future work implies searching for solutions to the group traveling salesman problem with the possibility of a joint trip plan edition by all the tourist group members and the multi-agent routing problem.