inbul 2004 
Value 
tourist sites 
ROUTE CONSTRUCTION 
Many relevant studies have already been carried out 
in the field of operations research, such as 7ravel 
Salesman Problem (TSP), Prize Collecting Travel 
Salesman Problem (PCTSP), and Orienteering Tour 
Problem (OTP). These problems are generally 
called the Travelling Salesman Sub-tour Problem 
(TSSP) (Mittenthal and Noon, 1992). 
As Silver (2002) pointed out, all algorithms 
currently available for finding optimal solutions to 
TSSP problems require a number of computational 
steps that grows exponentially with the size of the 
problem. “It is rather difficult, if not impossible, to 
obtain the optimal solution of the mathematical 
model representation of the problem under 
consideration". Therefore, most of the studies on 
optimisation look for heuristic solutions rather than 
for a mathematical model. Another difficulty in the 
optimisation is that there are often a large number of 
decision variables, which are combinatorial in 
nature. Even when the objective function is as 
simple as linear, there can be many local optima. 
Applying heuristic methods often results in a 
reasonable solution to a problem, but one that 
cannot be guaranteed to produce the mathematically 
optimal solution. 
The Prize Collecting Travelling Salesman Problem 
(PCTSP) is considered a variant of the well-known 
Travelling Salesman Problem (TSP) and has been 
studied in many researches, especially in the field of 
operations research (Balas, 1989; Dell' Amico ef al., 
1998; Mittenthal and Noon, 1992). The TSP is the 
problem of a salesman who wants to find, starting 
from his hometown, the shortest possible trip 
through a set of customer cities and to return to his 
hometown; visiting exactly once each city. The 
PCTSP is a relaxed variant of the TSP in which a 
salesman does not have to visit every city. This may 
be because he has limited resource available, such 
as time, distance or budget of travel, and his goal is 
to reduce cost as much as possible while collecting 
the minimum required prizes. Each city is 
associated with a value that represents the prize that 
the salesman may collect if he visits the city and/or 
the penalty that he has to pay when he does not visit 
the city. 
A similar optimisation problem is also studied in 
another application domain - Orienteering Tour 
Problem (OTP). Orienteering is a sport in which 
each participant is given a compass and a map, on 
which a number of places, called control points, are 
shown. One form of orienteering is known as a 
score orienteering event, in which each control point 
has a score allocated to it and all participants must 
reach the finish point within a given time. The 
control points close to the start and finish points 
usually have lower scores and those further away 
have higher scores. The participants do not have to 
visit all the points. The aim of each participant is to 
try to collect as high a score as possible within the 
given time. This requires each participant to solve 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004 
an optimisation problem to plan his route, to realize 
his limitations as to which and how many control 
points he should reach and to use up almost all the 
available time. 
Although the problem definition of PCTSP is 
different from that of OTP, i.e., minimizing the cost 
while collecting a sufficient total points versus 
maximizing the total points while maintaining the 
cost constraint, respectively, they both consist of 
two types of decisions, namely, selecting and 
sequencing. Because not all the nodes need to be 
visited, decisions have to be made on which node to 
be visited and which one not. On the other hand, the 
sequence of visiting the nodes plays also an 
important role to achieve the objective functions of 
the problem. A generally applied approach to solve 
both problem is so-called Tabu search — a heuristic 
method (Silver, 2002). The Tabu search starts with a 
complete feasible solution, and it continues 
developing additional complete solutions from a 
sequence of neighbourhoods, i.e., local 
improvement. There are variations of Tabu search 
and the main difference lies in the approach during 
the improvement phase. 
Tourist routing problem is essentially similar to 
PCTSP or OTP, in which each point in the 
candidate list becomes a city in PCTSP or a control 
point in OTP. Dell’ Amico ef al. (1998) proposed an 
extension/collapse algorithm for solving PCTSP and 
this research adopts this algorithm in constructing 
tourist routs. For details of this algorithm sce 
Dell’ Amico er al. (1998). 
EVALUATION 
Ideally, an evaluation of such a system should be 
carried out in a real tourist environment, in which 
the testers would be asked to follow several routes 
recommended by the software. However, due to 
resource constraints, mainly the time required to 
follow the routes, a simulated test environment has 
been designed for use on computers. 
In this simulated test environment, testers enter a 
weight for cach attribute of the tourist attractions. 
The software then generates four tourist routes — 
one is generated based on the weights given by the 
tester, .e.. the “original” preference, and the other 
three are generated based on the weights adjusted at 
different levels, i.e., “noisy” preferences, from the 
weights given by the tester. The objective is to find 
out if the testers prefer the routes generated based 
on their "original" preferences to the others that 
were derived using "noisy" preferences. 
In total, forty-five test cases were generated. Besed 
on the analysis of these forty-five cases, it can be 
concluded that the preference of the routes by the 
testers is quite consistent with the weight 
adjustment given to cach route by the software, i.e. 
that the bigger the difference of the weight 
adjustment is, the less likely the route is favoured by 
the testers. 
  
Rr EEE