A Novel Application Based on a Heuristic Approach for Planning Itineraries of One-Day Tourist

Abstract

Technological innovations have revolutionized the lifestyle of the society and led to the development of advanced and intelligent cities. Smart city has recently become synonymous of a city characterized by an intelligent and extensive use of Information and Communications Technologies (ICTs) in order to allow efficient use of information. In this context, this paper proposes a new approach to optimize the planning of itineraries for one-day tourist. More in detail, an optimization approach based on Graph theory and multi-algorithms is provided to determine the optimal tourist itinerary. The aim is to minimize the travel times taking into account the tourist preferences. An Integer Linear Programming (ILP) problem is introduced to find the optimal outward and return paths of the touristic itinerary and a multi-algorithms strategy is used to maximize the number of attractions (PoIs) to be visited in the paths. Finally, a case study focusing on cruise tourist in the city of Bari, demonstrates the efficiency of the approach and the user interaction in the determination of the itinerary.

1. Introduction

The planning of touristic itineraries is a typical decision making process for tourists visiting a city in a limited time period. The selection of the most valuable Points of Interests (PoIs) is not simple.

In the last years mobile applications are offering a variety of services from vacation planning to mobile tourist guides and tourism recommender systems [1,2]. The design of flexible, efficient, and user-friendly applications for mobile devices has a great interest from both a commercial and a research point of view. The authors in [3] propose a mobile application based on a hybrid multiobjective genetic algorithm to smartly generate feasible itineraries. The algorithm incorporates an advanced heuristic to build a route, with a start and an arrival time passing from a set of locations each characterized by a score measuring its attractiveness, an opening and a closing time, and visit duration. Vansteenwegen et al. [4,5] present an advanced mobile tourist guide, capable of suggesting a near-optimal and feasible selection of attractions and a route passing among them. The related optimization problem is solved by using a combination of guided local search metaheuristics. Booth et al. [6] develop a data model for trip planning in multimodal transportation systems and Navabpour [7] plans a trip with multimodal transportation based on Service Oriented Architecture (SOA). In addition, Andre et al. [8] design a journey planning system based on safety, weather and specific travel time for individual user. Gonzalez et al. [9] propose a fastest-path computation system on a road network using a traffic mining approach. However, while the above papers mainly focus on the mobile application architecture, the following two subsections analyze existing contributions focusing on methodology and parameters.

1.1. Related Works: Methodology-Based Classification

This section groups and analyses research works that provide rigorous description of heuristic and metaheuristic approaches to solve the Tourist Trip Design Problem (TTDP). These approaches result the only viable methods to efficiently optimize the travel itinerary, by analyzing the problem from different perspectives, with different problem variables and constraints. The objective in TTDP modeling is to identify a set of near-optimal itineraries to maximize tourist satisfaction. The baseline combinatorial optimization problem for TTDP is the orienteering problem (OP). The OP can be used to model the TTDP where the PoIs are associated with a profit and the goal is to find a single tour that maximizes the profit collected within a given time budget. In the OP, given a starting node s, a terminal node t and a positive time limit (budget), the goal is to find a path from s to t such that the total profit of the visited nodes is maximized. In the related literature, Garcia et al. [10] propose an intelligent routing system that defines an optimization problem including multiple paths to move from one location to another. Such a system, by exploiting an iterated local search metaheuristic method, suggests a personalized tour combining information about the local attractions, weather forecasting and public transportation. Gavalas analyzes the models, algorithmic approaches and methodologies about tourist trip design problems [11]. Recent approaches are reported aiming at taking into account a multitude of realistic PoIs attributes and user constraints. In this context, Gunawan et al. focus on the most recent works about the Orienteering Problem (OP) and its variants [12]. The authors focus on a comprehensive and thorough survey of recent variants of the OP, including the proposed solution approaches. The work reports the new variants of the OP, such as the Stochastic OP, the Generalized OP, the Arc OP, the Multi-agent OP, the Clustered OP and others. The authors summarize several interesting applications which are related to the mobile crowdsourcing problem, the Tourist Trip Design Problem, the theme park navigation problem and others. The authors in [13] provide a detailed explanation about operation on tour routes only qualitatively. An optimizer is proposed in [14], where a multiobjective evolutionary algorithm is used to identify the near-optimal solutions to the planning of multiple-day routes in a reasonable computational time. In the contribution [15], the authors present a heuristic procedure for the generalization of a optimization problem to plan personalized recommendations for daily sightseeing itineraries for mobile tourist guides.

Extensions of the OP have been applied to model more complex versions of TTDP: the OP with time windows (OPTW) considers visits to locations within a predefined time window; this allows modeling opening days/hours of PoIs. The time-dependent OP (TDOP) considers time dependency in the estimation of time required to move from one location to another; therefore, it is suitable for modeling multimodal transports among PoIs. In particular, Cotfas considers a more complex variant of the tourist trip design problem i.e., the time-dependent in the estimation of the time required to move from one location to another for planning daily tours according to tourist’s preferences [16].

The team orienteering problem (TOP) is the extension of the OP to multiple tours. The TOP with time windows (TOPTW) has been mostly commonly studied among the aforementioned OP variants since it is useful for modeling several real-life optimization problems. Vansteenwegen et al. propose a metaheuristic algorithm to tackle a more effective extension of the optimization problem [17]. The proposed algorithm performs a planning of a multipleday tour by considering a set of PoIs, a visiting duration, and a set of multiple opening and closing times per day combined with the trip constraints of the tourist.

Other studies propose approaches based on Graph Theory [18,19,20,21], applied in tourism. The authors in [19] deal with typical tourist attractions in urban destinations, as pedestrian zones, market areas or urban areas of architectural, cultural and scenic value rather than only visiting sites of restricted access or taking the fastest route to move among city landmarks. Herein, the authors introduce Scenic Athens, a context- aware mobile city guide for Athens (Greece) which provides personalized tour planning services to tourists. Scenic Athens derives near-optimal sequencing of PoIs along recommended tours, taking into account a multitude of travel restrictions and PoI properties, so as to best utilize time available for sightseeing. The authors in [20] define tourist routes by means of graph theory. The authors also calculate some relative indexes (e.g., the circle number, circle ratio, line-point ratio etc.) to make quantitative evaluation of tourist routes. Chen et al. apply the Graph theory to optimize tour path and tour flows to provide practical solutions to tourist guides [21].

1.2. Related Works: Parameter-Based Classification

Another classification that can be proposed is based on the works that emphasizes the study of the effect of key parameters of the TTDP on the final solution, such as: (i) the selection of transport modes to reach the different PoIs; (ii) the choice of PoIs; (iii) the number of tours to be generated, on the basis of visiting duration; (iv) the visit duration of a PoI; (v) the travel times among PoIs; (vi) the daily time budget that a tourist wishes to spend on visiting a PoI; (vii) the weather conditions.

Transport is a critical and dynamic process of tourism, which facilitates physical movement to points of interest [22,23,24]. Transportation affects the accessibility to the tourist destination, the distance travelled, and the comfort of the trip [25,26]. The authors in [27] develop a genetic algorithm (GA) to solve the TTDP that included multimodal transport and real traffic parameters and time constraints.

In [14] the influencing factors of the tour route choices of tourists are analyzed by means of a questionnaire survey. Moreover, tour routes multiobjective optimization functions are prompted for the tour route design with the aim of maximise the user satisfaction with the minimum tour distance. The authors in [17] analyze the planning of a multipleday tour by considering a set of PoIs, a visiting duration, and a set of multiple opening and closing times per day combined with the trip constraints of the tourist. The authors in [28] apply an evolutionary algorithm to solve the tour planning problem in time-dependent urban areas. Gavalas et al. [29] develop a tool for tourist itineraries that considered the departure time and the mode of transport on the tourist route. Wu et al. [30] develop a mathematical model to consider the selection of transport modes, the travel budget, and the maximum travel times. Zheng et al. [31] design a multi-objective model of one-day urban tourist routes, taking into account the transport modes and the complexity of urban tourism transport systems, as congestion, and the transport needs of tourists. Zhang et al. [32] develop a model for the construction of itineraries in scenic routes considering the modes of transport. The authors in [33] analyze the environmental implications of tourist itineraries by creating groups of tourists that use a single mode of transportation (i.e., taxis). Some works study the use of electric vehicles (EV) for the generation of more environmentally friendly tourist itineraries, such as [34,35,36].

Other works focus on planning trips for tourist group [33,37], that consider the individual preferences of each tourist. The authors in [38] develop a model for the route design problem for various cycle-tourists. The model consider the preferences of each tourist who incorporates different benefits on the same route. Finally, the authors in [33] develop a route planning model that considers multiple days, urban tourism, PoI categories, and heterogeneous preferences for a group of tourists that maximise profit and minimises travel time, distance, and cost.

1.3. Contribution of the Paper

From the analysis of the above reported studies, the OP is not suitable in case the PoIs need to be selected and exchanged among different itineraries, like outward and return paths of a one day trip, because of time constraint. In this case, it is necessary to implement a multi-level algorithm to be able to consult the tourist on any relocation of PoIs in the tour. To these aims, we applied the Travel Salesman Problem (TSP) [39,40,41] method that involves finding the shortest route through n nodes that begins and ends at the same city and visits every node. The TSP is among the best-known combinatorial optimization problems and has been intensely studied by researchers in various research fields.

In this paper, we aim to determine the optimal itinerary for the one-day tourist, maximizing the number of PoIs to be visited in the outward and return parth, and at the same time minimizing the travel times taking into account the tourist preferences and hard time constraints. The idea is to allow the tourist to select the preferred PoIs to be visited on the first part of the day, i.e., in the outward trip, and on the second part of the day, i.e., in the return trip, respectively. We formulate our optimization problem on the basis of Graph theory, TSP and multi-level algorithms. We model the city PoIs network on the basis of the graph theory, where the nodes represent the various attractions (PoI) of the city and two separate graphs are derived. The tourist can select the PoIs of the starting graph to be visited with high priority in the outward and return journeys, respectively. In our application the tourist is part of the multi-algorithms approach interacting with it and taking decisions for one-day tourist. The proposed approach plans the tourist itinerary, minizing travel times based on the TSP algorithm, taking into account the priority list of PoIs and the decisions of the user. The TSP is used in this paper since it allows to consider a first itinerary solution including all the PoIs of the city that is refined by the multi-level algorithms interacting with the tourists. In detail, compared with the analyzed works, this paper presents the following novelties:

• an innovative multi-level algorithm approach is proposed to determine the optimal roundtrip path: the outward and return journeys are specified and customized, minimizing the total travel time, including the visiting time of each PoI.
• the number of attractions to be visited is maximized and is splitted between the outward and return path in order to improve the visiting experience on the basis of user preferences.
• the tourist is seen as an active and informed user who directly interacts with the system for the optimal planning of both the outward and return journeys, not only providing initial inputs and preferences but taking decisions at intermediate stages of the approach.

The rest of the paper is organized as follows: Section 2 describes the one-day tourist itinerary planning problem; Section 3 presents the Multi-level algorithm approach for the itinerary planning while Section 4 provides the analysis of the algorithms performance and complexity; Section 5 demonstrates the effectiveness of the proposed approach by a case study focusing on the cruise tourist in the city of Bari and Section 6 provides the conclusions and future works perspectives.

2. The One-Day Tourist Itinerary Planning Problem

The one-day tourist, having reached a stage of his journey through the airplane, train, car or cruise ship etc., wonders how to spend at best his/her time in the city in a short time period (e.g., one day).

Due to the limited time, it is therefore necessary to pay attention to the organization of the visits and excursions. The tourist can opt for a tour pre-organized by the operator or he/she can plan it on his/her own. In the first case, one of the advantages concerns the mere observation of the predefined roadmap to visit the city, without any worries. This case, on the other hand, does not always satisfy the personal interests of the individual tourist who must follow the visiting group and, in addition, can not personally manage the route and the stops. In the second case, however, the tourist has more freedom of choice but he/she must plan independently the trip in a city and respect the departure times that are mandatory. Instead of relying on the tours organized by the company, sometimes with unsatisfactory results, the tourist by use only a smartphone can select the preferred attractions.

Today, there are numerous online travel planning systems that allow to automatically generate a selection and routing plan to visit PoIs that suit the tourist’s personal interests [42]. These systems implement various functionalities that aim to satisfy different profiles of tourist interest [43,44]. Therefore, considering a tourist discovering the city, in addition to walking through its most famous streets, he/she wants to head, for example, to a restaurant near an attraction to have lunch and taste the typical dishes of the place, and then resume the tour and return back. For instance, by simply accessing an app from the smartphone, he/she can set the time available to carry out the tour from a starting point to a restaurant and the time to return back. The visiting times must also include the stop times for activities such as take photos in front of a monument, go shopping, visit a museum and so on. The tourist can also select the preferred PoIs to be visited on the first part of the day, i.e., in the outward trip, and on the second part of the day, i.e., in the return trip, respectively. In addition, the tourist can also indicate the PoIs that are less important and that can be deleted by the roundtrip in case of time unavailability.

Then, let us describe an example in order to present the addressed problem. Firstly, the following assumptions are made:

• the tourist is an active user who wants to interact with the application in order to customize the daily roundtrip;
• the PoIs of the city are initialized by the application;
• the tourist indicates the starting and destination PoIs, the travel modes and time preferences as well as the PoIs to be visited with high and secondary priority, in the first and second part of the day, respectively.

Let us consider the case of a cruise tourist who wants to visit the city in one day, without loss of generality. When arriving at the port, the tourist needs to have a plan for the daily tour. In particular, he/she needs to decide which PoIs to visit based on the available time and in which order, also making a priority list to be sure to visit the most important ones. There can be also the necessity to specify which PoIs to be visited in the first part of the day, that is usually lightful and more appropriate to visit outdoor spaces like parks, before to have a lunch, usually in a typical restaurant. The tour for the second part of the day, starts after lunch allowing to complete the city visit going towards the final destination point, i.e., the port. Of course, an application is needed to help the tourist at planning the less time consuming roundtrip, respecting the preferences. In our scenario, the application initializes the PoIs network and shows to the user the map of the city PoIs with related information, including traveling times among each PoI couple based on transport means. Different trip solutions can be provided by the application based on the user choice regarding the stop time at each PoI and preferred way of transport: (1) fastest, (2) by foot, (3) by metro/bus. The tourist is also asked to indicate the starting and destination points of the roundtrip, that are different from the origin/final point (i.e., the port), as well as the time deadline for the roundtrip. In addition, the tourist is asked to decide which PoIs to be visited in the first and second part of the day, indicating the priority and the desired time to dedicate to the visit. On this basis, the application try to generate the customized outward and return tours of the day by applying the heuristic procedure presented in Section 3. If the deadline time both for the outward and return trips are respected, the heuristic procedure investigates the addition of secondary importance PoIs and generates the final roundtrip itineraries. On the contrary, if the deadline time of the outward and/or the return tours is violated, the heuristic procedure can exchange PoIs between the first and the second tour. In case some feasible solutions are determined, i.e., the deadlines of the outward and return trips are satisfied, the procedure delegates to the user the choice of a solution from a list created by the application. Afterwards, the heuristic procedure determines the final customized outward and return tours of the day including possible addition of secondary PoIs. Finally, if the deadline time of the outward and/or the return tours is violated and no feasible solution is achievable, a PoI deletion procedure must be implemented in order to respect the deadline travel time. Let us summarize the necessary input and output information and data of the proposed itinerary planning application:

Initial inputs from the user:

• starting and ending PoI;
• deadline time both for the outward and return trips;
• stop times;
• priority list of PoI;
• list of PoIs both for the outward and return trips;
• preferred mode of travel;

Moreover, other inputs are required to the user from the application while running in order to refine the roundtrip customization as described in detail in Section 3.

Real time inputs from the user:

• preferred itinerary from a list of feasible solutions determined by the proposed automatic procedure.

Outputs by the application:

• outward and return paths;
• outward and return travel times.

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 PoIs 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}=\left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{arc}(\mathrm{i},\mathrm{j})\mathrm{is}\mathrm{in}\mathrm{the}\mathrm{tour}i,j\in \left\{1,\dots ,m\right\}\hfill \\ 0\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(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{array}{cc}\hfill & min\sum _{i=1}^m\sum _{j=1,j\ne i}^m{c}_{ij}{x}_{ij}\hfill \\ \hfill & s.t.\hfill \end{array}\phantom{}$$

$$\left\{\begin{array}{}\mathrm{(2a)}\hfill & {\displaystyle \sum _{i=1,i\ne j}^m}{x}_{ij}=1j=1,\dots ,m\hfill \mathrm{(2b)}\hfill & {\displaystyle \sum _{j=1,j\ne i}^m}{x}_{ij}=1i=1,\dots ,m\hfill \mathrm{(2c)}\hfill & {\displaystyle \sum _{i\in K}}{\displaystyle \sum _{j\in K,j\ne i}}{x}_{ij}\le \left|K\right|-1\forall K\subset \left\{1,\dots ,m\right\},\left|K\right|\ge 2\hfill \end{array}\right.$$

with $c_{ij}>0$$\forall i,j\in \left\{1,\dots ,m\right\}$, $i\ne j$ time cost to travel from i to j, K nonempty subset of the set of m PoIs and $m(m-1)$ number of binary variables. In particular, constraints (2c) ensures that no subset K can generate sub-tours, i.e., only a single tour will be generated. In order to obtain the symmetric version of the TSP it is necessary to have $c_{ij}$=$c_{ji}$ $\forall i,j\in \left\{1,\dots ,m\right\}$, $i\ne j$. It holds that the number of variables in the symmetric TSP is halves with respect to the asymmetric TSP. In this paper, we consider the symmetric TSP inside the proposed heuristic approach modeled with an undirect graph to find the optimal travel times and paths associated to the outward and return tours.

3.1. The Proposed Heuristic Approach

The proposed approach starts by Algorithm 1 described by the UML diagram in Figure 2 that is the upper level Algorithm that executes two phases: (1) initialization phase; (2) itinerary planning phase.

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:

(a)

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}$;

(b)

foot preference: the weight of the arc is given by the travel time by foot on the corresponding arc of $G_{i,1}$;

(c)

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.

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_o$ (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:

$$\begin{array}{c}\hfill F\left(\lambda \right)=max\lambda \\ \hfill & s.t.\hfill \end{array}\phantom{}$$

$$\left\{\begin{array}{}\mathrm{(3a)}& \lambda \le t^{{}^{\prime }}=t_1^{{}^{\prime }}-t_o\hfill \mathrm{(3b)}& \lambda \le t^{{}^{″}}=t_1^{{}^{″}}-t_r\hfill \mathrm{(3c)}& t_1^{{}^{\prime }}=t_1+t_{stop}\left(P_o\right)+y_1\ast t_{stop,s}+y_2\ast t_{stop,e}+t_p\hfill \mathrm{(3d)}& t_2^{{}^{″}}=t_2+t_{stop}\left(P_r\right)+y_3\ast t_{stop,s}+y_4\ast t_{stop,e}+t_p\hfill \mathrm{(3e)}& y_1+y_3=1\hfill \mathrm{(3f)}& y_2+y_4=1\hfill \mathrm{(3g)}& \lambda \in \mathcal{R}\hfill \mathrm{(3h)}& y_1,y_2,y_3,y_4\in \{0,1\}\hfill \end{array}\right.$$

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^{{}^{″}}$ 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}\left(P_o\right)$ and $t_{stop}\left(P_r\right)$; 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. More precisely, 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^{{}^{″}}$, 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. 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^{{}^{″}}>0$;

2.

travel times do not exceed available times: $t^{{}^{\prime }}\le 0$ AND $t^{{}^{″}}\le 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 Figure 3 and Figure 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^{{}^{″}}$ 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 beacuse 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 1.2: PoI Deletion Procedure

Algorithm 1.2 starts the node deleting procedure (see UML diagram of Figure 4). If $t^{{}^{\prime }}>0$, a node is eliminated from $G_o$ and, in case $t^{{}^{″}}>0$, a node is simultaneously deleted from $G_r$. After that, Algorithm 1.2 computes $P_o$ and $t_1$, $P_r$, $t_2$ and, in particular, $t^{{}^{\prime }}$ and $t^{{}^{″}}$ by applying ILP1. Then, the algorithm checks if the time constraints on $t^{{}^{\prime }}$ and $t^{{}^{″}}$ are satisfied. These steps are repeated iteratively by Algorithm 1.2 until time constraints are not respected or no more node can be deleted. The Algorithm 1.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^{{}^{″}}>0$, respectively. On the contrary, if $t^{{}^{\prime }}\le 0$ and $t^{{}^{″}}\le 0$, the PoI elimination is not necessary anymore and the Algorithm 1.2 goes to Algorithm 1.3 where the possible addition of other points is evaluated.

Algorithm 1.3: PoI Addition Procedure

In the case $t^{{}^{\prime }}\le 0$ and $t^{{}^{″}}\le 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$. At this point, if condition $t^{{}^{\prime }}\le 0$ and $t^{{}^{″}}\le 0$ is still verified the Algorithm 1.3 proceeds by adding another node $v\in V_s$, until no more nodes $v\in V_s$ can be added. On the other hand, if the addition of a node does not satisfy the time constraints, the added node is removed from the relative path and the Algorithm 1.3 checks whether it is possible to insert other nodes by repeating the operation until all nodes $v\in V_s$ are examined (see the UML diagram in Figure 5).

4. Complexity and Performance Analysis

In this section, the analysis of the complexity and performance of the proposed algorithms are provided. The following results describe the algorithms complexity:

• the Algorithm 1 requires the implementation of the ILP 1 problem including two TSP and 4 decision variables. Hence, considering a branch-bound approach, the complexity of Algorithm 1 is $O\left(2^4\right)+2\ast O\left(K\right)=O\left(K\right)$, with $O\left(K\right)$ TSP complexity;
• the Algorithms 1.1, 1.2 and 1.3 show complexity $O(N\ast K)$ since the ILP 1 problem is included in a N-dimensional “while” loop, where N is the number of PoI of graph $G_i$.

We can conclude that the complexity of the heuristic approach is $O(N\ast K)$. In order to be compliant with application time constraints, the TSP has been implemented using the Lin-Kernighan algorithm that often keeps its tours within 2% of the Held-Karp lower bound [48], then $K=O\left(N^{2.2}\right)$. Therefore, our heuristic approach shows complexity $O\left(N^{3.2}\right)$. Let us underline that the proposed application interacts with users to find the final best solution. Therefore, the time to complete the heuristic approach application and provide the final solution strongly depends on the velocity of the user given the necessary inputs to the application.

The performance of the proposed algorithms are validated with benchmark orienteering algorithms presented in [49]. In particular, the data set used in [49] and reported in [50] is used as benchmark (see Figure 6). Since, in the considered benchmark data set the PoI importance is defined by a score, we associate the priorities to the higher score values as reported in Figure 6. Note that in Figure 6, X and Y are the cartesian coordinates of the PoI and the PoIs distance is computed using the Euclidean distance formula [49]. Moreover, for comparison purpose, we assume that (i) the PoI $V_d$ is selected as to minimize the total travel time, (ii) the Euclidean distance includes the stop time for visiting in our approach, (iii) the user preferences are randomly set in the instances simulation. Now, let us report the comparison results between the proposed heuristic and the D-algorithm and S-algorithm proposed by [49]. In particular, Figure 7, Figure 8 and Figure 9 report respectively the comparison results considering data set of problem 1, 2 and 3, where Tmax represents the total travel time. Comparing the score and time values it can be concluded that the proposed approach performs much better than D-algorithm and little worse than the S-algorithm. However, in case only addition of PoI are needed by Algorithm 1.3, the proposed approach performs better than S-algorithm too. It is also remarked that the performance of Algorithm 1.2 can be further improved when a considerable number of PoIs must be deleted.

5. Case Study

This section presents a case study where the proposed multi-level algorithm approach is applied to solve the cruise tourist problem in the metropolitan port city of Bari. Bari is the capital city of Apulia Region and the second biggest city in southern Italy. Since the roman epoch, Bari became an important commercial center, during the Saracen domination. From 1071, it became a big maritime center and still today it is an important port hub of the Mediterranean sea.

In the initialization phase of Algorithm 1, all the main attractions of Bari are determined and represented by the adjacency matrix of the graph $G_i$ as it shown in Figure 10. Note that the weight of arcs are decided on the basis of the time preference (a) described in Section 3, according to the user. For better understanding of Figure 10 let us consider two examples: “1mp” in the box from PoI 2 to PoI 1 means that the tourist should travel by foot for 1 min; “10m p+a” in the box from PoI 2 to PoI 7 means that the tourist should travel by foot and by bus for 7 min total. The tourist inputs are provided in the initialization phase of the mobile application, where the tourist inserts the preferences and constraints related to: (i) the maximum available time for the outward and return path; (ii) the PoIs to visit during the outward and return path; (iii) the preferred transport mode, i.e., by foot, by bus or the fastest way (see Figure 11). Moreover for each node of the PoI network, the tourist can edit the selection of transport mode according to his/her preferences (see Figure 12).

Let the Saint Nicolas Basilica (node 2) be the starting point and Lungomare Nazario Sauro (node 8) be the final point of the tourist itinerary. Note that for path $P_o$ the starting point is node 2 and the final point is node 8. On the contrary, for $P_r$ the starting point is node 8 and the final point is node 2. In particular, let us define the nodes of priority level 1 (maximum priority) $V_p=\{1,2,4,5,8,9,10\}$, and the secondary nodes with $V_s=\{3,6,7\}$. Furthermore, the PoI to be visited on the outward and return paths and the stop time at each PoI are also reported in Figure 10 and Figure 13.

The Algorithm 1 creates the two graphs $G_o$ and $G_r$ by using only the nodes of $G_i$ of priority level 1 (maximum priority) and calculates the travel times $t_1$ and $t_2$, as it is reported in Figure 14. It implies $V_o=\{1,2,4,5,8\}$ and $V_r=\{2,8,9,10\}$. The travel times $t_1$ and $t_2$ do not include the time needed to go from the port to the first stop of the tour, i.e., node 2, and vice versa that is equal to 10 min. In Figure 15 the vector of the times to reach the port from each node is shown.

Let us set $t_o=150$ min and $t_r=250$ min. Since $t^{{}^{\prime }}>0$, as $t_1^{{}^{\prime }}$ = 159 (obtained by the sum of the travel and stop times from one node to another in the outward path, except the stop times of node 2 and 8) and $t_2^{{}^{″}}$ = 189 (obtained by the sum of the travel and stop times from one node to another in the return path, considering also the stop times of node 2 and 8), this solution is not feasible.

Therefore, Algorithm 1 goes to Algorithm 1.1 that tries to exchange the nodes between graph $G_o$ and $G_r$ in order to obtain all the feasible solutions that are stored in FS. In the table FS, two solutions are stored which are obtained by the following two nodes exchanging: (i) node 4 of $G_o$ with node 10 of $G_r$, (ii) node 1 of $G_o$ with node 10 of $G_r$. In Figure 16, $P_o$ and $P_r$ of solution (i) obtained by solving ILP1 are shown. In this case $t^{{}^{\prime }}<0$ and $t^{{}^{″}}<0$, since $t_1^{{}^{\prime }}$ = 130 and $t_2^{{}^{″}}$ = 212 (node 2 and 8 are visited during the return path).

In Figure 17, $P_o$ and $P_r$ of solution (ii) obtained by solving ILP1 are shown. In particular, in this case $t^{{}^{\prime }}<0$ and $t^{{}^{″}}<0$, since $t_1^{{}^{\prime }}$ = 129 (node 2 and 8 are visited during the outward path) and $t_2^{{}^{″}}$ = 215.

The two resulting feasible solutions are shown to the user that can select the preferred one in the mobile application (see Figure 18). Let us suppose that the tourist selects path (i). Therefore, Algorithm 1.1 goes to Algorithm 1.3 that tries to add nodes of priority 2 both on the outward and on the return paths. Since it implies that $t^{{}^{\prime }}>0$, node 3 cannot be added to the route and it is removed. The adding of node 3 is checked for the outward path (see Figure 19). In this case, there is time available since $t^{{}^{″}}<0$ and $t_2^{{}^{″}}$ = 244. Therefore, node 3 with priority 2 is added to $G_r$. Moreover, since there are no other nodes of $G_i$ to be added, the outward journey does not change.

Figure 20 and Figure 21 depicts the GUI of the mobile application showing the final outward and return paths, respectively, connecting the identified PoIs.

The procedure ends and the tourist can get the sequence of attractions in both trips with the relative means of transport. In the proposed case study, the mathematical calculations to obtain the final solution are performed in about 2 seconds.

The presented application demonstrates the effectiveness of the proposed heuristic approach in planning the itinerary for the one-day tourist, customizing the outward and return paths of the roundtrip in the city of Bari. In particular, the application can manage the map of city PoIs, showing the travel means and times for each PoI pair, decided based on the user preferences. The tourist preferences can initially be input through specific app pages like presented in Figure 11 and Figure 12, where it is possible to decide which PoIs to be visited in the outward and return paths, respectively, and the preferred traveling mode. In particular, in the proposed case study it is evident how the Algorithm 1.1 recovers the initial unfeasible solution providing to the tourist alternative feasible trips including all the high priority PoIs. After the user choice, made as in the app page in Figure 20, Algorithm 1.3 further improves the solution adding node 3 belonging to secondary priority list, given one more PoI to be visited.

Let us remark that the obtained solution by applying the proposed procedure can be sub-optimal because of the human intervention. Indeed, with respect to a classical orienteering problem, the user subdivides the PoIs between outward and return trip and can choose a feasible itinerary according to the preferences affecting the real time procedure. Nevertheless, even if the obtained solution can be non optimal, it is surely customized based on the user preferences. Moreover, in Section 4, we enlighten that the proposed heuristic procedure shows better performances than other algorithms such as D-algorithm and S-algorithm [49] in some specific cases.

6. Conclusions

This paper is aimed at providing a tool to help the one-day tourist in the difficult choice to plan an itinerary in a city. Indeed, a tourist often renounces relying on professionals of the sector who offer a service although complete, often pre-packaged and not taking into account her/his passions and preferences.

The proposed approach builds a network of points of interest (PoIs), proposing the city attractions but leaving the choice of the PoIs to be visited by the tourist. Based on the obtained graph, a multi-algorithms approach is provided to determine the optimal itinerary. The tourist is part of the multi-algorithms approach interacting with it and taking decisions.

An Integer Linear Programming (ILP) problem is introduced to find the optimal outward and return paths of the touristic itinerary and the multi-algorithms strategy is used to maximize the number of PoIs to be visited in the paths. Moreover, a case study demonstrates the approach efficiency and the steps of the procedure.

Finally, an app prototype has been developed and several use cases are being tested to iron out bugs before writing the final code. Future works will focus on useful developments of the application: integrating the possibility of making reservations at hotels, purchasing entrance tickets for the various sites and promoting sustainable mobility by providing simple but complete and updated information on how to get around the city (bus/metro time schedule, opening/closing hours of attractions, etc.); locating bike-sharing stations and bicycle parking; considering the cost as additional objective function to be minimized. Furthermore, Algorithm 1.2 will be object of further studies in order to improve its performance.