Optimization of the tourist route by solving the problem of a salesman
Keywords:
tourist route, Transcarpathian region, tour operator, traveling salesman problem, optimization, solution search
Abstract
The article is devoted to the problem of constructing the optimal transport route of a bus excursion tour of a tour operator according to the minimal length criterion. Transportation expenses are an important part of a bus tour cost, and their minimization is a required condition for route development and planning. To solve this problem, the authors used the tour route calculating method as a kind of transport task, namely the task of the salesman. To solve this problem, one of the varieties of the transport problem, namely the salesman traveling problem, is applied. The essence of the traveling salesman problem is to find the shortest route between cities, if the distances between them are known. The beginning of the route and its end coincide, that is, the route is cyclic. The most popular in Ukraine sightseeing tours of tour operators to the Transcarpathian region are taken for the optimization. A mathematical model of the traveling salesman problem is made to construct an optimal transport route. The solution was found using the Microsoft Excel’s Solver add-in application program package. To solve the problem by this method, it was reduced to a special form and additional variables were introduced. The analysis helped the tour operator to check the existing sightseeing bus routes by the minimal length criterion. The results allowed making assumptions about the need to change some popular routes of Ukrainian tour operators in order to reduce transport costs. The method of bus tours evaluation of tour operators according to the minimal length criterion allows to check the tourist transportation optimality while planning the route and developing their own tourist product. The introduction of modern digital technologies and software to optimize the territorial organization of tourist routes is proposed, which will help tour operators of Ukraine in the design of bus tourist trips to nature and recreational locations in tourist regions. The development of an optimal model for the transportation of tourists on the highways and the reduction of their costs for consumption of transport services will contribute to the development of tourist trips in Ukraine. The necessity of using methods of geolocation of tourist resources for the construction of routes for visiting natural and cultural-historical monuments and tourist centers has been determined. The application of the proposed method will allow tour operators to reduce transport costs and, as a consequence, the total cost of the tourist product.References
1. Bellman, R., 1958. On a routing problem, Quarterly of Applied Mathematics, 87–90. Retrieved from: https://www.jstor.org/stable/43634538?seq=1
2. Da Silva, A. A., Morabito, R., Pureza V., 2018. Optimization approaches to support the planning and analysis of travel itineraries, Expert Systems with Applications, 112, 321–330, DOI:10.1016/j.eswa.2018.06.045
3. Dantzig, G., 1951. Application of the simplex method to a transportation problem. In: Koopmans, T. (Ed.), Activity Analysis of Production and Allocation. John Wiley and Sons, 359–373.
4. Dijkstra, E. W., 1959. A note on two problems in connexion with graphs, Springer Science+Business Media, 1 (1), 269– 271, DOI: 10.1007/BF01386390
5. Dorigo, M., Gambardella, L.M., 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary
Computation, 1 (1), 53–66, DOI: 10.1109/4235.585892.
6. Friggstad, Z., Gollapudi, S., Kollias, K., Sarlos, T., Swamy, C., & Tomkins, A., 2018. Orienteering algorithms for generating travel itineraries, In Proceedings of the
Eleventh ACM International Conference on Web Search and Data Mining, 180-188, ACM, DOI: 10.1145/ 3159652.3159697.
7. Google Maps. Retrieved from: https://www.google.com.ua maps
8. Grytsevych, V. S., Podvirna, Kh. Ye., Senkiv, M. I., 2019. Motor transport network of western region of Ukraine as a factor of development of tourism industry, Visnyk of
V. N. Karazin Kharkiv National University, series “Geology. Geography. Ecology”, 50, 91-100, DOI: https://doi.org/10.26565/2410-7360-2019-50-07
9. Helsgaun, K., 2014. Solving arc routing problems using the linkernighan-helsgaun algorithm. Roskilde University. Retrieved from: http://webhotel4.ruc.dk/~keld/research/GLKH/ARP_report.pdf
10. Hitchcock, F., 1941. The Distribution of a Product from Several Sources to Numerous Localities, Journal of Mathematics and Physics, 20 (1-4), 224-230, DOI:10.1002/sapm1941201224.
11. Hopfield, J.J., 1982. Neural networks and physical systems with emergent collective computational abilities, Proceedings of National Academy of Sciences, 79 (8),
2554–2558, DOI: 10.1073 / pnas.79.8.2554.
12. Hunziker, W., 1972. Le tourisme: caracteristiques principales (in French). Berne: Gurten.
13. Karta Zakarpatskoy oblasti s dostoprimechatel’nostyami. [Map of Transcarpathian region with attractions]. Retrieved from: http://www.karpatline.ru/maps_of_the_
carpathians/zakarpatie_region
14. Kaspar, C., 2018. Management der Verkehrsunternehmungen, De Gruyter Oldenbourg, Auflage: Reprint 2018.
15. Kaygili, S., Sinanoglu, D., Aksoy, E., & Sasmaz, A., 2018. Geoturism: Some Examples from Turkey. Journal of Geology, Geography and Geoecology, 26(1), 79-87.
DOI: https://doi.org/10.15421/111809
16. Kiptenko, V., Lyubitseva, O., Malska, M., Rutynskiy, M., Zan’ko, Y., Zinko, J., 2017. Geography of Tourism of Ukraine. In: Widawski K., Wyrzykowski J. (eds). The Geography of Tourism of Central and Eastern European Countries. Springer, Cham, DOI: https://doi.org/10.1007/978-3-319-42205-3_13
17. Little, J.D.C., Murty, K.G., Sweeney, D.W., and Karel, C., 1963. An algorithm for the Traveling Salesman Problem, Operations Research, 11, 972–989.
18. Mao, X., 2019. Study on ant colony optimization algorithm for “one-day tour” traffic line. Cluster Computing, 22, 3673–3680. Retrieved from: https://doi.org/10.1007/
s10586-018-2217-9
19. Matviychuk, L.Y., Lepky, M. I., Kostenko, S.A., 2016. Shlyakhy modernizatsiyi ta vdoskonalennya turystychnykh marshrutiv za dopomohoyu novitnikh tekhnolohiy. [Ways of modernization and improvement of tourist routes using the latest technology]. Retrieved from: https://msu.edu.ua/wp-content/uploads/visn/n21.pdf (in Ukrainian).
20. Mikhailov, S.A., 2019. Intelligent tourist assistance system: service-oriented architecture and implementation, Scientific and Technical Journal of Information
Technologies, Mechanics and Optics, 19 (3), 499–507. (in Russian), DOI: 10.17586/2226-1494-2019-19-3-499-507.
21. Monge, G., 1781. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, Photocopies du mémoire paru dans Histoire de l’Académie Royale des sciences, Année 1781, Paris, Imp. Royale, 1784, 666-704. Retrieved from: http://www.calames.abes.fr/pub/#details?id=Calames-201176107446381241
22. Nezdoyminov, S., Milashovska, O., 2019. River travel as a direction for the development of tourism in Ukraine, Journal of Geology, Geography and Geoecology, 28(1), 148-158. https://doi.org/https://doi.org/10.15421/111916
23. Padmabati, G., Monalisha, P., 2017. Optimization in Fuzzy Economic Order Quantity (FEOQ) Model with Promotional Effort Cost and Units Lost Due To Deterioration, LogForum 13(1), article 6, DOI:10.17270/J.LOG.2017.1.6
24. Pierdicca, R., Paolanti, M., Frontoni, E., 2019. eTourism: ICT and its role for tourism management, Journal of Hospitality and Tourism Technology, 10 (1), 90-106, DOI: 10.1108/JHTT-07-2017-0043.
25. Rani, S., Kholidah, K. N., Huda, S. N., 2018. A development of travel itinerary planning application using traveling salesman problem and k-means clustering approach,
[in:] Proceedings of the 2018 7th International Conference on Software and Computer Applications, ACM, 327-331, DOI: 10.1145/3185089.3185142.
26. Statistical yearbook: Transport and Communication of Ukraine – 2018, 2019. Retrieved from: http://www.ukrstat.gov.ua/druk/publicat/kat_u/2019/zb/08/zb_tr2018pdf.pdf
27. Szwarc, K., Boryczka, U., Twaróg, S., Szołtysek, J., 2019. A comprehensive study of classical heuristic algorithms used in the process of solving Transportation Problem, LogForum, 15 (3), 390-401, DOI: 10.17270/J.LOG.2019.346.
28. Ukrayina pokrashchyla svoyi pozytsiyi u povtornomu vidviduvanni naybilʹsh pryvablyvykh dlya turystiv krayin u 2019 rotsi, 2019. [Ukraine has improved its position in reiting the most attractive countries for tourists in 2019]. Retrieved from: https://delo.ua/econonomyandpoliticsinukraine/ukraina-uluchshilasvoi-pozicii-v-rejtinge-samyh-357611/ (in Russian).
29. Zakarpattia oblast [Transcarpathian region]. Retrieved from: http://ruraltourism.com.ua
30. Zheng, W., Liao, Z., 2019. Using a heuristic approach to design personalized tour routes for heterogeneous tourist groups, Tourism Management, 72, 313-325, DOI:
10.1016 / j.tourman.2018.12.013.
31. Walker, J. R., 2009. Introduction to Hospitality, Prentice Hall.
32. Warm weekend: Transcarpathian region and Thermal Waters. Retrieved from: https://www.accordtour.com/tours/1118340/ukraina_regulyarnyye_tury/ukraina
2. Da Silva, A. A., Morabito, R., Pureza V., 2018. Optimization approaches to support the planning and analysis of travel itineraries, Expert Systems with Applications, 112, 321–330, DOI:10.1016/j.eswa.2018.06.045
3. Dantzig, G., 1951. Application of the simplex method to a transportation problem. In: Koopmans, T. (Ed.), Activity Analysis of Production and Allocation. John Wiley and Sons, 359–373.
4. Dijkstra, E. W., 1959. A note on two problems in connexion with graphs, Springer Science+Business Media, 1 (1), 269– 271, DOI: 10.1007/BF01386390
5. Dorigo, M., Gambardella, L.M., 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary
Computation, 1 (1), 53–66, DOI: 10.1109/4235.585892.
6. Friggstad, Z., Gollapudi, S., Kollias, K., Sarlos, T., Swamy, C., & Tomkins, A., 2018. Orienteering algorithms for generating travel itineraries, In Proceedings of the
Eleventh ACM International Conference on Web Search and Data Mining, 180-188, ACM, DOI: 10.1145/ 3159652.3159697.
7. Google Maps. Retrieved from: https://www.google.com.ua maps
8. Grytsevych, V. S., Podvirna, Kh. Ye., Senkiv, M. I., 2019. Motor transport network of western region of Ukraine as a factor of development of tourism industry, Visnyk of
V. N. Karazin Kharkiv National University, series “Geology. Geography. Ecology”, 50, 91-100, DOI: https://doi.org/10.26565/2410-7360-2019-50-07
9. Helsgaun, K., 2014. Solving arc routing problems using the linkernighan-helsgaun algorithm. Roskilde University. Retrieved from: http://webhotel4.ruc.dk/~keld/research/GLKH/ARP_report.pdf
10. Hitchcock, F., 1941. The Distribution of a Product from Several Sources to Numerous Localities, Journal of Mathematics and Physics, 20 (1-4), 224-230, DOI:10.1002/sapm1941201224.
11. Hopfield, J.J., 1982. Neural networks and physical systems with emergent collective computational abilities, Proceedings of National Academy of Sciences, 79 (8),
2554–2558, DOI: 10.1073 / pnas.79.8.2554.
12. Hunziker, W., 1972. Le tourisme: caracteristiques principales (in French). Berne: Gurten.
13. Karta Zakarpatskoy oblasti s dostoprimechatel’nostyami. [Map of Transcarpathian region with attractions]. Retrieved from: http://www.karpatline.ru/maps_of_the_
carpathians/zakarpatie_region
14. Kaspar, C., 2018. Management der Verkehrsunternehmungen, De Gruyter Oldenbourg, Auflage: Reprint 2018.
15. Kaygili, S., Sinanoglu, D., Aksoy, E., & Sasmaz, A., 2018. Geoturism: Some Examples from Turkey. Journal of Geology, Geography and Geoecology, 26(1), 79-87.
DOI: https://doi.org/10.15421/111809
16. Kiptenko, V., Lyubitseva, O., Malska, M., Rutynskiy, M., Zan’ko, Y., Zinko, J., 2017. Geography of Tourism of Ukraine. In: Widawski K., Wyrzykowski J. (eds). The Geography of Tourism of Central and Eastern European Countries. Springer, Cham, DOI: https://doi.org/10.1007/978-3-319-42205-3_13
17. Little, J.D.C., Murty, K.G., Sweeney, D.W., and Karel, C., 1963. An algorithm for the Traveling Salesman Problem, Operations Research, 11, 972–989.
18. Mao, X., 2019. Study on ant colony optimization algorithm for “one-day tour” traffic line. Cluster Computing, 22, 3673–3680. Retrieved from: https://doi.org/10.1007/
s10586-018-2217-9
19. Matviychuk, L.Y., Lepky, M. I., Kostenko, S.A., 2016. Shlyakhy modernizatsiyi ta vdoskonalennya turystychnykh marshrutiv za dopomohoyu novitnikh tekhnolohiy. [Ways of modernization and improvement of tourist routes using the latest technology]. Retrieved from: https://msu.edu.ua/wp-content/uploads/visn/n21.pdf (in Ukrainian).
20. Mikhailov, S.A., 2019. Intelligent tourist assistance system: service-oriented architecture and implementation, Scientific and Technical Journal of Information
Technologies, Mechanics and Optics, 19 (3), 499–507. (in Russian), DOI: 10.17586/2226-1494-2019-19-3-499-507.
21. Monge, G., 1781. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, Photocopies du mémoire paru dans Histoire de l’Académie Royale des sciences, Année 1781, Paris, Imp. Royale, 1784, 666-704. Retrieved from: http://www.calames.abes.fr/pub/#details?id=Calames-201176107446381241
22. Nezdoyminov, S., Milashovska, O., 2019. River travel as a direction for the development of tourism in Ukraine, Journal of Geology, Geography and Geoecology, 28(1), 148-158. https://doi.org/https://doi.org/10.15421/111916
23. Padmabati, G., Monalisha, P., 2017. Optimization in Fuzzy Economic Order Quantity (FEOQ) Model with Promotional Effort Cost and Units Lost Due To Deterioration, LogForum 13(1), article 6, DOI:10.17270/J.LOG.2017.1.6
24. Pierdicca, R., Paolanti, M., Frontoni, E., 2019. eTourism: ICT and its role for tourism management, Journal of Hospitality and Tourism Technology, 10 (1), 90-106, DOI: 10.1108/JHTT-07-2017-0043.
25. Rani, S., Kholidah, K. N., Huda, S. N., 2018. A development of travel itinerary planning application using traveling salesman problem and k-means clustering approach,
[in:] Proceedings of the 2018 7th International Conference on Software and Computer Applications, ACM, 327-331, DOI: 10.1145/3185089.3185142.
26. Statistical yearbook: Transport and Communication of Ukraine – 2018, 2019. Retrieved from: http://www.ukrstat.gov.ua/druk/publicat/kat_u/2019/zb/08/zb_tr2018pdf.pdf
27. Szwarc, K., Boryczka, U., Twaróg, S., Szołtysek, J., 2019. A comprehensive study of classical heuristic algorithms used in the process of solving Transportation Problem, LogForum, 15 (3), 390-401, DOI: 10.17270/J.LOG.2019.346.
28. Ukrayina pokrashchyla svoyi pozytsiyi u povtornomu vidviduvanni naybilʹsh pryvablyvykh dlya turystiv krayin u 2019 rotsi, 2019. [Ukraine has improved its position in reiting the most attractive countries for tourists in 2019]. Retrieved from: https://delo.ua/econonomyandpoliticsinukraine/ukraina-uluchshilasvoi-pozicii-v-rejtinge-samyh-357611/ (in Russian).
29. Zakarpattia oblast [Transcarpathian region]. Retrieved from: http://ruraltourism.com.ua
30. Zheng, W., Liao, Z., 2019. Using a heuristic approach to design personalized tour routes for heterogeneous tourist groups, Tourism Management, 72, 313-325, DOI:
10.1016 / j.tourman.2018.12.013.
31. Walker, J. R., 2009. Introduction to Hospitality, Prentice Hall.
32. Warm weekend: Transcarpathian region and Thermal Waters. Retrieved from: https://www.accordtour.com/tours/1118340/ukraina_regulyarnyye_tury/ukraina
Published
2020-10-11
How to Cite
Shinkarenko, V., Nezdoyminov, S., Galasyuk, S., & Shynkarenko, L. (2020). Optimization of the tourist route by solving the problem of a salesman. Journal of Geology, Geography and Geoecology, 29(3), 572-579. https://doi.org/https://doi.org/10.15421/112052
Section
Статьи
