# 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.1 Initialization Phase  
The first phase of the algorithm concerns the initialization of data and it is divided into two parts. In the first part, the algorithm, by knowing the city map, creates the initial graphs of the city tourist attractions: a tourist attraction is associated with a node and all the nodes are connected to each other through indirect arcs. For each pair of nodes the time needed to go from one attraction to another is specified, on the basis of the transport means, with a weight associated with the arc that connects the nodes. In addition, the times to reach each attraction starting from the origin PoI and vice versa are also provided. In particular, two weighted graphs are initially considered, respectively named \(G_{i,1}\) and \(G_{i,2}\), composed by the same nodes and arcs, i.e., \(V_{i,1}=V_{i,2}\) and \(E_{i,1}=E_{i,2}\), where each node represents a PoI of the city, each arc indicates the connection between two nodes and the arc weight represent respectively the travel times by foot in \(G_{i,1}\) and by bus/metro in \(G_{i,2}\). Considering two nodes \(a\) and \(b\) of \(G_{i,2}\), here we assume that the trip from \(a\) to \(b\) is performed mainly by bus and/or metro, with the possibility that a short segment of this trip must be traveled by foot. Moreover, for each node of \(G_{i,1}\) and \(G_{i,2}\) we are assuming that the travel time to go from the origin PoI to the node is equal to the travel time to go from the node to the origin PoI. After that, the graph \(G_{i}=\{V_{i},E_{i}\}\) is defined composed by the same nodes and arcs of \(G_{i,1}\) and \(G_{i,2}\). On each arc of \(G_{i}\) the weight is set among the following three possibilities, based on the user preferences:  
Figure 2: The UML diagram of Algorithm 1: data initialization and itinerary planning.  
1. time preference: the weight of the arc is given by the minimum travel time among the corresponding ones of \(G_{i,1}\) and \(G_{i,2}\); 2. foot preference: the weight of the arc is given by the travel time by foot on the corresponding arc of \(G_{i,1}\); 3. bus/metro preference: the weight of the arc is given by the travel time by bus/metro on the corresponding arc of \(G_{i,2}\). In addition, the resulting graph \(G_{i}\) also keeps track of the transport means used on each trip segment, i.e., by foot or by bus/metro. In the second part of the initialization phase, the tourist sets the following preferences: * \(t_{o}\), time available for the outward trip and \(t_{r}\), time available for the return trip; * \(t_{s}\), stop time at each node \(v\in V_{i}\); * define set \(V_{p}\subseteq V_{i}\) of nodes of high priority and set \(V_{s}\subseteq V_{i}\) of nodes of secondary priority with \(V_{p}\cap V_{s}=\varnothing\); * \(v_{s}\) source node and \(v_{d}\) destination node, among the nodes \(v\in V_{p}\); * define set \(V_{o}\subset V_{p}\) and \(V_{r}\subset V_{p}\), \(V_{o}\cap V_{r}=\{v_{d},v_{s}\}\), of the nodes to be visited on the outward and return journeys, respectively.