# A Novel Application Based on a Heuristic Approach for Planning Itineraries of One-Day Tourist
## 3 The Multi-Level Algorithm Approach for Tourist Itinerary Planning
### The Proposed Heuristic Approach
#### 3.1.2 Itinerary Planning Phase  
On the basis of the input from the initialization phase, the Algorithm 1 proceeds with the construction of two separate graphs \(G_{o}\) and \(G_{r}\) to determine the _outward_ and _return_ paths, respectively. The graph \(G_{o}\) and \(G_{r}\) are composed by the nodes \(v\in V_{o}\) and \(v\in V_{r}\), respectively. Moreover, the graphs \(G_{o}\) and \(G_{r}\) are of order \(N_{0}\) (cardinality of \(V_{o}\)) and \(N_{r}\) (cardinality of \(V_{r}\)), respectively, and are implemented through the adjacency matrices. Since the graphs are not oriented, connected and complete, the adjacency matrices are symmetric with a null diagonal. We solve the TSP (2) for the graphs \(G_{o}\) and \(G_{r}\), respectively, in order to find the minimum path \(P_{o}\) and \(P_{r}\) and the associated travel time cost \(t_{1}\) and \(t_{2}\). Now, let us define the following integer linear programming problem ILP1 in order to maximize the available travel times for the outward and return paths:  
\[F(\lambda)=\max\lambda\] \[s.t.\] \[ \begin{cases}\lambda\leq t^{{}^{\prime}}=t_{1}^{{}^{\prime}}-t_{o}\\ \lambda\leq t^{{}^{\prime\prime}}=t_{1}^{{}^{\prime\prime}}-t_{r}\\ t_{1}^{{}^{\prime}}=t_{1}+t_{stop}(P_{o})+y_{1}*t_{stop,s}+y_{2}*t_{stop,e}+t_{ p}\\ t_{2}^{{}^{\prime\prime}}=t_{2}+t_{stop}(P_{r})+y_{3}*t_{stop,s}+y_{4}*t_{stop,e}+t_{ p}\\ y_{1}+y_{3}=1\\ y_{2}+y_{4}=1\\ \lambda\in\mathcal{R}\\ y_{1},y_{2},y_{3},y_{4}\in\{0,1\}\end{cases} \] (3a) where \(\lambda\) is the real decision variable that has to be maximized in order to maximize the difference between the effective travel times \(t_{1}^{{}^{\prime}}\) and \(t_{2}^{{}^{\prime\prime}}\) and the respective available times \(t_{o}\) and \(t_{r}\). Let us specify that for the outward path \(P_{o}\), the source PoI is set as the initial node while the destination PoI as the final node. On the contrary, for the return journey \(P_{r}\) the destination PoI is set as the initial node and the source PoI as the final node. Moreover, with constraints (3c) and (3d) ILP1 takes into account the following variables: the sum of the stop time period at each PoI of \(P_{o}\) and \(P_{r}\), respectively called \(t_{stop}(P_{o})\) and \(t_{stop}(P_{r})\); the time period \(t_{p}\) to reach the origin PoI from the final point; the stop time period for visiting the source and destination nodes denoted respectively by \(t_{stop,s}\) and \(t_{stop,e}\). In particular, constraints, (3c), (3d), (3e) and (3f) are introduced to ensure that the source and end PoI can be visited only one time respectively on the outward or on the return journey. Moreprecisely, constraint (3e) states that if the tourist stops for visiting the source PoI on the outward path, he/she will not repeat the visit on the return path: on the return path, the tourist will just pass through the source PoI without stopping there. The same statement of (3e) is done for the end/destination PoI by applying constraint (3f). The resulting paths \(P_{o}\) and \(P_{r}\) are not definitive and a further analysis is required to satisfy the tourist preferences. The travel times \(t_{1}^{{}^{\prime}}\) and \(t_{2}^{{}^{\prime\prime}}\), must not exceed the time available for visiting \(t_{o}\) and \(t_{r}\), respectively. Consequently, the following algorithms will manage the itinerary by adding and/or removing none, one or more PoI (nodes) from the path \(P_{o}\) and/or \(P_{r}\) so that the time constraints are respected.