Keywords

1 Introduction

In tourist routing problems and at certain points of interest (POIs) crowds of visitors can occur. The satisfaction experienced by the tourist and the image projected by the POI can be negatively impacted in such situations.

We study a problem of designing a tourist route with time windows where, in addition to maximizing tourist satisfaction and given recommended levels of occupancy at the POIs, the aim is to minimize both over occupancy and lost time in the route. Lost time occurs when the amount of time used to do the route is higher than the length of the route, defined as the minimum time required to do the route (travel time plus visit time in the best conditions). Lost time can be interpreted as waiting time. We formulate a mixed integer linear programming model to solve a TTDP with time windows and recommended occupancy levels for POIs.

The background to address the problem is the research that has been conducted on the Tourist Trip Design Problem (TTDP) found in the literature. Some surveys of the TTDP can be found in [4, 6, 7]. A review of algorithms proposed to solve the TTDP can be found in [3, 6].

The construction of algorithms that provide solutions in a very short time is especially relevant. Some articles in this respect include [1, 2]. Proposals to balance the visits to the POIs and avoid congestion are presented in several works found in the literature [5, 8] but, dislike our work, recommended occupancy levels for the POIs are not explicitly considered in the model.

2 Problem Statement and Mathematical Model

Consider a network N(V, E) where \(V=\{v_1,...,v_n\}\) is the set of nodes and \(E \subseteq V \times V\) is the set of edges. The travel time between nodes \(v_i\) and \(v_j\) is denoted \(\bar{t}_{ij}\), it is the length of the shortest path (faster path) from \(v_i\) to \(v_j\). A route is a sequence of nodes, \(v_1,v_{i1},...,v_{ir},v_n\), nodes \(v_1\) and \(v_n\) are the initial and final points in the route. For a route, the initial and final points can be the same. Each node \(v_i\), \(1<i<n\), is a point of interest (POI) and it has a score \(s_i > 0\) which represents its attractiveness as a point to be visited. The POI \(v_i\) has opening and closing times \(L_i\) and \(U_i\) respectively, \(t_i\) is the duration of the visit and \(cap_i\) is the capacity of POI \(v_i\). The recommended occupancy at POI \(v_i\) is \(c_i\), it is desirable that at most \(c_i\) visitors enter point \(v_i\) at time \(\tau \) (\(c_i= \alpha _i \times cap_i\) where \(0 \le \alpha _i \le 1\)). And \(\rho _i\) is the contribution of a new visit to occupancy at POI \(v_i\).

The length of a route, denoted \(T_r\), is the summation of the total travel time and the total visit time. The time budget or available amount of time to do the route is \(T_{max}\). Moreover, initial and final times, \(T_{I}\) and \(T_{F}\), are given, so that the route should be done in the time interval \([T_{I},T_{F}]\). We have that \(T_{max} \le T_{F}-T_{I}\), and \(\tau _1\), \(\tau _n\) represent the starting route time and ending route time respectively. The lost time or gap is the difference between the duration of the route, given by \(T_r\), and the time used to do it, \(T_u=\tau _n-\tau _1\).

The function \(\gamma _i(\tau )\) represents the occupancy level at instant \(\tau \). In order to define the occupancy function for a POI \(v_i\) in the interval \([L_i,U_i]\), we consider that the occupancy for a discrete set of instants \(L=\overline{\tau }_1< \overline{\tau }_2 <,...,\overline{\tau }_q= U\) are known. The occupancy function is given by a piecewise linear function built from the known occupancy values.

We want to find the route from the initial point \(v_1\) to the final point \(v_n\) which maximizes the total score, minimizes the total over occupancy, minimizes the lost time, and satisfies the time limitations constraints.

2.1 The Model

To state the model we use the following sets, and variables.

Index sets:

\(I={1,...,n}\): index set corresponding to node set V.

\(I_1=I \setminus \{1,n\}\): index set I excluding initial and final nodes in the route.

\(K=\{1,...,q\}\): index set for time partition.

Variables:

\(x_{ij} = 1\) if in the route we go from point \(v_i\) to point \(v_j\), otherwise \(x_{ij} = 0\).

\(\tau _i\): instant at which POI \(v_i\) is reached.

\(\gamma _i(\tau )\): occupancy at \(v_i\) in time \(\tau \).

\(u_i\): variables introduced in order to avoid subtours.

\(z_i\): over occupancy at \(v_i\).

\(a_{ik}\): variable used to define the occupancy function, for \(v_i\) and \(k \in K\).

\(y_{ik}\): binary variable for the occupancy function, for \(v_i\) and \(k=1,...,q-1\).

Then the problem is stated as follows:

$$\begin{aligned} \min \Big ( -\sum \limits _{(i,j)\in I_1\times I} s_i x_{ij}, \; \sum \limits _{i\in I_1} z_i, \; (\tau _n-\tau _1)-\sum \limits _{i,j \in I}(t_i+t_{ij})x_{ij} \Big ) \end{aligned}$$
(1)
$$\begin{aligned} \sum \limits _{j \not = 1} x_{1j} = 1 \qquad \qquad \sum \limits _{i \not = n} x_{in} = 1 \end{aligned}$$
(2)
$$\begin{aligned} \sum \limits _{i \not = n} x_{ik} = \sum \limits _{j \not = 1} x_{kj}, \qquad \forall k \not = 1,n \end{aligned}$$
(3)
$$\begin{aligned} \sum \limits _{i \not = n} x_{ik} \le 1, \qquad \forall k \not = 1,n \end{aligned}$$
(4)
$$\begin{aligned} \tau _n - \tau _1 \le T_{max} \end{aligned}$$
(5)
$$\begin{aligned} L_i \le \tau _i \le U_i, \qquad \forall i \not = 1,n \qquad T_I \le \tau _i \le T_F, \qquad \forall i \end{aligned}$$
(6)
$$\begin{aligned} \tau _i + t_i+t_{ij} \le \tau _j + M(1-x_{ij}), \qquad \forall i,j \end{aligned}$$
(7)
$$\begin{aligned} \tau _i = \sum \limits _{k=1}^q a_{ik}\overline{\tau }_k, \; \forall i \end{aligned}$$
(8)
$$\begin{aligned} a_{i1} \le y_{i1}, \; \forall i \quad a_{ik} \le y_{i,k-1}+y_{ik}, \; \forall i, \; k =2,...,q-1 \quad a_{iq} \le y_{i,q-1}, \; \forall i \end{aligned}$$
(9)
$$\begin{aligned} \sum \limits _{k=1}^q a_{ik} = 1, \; \forall i \qquad \sum \limits _{k=1}^{q-1} y_{ik} = 1; \; \forall i \qquad \gamma _i = \sum \limits _{k=1}^q a_{ik}\gamma _i(\overline{\tau }_k), \; \forall i \end{aligned}$$
(10)
$$\begin{aligned} z_i \ge (-c_i + \gamma _i+\rho _i) -M\Big ( 1-\sum \limits _{j \in I}x_{ij}\Big ), \; \forall i \not =1,n \end{aligned}$$
(11)
$$\begin{aligned} u_i-u_j \le (n-1)(1-x_{ij}) -1, \qquad \; i,j \not = 1, i \not =j \end{aligned}$$
(12)
$$\begin{aligned} 2 \le u_i \le n, \qquad \forall i \not = 1 \end{aligned}$$
(13)
$$\begin{aligned} \begin{array}{l} x_{ij} \in \{0,1\}, \; \forall i,j ; \; \qquad \qquad \qquad 0 \le z_i \le cap_i - c_i, \; \forall i \not = 1,n, \\ a_{ik} \ge 0, \; \forall i, k \in \{1,...,q\}, \; \qquad \qquad \gamma _i \ge 0, \forall i \\ y_{ik} \in \{0,1\}, \; \forall i, k \in \{1,...,q-1\}. \end{array} \end{aligned}$$
(14)
figure a
figure b

If the initial and final points coincide, in the formulation \(v_n\) represents node \(v_1\) considered as the final point in the route. Expression (1) represents the objectives: maximizing the total score, minimizing over occupancy, and minimizing the lost time or gap. Constraints (2) indicate that \(v_1\) and \(v_n\) are the initial and final points, respectively. Expression (3) represents the flow conservation conditions. Constraints (4) indicate that a POI is visited at most once. The time budget limitation is included in constraint (5) and the time windows restrictions are constraints (6). The conditions on the sequence of times are incorporated in expression (7). Constraints (8) to (10) define the occupancy function, and constraints (11) define \(z_i\) as the over occupancy at point \(v_i\), with M representing a large number. Constraints (12) and (13) are included to avoid subtours. Expressions (14) are the domain constraints.

2.2 Problem Resolution

To solve the 3-objective optimization problem we apply a constraint method. We maximize the total score constrained to over occupancy and gap limitations and fix an upper bound for both over occupancy and the gap. The problem is

$$\begin{aligned} \begin{array}{l} \max \sum \limits _{(i,j)\in I_1\times I} s_i x_{ij} \\ \text{ subject } \text{ to } (2)-(14), \; z_i \le \zeta _i, \; (\tau _F-\tau _I)-\sum \limits _{i,j}(t_i+t_{ij})x_{ij} \le \beta \\ \end{array} \end{aligned}$$
(15)

where \(\zeta _i\) is the highest over occupancy value admitted for POI i and \(\beta \) is the upper bound for the gap.

3 A Heuristic Algorithm to Solve the Problem

In this section we present a GRASP to solve the problem posed in Sect. 2. We consider that a solution to the problem can be represented by a list

$$\begin{aligned} R=[(v_1,\tau _1),(v_{i_1},\tau _{i_1}),(v_{i_2},\tau _{i_2}),...,(v_{i_q},\tau _{i_q}),(v_n,\tau _n)] \end{aligned}$$
(16)

where the nodes are pairwise different except perhaps the initial and final points which can be the same and \(\tau _1< \tau _{i_1}< \tau _{i_2}<...<\tau _{i_q}< \tau _n\). We use notations \((v_i,\tau _i)\) and \((i,\tau _i)\) indistinctly. For simplicity, we can omit times in (16).

figure c

For the route R, we denote \(I_1(R)\) the set made of the POIs in R and the initial node (\(v_1\)). That is, \(I_1(R)=\{1,i_1,i_2,...,i_q\}\). The score of the route is \(S(R)=\sum \limits _{i \in I_1(R)} s_i\) and the gap is \(T_u-T_r=(\tau _n-\tau _1)-T_r\). For \(i \in I_1 \setminus I_1(R)\) we define the unit profit of i for R as \( \displaystyle p_i = \max \limits _{j \in I_1(R)} \frac{s_i}{\varDelta T_{ij}}\), where \(\varDelta T_{ij}= -\bar{t}_{jk}+\bar{t}_{ji}+\bar{t}_{ik}+t_i\) and j and k are consecutive points in the route R, that is, we go from node j to node k. Let \(j(i) = \arg \{ p_i \}\), which is equivalent to \(j(i) = \arg \{ \min \limits _{j \in I_1(R)} \varDelta T_{ij} \}\).

Fixed the parameter values, a route is built by application of a sequence of insertions. Once a route where no other POI can be inserted is built, an improvement procedure is applied. The construction phase is described in Algorithm 1. The insertion of a node in a route has to be done taking into account the occupancy limitations. If a node i is inserted between nodes j and k, times \(\tau \) from node k to the final point of the route increase in at least \(\varDelta T_{ij}\) units. Due to occupancy limitations for some POIs, this increase could be bigger and the insertion could be unfeasible.

Algorithm 2 contains the insertion algorithm. For the initial and final points in the route, we consider \(t_1=0\) and \(U_n = T_F\). In order to avoid the algorithm stops too early giving very short routes, the gap time constraint in (15) is relaxed. The solution obtained is improved by application of several procedures such as the insertion of POIs at the end of the route, reduction of the gap with Algorithm 3, where a pushing operation is executed, and an exchange algorithm.

Table 1. Computational example
Full size table

4 Computational Example

We solve the TTDP for n POIs randomly generated in a \([0,100]\times [0,100]\) square, for \(n=25, 50, 75,100\) and the metric \(L_1\). For each n we generate three instances. The scores are randomly generated in [1, 100]. Times (in minutes) are \((T_I,T_F,T_{max})=(600,900,240)\) and \((T_I,T_F,T_{max})=(600,1080,420)\). The maximum capacity is 100 and \(\alpha \in \{0.8, 0.9, 1\}\). The break instants in the occupancy function \(\gamma \) go from 540 to 1080 by steps of 60, and the values are integer numbers randomly generated between 30 and 100. The contribution value is \(\rho =1\) and \(\beta =45\). The initial and final points in the route are the same. The algorithm is executed 3 times for each of the 24 instances. Table 1 shows the best solution (route with maximum score) for each scenario \((n,T_I,T_F,T_{max},instance)\). The last two columns contain the computational times (in seconds) required to find the solution, the time before the improvement and the time consumed by the improvement procedure, respectively. The rest of times presented in the table are given in minutes.

5 Conclusions

Tourist route design is an important issue in the tourist management field. The problem modelled in this paper is to find a tourist route taking into consideration time windows and occupancy constraints, and 3-objectives. We maximize the total score while the other two objectives are incorporated as constraints. We propose a GRASP to solve the problem heuristically and present some preliminary computational results. Although a deeper study of the problem and the proposed heuristic is required, with a more extensive computational analysis, the results obtained seem promising.