A new mathematical model and a heuristic algorithm for the tourist trip design problem under new constraints: a real-world application

Abstract

The tourist trip design problem (TTDP) is about to generate routes for tourists to maximize the points of interest (POIs) visited within specific time windows. In this study, new constraints: budget, weather and break are considered. First, the budget is required for entrance fees and the distance between two points where a taxi has to be used. Additionally, the expense of the break was taken into account. Then, the weather was considered for summer and for other seasons. On a summer day, tourists are likely to prefer visiting POIs, which are indoor areas, between specific times e.g. 11 a.m. to 3 p.m. to protect against the side effects of the sun. Furthermore, tourists need to take a break to relax during the trip. A mathematical model of the TTDP with these new constraints (TTDP-BWB) was developed. Then, a heuristic algorithm was developed with a new defined function that took the new constraints into account. The algorithm was codded using Android Studio and developed a mobile application for the case of Eskisehir in Türkiye. Problems are generated on the small and medium scale for the case of Eskisehir and used large-scale problems from published literature. The results of the algorithm were compared with the results of the mathematical model for the small scale problems. Additional, large-scale problems from literature were solved to see the performance of the heuristic algorithm. Computational results showed that the algorithm is promising.

1 Introduction

Tourism plays an important role in the economy of countries. Approximately 1460 million international tourists contributed to tourism in 2019, and within 10 years, real growth in international tourism receipts is 54% while the growth in world gross domestic product (GDP) is 44% [46].

When tourists explore a city, firstly they should decide which points of interest (POIs) to visit. After that, they should plan their daily routes for the remaining days of their tour. This plan requires to learn some information, such as visiting times, entrance fees and time windows for each POI, and the time between POIs, etc. Additionally, they should take into consideration their personal limits, e.g. budget and time. This problem is called the tourist trip design problem (TTDP) in published literature (see e.g. [5, 13, 14, 16, 17, 26, 32, 33, 37]. and is an extension of the team orienteering problem (TOP) (see e.g. [4, 7, 8, 10, 36] that applies in the travel industry. The aim of the problem is to construct routes which start and end at a particular point, and the objective is to maximize the total score which are based on interest of a tourist visiting POIs. Also, the score is sum of points given by the tourist that shows how much the tourist keens on visiting the each POI.

In this study, TTDP was handled with three new constraints: budget, weather and break, and abbreviated the new problem to TTDP-BWB. Budget was considered to be only the entrance fee to POIs. However, tourists pay for transportation if the travel distance to a POI is too far to walk. It was assumed that tourists use taxis when it was impossible to walk. Thus, in this study, the standing taxi charge and taxi fare per kilometer were taken into consideration besides the entrance fee as individual parameters of the problem dealing with budget. Additionally, the expense of taking a coffee break, as explained later, was also taken into consideration.

Choosing the time to visit each POI was considered, especially those that are outdoors and affected by the weather. During the summer season, tourist may not prefer to be outside between specific times, e.g. between 11 a.m. and 3 p.m. due to heat. Thus, outdoor POIs should be visited outside of these times and inside POIs should be preferred instead. However, cold and rainy days are not handled in this study since it is the choice of the tourist whether to walk in the rain or not, and some of them may not care about being outside on these days.

After visiting a certain number of POIs, tourists need a break. In this study, it was focused on a coffee break (see e.g. [34], not a main meal, since the expense, time and duration resulting from the choice of a main meal may differ greatly from person to person. Thus, one coffee break within a limited duration was considered under a time window within a tolerance. Furthermore, an average expense for this break was added to the budget constraint.

Firstly, the current mathematical model of TTDP (see e.g. [23, 36]. was improved by adding new constraints or modifying some of the existing constraints and proposed a mathematical model. Additionally, new decision variables were defined to construct the constraints about weather and breakpoints, and defined new parameters for all new constraints.

Then, a heuristic algorithm was proposed with a newly defined function to solve the problem given the computational complexity of the TTDP-BWB mathematical model. Budget, time and the scores for POIs was put into the heuristic function to balance the objective function as well as the main constraints on time and budget in the other constraints: weather and breakpoints were also affected by them. The main advantages of the heuristic algorithm is to have an easy structure and to solve the problem within a reasonable time, in that any tourist does not want to wait too long to generate a route.

Finally, the algorithm was codded using Android Studio to develop a mobile application for tourists. This mobile application was mainly designed for the case of Eskisehir, Türkiye. Furthermore, small and medium problems were generated using the case of Eskisehir and large-scale problems from published literature. The results were compared with the mathematical model solutions where it was found within a reasonable time.

The main contributions of the paper can be summarized as follows:

• A new mathematical model of TTDP was proposed by considering new conditions: budget, weather, and break time.

• A heuristic algorithm where the function used for the selection of the next POIs consists of two significant parameters: the cost and the time needed to visit the next POI and scores of POIs given by tourists was proposed.

Addition, in this paper, the followings are applied for computational results of both real-life cases of Eskisehir, Türkiye and test problems from published literature.

• A mobile application was developed for the case of Eskisehir, Türkiye.

• Different small-scale test problems from the case of Eskisehir, Türkiye was proposed, and then the results of the heuristic algorithm were compared with the results of the mathematical model.

• The test problems from literature were solved to show the performance of the heuristic algorithm for large-scale problems.

The rest of the study is organized as follows: Sect. 2 reviews the literature on TTDP. The proposed mathematical model is given in Sect. 3, while Sect. 4 explains the heuristic algorithm. The computational results are then analyzed in Sect. 5. Finally, some implications of the study is given for Practice and Academicsin Sect. 6, and Sect. 7 draws some conclusions from the study.

2 Literature review

2.1 Team orienting problem

This section was started considering state-of-the-art problems with TOP – the team orienteering problem – which is the most related topic, since TTDP is an extension of that problem. TOP [8] itself is an extension of the orienteering problem (OP) for multiple tours, while OP is a special type of traveling salesman problem for the situation where all points are not visited and where the aim is to maximize profit [9, 24]. Recently, several methods such as a tabu search ([7, 19], a guided local search metaheuristic [38], a memetic algorithm [6], particle swarm optimization [10, 28] have been presented to solve the TOP. Moreover, Archetti et al. [3] proposed a new version of TOP in which the nodes are located on an arc (TOARP). Then, several methods have been proposed in published literature: a metaheuristic method [4] and a column generation approach [29].

Addition, TOP has been studied with considering time windows and named as TOP with time windows which is the most related version of TOP related to TTDP. Metaheuristic approaches such as iterated local search [39], an ant colony system [27], an lp-based granular variable neighborhood search [23], a simulated annealing heuristic [25] and an iterative three-component heuristic [18] were developed in the literature. Furthermore, we refer the reader to the survey about different types of OP and TOP by Vansteenwegen et al. [41] and Gunawan et al. [17].

2.2 Tourist trip design problem (TTDP)

TTDP is considered as an application of TOP and Vansteenwegen and Van Oudheusden [37] firstly used operations research (OR) techniques to model the TTDP, and proposed decision models. Then, Souffriau et al. [32] proposed using a combination of artificial intelligence and metaheuristic (guided local search) to solve a simple version of TTDP by only considering the maximum allowed distance, and the algorithm was applied to the case of the city of Ghent. After that, Souffriau et al. [33] took the opening hours of POIs and model TTDP as an extension of TOP with time windows. Additionally, an iterated local search algorithm (ILS) on a mobile phone was proposed. Also, we refer the reader to the survey of the metaheuristics for TTDP by Vansteenwegen et al. [40]. Similarly, Gavalas et al. [13] proposed a novel heuristic and develop a mobile application for TTDP. Brito et al. [5] proposed a fuzzy GRASP algorithm to solve TTDP. Mei [26] developed an ant colony algorithm under the Android platform.

Furthermore, TTDP was improved with additional new constraints, new algorithms, and various applications. Vansteenwegen et al. [42], developed a web application for five cities in Belgium. A greedy adaptive search algorithm (GRASP) was proposed to solve TTDP with the new constraint: lunch time, while a mathematical model was not included. Abbaspour and Samadzadegan [1] dealed TTDP with several models of transportation system: bus, subway, walking, and propose a mathematical model and two adapted genetic algorithms. The data was obtained from the city of Tehran. Garcia et al. [12] taken into account the transportation as walking and public transport and develop an iterated local search algorithm to solve TTDP in real-real time. Computational results were obtained by using the data from the city of San Sebastian. In addition, we refer the reader to the survey about TTDP comparing with OP and TOP by Gavalas et al. [14].

Moreover, Gavalas et al. [15] considered time dependency between POIs and proposed two novel randomized metaheuristic approaches based on ILS. Zheng et al. [43] proposed a four-step heuristic algorithm to solve TTDP with aesthetic fatigue and variable sightseeing value, and applied data from the Jiuzhali Valley in Sichuan, China. Kotiloglu et al. [21] developed a novel filter-first, tour-second framework with an iterated tabu search algorithm for TTDP that had a set of mandatory points selected by the tourist. Sylejmani et al. [35] extend TTDP for tourist groups by considering individual preferences and mutual social relationship. Then a mathematical model was developed and an algorithm based on tabu search. Wörndl et al. [47] recommended TTDP for a walking route and modified Dijkstra’s algorithm to find the shortest route and maximize the entertainment. Expósito et al. [11] clustered POIs to represent different types of attraction sites and then a fuzzy GRASP algorithm was proposed using distance- and score-based evaluation criteria. Ko et al. [20] considered tourist fatigue in the objective function and developed an ILS.

Recently, Zheng et al. [44] improved TTDP by adding hotel selection and proposed a two-level heuristic approach that combined a genetic algorithm and a variable neighborhood search. Also, the case of Xiamen—a coastal city in south eastern China—was studied to evaluate the performance of the algorithm. Zhao and Alfandari [45] introduced a diversified package tour to balance the trade-off between the tourist’s choice and the economy of scale for tourism agencies. Then, branch-and-price and branch-cut-and-price methods were developed and the instances from both published literature and the case of Chinese online travel agencies (OTA) were solved to test the methods. Ruiz-Meza and Montoya-Torres [30] considered heterogenous preference of tourist group and the level of CO2 emission. Then the mathematical model was developed and results by using data sets were obtained. Addition, we refer the reader to the systematic review about TTDP [31].

It can be concluded that the research gap is to deal with a model that takes into consideration all of the constraints- budget, weather, and break time- at once. Thus, a comparative review of the literature is summarized in Table 1 that compares studies with some features: budget, weather, and break time constraints, mathematical model, algorithm and real-world application. It can be seen from table, this study contains all of these feature.

Table 1 Literature review

3 Mathematical model

The TTDP-BWL was formulated with the new constraints: budget, weather and break time. New parameters and new decision variables are defined to handle these constraints. The definition of the sets, parameters and decision variables were as follows:

Sets:

$K$	Set of days
$I$	Set of POIs
${I}_{0}$	Set of POIs and the starting point (${I}_{0}=I \cup \{0\}$)

Parameters:

${p}_{i}$	The score of the $i$ th POI by the tourist,$\forall i\in I$
${t}_{ij}$	Travel time between the $i$ th and $j$ th POIs,$\forall i, j\in {I}_{0}$
${v}_{i}$	Visit time for the $i$ th POI,$\forall i\in I$
${T}_{max}$	Maximum route duration,$\forall k\in K$
${[e}_{i},{l}_{i}]$	Time windows for the $i$ th POI,$\forall i\in I$
$\left[{e}_{i}, O{e}_{i}\right]$ $\cup$ $[O{l}_{i}, {l}_{i}]$	Time windows of a POI if it is outdoors and the summer season, $\exists i\in I$ where $O{e}_{i}$ is the latest time to visit in the morning e.g. 11 a.m. and $O{l}_{i}$ is the earliest time to visit afternoon e.g. 3 p.m.
${T}_{start}$	The starting time of the routes
$B$	The budget for the routes
${c}_{i}$	The entrance fee of the $i$ th POI,$\forall i\in I$
${tu}_{ij}$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\;{\text{a}}\;{\text{taxi}}\;{\text{is}}\;{\text{used}}\;{\text{between}}\;{\text{the}}\;{\text{ith}}\;{\text{and}}\;{\text{the}}\;{\text{jth}}\;{\text{POIs}}} \\ {0,\;{\text{otherwise}}} \\ \end{array} } \right.$ ,$\forall i, j\in {I}_{0}$
$k{m}_{ij}$	The distance in km between the $i$ th and the $j$ th POIs
$tf$	Taxi fare per kilometer
$to$	Taxi standing charge
${b}_{i}$	$\left\{\begin{array}{l}1, if \;the\; ith\; POI \;is\; suitable\; for\; a\; break\\ 0, \quad otherwise\end{array}\right.$, $\forall i\in I$
$BT$	The break times for the routes
$B{T}_{tol}$	The break time tolerances for the routes
$DB$	Duration of the break time
${c}_{b}$	Cost of break
${O}_{i}$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\;{\text{the}}\;{\text{ith}}\;{\text{POI}}\;{\text{is}}\;{\text{outdoor}}} \\ {0,{\text{otherwise}}} \\ \end{array} } \right.$, $\forall i\in I$
$S$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\;{\text{it}}\;{\text{is}}\;{\text{the}}\;{\text{summer}}\;{\text{season}}} \\ {0,{\text{otherwise}}} \\ \end{array} } \right.$
$M$	A big number

Decision variables:

${x}_{ijk}$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\frac{{{\text{route}}}}{{{\text{day}}}}k\;{\text{goes}}\;{\text{from}}\;i\;{\text{to}}\;j} \\ {0,{\text{otherwise}}} \\ \end{array} } \right.$, $\forall i,j \in I_{0} ,i \ne j,k \in K$
${y}_{ik}$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\;{\text{the}}\;{\text{ith}}\;{\text{POI}}\;{\text{is}}\;{\text{included}}\;{\text{in}}\;{\text{route}}/{\text{day}}\;k} \\ {0,{\text{otherwise}}} \\ \end{array} } \right.$, $\forall i\in I, k\in K$
${T}_{i}$	The start time of the visit to the ith POI, $\forall i\in {I}_{0}$
${w}_{i}$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\;{\text{the}}\;{\text{ith}}\;{\text{POI}}\;{\text{is}}\;{\text{outdoors}}\;{\text{and}}\;{\text{it}}\;{\text{is}}\;{\text{summer}}\;{\text{season}}} \\ {{\text{and}}\;{\text{the}}\;{\text{ith}}\;{\text{POI}}\;{\text{should}}\;{\text{be}}\;{\text{visited}}\;{\text{after}}\;{\text{Ol}}_{i} } \\ {0,{\text{otherwise}}} \\ \end{array} } \right.$,$\forall i\in \mathrm{I}$.
$B{P}_{i}$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\;{\text{the}}\;{\text{ith}}\;{\text{POI}}\;{\text{is}}\;{\text{the}}\;{\text{breakpoint}}} \\ {0,{\text{otherwise}}} \\ \end{array} } \right.$, $\forall i\in I$
${v}_{k}$	$\left\{ {\begin{array}{*{20}l} {1,{\text{if}}\;{\text{on}}\;{\text{the}}\;{\text{kth}}\;{\text{day}}\;{\text{there}}\;{\text{can}}\;{\text{be}}\;{\text{a}}\;{\text{break}}} \\ {0,{\text{otherwise}}} \\ \end{array} } \right.$, $\forall k\in K$

The mathematical model was formulated as follows:

$$\mathrm{max}z=\sum_{k\in K}\sum_{i\in I}{p}_{i}{y}_{ik}$$

(1)

$\mathrm{subject \quad to}$

$$\sum_{j\in {I}_{0}}{x}_{0jk}=\sum_{j\in {I}_{0}}{x}_{j0k}\le 1 \quad \forall k\in K$$

(2)

$$\sum_{\begin{array}{l}j\in {I}_{0} \\ j\ne i\end{array}}{x}_{ijk}=\sum_{\begin{array}{c}j\in {I}_{0}\\ j\ne i\end{array}}{x}_{jik} \quad \forall i\in I, k\in K$$

(3)

$$\sum_{\begin{array}{c}j\in {I}_{0}\\ j\ne i\end{array}}{x}_{ijk}={y}_{ik} \quad \forall i\in I, k\in K$$

(4)

$$\sum_{k\in K}{y}_{ik}\le 1 \quad \forall i\in I$$

(5)

$$\sum_{i\in {I}_{0}}\sum_{k\in K}{c}_{i}{y}_{ik}+\sum_{i\in {I}_{0}}\sum_{\begin{array}{c}j\in {I}_{0}\\ j\ne i\end{array}}\sum_{k\in K}\left(to+tf.k{m}_{ij}\right).t{u}_{ij}.{x}_{ijk}+\sum_{i}{c}_{b}.B{P}_{i}\le B$$

(6)

$${T}_{0}={T}_{start}$$

(7)

$${T}_{j}\ge {T}_{i}+{v}_{i}+B{P}_{i}*DB+{t}_{ij}-M.\left(1-\sum_{k\in K}{x}_{ijk}\right) \quad \forall i\in {I}_{0}, j\in I$$

(8)

$${T}_{i}+{v}_{i}+DB.B{P}_{i}+{\sum }_{k\in K}{t}_{i0}.{x}_{i0k}\le \left({T}_{max}+{T}_{start}\right)+M.\left(1-{\sum }_{k\in K}{y}_{ik}\right) \quad \forall i\in I$$

(9)

$${w}_{i}{.O}_{i}.S.O{l}_{i}.\sum_{k\in K}{y}_{ik}+{e}_{i}.\left(1-{O}_{i}.S\right).\sum_{k\in K}{y}_{ik}\le {T}_{i} \quad \forall i\in I$$

(10)

$${T}_{i}\le {(1-w}_{i}){.O}_{i}.S.O{e}_{i}.\sum_{k\in K}{y}_{ik}+M.{w}_{i}.S.{O}_{i}+({l}_{i}-{v}_{i}-DB.B{P}_{i}).(1-{O}_{i}.S).\sum_{k\in K}{y}_{ik} \quad \forall i\in I$$

(11)

$${v}_{k}.\left(BT-{B}_{tol}\right).\sum_{j\in I}{x}_{0jk}\le \sum_{i\in I}{b}_{i}.B{P}_{i}.{T}_{i}.{y}_{ik}\le {v}_{k}.\left(BT+{B}_{tol}\right).\sum_{j\in I}{x}_{0jk} \quad \forall k\in K$$

(12)

$$\sum_{j\in I}{T}_{j}{x}_{j0k}\le M*{v}_{k}+\left(BT+{B}_{tol}\right) \quad \forall k\in K$$

(13)

$$\left(BT+{B}_{tol}\right)\le M*{\mathrm{v}}_{\mathrm{k}}+\sum_{j\in I}{T}_{j}{x}_{j0k} \quad \forall k\in K$$

(14)

$${x}_{ijk}\in \left\{\mathrm{0,1}\right\} \quad \forall i,j\in {I}_{0}, k\in K$$

(15)

$${y}_{ij}\in \left\{\mathrm{0,1}\right\} \quad \forall i,j\in {I}_{0}$$

(16)

$$B{P}_{i}\in \left\{\mathrm{0,1}\right\} \quad \forall i\in I$$

(17)

$${w}_{i}\in \left\{\mathrm{0,1}\right\} \quad \forall i\in I$$

(18)

$${T}_{i}\ge 0 \quad \forall i\in {I}_{0}$$

(19)

Firstly, the objective function (1) of the problem is to maximize the total score which is awarded to POIs by the tourists. Constraint (2) ensures that each route starts and ends at the starting point if the $k$ th route is used. The right hand side of the constraints is smaller than 1 since some days may not be used to visit POIs due to other constraints, e.g. budget may not be enough. Constraint (3) states that if a route arrives at a POI, then it also departs from there. Constraint (4) ensures that if a POI is assigned to a route then the POI is visited by that route. Constraint (5) ensures that each POI is assigned one route at most.

Next, the budget is controlled by constraint (6). The total expenses include the entrance fee and the taxi fee if a taxi is necessary between two consecutive POIs. Constraint (7) states that the starting time of the route is equal to the preferred starting time.

Then, constraint (8) requires that the starting time of a POI on a route should be later than the previous POI on the same route. The visiting time and the travelling time between these two consecutive POIs are also considered. Furthermore, if the previous POI is a breakpoint, then the duration of the break time is taken into consideration. Constraint (9) ensures that the maximum time for each route takes the time to visit a POI into consideration. If returning to the starting point, then the travel time between the relevant POI and the starting point is considered. In addition, the duration of any break time is also taken into consideration.

After that, constraints (10) and (11) state that the start time of the visit to a POI matches the opening time windows of the POI, and these constraint are significant to prevent the starting time before the opening time and thus the waiting time does not occur. If the POI is outdoors and it is the summer season, then the start time of the visit can be before $O{e}_{i}$ or after $O{l}_{i}$. In this situation, the decision parameter ${w}_{i}$ controls the “or” statement between constraints (10) and (11). If ${w}_{i}$ is equal to 1, then it means that the start time of the visit is after $O{l}_{i}$, otherwise it is earlier than $O{e}_{i}$. If the POI is not outdoors and it is not summer, whether the value of ${w}_{i}$ is 1 or 0, the start time of the visit is between the original time windows, since the product of parameter ${O}_{i}=0$ and $S=0$. Note that ${w}_{i}$ should be a decision variable instead of a parameter since ${w}_{i}$ decides the start time of the visit before $O{e}_{i}$ or after $O{l}_{i}.$

Finally, the start time of the breakpoint is chosen for each route with a break time within the tolerances of constraints (12), (13) and (14). The breakpoint for each route is selected from POIs that are assigned to the route and are suitable for a break. The sum $\sum_{j\in I}{x}_{0jk}$ is equal to 1 if the $k$ th route is used, otherwise the value is 0. Thus, multiplying both sides of the inequality by $\sum_{j\in I}{x}_{0jk}$ ensures that if the $k$ th route is not used, a breakpoint is not chosen. Additional, ${v}_{k}$ takes the value 1 together with constraint (13) and (14) if a break is suitable for the $k$ th route before the break time has ended, otherwise it takes the value 0. In this case, constraint (12) is forced to 0 for both sides and the route is ended without a break right after the break time, plus its tolerances, has ended. Furthermore, constraints (15) to (19) specify the variable domains. Additional, the number of decision variables is $O({I}_{0}^{2}K+IK+{I}_{0}+2I+K)$ while the number of constraints is $O\left({I}_{0}I+2IK+4I+2K+3\right)$.

Constraints (2), (4) and (8) to (11) are modified from published literature (se e.g. [37]. In constraint (2), all days are not allowed to be constructed because of some constraints e.g. all the budget is consumed before assigning POIs to all routes/days, since the tourist may not have enough budget for all routes/days she/he selects. Constraint (4) is formulated with an equality because if ${y}_{ik}$ is equal to 1, then the departure from $i$ must occur. Significant modifications are established for constraints (8) to (11) to add the breaktime and the season effect into the time windows.

Constraints (6), (7), (12), (13) and (14) are newly formed in this study. First, while tourists travel, they may have limited money. The generated routes should fit the budget of tourists under constraint (6). Then, the costs of the route are the entrance fees and the distance between two points where a taxi has to be used. In general, ${T}_{0}$ is assumed to be 0. However, there is a start time defined by tourists. Thus, constraint (7) is written. Constraint (12) is formed by selecting the breakpoint for each route used. Lastly, constraint (13) and (14) are for the situation where a break may not be possible.

4 The Heuristic algorithm for TTDP-BWB

A heuristic algorithm was proposed to solve TTDP-BWB. The algorithm can be classified as greedy algorithm since it uses a function to select the next POIs under the problem constraints and selects the POI that has the maximum function value if the POI is suitable for selecting under the problem constraints. The function covers three parts: budget, time and the POI score as follows:

$${f}_{ij}=\left(\frac{1}{\left(\left(to+tf.k{m}_{ij}\right).t{u}_{ij}+{c}_{j}\right).{f}_{{B}_{i}}}\right).\left(\frac{1}{({\mathrm{t}}_{\mathrm{ij}}+{\mathrm{v}}_{\mathrm{j}}).{f}_{{T}_{i}}}\right).{p}_{j} \quad \forall i\in {I}_{0},j\in I$$

(20)

where${f}_{{B}_{i}}=\underset{j\in I}{\mathrm{max}}\frac{1}{(to+tf.k{m}_{ij}).t{u}_{ij}+{c}_{j}} , {f}_{{T}_{i}}=\underset{j\in I}{\mathrm{max}}\frac{1}{{t}_{ij}+{v}_{j}} \quad \forall i\in {I}_{0}$.

The first part of the function considered the proportion of the expense budget used going from the $i$ th POI to the $j$ th POI. The $\left(to+tf.k{m}_{ij}\right).t{u}_{ij}$ and ${c}_{j}$ show the cost of taxi usage, and the entrance fee, respectively. The term ${f}_{{B}_{i}}$ gives the maximum value of this proportion. Thus, a normalized value between 0 and 1 was obtained. The value 1 means that going from the $i$ th POI to the $j$ th POI is the most suitable choice, according to the budget. The second part is about the time as a proportion of the total time spent going from the $i$ th POI to the $j$ th POI and the visit time for the $j$ th POI. ${\mathrm{t}}_{\mathrm{ij}}$ and ${\mathrm{v}}_{\mathrm{j}}$ represent the travel time and the visiting time. Similarly, ${f}_{{T}_{i}}$ is the maximum value and this part is also normalized. The last part of the function is the score for the $j$ th POI, which is a significant parameter of the TTDP-BWB. This score is between 0 and 5. The score may decrease with the value of the first and second part of the function. In this way, the expense and time needed to go from the $i$ th POI to the $j$ th POI is taken into consideration as well as the scores given by tourists.

The proposed heuristic algorithm is explained using the algorithm pseudocode. The same notations are used as the proposed mathematical model. The algorithm starts at the starting point for each route $k$, then chooses the next POI with the function (20) under the constraint of time windows, budget, break time and weather. This procedure continues until the budget runs out or the time is up, or there are no suitable POIs left.

Line 1 is about initialization of the algorithm. The parameters (see the parameters of the mathematical model) are read, the list of routes/days $route\left(k\right)$ and suitable POIs for each route/day $list\left(k\right)$ is set. The starting point is assigned to each route. Furthermore, all POIs are added to the suitable list for each route and then the function (20) is calculated. Lastly, the remaining budget is equal to the tourist budget. The routes are constructed between the lines 2 and 12. In line 3, the remaining time for each route is defined as the tourist’s maximum route duration at the beginning of assigning any POI to each route/day after the starting point. Additionally, the starting time for each route/day is defined as the tourist’s start time. In line 6, the next POI is chosen according to the function (20). Then, in line 7, the constraints are checked to decide whether the chosen POI is suitable to assign as the next POI for that route/day. If all the constraints are satisfied, then the selected POI is removed from the list of all routes/days, since each POI can be visited one time at most, and is added to the route list of the relevant route/day. Additional, the break time and the break point are defined if the current time is suitable for break. If there is not any available POI for break, then the route is ended by returning the starting point. Otherwise, in line 8, the selected POI is removed from the suitable list of relevant routes/days. In line 10, if the suitable list of the relevant $k$ th route is not empty, then all discarded $j$ s from lines 5 to 9 are added to the list again, given that from the current point, it may not be suitable to go to these $j$ s. However, from the next point, it may be feasible to travel to those POIs.

5 Computational experiments

There are two parts in this section. In the first part, instances were generated using the case of Eskisehir and in the second part, large-scale problems were generated using test problems from published literature. The experiments were run on a computer with an Intel® Core™ i5 9300HF CPU at 2.40 GHz with 8 GB of RAM, using simulation mobile devices which means the CPU times will be similar for a mobile phone.

5.1 The mobile application for the case of Eskisehir

The heuristic algorithm was coded using Android Studio and a mobile application was developed for the case of Eskisehir. In Fig. 1, the screenshots of the mobile application are shown. The picture on the left shows the main screen where the users write the budget, starting time, travel date, travel time (in hours) and travel days, and then choose the starting point for their trip. The picture on the right shows the scoring screen where the users award a score for each POI of Eskisehir from 0 to 5. A score 0 for a POI means that the user will not visit this POI, while a score 5 of a POI means that the user absolutely wants to visit this POI. The other scores show the desire to visit a POI between never and absolutely.

Fig. 1

The screenshots from the mobile application for the case of Eskisehir, Türkiye

5 points was defined as possible starting points for Eskisehir where tourists choose to stay nearby. The users may choose the closest points among the starting points available. Since Eskisehir is a small town and these starting points are chosen to cover the whole city, these starting points are enough. A tourist will most probably be staying at a place near one of those starting points. 43 POIs is defined including parks, museums, shopping centers and famous streets. All the parameters needed, such as opening and closing times, entrance fees etc., are listed.¹ Additionally, the break time $BT$ is defined in the middle of the route with a tolerance of $B{T}_{tol}$ $\pm 30$ minutes, and the duration of the break $DB$ is given as $30$ minutes. The locations of the starting points and POIs are given in Fig. 2.

Fig. 2

The locations of the starting points (a) and all POIs (b) for the case of Eskisehir, Türkiye

5.2 The results for Eskisehir

A problem containing 28 POIs was generated for Eskisehir.² New problems were generated with different parameters: the season $S$, the number of days $K$, the budget $B$ and the maximum route duration ${T}_{max}$. The season $S$ is shown as 1 or 0, which means that the season is summer or not summer, respectively. In total, 18 problems were produced. The locations are shown in Fig. 3.

Fig. 3

The locations of POIs for the problems generated

All the problems were solved by both mathematical model, and the proposed heuristic algorithm (Heuristic-TTDP-BWB). The mathematical model is solved by using a GAMS (General Algebraic Modeling System) optimization software program using SCIP solver (see e.g. [22]. Additional, a time limit of 12 h is put and it should be noted that the Heuristic-TTDP-BWB finds solutions within seconds. The results for GAMS-SCIP ${z}_{model}$ and the Heuristic-TTDP-BWB ${z}_{heuristic}$, the gap between the solutions, and the solving time needed for both GAMS-SCIP and the Heuristic -TTDP-BWB are shown in Table 2. The gap between solutions were calculated as follows:

Table 2 Results for the medium problem for Eskisehir with 28 POIs

$$GAP\mathrm{ \%}=\frac{{z}_{model-best-bound}-{z}_{model}}{{z}_{model-best-bound}}.100$$

(21a)

$$GAP\mathrm{ \%}=\frac{{z}_{model}-{z}_{heuristic}}{{z}_{model}}.100$$

(21b)

$$GAP\mathrm{ \%}=\frac{{z}_{model-best-bound}-{z}_{heuristic}}{{z}_{model-best-bound}}.100$$

(21c)

Compared to GAMS-SCIP, the Heuristic-TTDP-BWB found better solutions for 14 of the 18 problems, worse solutions for 2 of the 18 problems, and the same solutions for 2 of the 18 problems. The average gap for better solutions was − 15% while the average gap for worse solutions was 14%. Additionally, the best gap was − 38%, while the worst gap was 23%. Furthermore, the overall average gap was − 10%. In addition, a comparison of GAMS-SCIP and the Heuristic-TTDP-BWB is shown in Fig. 4. These results demonstrated that the performance of the Heuristic -TTDP-BWB is remarkable with respect to the model results. Furthermore, the results are compared with best bounds (which may be hard to reach these values since the dual gap is possible), and GAMS-SCIP with 12 h’ time limit had 28% of overall average gap while the Heuristic-TTDP-BWB had 22% of overall average gap. Addition, the Heuristic-TTDP-BWB reached the best bound in 4 problems. Since the mathematical formulation of the TTDP-BWB is integer, exact solvers such that GAMS-SCIP need so much time (the needed time may be days to find the exact solution) than heuristic algorithms which is not generate the exact solution however good solution with less time. So, it is the reason that there is a time limit for GAMS-SCIP and the Heuristic-TTDP-BWB is able to find better solutions than GAMS-SCIP. Moreover, in Fig. 5, the routes for the problem PE28_13_5 are shown on the map of Eskisehir and In Fig. 6, the screen view of the application is represented. A tourist would probably feel pleased with the route obtained by the Heuristic -TTDP-BWB.

Fig. 4

A comparison of GAMS-SCIP ${z}_{model}$ and the Heuristic -TTDP-BWB ${z}_{heuristic}$ for the case of Eskisehir, Türkiye

Fig. 5

The routes for the problem PE28_13_5 obtained by GAMS-SCIP on the map of Eskisehir

Fig. 6

The screen view of the mobile application for the routes

5.2.1 Sensitivity analysis

In this section, sensitivity analysis of weather, number of days, budget and time ($S, K, B$ and ${T}_{max}$) are made for both GAMS-SCIP and the Heuristic-TTDP-BWB, and the results are given in column graphics in Fig. 7. When non-summer case (S = 0) as summer case (S = 1) is analyzed, GAMS-SCIP finds solutions that have better value of objective function for non-summer case than summer case since the number of constraints increases for summer case because of visiting times of POIs. However, the heuristic-TTDP-BWB is able to generate similar solutions for both cases. Moreover, number of days and budget are investigated together in that when the number of days increases, the budget should be increase either to afford the expense of additional days. As expected, these parameters have positive effect on the value of objective function, and both GAMS-SCIP and the heuristic-TTDP-BWB get better solutions while the value of these parameters are getting greater. Finally, time has the similar impact as number of days and budget on the value of objective function.

Fig. 7

Sensitivity analysis of parameters $S$ for GAMS-SCIP (a) and the Heuristic-TTDP-BWB (b), $K, B$ for GAMS-SCIP (c) and the Heuristic-TTDP-BWB (d), and $T$ for GAMS-SCIP (e) and the Heuristic-TTDP-BWB (f)

5.3 Results of the large scale problems from published literature

The large problems³ with 100 POIs were generated from a data set by Montemanni and Gambardella [27] and used to investigate the performance of the Heuristic -TTDP-BWB on a large scale. The score of each POIs, location of POIs, the starting point, time windows of each POI are taken from the data set and the new parameters (entrance fee, the suitability of a POI for a break, whether a POI is an open area) needed for TTDP-BWB were obtained randomly. The distance between two POIs was represented by the Euclidian distance even though real distances instead of Euclidian distance is used in the case study, Eskisehir, Türkiye. Because, the locations are defined as x- and y-axis for the large problems. It should be noted that the real distances should be used in real world applications. Also, the unit of the distance is taken as km. Then, the taxi usage between two POIs was defined as 1 if the distance was greater than 5 km. The travel duration between two POIs was calculated by multiplying the distance by 2 min/km if the taxi was not used. Otherwise, the duration was equal to the distance. The other parameters used in the Heuristic -TTDP-BWB are shown in Table 3.

Table 3 The other parameters of the large scale problems

The results are shown in Table 4. All solutions were obtained within a second. These results demonstrated that the speed of the Heuristic-TTDP-BWB was good enough even when the size of the problem was large, e.g. 100 POIs. Additional, the results are given in Fig. 8 as non-summer case (S = 0) as summer case (S = 1). It may be concluded that the Heuristic-TTDP-BWB is able to produce the solutions where the values of the objective functions are close to each other when the season selection is summer or not. However, for non-summer cases, the value of objective function may certainly be greater than summer cases since summer cases has one more constraint that is not to visit open area POI during some time period.

Table 4 Results of the large problems from published literature

Fig. 8

The results of large problems where non summer case (S = 0) as summer case (S = 1). y-axis shows the value of objective function

Moreover, since TTDP-BWB which is a new version of TTDP is handled in the paper and thus the results are original, to compare the results of large problems, a gap is also proposed as following:

$$\widetilde{Gap}\mathrm{\%}=\frac{{\widetilde{z}}^{*}-{z}_{heuristic}}{{\widetilde{z}}^{*}}*100$$

(22)

where ${\widetilde{z}}^{*}$ is the sum of all POIs without considering any constraint and is the best possible value which is likely unfeasible under the problem constraints. The gaps are given in Table 5. While the gap is higher for the problems c101-rc108, the gap is relatively small for the problems c201-rc208. It is certainly impossible to reach the value of ${\widetilde{z}}^{*}$ because of the problem constraints. Additional, the time range of the problems c101-rc108 are too short while the visit times are too large and it is natural that the parameters of the problems are also effective on the quality of the solutions besides of algorithm. Thus, to make an interpretation on the results, it should be underlined the results that are smaller than 55%, and 14% (average gaps) for the problems c101-rc108 and c201-rc208, respectively. According to these gaps, 28 out of 58 and 35 out of 54 results are lower average gaps for the problems c101-rc108 and c201-rc208, respectively.

Table 5 Gaps between the results of large problems and the best possibleresult (may be infeasible) for comparison

6 Implications for practice and academics

TTDP dealt in in this paper includes novel constraints which are related to practical conditions: weather, budget and break time. From the viewpoint of tourists, it can be remarked that tourists can plan their trips by deciding only three issues: which POIs are desired to visit with a degree, their budget, and their time of the trip. These three issues are basic information that each tourist can inform. The rest of other parameters of the problem is obtained from POIs such as opening and closing time and from weather forecasting as sunny day or not etc. After that, the algorithm called the heuristic-TTDP-BWB in this paper is readily applied to obtain a solution under problem constraints with the aim of maximizing tourists’ satisfaction (maximize the total score which is awarded to POIs by the tourists). Moreover, since the computation time to generate a solution by the Heuristic-TTDP-BWB is relatively less even if the number of POIs is large-scale, it can be concluded that the Heuristic-TTDP-BWB is an algorithm that is quite appropriate to implemented in practice. Addition, from the managerial implications, as the number of tourists who are grateful with the trip heightens, the number of tourists who are willing to come in the future is going to be ascended. Furthermore, the Heuristic-TTDP-BWB is easy to apply for different touristic regions, cities etc. and code as a mobile application which are functional for tourists, since every tourist has most probably a smart phone and internet connection within it and is used to take advantage of mobile applications.

Finally, from implications for academics, the mathematical model of TTDP is improved by adding the new constraints and as a consequence of new constraints, new parameters and decision variables are defined. Thus, the mathematical model of TTDP-BWB is a novel model in literature. In the meantime, a novel heuristic is proposed based on newly defined function that covers scores of POIs given by tourists, and also both budget and time. The other constraints are examined within the heuristic. Thus, the Heuristic-TTDP-BWB is capable of using budget and time efficiently to maximize the total scores of POIs visited under the other constraints of problem. Addition, small scale test problems which are based on real-world data from Eskisehir, Türkiye are generated and large-scale test problems are modified from published literature, thus if another algorithms are developed to solve the TTDP-BWB, then the performance of the related algorithms can be compared by using these test problems. In this way, new test problems for both small-scale and large-scale in the literature exist for the TTDP-BWB which is also a new variation problem of TTDP in literature.

7 Conclusions

In this study, TTDP was investigated with new constraints: budget, weather and break times. The budget is used to travel between two POIs if a taxi is needed, for the POI entrance fee – if not free, and for a coffee at break time. Consideration was given to what season it was. If the season was summertime, then the visiting time of an open area POI is limited e.g. before 11:00 a.m. and after 16:00 p.m. to offer protection from the effects of the sun. Break time was to take a rest during the route. The problem is abbreviated as TTDP-BWB.

Mathematical model of TTDP-BWB was constructed, and then a heuristic algorithm called Heuristic -TTDP-BWB was proposed. A case study was created for Eskisehir in Türkiye and all needed the data was formed. Then, a mobile application for Eskisehir was developed by coding the Heuristic -TTDP-BWB. problems containing 28 POIs for the case of Eskisehir was generated and solved by both mathematical model and the Heuristic-TTDP-BWB to see the performance of the Heuristic -TTDP-BWB. The results of these problems for the Heuristic -TTDP-BWB were promising when the results were compared with the solutions of the mathematical model. Additionally, the time needed to find a solution with the Heuristic -TTDP-BWB was a second, which is really practical for a tourist who wants to use the mobile application. Furthermore, the Heuristic -TTDP-BWB was able to quickly find solutions to even large scale problems with 100 POIs, which demonstrated its real-life applicability.

For future research, a mobile application could be developed with the Heuristic -TTDP-BWB for other tourist cities in Türkiye, other countries, and for the IOS operating system. A metaheuristic could be developed to see if it made a difference in terms of solution quality and solution time compared with the Heuristic -TTDP-BWB.