DEIM Forum 2019 H7-6

観光行動の不確定性を考慮したルート推薦
Junjie SUN† and Qiang MA†† Department of Social Informatics, Graduate School of Informatics, Kyoto University
Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan
E-mail: †jj-sun@db.soc.i.kyoto-u.ac.jp, ††qiang@i.kyoto-u.ac.jp
Abstract Tour planning system automatically recommends travel routes for tourists visiting unfamiliar cities,
which is a very helpful application. Several web and mobile tour planning systems have been proposed in researchand industry but they are still far from available for real tourists. Conventional work are mainly modeled with Orienteering Problem (OP), which maximize tourists’ profits under the giving constraints. However, it is very hard to
define the optimal travel route and the recommended routes are usually not applicable since real tourists’ behaviors
are not suﬃciently considered. To address this issue, we proposed a heuristic method to recommend travel routes
upon the understanding of real users’ uncertain travel behaviors.
Key words Sightseeing, Tour Planning, Travel Route Recommendation

1 Introduction
In recent years, tourism has become one of the most important industries in the whole world. At the same time,interested in proposing heuristic algorithms for adding much
more complicated realistic constraints. For example, In [6],Ander et al. integrated public transportation services andmulti-day tour planning is considered in [9].

benefiting from the rapid development of location-based so-（ 2 ） Data Mining. To provide a better travel experiencecial networks, there are many user generated contents (UGC)

for tourists, they use data mining methods to analysis POIs’(e.g., photos, check-ins, and ratings) available on the Inter-

attributes and user preferences that mined from UGC andnet. Various research and services are aiming to help tourists

OP-based methods are applied for tour planning. For exam-with a better tourism experience when they travel in an un-ple, In [10], Lim et al. estimated tourists’ personalized prefer-familiar urban area (e.g., point of interest (POI) recommen-

ences through social images and machine learning methods

dation). One of the important tasks is tour planning or rec-were proposed in [3]. Also, like [17], the most representa-

ommendation that aims to automatically recommend travel

tive travel route was recommended by retrieving all otherroutes that meet users’ requirements, which is addressed in

tourists’ travel history.

this paper.

However, with higher demand for tour planning, there is

Currently, most existing research and services on tour

still no eﬃcient method or system widely applied online rightplanning are based on the model of Orienteering Problem

now. One possible reason could be the drawback of OP-(OP) and it’s variants [12]. OP is a classical route planning

based model, which assumes an optimal travel route is aproblem, which the objective is to maximize the score of ascore-maximized route under the given constraints. Diﬀer-

subset of ordered nodes without exceeding the time budget

ent from refuge or rescue route planning tasks that also canon an undirected graph with weighted nodes and travel time

be modeled with OP, it is very hard to define what is an op-

between these nodes [14]. Mapping to our tour planning task,

timal travel route. Furthermore, tourists do not always visit

an urban area is a graph, a POI is a node on the graph, thepopular attractions one by one and there are many factors

time cost to travels from one POI to another is the travelthat can let tourists change their plan. For instance, sometime between nodes, and users’ satisfaction is represented as

tourists might wander around a popular attraction before

the score (i.e., tourists visit a POI to collect the score). The

moving to a next far away poplar attraction or visit some

output is an optimal travel route by maximizing the user

less well-known attraction on the way to the next popularsatisfaction score under the given total travel time budget.

attraction. As a result, we should model various user mobil-

With the above OP model, there are mainly two researchareas interested in this tour planning task:

ity’s uncertainty into the tour planning task.
In this paper, we studied a tour planning task by intro-（ 1 ） Operational Research (OR). Since OP can be built

ducing the mobility uncertainty and proposed a heuristic al-as an OR problem and it is NP-hard complexity, they are

gorithm to recommend travel route.

2 Related Workless well-known POIs as unknown knowledge. This is because
top-popular POIs’ information is always easier to obtain andAs we introduced in the last section, there are various

recommended, while those less well-known POIs’ profits aretour planning methods and systems have been proposed

relatively lower. Therefore, we split all POIs into two parts,

from views of diﬀerent research fields. One of the earliest

and normalize the popularity with the maximum value inOP-based method [4] mined POIs from social images. Sim-each part as the assigned profit value for each POI.

ilar ideas have been extended by Lim et al. and Zhao et

ϵ−greedy is a simple and eﬃcient algorithm for E&E prob-

al. in [10], [19], which using social images’ metadata infor-

lems. It uses a simple trade-oﬀ ratio ϵ to control the balancemation and visual features to estimate users’ preferences.

between exploration and exploitation. For instance, a pop-

Other personalized methods or systems have been proposedular POI is selected for a proportion 1 − ϵ, and a random

in diﬀerent ways. For instance, in [15], [18], the authors de-

exploration is selected for a proportion ϵ. It ensures the rec-veloped an interactive web system that users can manuallyommended route is mainly composed of popular POIs but

select travel preferences. Personalization was automaticallyalso includes a little exploration.

estimated in [20] with a feature-centric collaborative filtering

However, tourists are unlikely to visit less well-known POIs

method. Tour planning also has been proposed as an infor-

exclusively and are more likely to visit them on the way. Thismation retrieval task in several studies. In [2], [17], the au-

limits the exploration not on the entire graph, but a small

thors modeled the tour planning task as a max cover problem

set of POIs. For example, tourists might wander around athat finds the most suitable travel routes from other tourists

popular attraction before moving to a next far away poplar

travel history.

attraction. With this assumption, we add a constraint that

OP-variant models were leveraged as basic models to apply

exploration only allows those less well-known POIs in thefor taking more realistic constraints into account. Team OP

region of the last visited POI. Therefore, we need to divide(TOP) extends OP by allowing multiple tours, which is ap-

the POI graph into diﬀerent regions to represent potential

plied for multi-day tour planning in [4], [7]. Diﬀerent from the

explorable areas. Several strategies can be considered in thisTOP, a recent study [5] proposed a multi-day tour planningstep. For example, we use clustering methods to automati-

algorithm by maximizing the utility of the worst day. The

cally divide regions, or define the scope centered on popularmost studied extension of OP-based tour planning model is

POIs, or directly use the administrative area division. Fig-

TOP with Time Windows (TOPTW). It adds open and closeure 1 shows a result of using K-Means clustering algorithm,

time for each node (i.e., POIs’ opening hours) on TOP and

which divides the whole Kyoto city to diﬀerent areas accord-

was solved with Iterated Local Search (ILS) algorithm in [13].

ing to their distances.

Based on this extension, public transportation services were

After the region division, a Greedy Randomized Adaptive

integrated into [6]. [8] is probably the most complete study

Search Procedure [11] with ϵ − greedy algorithm is proposed

for tour planning that based on TOPTW and jointly mod-for tour planning. For each solution, a greediness parameter

eled various settings mentioned in previous studies. In [16],is initiated by drawing a value from a uniform distribution,

the authors defined super-POI for the large sightseeing areas

which the value is between 0 and 1 and represents the bal-

which contain smaller sightseeing spots and split into outerance between greediness and randomness. At each insert

and inner route planning.

iteration, another value is drawn from a uniform distribu-

3 A Heuristic Tour Planning Method
In this section, we introduce our proposed heuristic tour

tion, which is ϵ to decide whether the top-popular or lesswell-known POIs should be inserted. If ϵ > ExpRatio, all
top-popular POIs are initialed into candidate list, otherwise,planning method. Given a set of POIs with their profits (e.g.,
popularity) and a user query (i.e., start, destination, travel
time budget), the algorithm outputs a travel route.
To take user mobility’s uncertainty into consideration, we
add a random mechanism inspired by the concept of Exploration and Exploitation (E&E) [1] in information retrieval
research filed into the tour planning procedure. E&E is atrade-oﬀ between exploring unknown search space and maximizing rewards that already found. We borrow this concept
to model users’ uncertain decision behaviors. For instance,
we treat top-popular POIs as known knowledge, and otherFigure 1 A region divide example of Kyoto city

all less well known POIs inside the region of last inserted

AVERAGE RATING SCORE

node is initiated into the candidate list. For all POIs in the

ε-GRASP
7.71

Pop+Transition

7.28

7.57

7.71

PopTourcandidate list a heuristic value hi is calculated as the following:prof iti,(1)
shif tiwhere prof iti is the normalized profit value of the POI and

5.71

6.43

hi =

shif ti is the total time cost of inserting POI i (i.e., the travel
time and visit duration). A threshold value is computed by
QU E RY 1

QU E RY 2

multiplying the diﬀerence between the maximum and miniFigure 2 Average user rating scores

mum heuristic values by the greediness parameter. Then an
insertion is done by randomly select a POI which the heuris-

PopTour7%

tic value should be larger than the heuristic value. The insertion step is over when no feasible POI can be inserted into
the recommended list and this is a complete search. Until themax number of search is reached, then a local search procedure (e.g., 2-Opt, remove and replace two arcs in a sub-tour)

ε-GRASP50%

is applied to the best-found tour and return it as the final

Pop+Transition
43%

solution. Algorithm 1 concludes the whole procedure.
Algorithm 1: GRASP with ϵ − greedy
1

while IterationN umber < M axIteration do

2

Solution = {}3

Greediness = random(0, 1)

4CandidateList = GenerateCandidates(Solution)5

repeatPopTour

Pop+Transition

ε-GRASP

Figure 3 Percentage of user selected as helpful6

ϵ = random(0, 1)

query, we use the following methods to compare the per-7

CandidateList =formances:

UpdateCandidateList(ϵ, ExpRatio, Greediness)
CurrentN ode = RandomlySelect(CandidateList)

8

Solution = Insert(CurrentN ode)

910

until no feasible insertion available

11

SolutionSet ← Solution

12

BestF ound = LocalSearch(BestF ound)13

return BestF ound•

PopTour: A simple OP-based method that only takes

POI popularity as the profit.
•

Pop+Transition:

A mixed OP-based method thattakes both POI popularity and transition probability as the
profit.
•ϵ−GRASP: Our proposed GRASP with ϵ − greedy

method in this paper.
We asked 7 foreigner tourists to rate all recommended
travel routes of diﬀerent methods. We also asked them which

4 Experiments and Results

result is the most helpful solution. The results is summarized
A Real Tourism Dataset. To evaluate our proposedin 2 and 3.

tour planning framework, we prepared a real tourism dataset

From the results, we found that after considering user mo-of Kyoto city. This dataset originally contains 450 foreigner

bility’ uncertainty, it not only did not reduce the quality of

tourists and 406 students’ school excursion one-day tour GPS

the recommended routes but made users feel more helpful.

trail data. According to the GPS trails, we first map all GPS
points to 123 POIs that represent sightseeing attractions.

5 Conclusion and Future Work

Then other attributes about POIs, such as location, visit

In this paper, we studied the tour planning task that aims

duration and visit popularity can be computed. For simplic-

to automatically recommend a travel route for tourists. We

ity, the travel speed between POIs is set as an average speed

introduced a concept about user mobility’s uncertainty and12km/h.

take it into the tour planning task. A heuristic tour plan-

Results and Case Study. There are two queries aretested:Query1 (′ KyotoM useum′ ,′ SanjoStation′ , 4h) andQuery2 (′ KyotoU niversity ′ ,′ SanjoStation′ , 7h).

For eachning with ϵ − greedy is proposed in this paper and has been
evaluated by real tourists.
Since we our current proposed method is still very sim-ple, we need to further improve it in our future work.
For instance, we cannot automatically decide the value of
ExpRatio but manually set it. Also, diﬀerent regions shouldhave their own ExpRatio which represent diﬀerent potential
explorable sightseeing resources.

Acknowledgements
Thanks for the data provided by Prof.

Hidekazu

KASAHARA. This work is partly supported by MIC
SCOPE(172307001).

References[1] Athukorala, K., Medlar, A., Oulasvirta, A., Jacucci, G., &Glowacka, D. (2016, March). Beyond relevance: adapting
exploration/exploitation in information retrieval. In Proceedings of the 21st International Conference on Intelligent
User Interfaces (pp. 359-369). ACM.
[2] Brilhante, I., Macedo, J. A., Nardini, F. M., Perego, R.,& Renso, C. (2013, October). Where shall we go today?:planning touristic tours with tripbuilder. In Proceedings ofthe 22nd ACM international conference on Information &Knowledge Management (pp. 757-762). ACM.
[3] Chen, D., Ong, C. S., & Xie, L. (2016, October). Learning
points and routes to recommend trajectories. In Proceedingsof the 25th ACM International on Conference on Information and Knowledge Management (pp. 2227-2232). ACM.
[4] De Choudhury, M., Feldman, M., Amer-Yahia, S., Golbandi, N., Lempel, R., & Yu, C. (2010, June). Automaticconstruction of travel itineraries using social breadcrumbs.
In Proceedings of the 21st ACM conference on Hypertext
and hypermedia (pp. 35-44). ACM.
[5] Friggstad, Z., Gollapudi, S., Kollias, K., Sarlos, T., Swamy,
C., & Tomkins, A. (2018, February). Orienteering Algorithms for Generating Travel Itineraries. In Proceedings ofthe Eleventh ACM International Conference on Web Searchand Data Mining (pp. 180-188). ACM.
[6] Garcia, A., Vansteenwegen, P., Arbelaitz, O., Souﬀriau, W.,& Linaza, M. T. (2013). Integrating public transportationin personalised electronic tourist guides. Computers & Operations Research, 40(3), 758-774.
[7] Gavalas, D., Konstantopoulos, C., Mastakas, K., &Pantziou, G. (2014). A survey on algorithmic approaches
for solving tourist trip design problems. Journal of Heuristics, 20(3), 291-328.
[8] Gavalas, D., Kasapakis, V., Konstantopoulos, C., Pantziou,
G., Vathis, N., & Zaroliagis, C. (2015). The eCOMPASS
multimodal tourist tour planner. Expert systems with Applications, 42(21), 7303-7316.
[9] Hu, Q., & Lim, A. (2014). An iterative three-component
heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 232(2),276-286.
[10] Lim, K. H., Chan, J., Leckie, C., & Karunasekera, S. (2015,
July). Personalized Tour Recommendation Based on User
Interests and Points of Interest Visit Durations. In IJCAI(Vol. 15, pp. 1778-1784).
[11] Kotiloglu, S., Lappas, T., Pelechrinis, K., & Repoussis, P.
P. (2017). Personalized multi-period tour recommendations.
Tourism Management, 62, 76-88.
[12] Souﬀriau, W., & Vansteenwegen, P. (2010, July). Tourist
trip planning functionalities: StateâĂŞofâĂŞtheâĂŞart andfuture. In International Conference on Web Engineering(pp. 474-485). Springer, Berlin, Heidelberg.

[13] Vansteenwegen, P., Souﬀriau, W., Berghe, G. V., & Van
Oudheusden, D. (2009). Iterated local search for the teamorienteering problem with time windows. Computers & Operations Research, 36(12), 3281-3290.
[14] Vansteenwegen, P., Souﬀriau, W., & Van Oudheusden, D.
(2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1-10.
[15] Vansteenwegen, P., Souﬀriau, W., Berghe, G. V., & Van
Oudheusden, D. (2011). The city trip planner: an expert system for tourists. Expert Systems with Applications,38(6), 6540-6546.
[16] Wang, C., Gao, Y., Gao, X., Yao, B., & Chen, G. (2018,
November). eTOUR: A Two-Layer Framework for Tour Recommendation with Super-POIs. In International Conference
on Service-Oriented Computing (pp. 771-778). Springer,Cham.
[17] Wen, Y. T., Yeo, J., Peng, W. C., & Hwang, S. W. (2017).
Eﬃcient Keyword-Aware Representative Travel Route Recommendation. IEEE Transactions on Knowledge and Data
Engineering, 29(8), 1639-1652.
[18] Kurata, Y. (2011, January). CT-Planner2: More flexible
and interactive assistance for day tour planning. In ENTER(Vol. 2011, pp. 25-37).
[19] Zhao, P., Xu, X., Liu, Y., Sheng, V. S., Zheng, K., & Xiong,
H. (2017, October). Photo2Trip: Exploiting Visual Contents in Geo-tagged Photos for Personalized Tour Recommendation. In Proceedings of the 2017 ACM on Multimedia
Conference (pp. 916-924). ACM.
[20] Zhang, C., Liang, H., & Wang, K. (2016). Trip recommendation meets real-world constraints: POI availability, diversity, and traveling time uncertainty. ACM Transactions on
Information Systems (TOIS), 35(1), 5.