Modified ant algorithm for constructing a time-limited tourist route

The article considers the task of building a tourist route with predetermined points of the beginning and end of the route. The objects are divided into two types. The first ones are mandatory, which should certainly be included in the resulting route. And the second ones are additional ones, which are not necessary to visit. The route is formed taking into account the priorities set for the objects by the tourist, based on his interests and preferences, while the total time of visiting the objects should not exceed the specified deadline for arrival at the end point of the route. To solve this problem, the article proposes an approach based on the construction of a route by known methods along the main objects and its further expansion using ant strategies. To this end, the concept of "satiety" of the ant and the probability of returning to the main route are introduced, so that it is possible to control the time reserve. At the end of the article, we present the results of a computational experiment aimed at assessing the influence of the ant algorithm parameters on the resulting route and developing recommendations for adjusting these parameters depending on the size of the problem. In addition, a comparative analysis of the routes obtained by the proposed algorithm and the exact branch-and-bound method for a given set of objects is carried out, based on the results of which a conclusion is drawn about the effectiveness of the proposed algorithm.

1. Geunes J. Operations Planning: Mixed Integer Optimization Models (Operations Research Series). Boca Raton: CRC Press; 2014. 218 p. https://doi.org/10.1201/b17414

2. Ntakolia C., Iakovidis D.K. A swarm intelligence graph-based pathfinding algorithm (SIGPA) for multi-objective route planning. Computers & Operations Research. 2021;133. https://doi.org/10.1016/j.cor.2021.105358

3. Suchkova T.M., Volkova L.L. On developing a recommender system for touristic routes basing on user's thematic preferences. In: Artificial Intelligence in Management, Control, and Data Processing Systems: Proceedings of the II All-Russian scientific conference: in 5 volumes: Volume 1, 27-28 April 2023, Moscow, Russia. Moscow: Publishing House «KDU»; 2023. P. 145–150. (In Russ.).

4. Poletajkin A.N. Computer system for compiling tourist routes by method of genetic algorithms. In: Tekhnicheskaya ekspluatatsiya vodnogo transporta: problemy i puti razvitiya: Materialy Vtoroi mezhdunarodnoi nauchno-tekhnicheskoi konferentsii, 23-25 October 2019, Petropavlovsk-Kamchatsky, Russia. Petropavlovsk-Kamchatsky: Kamchatka State Technical University; 2020. P. 158–162. (In Russ.).

5. Pasandi L., Hooshmand M., Rahbar M. Modified A* Algorithm integrated with ant colony optimization for multi-objective route-finding; case study: Yazd. Applied Soft Computing. 2021;113. https://doi.org/10.1016/j.asoc.2021.107877

6. Zheng W., Liao Zh., Qin J. Using a four-step heuristic algorithm to design personalized day tour route within a tourist attraction. Tourism Management. 2017;62:335–349. https://doi.org/10.1016/j.tourman.2017.05.006

7. Ruiz-Meza J., Brito J., Montoya-Torres J.R. A GRASP-VND algorithm to solve the multi-objective fuzzy and sustainable Tourist Trip Design Problem for groups. Applied Soft Computing. 2022;131. https://doi.org/10.1016/j.asoc.2022.109716

8. Korbut A.A., Finkel'shtein Yu.Yu. Diskretnoe programmirovanie. Moscow: Nauka; 1969. 368 p. (In Russ.).

9. Żak A. Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs. European Journal of Combinatorics. 2013;34(4):724–735. https://doi.org/10.1016/j.ejc.2012.10.009

10. Rodzin S., Rodzina O., El-Khatib S. Hybrid segmentation ant algorithms of medical images. Vestnik Chuvashskogo universiteta. 2017;(3):262–272. (In Russ.).

11. Medvedev S.N., Medvedeva O.A. Modified ant colony optimization algorithm for solving the vehicle routing problem with a given load capacity. Journal of Physics: Conference Series. 2021;1902. https://doi.org/10.1088/1742-6596/1902/1/012123