Information Technology Reference
In-Depth Information
4 Generalized Orienteering Problem
The orienteering problem is a subset selection version of well-known traveling sales-
man problem (TSP) with profits. The objective of the OP is to construct a path start-
ing at an origin and ending at a destination which maximizes the total profit without
violating a prescribed travel distance limit. Due to the fact that distance is limited,
tours may not include all locations. It should be noted that the OP is equivalent to the
TSP when the distance is relaxed just enough to cover all points and the start and end
points are not specified. The OP is used to model many practical problems such as in-
ventory routing, customer or vehicle assignment, and production scheduling. Addi-
tionally, a variation of OP with time windows has applications to problems including
postal delivery or school bus routing.
The GOP, proposed by Wang et al. [7], is a generalization of the orienteering prob-
lem. The main difference between the two is that each city in GOP has multiple
scores while each city in OP has only one score. So, the objective of GOP is to find
the optimal tour under the constraint of total distance limit while satisfying multiple
goals rather than only one goal as is the case with OP [8].
4.1 Problem Formulation for OP and GOP
The objective of the OP problem is to find an acyclic path from a start point to an end
point so that the total score collected from the visited points will be maximized with-
out violating the given distance constraint (i.e., the total length of the edges forming
the path should be less than a specified limit). The OP problem is a known NP-hard
problem.
The GOP differs from OP because each point in GOP has more than one score. The
score vector is expressed as
T
=
S
, where
m
is the number
of individual goals. A differentiable objective function, which defines the total score
of path
P
, can be formulated as follows:
(
i
)
(
S
(
i
),
S
(
i
),
,
S
m
i
(
))
…
1
2
⎡
1
/
k
⎤
m
⎧
⎫
∑∑
=
⎢
⎣
k
⎥
⎦
Z
=
W
[
S
(
i
)]
(15)
⎩
⎨
⎭
⎬
g
g
⎢
⎥
g
1
i
∈
P
where
W
is the weight of goal
g
, and the exponent
k
is a controlling constant
which is set to 5 in the example tackled in the following section.
4.2 Eastern China Touring Example
The GOP example using eastern China, which has 27 cities and 4 goals, was first pro-
posed in [7]. If a traveler visits the eastern part of China, as shown in Figure 3, and
the person wants to travel to as many cities as possible with the purpose of best fulfill-
ing multiple goals such as maximizing: 1) natural beauty, 2) historical interest, 3) cul-
tural event, and 4) business opportunities under the limited total moving distance, the
travel can become a generalized orienteering problem where each city has certain
quantified scores for all goals. The tour is evaluated based on the summation of those
scores obtained from all locations forming the tour.
Search WWH ::
Custom Search