=Paper=
{{Paper
|id=Vol-1772/paper5
|storemode=property
|title=Multi Attributes Approach for Tourist Trips Design
|pdfUrl=https://ceur-ws.org/Vol-1772/paper5.pdf
|volume=Vol-1772
|authors=Ilaria Baffo,Pasquale Carotenuto,Antonella Petrillo,Fabio De Felice
|dblpUrl=https://dblp.org/rec/conf/aiia/BaffoCPF16
}}
==Multi Attributes Approach for Tourist Trips Design==
https://ceur-ws.org/Vol-1772/paper5.pdf
Multi Attributes Approach for Tourist Trips Design
Ilaria Baffo1, Pasquale Carotenuto2, Antonella Petrillo3, Fabio De Felice4
1
Industrial Engineering School (DEIM) - University of Tuscia, Italy
ilaria.baffo@unitus.it
2
Istituto per le Applicazioni del Calcolo (IAC) - CNR, Italy
p.carotenuto@iac.cnr.it
3
Department of Engineering - University of Naples “Parthenope”, Italy
antonella.petrillo@uniparthenope.it
4
Department of Civil and Mechanical Engineering - University of Cassino and Southern
Lazio, Italy
defelice@unicas.it
Abstract. The authors propose a Multi Attributes approach to meet the demand
of personalized tourist tours into cultural cities. Respecting to others works
present into the literature, in this paper the decisional process includes two
phases and a high number of variables that don’t increase the complexity of the
problem. A real application in an Italian city, Florence, is presented to
demonstrate the great potential of this system into real context. The first phase
of optimization is solved applying an innovative Genetic Algorithm, the second
one a Multi Criteria Method, Analytic Hierarchy Process (AHP). The
combination of these two approach gives flexibility to the system with respect
to number of variables and allow to return a good solution for tourist in few
second of computational time.
1 Introduction
The increasing use of mobile devices in everyday life has favored the creation of
intelligent applications also in field such as tourism, culture and hobbies. One of the
most interesting applications provides opportunity to help tourists in choosing the best
route given a maximum time of visit. During the last years several researchers have
faced this problem with the aim to reduce uncertainty and increase the personalization
of the tourist paths. In the scientific literature, the problem is better known as Tourist
Trip Design Problem (TTDP). The authors in this work propose a Multi Attributes
Decision Support System (MDSS) to meet the demand of personalized tourist tours
into cultural cities. As described in the following many researchers have successfully
addressed this problem, but, only few of these have proposed real applications able to
consider several attribute to decisional process. The Multi Attributes Decision
Support System proposed, facing the TDPP in two steps. Firstly, a Genetic Algorithm
(GA) solves in optimal way the Orienteering Problem (OP) on real instances coming
from Italian historical cities, Florence. The validation of algorithm is guaranteed
creating an A Mathematical Programming Language (AMPL) model able to return the
optimal solution for small instances of the same problem. Finally, the optimal
solutions are compared on basis of different attributes having the features to be added
up. The last step has been conducted with the use of Multi Criteria Analysis Methods.
Thank to this approach, the obtained solutions can be evaluated on basis of several
attributes like: time of decision with respect to time of travel, duration of travel,
levels of freedom into the decision, degree of additionality of preferences, number of
decision-makers, numbers of cultural heritages to visit, etc. Real cases studies are
given with the aim to offer development ideas for implementation of smart
applications for tourist trips' design. The proposed methods can reach important
results where the variables of the problem are numerous and the optimization process
too long and complex. The rest of paper is organized as follows: a review of literature
is given in section 2, the mathematical model and its resolution with genetic algorithm
is explained in section 3. Section 4 presents AHP approach and its integration with
optimization model is discussed. Application and results are analyzed in Section 5.
Finally, conclusion and future researches are proposed in section 6.
2 Literature Review
As well explained in [5,10] the described route-planning problem has been considered
as an application of the Orienteering Problem or its variants. In the OP, several
locations with an associated score have to be visited only once in order to obtain a
total trip score. The objective is to obtain a total trip score as high as possible without
violating a time restriction. There have been works on exact methods that have
yielded solutions to smaller sized problems. Due to the computational limitations of
the exact algorithms, several heuristic were explored to many researchers in the past.
The first heuristics were proposed by Tsiligirides (1984) in [9] and are known as the
S-algorithm and the D-algorithm. The S-algorithm uses the Monte Carlo method to
construct routes using probabilities correlated to the ratio between node score and
node distance from the current node. The D-algorithm is built based upon the vehicle
scheduling method proposed by Wren and Holiday (1972) [12]. Others heuristics
have been explored in the years to solve this kind of problems, in [8] a Tabu Search
approach has been used for Multi Constrained Team Orienteering Problem and its
application in touristic trip planning. In [7,11] the authors propose to solve the Multi–
Constraint Team Orienteering Problem with Multiple Time Windows with known
heuristic like Iterated Local Search (ILS) and Greedy randomized adaptive search
procedure (GRASP). Iterated Local Search is proposed also in [4] to solve real-time
Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW).
During the last years, many authors have chosen to implement evolutionary algorithm
trying to reduce the computational time and to improve the quality of proposed
solution to tourist. In [2] the authors propose an evolutionary algorithm to solve a
multi-objective problem for personalized tours in street networks. In this case, the trip
is long multiple–day and a Team Orienteering Problem with Time Windows
(TOPTW) is solved with a heuristic approach whose computational times are not
clearly declared. The aim of the authors is to give in few second an optimal solution
of OP and secondly introduce more elements that can be analyzed with multi criteria
analysis. In this way, the complexity of the problem is lower and the computational
time too, then the approach is more usable for real time digital applications.
35
3 Problem Description
In this work the authors face the single day Tourist Trip Design Problem (TTDP)
modelling an Orienteering Problem (OP). In the OP, a set of N location, also called
Point of Interest (PoIs), corresponding with nodes i is given, each with a score Si. The
starting point and the end point are fixed. The time tij needed to travel from vertex i to
j is known for all vertices. The problem became more complex because not all the
vertices can be visited since a given threshold Tmax limits the available time. The goal
of the OP is to determine a path, limited by Tmax that visits some of the vertices, in
order to maximize the total collected score. Other works propose to optimize the
problem maximizing the number of PoIs visited, the problems coincide if we suppose
each point’s score equal to 1. The scores are assumed to be entirely additive and each
vertex can be visited at most once. In this algorithm the maximum time available to
visit the PoIs is considered as constrain of the problem. At the same time, all solutions
are defined by a set of PoIs visited, a time of visit for each point and a time of
walking from one point to another point. The OP can be formulated as follows: Si≥0 is
the score associated to node i, cij is the cost associated to path between node i and
node j. Usually n nodes are considered in the Euclidean plane. Since the distance and
travel time between nodes are determined by the geographical measure, distance is
used as the representative of path’s cost. Generally, the mathematical model of the OP
is formulated as follows:
n n
(1)
Si xij
i=1 j=1
Subject to
n n-1 (2)
x1j = xin =1
j=2 i=1
n-1 n
(3)
xik = xkj ≤1 k=2,…,n-1
i=2 j=2
n n
cij xij Tmax ∀i, j 1,…,n (4)
i 1 j 1
(5)
2 ui n ∀i 1,…,n
(6)
ui – uj +1 n‐1 1‐xij ∀ i,j 1,…,n
(7)
xij ∈ 0,1 ∀ i,j 1,…,n
Where (1) represents the problem’s Objective Function to maximize the total
collected score S. Constraint (2) guarantee that the path starts in vertex 1 and ends in
vertex N. Constraint (3) ensures the connectivity of the path and guarantee that every
vertex is visited at most once. Constraint (4) ensures the limited time budget T.
36
Constraints (5) and (6) are necessary to prevent sub-tours. Constraints (7) requires
that the variables are binary. The decisional variable xij is equal to 1 if the node j to i
are connected, 0 else. This formulation guarantees as result a tour able to: Visit as
many PoIs as possible; Visit PoIs at most once; Visit PoIs that maximize the Total
Score (Objective Function); Visit PoIs connected among them; and Visit PoIs
respecting the limitation time. The set of solutions coming from the genetic algorithm
represent the inputs for multi criteria approach with AHP.
4 Multi criteria approach: Analytic Hierarchy Process.
The AHP breaks down a decision-making problem into several levels in such a way
that they form a hierarchy with unidirectional hierarchical relationships between
levels [3]. The AHP for decision making uses objective mathematics to process the
inescapably subjective and personal preferences of an individual or a group in making
a decision. With the AHP, one constructs hierarchies or feedback networks, then
makes judgments or performs measurements on pairs of elements with respect to a
controlling element to derive ratio scales that are then synthesized throughout the
structure to select the best alternative. The top level of the hierarchy is the main goal
of the decision problem. The lower levels are the tangible and/or intangible criteria
that contribute to the goal. The bottom level is formed by the alternatives to evaluate
in terms of the criteria. The modeling process requires a pairwise comparisons of the
elements in each level using a scale of 1-9, as suggested by Saaty [6]. The result of
the comparison is the so-called dominance coefficient aij that represents the relative
importance of the component on row (i) over the component on column (j), i.e.,
aij=wi/wj. The pairwise comparisons can be represented in the form of a matrix. After
all pairwise comparison is completed, the priority weight vector (w) is computed as
the unique solution of Aw=λmaxw, where λmax is the largest eigenvalue of matrix A.
Finally, consistency index CI is estimated. CI could then be calculated by:
CI=(λmax−n)/n−1. In general, if CI is less than 0.10, satisfaction of judgments may be
derived. For this application the AHP takes as input the results of optimization
process and evaluates these under several criteria better explained in the next
paragraph. As first activity, the mathematical model is supposed to model the
capacitated orienteering problem, as second phase we solve the formulation
implemented a meta-heuristic known as Genetic Algorithm (GA). Then, we applied a
multi-criteria analysis (AHP model) to algorithm’s results to order the founded
solutions respect to the following objectives: Time L-path, Visited places, Ticket cost.
5 Problem Resolution
The authors propose an optimization approach that draw inspiration on Genetic
Algorithm (GA) as developed by Holland (1975) and then described by Goldberg
(1989). GA starts initializing a First Population composed by a pre-determinate
number of individuals. Each individual represents a solution for the faced problem
and it is characterized by several elements such a chromosome and a fitness value.
37
The individual’s chromosome is composed by several gene that can assume binary or
integer value, the combination of these genes usually represents the problem’s
solution thanks to a correspondence between the gene’s value and the problem’s
variables value. The individual’s fitness value corresponds to solution objective
function’s value, and it’s basic into determinate the individual’s probability to survive
at evolution process, so that bad individuals are destined to not have a long life into
population. The difference between the old and the new population in the
evolutionary process is guaranteed by the presence of two important operations called
Mutation and Crossover. After several generations, the best solution converges, and it
hopefully represents the optimum or suboptimum solution to the problem at hand. GA
are successfully applied to different contexts in order to solve a very large number of
problems, for this purpose various and original genetic operators are developed, that
revisit the original concept of mutation and crossover. In this application the authors
adopt a circular representation of chromosome and several heuristic techniques to
improve the evolutionary process through mutation and crossover operations. In our
GA the chromosome is composed of all nodes that the tourist want visit, without the
start node and the end node that can be added at the end of optimization process. This
coding of chromosome with respect to problem’s solution representing by a single
tour, allows to have only admissible solutions better or worst on basis of Total score
reached by visiting more or more better PoIs. The Fig. 1 shows like each chromosome
represents a sequence of visiting PoIs, i.e. a tour, i.e. a solution for the OP. The
Closed loop Structure of Chromosome code allows a wider and faster research of
solutions.
Fig. 1: Encoding and Decoding process
As previously described the GA structure is based on constitution of a population at
each iteration. This population step by step evolves and the algorithm found better
solutions for the faced problem. Following a synthetic description of the implemented
GA pseudocode is reported.
Parameters Setting
Initialization
Generate a feasible solution randomly as individual
38
Save them into the population Pop (i)
Loop until the population’s size S is reached
Calculate Fitness to define the Best Individual BI(i) of P(i)
While the number of iterations isn’t reached do
Set iteration i = 0
Selection: Roulette function for selecting two individual as parent
Crossover (Single, PMX)
Evaluate Fitness
Update the Best individual when offspring is better than actual Best
Individual BI(i)
Mutation (Smart Swap)
Evaluate Fitness
Update the best individual when offspring is better than actual Best
Individual BI(i)
Build
Build new Population Pop (i+1) as collection of individuals generated
with Crossover and Mutations Operations
Next i
End - Return the best individual containing the best tour
More details are given into a previous publication of authors in [1]. The solutions
given by optimization process constitute inputs for Multi Criteria Analysis Approach.
Finally, the Multi Attributes Approach for Tourist Trips Design Problem (MATTDP)
gives as output a solution that takes into account a lot of variables, some of these are
considered into optimization process and others into Multi Criteria Analysis Process.
5.1 Real Application
In this paragraph, we propose the results obtained for the single-day Tourist Trip
Design Problem (TTDP) in the city of Florence. We consider 24 PoIs, all included
into urban areas of the city. We fix the PoIs of departures and of arrival and the
maximum time that the tourist has to visit the city, variable from 390 minutes to 930
minutes. We calculated the distance matrix and set the algorithm parameters (numbers
of individuals, population and Best Solution Containers’s (BSC) size, Frequency rate
of genetic operators) on the basis of preliminary tests that have given the best
configuration of algorithm. For each PoI, we suppose that the tourist assigns a
different score on the basis of your preference. The Total time of tourist path is
calculated as summarize between the time to reach the PoI and the time to visit it that
it is supposed to be equal to 30 min for each one. The Table 2 presents the results
coming from the optimization process; the authors found 5 solutions/tours (called 1,
2, 3, 4, 5) for 5 different time each one starting from PoI 1 and ending to PoI 24. Each
PoI is represented by a number from 1 to 24 and each Tour can be considered as a
sequence of visited PoIs. As showed in Table 1 for each solution a Real time of tour, a
total time of tour, a total score of tour and the number of visited PoIs are given. Tmax
real is expressed in minutes like Time for visit the PoIs and the relative Total Time.
Tmax is expressed in a conventional measure used into the algorithm, Total Score and
Visited PoIs have no units of measure. For summarizing, each solution coming from
optimization process is characterized by a number or a sequence of visited PoIs, and a
Total time needed for completing the tour as sum of time to reach all PoIs of tour and
time to visit them.
39
Table 1: Data of solutions
Solutions 1 2 3 4 5
Tmax 5 8 10 15 20
Real Tmax 60 96 120 180 240
Time of visit 330 450 540 660 690
Total time 390 546 660 840 930
Total score 75 110 145 170 185
Visited PoIs 11 15 18 22 23
The outputs of optimization process as before described are given as inputs of AHP
model built as in Fig. 2. In the present paper AHP Absolute model is applied as in [3].
Table 2: Solutions of optimization
Solutions Tour
1 1 10 7 18 3 2 5 6 4 23 24
2 1 20 18 12 2 3 10 4 6 5 8 17 22 23 24
3 1 18 12 14 9 3 5 2 6 4 8 17 22 21 23 16 11 24
4 1 14 19 18 12 2 3 10 17 21 22 7 5 6 9 8 4 23 16 11 24
5 1 2 9 6 5 3 7 12 10 18 20 19 22 4 17 8 21 23 16 11 14 24
AHP Absolute model is based on paired comparisons among the elements of a set
with respect to a common attribute. Experts team developed pairwise comparison
matrices to determine the weights of criteria. Consistency index has been estimated
(CI 0.018). Results show that the most important criteria is “C1. Time Lpath” with a
score of 56%, followed by “C3. Ticket cost” with a score of 32%, and finally is the
criteria “C2. N° Visited places” with a score of 12%. In AHP Absolute model criteria
are further subdivided into a level for intensities. The scores of these intensities are
each weighted by the priority of its criterion and summed to derive a total ratio scale
score for the alternative. Each criterion has ratings listed under it. Tab. 3 shows the
final ranking of the AHP Model.
Fig. 2. AHP Absolute Model
Priorities C1 Time Lpath C2 N* Place Visited C3 Ticket cost
0.5584 0.1219 0.3196
5 0.3750 0.5 km 11 10-20 €
8 0.2423 1 km 15 20-40 €
10 0.1599 1.5 km 18 40-60 €
15 0.1174 2 km 22 60-80 €
20 0.1052 2.5 km 23 80-90 €
Tab. 3. Final Ranking
40
6 Conclusions and Future Researches
In this work the authors present a Multi Attributes Approach for solving single-day
Tourist Trips Design Problem (MATTDP). The proposed System is applied to a real
case into the Italian city of Florence. Thanks to two phases of this approach it is
possible to include several variables into the decisional process without increase the
complexity of the problem. For future researches, the authors want to implement the
system in a big instance of the problem considering also time windows constraints for
visiting PoIs. The next step could be to implement a mobile application for
smartphone and tablet in order to test the real usability of this system in real context.
References
1. Baffo, I., Carotenuto, P., Storchi, G., A genetic algorithm to design touristic routes in a bike
sharing system, 14th international conference on modeling and applied simulation, At
Bergeggi (Liguria) – Italy, (2015).
2. De Falco, I., Scafuri, U., & Tarantino, E. A multiobjective evolutionary algorithm for
personalized tours in street networks. In European Conference on the Applications of
Evolutionary Computation. Springer International Publishing. (2015) 115-127.
3. De Felice F., Petrillo A., Absolute measurement with analytic hierarchy process: A case
study for Italian racecourse. International Journal of Applied Decision Sciences. Volume 6,
Issue 3, 2013, (2013) 209-227.
4. Garcia, A., Arbelaitz, O., Linaza, M. T., Vansteenwegen, P., & Souffriau, W. Personalized
tourist route generation. In International Conference on Web Engineering. Springer Berlin
Heidelberg. (2010) 486-497.
5. Gavalas, D., Konstantopoulos, C., Mastakas, K., & Pantziou, G. A survey on algorithmic
approaches for solving tourist trip design problems. Journal of Heuristics, 20(3), (2014) 291-
328.
6. Saaty, T.L., (1977. A scaling method for priorities in hierarchical structures. Journal of
Mathematical Psychology 15, 234–281.
7. Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. The
multiconstraint team orienteering problem with multiple time windows. Transportation
Science, 47(1), (2013), 53-63.
8. Sylejmani, K., Dorn, J., & Musliu, N. A tabu search approach for multi constrained team
orienteering problem and its application in touristic trip planning. In Hybrid Intelligent
Systems (HIS), 12th International Conference on IEEE. (2012) 300-305.
9. Tsiligirides, T., Heuristic Methods Applied to Orienteering. Journal of Operational Research
Society, vol. 35, no. 9, (1984) 797-809.
10.Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. The orienteering problem: A
survey. European Journal of Operational Research, 209(1), (2011) 1-10.
11.Vansteenwegen, P., Souffriau, W., Berghe, G. V., & Van Oudheusden, D. Metaheuristics for
tourist trip planning. In Metaheuristics in the Service Industry. Springer Berlin Heidelberg.
(2009) 15-31.
12.Wren A., Holiday A., Computer Scheduling of Vehicles from One or More Depots to a
Number of Delivery Points. Operations Research Quarterly, vol. 23, (1972) 333-344.
41