Approach to Construction of Optimal Tourist Routes Based on the Analysis of Existing Solutions

Abstract

The tourism sector is currently witnessing a significant transformation driven by technological automation. As this evolution unfolds, it is crucial to harness intelligent technologies not only to enhance the industry but also to simplify the experience for tourists themselves. One aspect of simplification that would greatly benefit every tourist exploring a new city is a tool capable of suggesting an optimal sequence for visiting the city's best attractions. This tool would take into account the personal preferences of the tourist as well as the spatial context of the city. In this research, we present findings that are pertinent to the development of such a tool and propose an initial approach to provide these functionalities. Our proposed solution involves applying a relevant variant of the Vehicle Routing Problem with Pickup and Delivery (VRPP) or the Traveling Salesman Problem (TSP) algorithm. By leveraging user-supplied preferences and extracting relevant information from external factors, we aim to assist users in planning their optimal viewing experiences. To realize this solution, we envision creating a modern web application utilizing cutting-edge technologies. The primary focus of this application would be to generate optimal tourist routes on a per-city basis. This means that the tool would prioritize suggesting viewing sequences for tourist attractions within the city where the user is staying or traveling through, as well as attractions in close proximity to the city. Our research aims to contribute to the ongoing wave of technological automation in the tourism sector by developing a tool that simplifies the planning process for tourists. By leveraging advanced algorithms and a modern web application, we strive to provide an optimal viewing sequence of attractions based on individual preferences and the spatial context of the city.

1. Introduction

Tourism has been closely connected to technological innovations since the dawn of Information and Communication technologies [ 2 ]. Analyzing the development of technology in tourism across the last 3 decades will provide a meaningful insight into the direction of consumer preferences and the emerging technologies used to improve their experience.

In the 1990s Information Technology (IT) started to be regarded as the primary interface between the tourists and the tourism suppliers.

It provided tools that allowed consumers to find and buy desired products and suppliers to offer and manage their products effectively on a global scale. The emerging Information and Communication Technologies (ICTs) at this time were said to be a "revolution for the tourism industry, comparable only to the introduction of the jet engine" [ 4 ]. Many sources from this period talk about a "new" tourist [ 4, 5 ]. A type of tourism consumer that is more independent and actively searches for unique and personalized experiences. This kind of tourist relies less on traditional travel agencies and has a distaste towards packaged tours and low flexibility experiences with a lack of possibilities for personal growth or "edutainment" [ 6 ].

In the 2000s the trends of the previous 10 years solidified, and tourists increasingly use online tools to organize their travels. They use online reservation systems and online travel agencies (Expedia), search engines and meta-search engines (Google, Kayak), destination management systems (visitbritain.com), social networks and forums (Wayn, TripAdvisor), sites for price comparison (Kelkoo), etc. [ 7 ].

In the early 2010s tourism became the largest category of services and goods purchased online [ 13 ]. The entire industry became even more focused on the tourists and their demands, which need to be effectively identified and fulfilled. In addition, the tourists revealed themselves to be even more active in managing their travel experiences and relations with other consumers [ 2 ]. Thus, continuing the major trends of previous decades.

In this paper we will first go over the recent research findings about the usage of online tourism tools and the tourist trip design problem (TTDP) in section 2. Related Work. Next, in section 3. Existing software solutions, the current state of online tools trying to simplify trip planning is analyzed and reviewed. In section 4. Existing methods an overview of different methods for solving TTDP algorithmically is presented. Then we propose our own method in section 5. Proposed method. A summary of past and future work is given in section 6. Conclusion at the end of the paper.

2. Related work

A 2018 study conducted in Italy [ 9 ] showcased an increased interest in collaborative consumption overall and an even higher increase for younger generations (Figure 1). The study compared millennials (generation Y, born 1980 - 1995) and iGen members (generation Z, born 1995 – 2009) from different regions of Italy (North, Center and South). The study shows a similar trend for the usage of online tools as a source of information for tourism choices (Figure 2).

.

Figure 1: Interest in collaborative consumption in different parts of Italy. Source: [ 1 ].

An exhaustive survey from 2014 [ 10 ] defines the tourist trip design problem (TTDP) as a routeplanning problem of trying to select points of interest (POIs) according to tourist preferences and outside factors such as weather, visiting hours and entrance fees. In context to our work the most interesting part is the overview of algorithmic approaches to solving this problem.

The authors list a set of input data that should be evaluated by an algorithm, the most relevant being the "profit" gained by visiting a location (this represents user preferences) and the time required to travel to and visit the location. One interesting take away from this paper is that the weight of a route between locations should be represented by time because we need to account for the fact that different attractions take longer/shorter to visit.

Next the authors go into detail on a variety of possible algorithmic solutions to construct optimal tourist routes from this data. They also mention some personal electronic tourist guides (PETs), which are mostly mobile and web applications that offer some form of tourist route planning. In our research we have found Furkot, Komoot, Wanderlog and Roadtrippers to be worth closer evaluation.

The algorithmic solutions can be separated into 2 categories [ 10 ]: • Single tour TTDP variants - these focus on creating a single route according to the tourist preferences and the external factors. • Multiple tour TTDP variants - these create a number of routes depending on the length of the tourist visit in days.

The single tour variants appear to be more relevant to the topic of this work and are the starting point even if multiple tours were to be implemented in the future. These variants are all singlecriterion variants of the travelling salesman problem with profits (TSPP), a bicriteria generalization of TSP [ 11 ]. The two criteria are maximizing profit (tourist satisfaction) and minimizing the travel cost (travel time).

The most relevant variant of TSPP is the orienteering problem (OP) which doesn’t minimize travel cost but keeps it under a certain value (e.g., total time that the tourist has for the tour) while still maximizing collected profit [ 12 ]. Solving the tourist trip design problem has been illustrated to be the most important application of the orienteering problem [ 13 ].

The multiple tour variants allow for a tourist stay at a location (e.g., a city) that spans multiple days and create a set of tourist routes, one for each day, so that user satisfaction is maximized over the course of the whole stay. This can be represented mathematically as a vehicle routing problem with profits (VRPP) [ 14 ]. The OP variation of the VRPP - meaning a multiple tour variant, where we have a cost constraint instead of trying to minimize the cost of the routes - is known as the team orienteering problem (TOP) [ 15 ]. Both the OP and TOP have several known extensions that allow for modelling more complex versions of the problem by taking into account more parameters (e.g., minimizing money spent on paid attractions and taking into account opening and closing hours) [ 10 ].

3. Existing software solutions

There are several personalized tourism helper applications, specifically in the area of route planning. In this section we mention the most relevant ones and how they compare to our proposed solution.

The tools Furkot [ 16 ] and Komoot [ 17 ] have similar interfaces and offer similar functionalities (Figure 3, Figure 4). They offer the planning of short to long range routes by adding waypoints from a map. Both maps have predefined POIs to choose from. Furkot provides additional functionality focused on booking hotels, while Komoot is focused more on sports tourism and the fitness benefits of given routes.

Neither application allows for automatic optimization of routes - waypoints are always appended to the end of the route. Additionally, the recommendation system the tools provide is fairly limited and doesn’t provide much help to a tourist.

Roadtrippers [ 18 ] is the most popular road trip planner. It provides a web interface with a map (Figure 5) where users can add waypoints to a route - no automatic route optimization is implemented. The application has an extensive list of categories of POIs, but for a smaller city like Bratislava no POIs are being offered. The application also seems to be focused on long distance trips spanning several cities.

Wanderlog [ 19 ] is a service that provides a large set of tourism helper functionalities ranging from personalized POI suggestions to collaborative planning with multiple users. It is also the only tool in our research that implements route optimization when creating itineraries, although without taking into account preferences or external factors - only minimizing the travelled distance – and requiring a subscription fee to be used (Figure 6). After trying, testing, and analyzing various online tourism helpers for creating tourist routes (or trips), we can conclude that there are several key issues that create space for a better solution, namely: • Lack of automatic route optimization - most tools don’t bother with reordering the POIs to an optimal order at all. Wanderlog offers this only as a paid ("Pro") feature. • Lack of personalized recommendations - most tools only allow users to pick the POIs manually, some offer popular recommendations, none of them offer recommendations based on previous trips or other personal preferences. • Lack of automatic route optimization based on external factors - even the tool that offers automatic route optimization does not take into account time spent at the location, current weather conditions, time of day or funds needed for the visit. Only travel time is considered.

Therefore, a new tool should be created that remedies all these insufficiencies and implements easy sharing, reviewing and collaboration of trips that is already present in tools like Wanderlog and TripAdvisor.

4. Existing methods

According to the newest review of the algorithmic solutions to the TTDP [ 20 ], there is a large variety of ways to solve this NP-hard problem, each either setting a different set of parameters and expected results or attempting to use a new approach to find out its effectiveness. We can separate these existing methods into categories to better understand the algorithm landscape. Based on the number of objectives there exist two types of methods [ 20 ]: • Single-objective - these methods only create itineraries with one objective in mind maximizing the benefit from visited POIs. Time and budget can serve as limits that cannot be overstepped. These are modeled as OPs or TOPs. • Multi-objective - these methods consider more than one objective when creating an optimal route, e.g., maximizing benefit from visited POIs and simultaneously minimizing budget cost [ 19 ], time spent etc.

Similarly, we can divide the methods in correspondence to the TTDP problem models into two other categories:

• Single-tour - these methods only create one route with the given set of parameters and POIs.

• Multi-tour - these methods create multiple routes with non-repeating POIs, usually to simulate multi-day stays.

Lastly, we can separate these methods based on the type of algorithm they use into three categories [ 19 ]:

• Exact - these methods use exact algorithms to find the perfect solution. In the most part they are impractical to solve any TTDP variant due to its complexity, particularly for higher numbers of POIs (above 50-60).

• Heuristic - using a heuristic can give us "good enough" results in short computational times. Usually, a greedy algorithm is applied.

• Metaheuristic - In a majority of cases a metaheuristic is necessary for the best results. In most cases a new result is achieved by combining different metaheuristics.

Figure 7 displays the overall tendency towards certain types of algorithms and what fields might be less explored. Particularly, multi-objective methods make up only a quarter of the current research.

One of the biggest holes in existing methods lies in the construction of group itineraries [ 20 ]. Most works don’t consider themselves with heterogeneous preferences of different tourists in a group. This is even more true for multi-objective methods. Furthermore, there is only one work that directly uses personal preferences of the tourist in the algorithm at all [ 23 ]. Most works assume the benefit of the POIs is already known.

Expósito et al. [ 24 ] have created a fuzzy version of the GRASP algorithm to solve the TTDP for a variation, where POIs are clustered by type only one POI from given cluster is visited. Although this is a very specific variation the algorithm gives good results.

In 2021 Ruiz-Meza et al. [ 25 ] have also worked on a fuzzy algorithm which is multi-objective and even considers heterogeneous preferences. These preferences are given and not extracted in any meaningful way. This method shows very long execution times (above 60 minutes) on excellent hardware with a small number of POIs.

Tlili et al. [ 26 ] have created a multi-tour single-objective solution using kNN clustering combined with simulated annealing (SA). They include user preferences that the user has to manually define. This solution proved quite efficient. Additionally, SA is one of the most effective methods to solve multi-objective TTDP as well [ 20 ].

5. Proposed method

Based on the above research we see a lot of potential in utilizing recent findings to make tourism simpler for a user. We propose a solution that would apply a relevant variant of the VRPP or TOP algorithm to allow users to plan optimal viewing experiences based on supplied and extracted preferences and external factors.

This solution would be in the form of a modern web application built using cutting- edge technologies. This application would focus on constructing optimal tourist routes on a per city basis. This means the focus will be on viewing tourist attractions in a city the user is staying in or traveling through, and in its vicinity. This way the scope of the work is manageable while also relevant.

On top of optimal routing the application would provide a simple recommendation system that would make the experience of the users smoother and allow for easier evaluation of unsure preferences when planning routes. This application will also allow the collection of relevant data that can then be used for tourism demand forecasting by other systems.

We propose an algorithmic solution using kNN clustering and simulated annealing metaheuristic to solve the TTDP for a group of tourists with heterogeneous prefer ences. This method will be multi-objective with at least 2 objectives - maximizing benefits and minimizing costs.

This will be a multi-route solution, thus creating routes for a multi-day stay. The routes will always begin and end at the same spot - presumably the place of stay. The group will never be split up, but the overall benefit of the group will be optimized due to the heterogeneous preferences.

First the POIs will be clustered using the kNN clustering algorithm, this will determine groups of POIs that are close together and can be viewed in one day [41]. Then, simulated annealing will be used to create optimal routes in these clusters.

If we let P = {p1, ..., pN} represent the set of POIs, S = {s1, ..., sN} the set of routes through these POIs and G = {u1, ..., uN} the group of tourists as a set of users, then we can define the problem as: | | | | where f is the profit function, c is the cost function and y is a binary variable that is 1 when the pj is visited in route Si and otherwise 0.

The personal preferences of individual tourists will be represented by a preference vector [ 27 ], which is easy to mine and can be compared to a vector for each POI constructed from manually assigned tags or by mining information about the POI and applying stop-word removal and stemming [ 27 ]. Each POI p has a relevance vector, ⃗vp ∈ [ 0, 1 ]|C| containing normalized relevance preference vector, ⃗vu ∈ [ 0, 1 ]|C|

As mentioned at the beginning of this chapter, the method will be implemented in a web application. We will now define some functional and non-functional requirements to specify the functionality of this implementation. We proposed functional and nonfunctional requirements for our system.

1. Functional requirements.

his routes. and ends at the place of stay.

FR01 Registration - the user can register and create an account on the app. FR02 Set a place of stay - the user can set where he is staying in the city during his trip. FR03 Set number of days - the user can set how many days he will be touring the city for FR06 Set must-see POIs - the user can manually set which locations must be included in FR07 Create routes - the app will create and optimal route for each day of stay that begins

FR08 Route sharing - the user can add other users to the trip. FR09 Preference setting - The user can set his own preferences using tag words. FR10 POI recommendation - the app will add POIs to the route based on the preferences

• • • • • • • • • • • of the entire group of users in the trip.

2. Non-functional requirements

take less than 1 second.

NFR01 Speed - creating routes must take at most 5 minutes. Other communication must NFR02 Secure communication - all communication with the app will be encrypted.

NFR03 Secure data - all stored private data will be encrypted.

NFR04 Documentation - the app will be properly documented.

6. Conclusion

In this paper, the development of tourism was explored to showcase the need for new tools in the field of trip planning. This relates closely to the tourist trip design problem for which we presented an overview of relevant algorithms, their basic categorization and principles.

After analyzing some existing tourism helpers, we have concluded that there is a lot of room for improvement in developing new methods of generating optimal tourist routes and creating practical solutions for tourists to use. Next, we explored the methods of solving the TTDP and discovered there is variety of approaches and algorithms with more still being developed and tested. With many combinations not being yet fully explored.

Lastly, we provided an initial overview of our proposed solution that will use simulated annealing in combination with clustering to provide optimal routing for groups of tourists. We described a web application that would facilitate this method and be used for evaluation. We mention some requirements of the application.

Future work consists of fully constructing and implementing the proposed method and its algorithms, testing it on different data sets and comparing it to other state of the art methods of solving the TTDP. Afterwards, the web application will be created and serve to put the method to practical use and evaluate it under real conditions.

Acknowledgements

The work reported here received funding from the EU's NextGenerationEU instrument through the Slovakia's Recovery and Resilience Plan, project No. 09I03-03-V01-00030..

References

[1] TUSSYADIAH , Iis . A review of research into automation in tourism: Launching the Annals of Tourism Research Curated Collection on Artificial Intelligence and Robotics in Tourism. Annals of Tourism Research . 2020 , vol. 81 , p. 102883 .

[2] NAVÍO-MARCO , Julio; RUIZ-GÓMEZ, Luis Manuel; SEVILLA-SEVILLA, Claudia. Progress in information technology and tourism management: 30 years on and 20 years after the internet-Revisiting Buhalis & Law's landmark study about eTourism . Tourism management. 2018 , vol. 69 , pp. 460 - 470 .

[3] Yehorchenkova , N. ; Yehorchenkov , V ; Finka, M. ; Ondrejička , V. ; Jamečný V. ; "Concept of Smart Twin City Bratislava" . 2023 IEEE European Technology & Engineering Management Summit , 20 - 22 April 2023, Kaunas University of Technology, Lithuania, p. 46 - 51

[4] TESLIA , I.; YEHORCHENKOVA , N.; YEHORCHENKOV , O.; KLEVNA , I.; KATAIEVA, Y. ; KLEVANNA, G. Development of reflex technology of action identification in project planning systems . International Conference on Smart Information Systems and Technologies, NurSultan , 28 - 30 April 2022 , ISBN 978-166546790-2, https://doi.org/ 10.1109/SIST54437. 2022 .9945727

[5] BUHALIS , Dimitrios et al. Trends in information technology and tourism. Trends in outdoor recreation, leisure and tourism . 2000 , pp. 47 - 61 .

[6] BUHALIS , Dimitrios; LAW, Rob. Progress in information technology and tourism management: 20 years on and 10 years after the Internet-The state of eTourism research . Tourism management. 2008 , vol. 29 , no. 4 , pp. 609 - 623 .

[7] BUHALIS , Dimitrios. Strategic use of information technologies in the tourism industry . Tourism management. 1998 , vol. 19 , no. 5 , pp. 409 - 421 .

[8] ABOU-SHOUK , Mohamed; LIM, Wai Mun; MEGICKS, Phil. Internet adoption by travel agents: A case of Egypt . International Journal of Tourism Research . 2013 , vol. 15 , no. 3 , pp. 298 - 312 .

[9] MONACO, Salvatore. Tourism and the new generations: emerging trends and social implications in Italy . Journal of Tourism Futures . 2018 , vol. 4 , no. 1 , pp. 7 - 15 .

[10] GAVALAS , Damianos; KONSTANTOPOULOS, Charalampos; MASTAKAS, Konstantinos; PANTZIOU, Grammati . A survey on algorithmic approaches for solving tourist trip design problems . Journal of Heuristics . 2014 , vol. 20 , no. 3 , pp. 291 - 328 .

[11] KELLER, CP; GOODCHILD, MF. The multiobjective vending problem: a generalization of the travelling salesman problem . Environment and Planning B: Planning and Design . 1988 , vol. 15 , no. 4 , pp. 447 - 460 .

[12] TSILIGIRIDES , Theodore. Heuristic methods applied to orienteering . Journal of the Operational Research Society . 1984 , vol. 35 , no. 9 , pp. 797 - 809 .

[13] GUNAWAN , Aldy; LAU, Hoong Chuin; VANSTEENWEGEN , Pieter. Orienteering problem: A survey of recent variants, solution approaches and applications . European Journal of Operational Research . 2016 , vol. 255 , no. 2 , pp. 315 - 332 .

[14] ARCHETTI , Claudia; HERTZ, Alain; SPERANZA, Maria Grazia . Metaheuristics for the team orienteering problem . Journal of Heuristics . 2007 , vol. 13 , no. 1 , pp. 49 - 76 .

[15] CHAO , I-Ming; GOLDEN , Bruce L ; WASIL, Edward A . The team orienteering problem . European journal of operational research . 1996 , vol. 88 , no. 3 , pp. 464 - 474 .

[16] Furkot [https://trips.furkot.com/ui]. URL: Accessed: 2022-12-12.

[17] komoot [https://www.komoot.com/plan]. URL: Accessed: 2022-12-12.

[18] Roadtrippers [https://roadtrippers.com/]. URL: Accessed: 2022 -12-12.

[19] Wanderlog [https://wanderlog.com/]. URL: Accessed: 2022 -12-12.

[20] RUIZ-MEZA , José; MONTOYA-TORRES, Jairo R. A systematic literature review for the tourist trip design problem: extensions, solution techniques and future research lines . Operations Research Perspectives . 2022 , p. 100228 .

[21] YARMILKO , A. ; ROZLOMII, I.; KOSENYUK, H. Hash Method for Information Stream's Safety in Dynamic Cooperative Production System . In International scientific-practical conference, 2022 , pp. 173 - 183

[22] WISITTIPANICH , Warisa; BOONYA, Chanagan. Multi-objective tourist trip design problem in chiang mai city . In: IOP Conference Series: Materials Science and Engineering. IOP Publishing , 2020 , vol. 895 , p. 012014 . No. 1 .

[23] BRILHANTE , Igo; MACEDO, Jose Antonio; NARDINI, Franco Maria; PEREGO , Raffaele; RENSO, Chiara. Where shall we go today? Planning touristic tours with TripBuilder . In: Proceedings of the 22nd ACM international conference on Information & Knowledge Management . 2013 , pp. 757 - 762 .

[24] EXPÓSITO , Airam; MANCINI, Simona; BRITO, Julio; MORENO, José A . A fuzzy GRASP for the tourist trip design with clustered POIs . Expert Systems with Applications . 2019 , vol. 127 , pp. 210 - 227 .

[25] RUIZ-MEZA , José; BRITO, Julio; MONTOYA-TORRES, Jairo R . Multiobjective fuzzy tourist trip design problem with heterogeneous preferences and sustainable itineraries . Sustainability . 2021 , vol. 13 , no. 17 , p. 9771 .

[26] TLILI , Takwa; KRICHEN, Saoussen . A simulated annealing-based recommender system for solving the tourist trip design problem . Expert Systems with Applications . 2021 , vol. 186 , p. 115723 .

[27] SOUFFRIAU , Wouter; VANSTEENWEGEN, Pieter; VERTOMMEN, Joris; BERGHE, Greet Vanden; OUDHEUSDEN , Dirk Van . A personalized tourist trip design algorithm for mobile tourist guides . Applied Artificial Intelligence . 2008 , vol. 22 , no. 10 , pp. 964 - 985 .