Challenges in User-Adaptive Tour Planning Systems
Yohei Kurata
SFB/TR 8 Spatial Cognition, Universität Bremen
Postfach 280334 Bremen, Germany
ykurata@informatik.uni-bremen.de

Abstract. User-adaptive tour planning systems are tourist information systems
that can make tour plans customized for individual users. Several systems havebeen already proposed, but such usability issues as frustrating
preference/personality registration process and lack of sense of participation
still remain. In this paper, we review these usability issues and discuss thefollowing challenges for more practical user-adaptive tour planning systems:
collaborative tour planning, smart detection of user’s preferences, more realistic
settings of tour optimization problems, and mobile-oriented service.
Keywords: tour planning, user’s preference, selective travelling salesman
problem, candidate/critique model, trajectory-based preference detection

1.

Introduction

Tourism is a spatial activity that depends highly on the preferences of individual
tourists. Naturally, tourist information systems are desired to provide information
adapted to individual users, especially when the users’ destination is a tourist citywhere many types of points of interest (POIs) exist densely and tourists have todecide which POIs to visit without sufficient prior knowledge. Indeed, a number ofuser-adaptive tourist information systems have been proposed before. For instance,some systems sort or filter POIs based on the user’s preference (e.g., [1-3]). However,even if the user is informed about which POIs will be interesting for him/her,designing an efficient tour plan remains a hard task. Thus, several tourist information
systems, including ours [4, 5], were equipped an ability to design tour plans
customized for individual users [4-8]. These tour planning systems still have several
usability problems, such as frustrating process of preference registration and lack ofsense that the user participates in the planning. In this paper, we review these
problems and discuss some challenges to achieve more practical user-adaptive tour
planning systems.
The remainder of this paper is structured as follows: Section 2 reviews the previous
user-adaptive tour planning systems. Section 3 discusses the problems and challenges
in user-adaptive tour planning systems. Finally, Section 4 concludes the discussion.

2

Yohei Kurata

2.

Tour Planning Systems

Most tour planning systems have similar three-step structures: preference setting,evaluation of POIs, and route optimization. As an example, screenshots of our system[4, 5] are shown in Figs. 1a-e. In this system, the user specifies his/her interest
through a questionnaire (Fig. 1b), from which the system judges the user’s preference.
Based on this preference, the system calculates the expected value of each POI.
Finally, the system computes a tour plan that maximizes the total values of POIs to bevisited (Figs. 1c-d). The system can also show the information about POIs (Fig. 1e).

(a)

(c)

(b)

(d)

(e)

Fig. 1. Screen shots of our tour planning system [4, 5]: (a) its main screen, (b) a question asking
users’ preference over two tour purposes, (c-d) a customized tour plan shown on a map and by
text, and (e) information about a POI

Setting of the user’s preference is a problematic process. Traditional decisionsupport systems ask the user to specify his/her preference on several criteria
manually, for instance by sliders [9]. This approach frustrates the users because they
are forced to evaluate their own preference on obscure scales. Thus, our system took
an alternative approach based on AHP (Analytical Hierarchical Process) [10], inwhich the user is given fifteen questions that ask which tour purpose is preferable(Fig. 1b) and from his/her answers the system calculates the user’s weights on ten tour
purposes (Fig. 2). We considered that the weights on these ten tour purposes represent
the user’s tour preference. This comparison-based process is easier than the sliderbased approach, but the questionnaire takes a lot of time. To realize more quickChallenges in User-Adaptive Tour Planning Systems

3

setting of user’s preference, some systems ask the user to input age, gender,
occupation, and so on, assuming that the tourists with demographically similar
properties have similar tour interests [1, 8]. This approach, however, also frustrates
the users, making them feel that their privacy is offended or that the system has astereotypical view of their preferences.
Once the user’s preference is modeled, the system evaluates all POIs in the target
area based on this model. The value of each POI may be evaluated from the user’s
weights on several criteria and the POI’s scores in these criteria [4, 5] or based on theevaluation by other tourists with similar preferences/properties [1, 8]. In our previous
system, each POI is rated in ten criteria, which corresponds to the ten tour purposes(Fig. 2). Thus, by weighting the ten criteria with the weights on the ten tour purposes,
the score (value) of each POI is calculated.
Finally, the system computes an optimal tour plan. Normally, this problem is avariation of the Selective Traveling Salesman Problem (STSP) [11] and defined, forexample, as follows:
Given a complete graph, , the utility (value) of each node , the time
, the travel time between two nodes, origin
spent at each node
, destination, and time constraint , find a series of nodes
to be visited,…,that maximize the some of utilities under atime constraint .
maximize ∑s.t. ∑∑(1),
Since this problem is NP-hard, we developed a heuristic algorithm for approximate
solutions, in which we gradually increased the time constraint up to T while revising
the tour plan repeatedly [4]. Alternatively, P-Tour [6] adopted a genetic algorithm forapproximate solutions. We, however, believe that strict solutions may be derived in apractical time by dynamic programming, since the scale of the problem is usuallysmall (for instance, a tourist rarely visits more than ten POIs in one day).
Tour Purposes
Relaxing
Play andExercise

HealthEnhancement

Food and
Shopping

Social Needs
Viewing
Sceneries

Cultivate
Friendship

Visit Famous
PlacesSelf‐Actualization
SocialExperience

Enlarge One’s
Knowledge

Experience
New Things

Regional
Study

Fig. 2. Hypothesized structure of ten tour purposes used in [4, 5]

3.

Problems and Challenges

We asked 25 human subjects to test our prototype system [4]. Almost all users agreed
that the customized tour plans matched their preferences, even though they could nottell whether the recommended plans looked the best for them. Some users complained

4

Yohei Kurata

about the inability to modify the recommended plans—for instance, removing the
POIs that they had visited before. Some users complained about the questionnaire, as
it took long time and seemed not directly linked to the planning process.
Actually other tour planning systems have similar problems, as they also impose
certain frustrating preference/personality registration processes and do not allow
manual modification of recommended plans. Exceptionally, P-Tour [6] avoids thepreference/personality registration process, leaving the evaluation of POIs entirely tousers. Thus, the user has much freedom to express what he/she does and does notwant to visit. As a drawback, the user is forced to estimate the value of POIs thathe/she has never been. We, therefore, consider that the desirable approach is a hybridone; that is, the system coordinates the tour planning while the user is allowed tomodify the plan and participate in the planning. The system also learns the user’s
preference from his/her involvement and makes use of this information to revise tour
plans. We are going to explain this idea more explicitly.
3.1.

Collaborative Design of Tour Plans

How can we encourage the participation of the users, without increasing their
obligations? One possible solution is the use of the candidate/critique model [12].
Imagine that you are shown several plans: one fits the tentative model of yourpreference, while others follow different interests. Then, you are asked to compare theplans and specify which you prefer. If you choose one of the alternatives, then thesystem infers what criteria you emphasize, revises the model of your preference, andrecomputed tour plans. This process is repeated until you agree with therecommended plan. This approach is preferable for the user, since he/she can learn
available choices and clarify his/her needs through the comparison of actual plans.
Even though this approach may be time-consuming, the user probably gets highsatisfaction in the final plan. Fig. 3 shows the interface design of an envisioned tour
planning system that will enable such collaborative tour planning. For simplification,
it shows only two plans on a screen, but the user can see various alternative plans withdifferent characteristics by clicking the buttons in the right-bottom.
For more flexible tour planning, it is also desirable that the system allows the user
to express which POIs he/she wants to visit or avoid. Even if the user does not want toestimate the value of all POIs, he/she may want to specify his/her request aboutcertain POIs. For instance, a tourist, who usually likes art museums but not historicalmonuments, may request to visit Palace of Versailles because it is world-famous,
while he may also request not to visit Musée d'Orsay because he has been there
several times. The tour planning system should be able to accept such case-by-caserequests, just like a human tour coordinator can do. The interface design in Fig. 3 also
considers the support of such requests. Addition/removal of a POI can be realized by
dragging its name tag to the three icons labeled “add to tour”, “not attractive”, and“visited before”. We distinguished “not attractive” and “visited before” because
dragging to the former icon may be used to revise the user’s preference model, whiledragging to the later icon does not.

Challenges in User-Adaptive Tour Planning Systems

Recommended?

Bremen - Tour Planner
3:00 +–
Alternative — Longer (4:00)

for

5
×

Overseas
MuseumOverseas
Museum+ Wind MillWind Mill

Modern Art
Museum

Add toTour

Modern Art
MuseumStatues of Roland& Town Musician
BöttcherStreetStatues of Roland& Town Musician
BöttcherStreet

St. Petri-Dom

Not
Attractive

Paula ModersohnBecker Museum

St. Petri-Dom– Paula ModersohnBecker Museum

SchnoorDistrict

Art Museum

SchnoorDistrict

Visited
BeforeI Prefer the Recommended,
but Need More Adjustment
Take This Tour+ Art Museum

I Prefer the Alternative
Show Another Alternative
Shorter TimeLonger Time
More Academic

More RelaxedMore Social

Fig. 3. An image of a new tour planning system that realizes collaborative tour planning

In Fig. 3, the value of each POI is shown by 1- to 5-stars, as the stars are moreintuitive than quantitative scores (e.g., Fig. 1e). On the other hand, the total values of
the recommended plan and alternative plan are not displayed, because the total values,
calculated from an incomplete model of the user’s preference, may confuse the user’s
choice of two plans.
3.2.

Smart Detection of Users’ Preference

How can we avoid the preference/personality registration process? One potential
solution is, as introduced in the previous section, that the system seeks the user’s
preference from the choice of alternative plans through iterative interactions. The
second potential solution, which is effective in mobile use, is to ask the user toevaluate each POI after a visit and to revise the model of the user’s preference
according to the user’s response. Of course, the evaluation of POIs easily becomes anannoying process during an actual tour. Thus, we should carefully design theinteraction process, such that the evaluation is easy (e.g., selection from one-star to
five-star) and its frequency is minimized.
Another potential solution in mobile scenarios is to learn the user’s preference
from his/her trajectory. Where the user visits and how much time he/she spends there
may tell something about his/her preference, especially when it is compared with thedata of ordinary people. Schmidt-Belz et al. [2], however, questions this trajectorybased approach, saying that the visit to a church may be not because of the tourist’s
interest in churches, but because of a concert in the church, an exceptional view from6

Yohei Kurata

its tower, or even a little café in the aisle. Yet, we believe that the trajectory-based
preference detection is still useful, especially if we can tell from the micro-leveltrajectory whether he is actively involved in sightseeing or, say, taking a rest in a POI.
Kiefer and Schlieder [13] discusses the method to infer the user’s intentions by
parsing his/her trajectory. Such mobile intention recognition techniques are useful for
inferring the user’s touring behaviors from his/her trajectories.
3.3.

More Realistic Settings of Tour Optimization Problems

Although it is not apparent in our user test, one weak point of our previous system is
its too simple setting of the tour optimization problem. To make the problem more
realistic, we can think about the following extensions:
1. To assign values not only POIs, but also links
2. To allow the temporal/seasonal fluctuation of POIs’ values;
3. To regard the travel time between POIs as a fuzzy value;
4. To adapt the estimated time spent at each POI to each user;
5. To take weather conditions into account; and6. To give lower scores to ‘monotonous’ tours.
By Extension 1, the attractiveness of routes between POIs is incorporated into tour
planning. This extended problem is a sort of EPTP (Enhanced Profitable Tour
Problem), whose approximate solution algorithm is already proposed in [14]. Of
course, how to evaluate the attractiveness of routes remains as a research question.
Extension 2 is critical for practical tour planning. For instance, museums have zero
value when they are closed. Some overlooks have more values at sunset, while losing
their values when the sunlight comes from the front. Botanical gardens are attractive
in summer, but not in winter. In this way, POIs’ values vary from time to time andsuch temporal fluctuation is not ignorable. Matsuda et al. [15] already tackled
Extensions 2 and 3. They formulated FORPS (Fuzzy Optimal Routing Problem for
Sightseeing) and proposed a heuristic algorithm for its approximate solutions.
Extension 3 is also important for supporting the variation of travel time due to traffic
jams or infrequent service of public transportation.
For Extension 4, we have to develop a model for estimating the time spent at a POI
from the tourist’s preference and the POI’s characteristics. For this, we have toanalyze the statistical data of tourist behaviors.
Extension 5 is also essential for practical tour planning. For instance, if the weather
forecast predicts rain in the afternoon, it is better to plan a tour such that outdoor
attractions are visited in the morning while museums are left for the afternoon. Even
after the tour has started, the plan should be modified flexibly in case of a sudden rail.
These problems can be handled by the techniques used for Extension 2.
As for Extension 6, current systems evaluate POIs individually, but not as a
combination. As a result, for instance, if the user likes museums, the systems tend torecommend a plan that visits museums for all day—which may be boring even forthis user. Thus, it is desirable that the systems can evaluate the monotony of visited
POIs and utilize it for tour planning.

Challenges in User-Adaptive Tour Planning Systems

3.4.

7

Mobile-Oriented Service

In the big trend to mobile computing, tour planning systems will be used more often
in mobile context. A key question is how to provide the service tailored to mobile
devices. For instance, the mobile version of P-Tour [16] monitors the user’s location
by GPS and warns the user if he/she is out of the route or behind schedule [16]. The
capability of such schedule monitoring and real-time tour re-planning is a potential
strength of tour planning systems in mobile use. Trajectory-based preference
detection (Section 3.1) is another possibility of mobile-oriented tour planningsystems. Furthermore, the potential of tour planning systems is more expanded if it iscombined with other intelligent mobile technologies, such as smart route navigation(e.g., route-specific route instructions [17]) and location-based querying (e.g.,
iPointer® [18]), to form a comprehensive tour support system.

4.

Conclusions

Tourist information systems should meet a large variety of user’s needs. At the sametime, the systems should not provide too much information to the users, as
overwhelming amount of information makes their decision more difficult. We alreadyhave several user-adaptive tour planning systems, but, they still have room for
improvement. We discussed several challenges for the future tour planning systems;
they are (i) collaborative tour planning, (ii) smart detection of user’s preference, (ii)more realistic setting of tour optimization problems, and (iv) mobile-oriented tour
planning service. In addition, the validity of the tourist preference model in theprevious tourist information systems (e.g., that in Fig. 2) should be examined
carefully for the improvement of the tourist information system.
Smart detection of user’s preference/needs/personality is a key technology for all
kinds of user-adaptive information systems. Among these systems, mobile
information systems can make use of the user’s locational information for profilingthe users. The idea of trajectory-based preference detection is applicable to other useradaptive spatial information systems. For instance, bike navigation systems may learn
from the trajectory what kind of routes that the user prefers. The information about
where and how long the user spend time during shopping may be useful for adapting
advertisements to the users. We, therefore, believe that the research on trajectorybased preference detection will expands the capability of spatial assistance systems.

Acknowledgement
Yohei Kurata’s work is supported by DFG (Deutsche Forschungsgemeinschaft)through the Collaborative Research Center SFB/TR 8 Spatial Cognition.

8

Yohei Kurata

References
1. Ricci, F., Arslan, B., Mirzadeh, N., Venturini, A.: ITR: A Case-Based Travel Advisory
System. In: Craw, S., Preece, A. (eds.): ECCBR 2002, Lecture Notes in Artificial
Intelligence, vol. 2416, pp. 613-627. Springer, Berlin/Heidelberg, Germany (2002)
2. Schmidt-Belz, B., Nick, A., Poslad, S., Zipf, A.: Personalized and Location-Based Mobile
Tourism Services. In: Workshop on Mobile Tourism Support Systems (2002)
3. Ardissono, L., Goy, A., Petrone, G., Segnan, M., Torasso, P.: Intrigue: Personalized
Recommendation of Tourist Attractions for Desktop and Handset Devices. Applied
Artificial Intelligence: Special Issue on Artificial Intelligence for Cultural Heritage andDigital Libraries 17(8-9), 687-714 (2003)
4. Kurata, Y.: Development of a Preference-Based Tour Planning System. Bachelor Thesis (inJapanese). Department of Urban Engineering, University of Tokyo, Tokyo, Japan (2000)
5. Kurata, Y., Okunuki, K., Sadahiro, Y.: Development of a Preference-Based Tour Planning
System. In: Papers and Proceedings of the Geographic Information Systems Association (inJapanese), vol. 9, pp. 199-202 (2000)
6. Maruyama, A., Shibata, N., Murata, Y., Yasumoto, K., Ito, M.: A Personal Tourism
Navigation System to Support Traveling Multiple Destinations with Time Restrictions. In:
18th IEEE International Conference on Advanced Information Networking andApplications, pp. 18-21 (2004)
7. Goy, A., Magro, D.: STAR: A Smart Tourist Agenda Recommender. In: Configuration
Workshop at ECAI 2004, pp. 8/1-8/7 (2005)
8. Lee, J., Kang, E., Park, G.-L.: Design and Implementation of a Tour Planning System for
Telematics Users. In: Gervasi, O., Gavrilova, M. (eds.): ICCSA 2007, Lecture Notes in
Artificial Intelligence, pp. 179-189. Springer, Berlin/Heidelberg, Germany (2007)
9. Hochmair, H., Rinner, C.: Investigating the Need for Eliminatory Constraints in the User
Interface of Bicycle Route Planners. In: Cohn, A., Mark, D. (eds.): COSIT'05, Lecture Notes
in Computer Science vol. 3693, pp. 49-66. Springer, Berlin/Heidelberg, Germany (2005)
10.Saaty, T.: The Analytic Hierarchy Process: Planning, Priority Setting, Resource Allocation.
McGraw-Hill, New York, USA (1980)
11.Laporte, G.: Tour Location Problems. European Journal for Operations Research 106, 2-3(1996)
12.Linden, G., Hanks, S., Lesh, N.: Interactive Assessment of User Preference Models: The
Automated Travel Assistant. In: Jameson, A., Paris, C., Tasso, C. (eds.): Sixth International
Conference on User Modeling, pp. 67-78. Springer (1997)
13.Kiefer, P., Schlieder, C.: Exploring Context-Sensitivity in Spatial Intention Recognition. In:
Gottfried, B. (ed.): Intl. Workshop on Behavioral Monitoring and Interpretation, TZIBericht, vol. 42, pp. 102-116. Technogie-Zentrum Informatik, Universität Bremen (2007)
14.Joset, M., Stille, W.: A User-Aware Tour Proposal Framework Using a Hybrid Optimization
Approach. In: 10th ACM International Symposium on Advances in Geographic Information
Systems, pp. 81-87. ACM Press (2002)
15.Matsuda, Y., Nakamura, M., Kang, D., Miyagi, H.: An Optimal Routing Problem for
Sightseeing with Fuzzy Time-Varying Weights. In: IEEE International Conference on
Systems, Man and Cybernetics, vol. 4, pp. 3665-3669 (2004)
16.Shiraishi, T., Nagata, M., Shibata, N., Murata, Y., Yasumoto, K., Ito, M.: A Personal
Navigation System with Functions to Compose Tour Schedules Based on Multiple
Conflicting Criteria. IPSJ Digital Courier 1, 528-536 (2005)
17.Richter, K.-F., Klippel, A., Freksa, C.: Shortest, Fastest, – but What Next? A Different
Approach to Route Directions. In: Münsteraner GI-Tagen 2004, pp. 205-217. IFGI prints,
Münster, Germany (2004)
18.Frank, C.: An Egocentric Spatial Data Model. Department of Spatial Information Scienceand Engineering, Master Thesis. University of Maine, Orono, Maine, USA (2003)