Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397

Issue N3 2024 year

DOI: 10.17587/prin.15.134-145
System for Selecting Tourist Routes Based on Genetic Programming
A. K. Khoroshavin, Postgraduate Student, a.khoroshavin@g.nsu.ru, Novosibirsk State University, Novosibirsk, 630090, Russian Federation
Corresponding author: Aleksey K. Khoroshavin, Postgraduate Student, Novosibirsk State University, Novosibirsk, 630090, Russian Federation, E-mail: a.khoroshavin@g.nsu.ru
Received on December 17, 2023
Accepted on January 17, 2024

One of the most important tasks in tourism is helping tourists plan a trip to a given place. Since it is impossible to visit all places, tourists try to be rational and choose what they find most acceptable and attractive. Each plan has limitations (e. g., length of tour, limited budget) and preferences (e. g., art, culture, historical sites, architecture, modernism) that should be considered when planning your travel trip. This is a special case of the Orientation problem — Tourist trip design problem. The goal is to maximize the total score achieved within a given tour duration limit. This paper focuses on developing a recommendation system that considers users limitations during tour planning and their preferences. Since this problem is an NP-hard problem, heuristic algorithms such as the genetic algorithm (GA) are well suited for solving it. However, this algorithm can take a very long time to find the optimal solution, so this article focuses on developing a greedy strategy of GA to find optimal or near-optimal solutions. Instead of random genetic transformations, the algorithm consciously modifies optimal routes in order to find the desired tour for the users in a shorter time. After this, the developed algorithm was compared with a GA using various generated user profiles. Over 700 locations in Novosibirsk were used as a dataset for making recommendations. These modifications made it possible to obtain optimal routes faster than the standard implementation of the genetic algorithm.

Keywords: recommender system, genetic algorithm, fitness function, routes, selection criteria, time constraints, over-specialization problem, category hierarchy, crossover, mutation
pp. 134–145
For citation:
Khoroshavin A. K. System for Selecting Tourist Routes Based on Genetic Programming, Programmnaya Ingeneria, 2024, vol. 15, no. 3, pp. 134—145. DOI: 10.17587/prin.15.134-145 (in Russian).
References:
    • Khoroshavin A. K. Reducing the influence of the cold start problem in the formation of tourist recommendations, Materials of the IX International Conference "Knowledge-Ontologies-Theories" (ZONT-2023), 2023, pp. 272—278, (in Russian).
    • Vansteenwegen P., Souffriau W., Vanden Berghe G., Van Oudheusden D. The City Trip Planner: An expert system for tourists, Expert Systems with Applications, 2011, vol. 38, no. 6, pp. 6540 — 6546. DOI: 10.1016/j.eswa.2010.11.085.
    • Brito J., Expiosito-Marquez A., Moreno J. A. A fuzzy GRASP algorithm for solving a tourist trip design problem, In 2017 IEEE international conference on fuzzy systems (FUZZ-IEEE), Naples, Italy, 2017, pp. 1—6. DOI: 10.1109/FUZZ-IEEE.2017.8015656.
    • Castillo L., Armengol E., Onaindia E. et al. SAMAP: A user-oriented adaptive system for planning tourist visits, Expert Systems with Applications, 2008, vol. 34, no. 2, pp. 1318—1332. DOI:. 10.1016/j.eswa.2006.12.029.
    • Paulavicius R., Stripinis L., Sutaviciute S. et al. A novel greedy genetic algorithm-based personalized travel recommendation system, Expert Systems with Applications, 2023, vol. 230, article 120580. DOI: 10.1016/j.eswa.2023.120580.
    • Vansteenwegen P., Souffriau W., Oudheusden D. V. The orienteering problem: A survey, European Journal of Operational Research, 2011, vol. 209, no. 1, pp. 1—10. DOI: 10.1016/j.ejor.2010.03.045.
    • Golden B. L., Levy L., Vohra R. The orienteering problem, Naval Research Logistics, 1987, vol. 34, no. 3, pp. 307—318. DOI:. 10.1002/1520-6750(198706)34:33.0.CO;2-D.
    • Stitini O., Kaloun S., Bencharef O. An Improved Recom-mender System Solution to Mitigate the Over-Specialization Problem Using Genetic Algorithms, Electronics, 2022, vol. 11, article 242. DOI: 10.3390/electronics11020242.
    • Xin-She Yang. Nature-Inspired Optimization Algorithms, Elsevier, 2014, Chapter 14, pp. 197—211.
    • Zitzler E. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach / E. Zitzler, L. Thiele, IEEE Transactions on evolutionary computation, 1999, vol. 3, no. 4, pp. 257—271. DOI: 10.1109/4235.797969.
    • Holland J. P. Adaptation in Natural and Artificial Systems. An Introductory Analysis with Application to Biology, Control and Artificial Intelligence, University of Michigan, 1975, 210 p.
    • Zitzler E., Laumanns M., Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm, TIK report, 2001, vol. 103. DOI: 10.3929/ethz-a-004284029.