# 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
Now, considering that \(t_{o}\) and \(t_{r}\) are the available travel times to complete the outward and return journeys, respectively, two cases which needs to be managed can arise:  
1. travel times exceed available times: \(t^{{}^{\prime}}>0\) OR \(t^{{}^{\prime\prime}}>0\);
2. travel times do not exceed available times: \(t^{{}^{\prime}}\leq 0\) AND \(t^{{}^{\prime\prime}}\leq 0\);  
In particular, the management of case 1 is performed by Algorithm 1.1 and Algorithm 1.2, respectively described by the UML diagrams in Figures 3 and 4, while case 2 is managed through Algorithm 1.3 described by the UML diagram of Figure 5 in the following. At the end of Algorithm 1.1 and Algorithm 1.3, Algorithm 1 displays the final itinerary to the tourist. Algorithm 1.1: PoI Exchange Procedure  
In case 1, it is necessary to manipulate the outward and return paths, \(P_{o}\) and \(P_{r}\), in order to respect the time constraints, to avoid delay in the origin PoI. An attempt is made to keep all the PoI of high priority by exchanging nodes between those selected for the outward and the return journeys. To this aim, a node belonging to the outward graph \(G_{o}\) is exchanged with a node belonging to the return graph \(G_{r}\). Once the exchange has been made, the Algorithm 1.1 determines the new paths \(P_{o}\) and \(P_{r}\) and the travel time \(t_{1}\) and \(t_{2}\) by applying ILP1. Afterwards, it checks if the times \(t^{{}^{\prime}}\) and \(t^{{}^{\prime\prime}}\) are positive or negative and one of the two cases can occur, as highlighted in Figure 3.  
If case 1 occurs, Algorithm 1.1 updates the table \(FS\) of feasible solutions, i.e., records the paths \(P_{o}\) and \(P_{r}\) obtained by feasible nodes exchange. Afterwards, all the possible nodes exchange are tried between the two graphs (see Figure 3) and all the feasible solutions are recorded in Table \(FS\). If case 2 occurs the Algorithm 1.1 ignores the obtained solution because it is not feasible and proceeds with the node exchange procedure until other combinations are no longer possible. After all possible nodes exchange have been made, the Algorithm 1.1 checks if suitable solutions have been found. If table \(FS\) is not empty, Algorithm 1.1 asks the tourist to indicate one of the solution in table \(FS\) and Algorithm 1.1 goes to Algorithm 1.3. On the contrary, if table \(FS\) is empty, i.e., no feasible node exchange are possible, Algorithm 1.1 goes to Algorithm 1.2 to start the node deleting procedure. Algorithm 2: PoI Deletion Procedure  
Algorithm 2 starts the node deleting procedure (see UML diagram of Figure 4). If \(i^{{}^{\prime}}>0\), a node is eliminated from \(G_{o}\) and, in case \(t^{{}^{\prime\prime}}>0\), a node is simultaneously deleted from \(G_{r}\). After that, Algorithm 2 computes \(P_{o}\) and \(t_{1}\), \(P_{r}\), \(t_{2}\) and, in particular, \(t^{{}^{\prime}}\) and \(t^{{}^{\prime\prime}}\) by applying ILP1. Then, the algorithm checks if the time constraints on \(t^{{}^{\prime}}\) and \(t^{{}^{\prime\prime}}\) are satisfied. These steps are repeated iteratively by Algorithm 2 until time constraints are not respected or no more node can be deleted. The Algorithm 2 displays an error message in case, after all possible nodes of \(G_{o}\) or \(G_{r}\) have been deleted, it still holds \(t^{{}^{\prime}}>0\) or \(t^{{}^{\prime\prime}}>0\), respectively. On the contrary, if \(t^{{}^{\prime}}\leq 0\) and \(t^{{}^{\prime\prime}}\leq 0\), the PoI elimination is not necessary anymore and the Algorithm 2 goes to Algorithm 2 where the possible addition of other points is evaluated. Figure 3: The UML diagram for the node exchange procedure. **Algorithm 1.3**: Pol Addition Procedure  
In the case \(t^{{}^{\prime}}\leq 0\) and \(t^{{}^{\prime\prime}}\leq 0\), it is reasonable to add one or more nodes to the paths \(P_{o}\) and \(P_{r}\). Thus, a node \(v\in V_{s}\) with secondary priority is temporarily added to \(G_{o}\) and \(G_{r}\). Note that \(N_{s}\) is the cardinality of \(V_{s}\).