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, non-guaranteed 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.
[1] Z. Malcienė, L. Skauronė, "Application of Information Systems in Tourism and Leisure Sector", Int. Jou. Soc. Hum. Inve, Iss. 6, No 2, pp. 5341-5346, Feb. 2019. https://doi.org/10.18535/ijsshi/v6i2.11
[2] F. Ricci, "Recommender Systems in Tourism", in Handbook of e-Tourism, Cham, Germany, Springer, 2022, pp. 457-474. https://doi.org/10.1007/978-3-030-48652-5_26
[3] J. Li, Z. Luo, H. Huang, Z. Ding, "Towards Knowledge-Based Tourism Chinese Question Answering System", Mathematics, Iss. 10, No. 4, p. 664, 2022. https://doi.org/10.3390/math10040664
[4] B. Ojokoh, "A Review of Question Answering Systems", J. of Web Eng., Iss. 17, No. 8, pp. 717-758, Jan. 2019. https://doi.org/10.13052/jwe1540-9589.1785
[5] Y. Sui, "Question Answering System Based on Tourism Knowledge Graph", in J. Phys. Conf. Ser., Wuhan, China, p. 012064, Mar. 2021. https://doi.org/10.1088/1742-6596/1883/1/012064
[6] J. A. Orama, A. Huertas, J. Borràs, A. Moreno, S. Clavé, "Identification of Mobility Patterns of Clusters of City Visitors: An Application of Artificial Intelligence Techniques to Social Media Data", Appl. Sci., Iss. 12, No. 12, p. 5834, Jun. 2022. https://doi.org/10.3390/app12125834
[7] B. Rathnayake, D. Kasthurirathna, "Generating an Optimal Tour Plan with Optimization", Int. J. of Comp. Appl., Iss. 184, No. 38, pp. 31-39, Dec. 2022. https://doi.org/10.5120/ijca2022922473
[8] R. A. Sánchez-Ancajima, M. Jiménez-Carrión, F. Gutierrez, A. O. Hermenegildo-Alfaro, M. A. Saavedra-López, "Applications of Intelligent Systems in Tourism: Relevant Methods", J. of Internet Services and Information Security, Iss. 13, No. 1, pp. 54-63, Mar. 2023. https://doi.org/10.58346/JISIS.2023.I1.006
[9] Y. Chen, X. Zheng, Z. Fang, Y. Yu, "Research on Optimization of Tourism Route Based on Genetic Algorithm", J. Phys. Conf. Ser, Iss. 1575, No. 1, p. 012027, Jun. 2020. https://doi.org/10.1088/1742-6596/1575/1/012027
[10] E. Saeki, S. Bao, T. Takayama, N. Togawa, "Multi-Objective Trip Planning Based on Ant Colony Optimization Utilizing Trip Records", IEEE Access, Iss. 10, pp. 127825-127844, Dec. 2022.
https://doi.org/10.1109/ACCESS.2022.3227431
[11] H. Sun, Y. Chen, J. Ma, Y. Wang, X. Liu, J. Wang, "Multi-Objective Optimal Travel Route Recommendation for Tourists by Improved Ant Colony Optimization Algorithm", J. of Advanced Transportation, Vol. 2022, p. 6386119, Oct. 2022. https://doi.org/10.1155/2022/6386119
[12] L. Sengupta, R. Mariescu-Istodor, P. Fränti, "Which Local Search Operator Works Best for the Open-Loop TSP?", Appl. Sci, Iss. 9, No. 19, p. 3985, Sept. 2019. https://doi.org/10.3390/app9193985