# 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  
In this Section, we want to present an adequate solution to the problem of the one-day tourist, whose goal is to visit the greatest number of attractions and carry out activities of his own liking, respecting the times available for visiting. First of all the city PoI network needs to be modeled in order to connect all the PoIs and decide the best itinerary. We apply the Graph theory [21; 45] to model and study the PoIs network which in this paper is modeled as a weighted connected graph [46]. From each graph a path is determined ensuring that the tourist will visit only once those nodes representing the essential PoI: (i) the first path, called outward path, is from the source to the destination; (ii) the second path, called return path, is from the destination to the source. In particular, the nodes of the graph represent the city attractions. In addition, the weight of an arc connecting two nodes represents the travel time between two attractions. More in detail, the proposed approach uses two graphs \(G_{o}\) and \(G_{r}\) that are built considering the following tourist inputs: the starting and ending PoIs of the outward path (they correspond to the ending and starting PoIs of the return path), the other preferred Pols to visit during the outward and return path, the preferred transport mode. The starting PoI (ending PoI) of the outward path is represented by the source node (destination node) \(v_{s}\) (\(v_{d}\)) as shown in Figure 1. Moreover, the starting PoI is the place that the tourist firstly reaches after leaving the airport, port or station that are respresented in Figure 1 with the origin node \(V_{origin}\). The origin node is not included in the set of nodes of \(G_{o}\) and \(G_{r}\). Finally, each arc of graphs is weighted by the travel time between two PoIs and the time depends by the preferred transport mode chosen by the tourist. The proposed approach to solve the tourist problem is based on a multi-level algorithm approach [39]. The proposed Algorithms are modeled by means of UML diagrams. UML is a standard highly recognized language widely used to visually describe software programs and algorithms [47]. More specifically, there is the main algorithm, so called Algorithm 1, that is responsible for the data initialization and for the determination of the initial paths. Moreover, Algorithm 1 makes use of two sub-algorithms to find an optimal planning of the itinerary based on the tourist needs in term of time and places of interest, by applying the TSP algorithm. The TSP is about a traveling man who wants to visit only once each PoI of the list returning to the initial PoI through the least cost route. The TSP is suitable to be modeled through a graph in which the nodes are the PoI and each arc connects a couple of PoI (\(i,j\)) including a travel cost from \(i\) to \(j\). The total lenght of a journey is given by the sum of the arc weights included in the round-trip of the traveler. In order to formulate the generic version of the asymmetric TSP, the following binary variables are needed:  
\[x_{ij}= \begin{cases}1&\text{if arc (i,j) is in the tour}\qquad i,j\in\{1,\dots,m\}\\ 0&\text{otherwise}\end{cases}  \tag{1}\]  
with \(m\) total number of PoIs. Now, according to the Dantzig-Fulkerson-Johnson formulation the TSP can be formalized as the following integer linear programming problem:  
\[ \begin{split}&\text{}min\sum_{i=1}^{m}\ \sum_{j=1,j\
eq i}^{m}c_{ij}x_{ij}\\ &\text{}s.t.\end{split} \] \[ \begin{split}&\left\{\sum_{i=1,i\
eq j}^{m}x_{ij}=1\qquad j=1, \dots,m\\ &\sum_{j=1,j\
eq i}^{m}x_{ij}=1\qquad i=1,\dots,m\\ &\sum_{i\in K}\sum_{j\in K,j\
eq i}x_{ij}\leq|K|-1\qquad\forall K \subset\{1,\dots,m\},|K|\geq 2\end{split} \right.\end{split} \tag{2a}\] \[ \begin{split}&\left\{\sum_{i=1,i\
eq j}^{m}x_{ij}=1\qquad j=1, \dots,m\\ &\sum_{j=1,j\
eq i}^{m}x_{ij}=1\qquad i=1,\dots,m\\ &\sum_{i\in K}\sum_{j\in K,j\
eq i}x_{ij}\leq|K|-1\qquad\forall K \subset\{1,\dots,m\},|K|\geq 2\end{split}