Information Technology Reference
In-Depth Information
serviced. As an extension of these problems, the TOP clearly appears to be NP-hard.
Many TOP real applications are described in the literature: athlete recruiting from
high schools [3], technician routing and scheduling problem [4], TSPs with profits
[5], etc. Butt et al. [6] present an exact algorithm based on column generation to solve
the TOP. They deal with problems up to 100 locations, provided that the number of
selected locations in each tour remains small. Boussier et al. [7] propose a branch-
and-price approach to solve problems with up to 100 locations. Only problems in
which the number of possible locations in a route is low, namely, up to about 15 per
route, can be solved in less than 2h of calculation. The first published TOP heuristic
was developed by Chao et al [8]. Tang and Miller-Hooks [4] developed a tabu search
heuristic embedded in an adaptive memory procedure. Archetti et al. [9] came up with
two variants of a tabu search heuristic and a slow and fast Variable Neighbourhood
Search (VNS) algorithm. Ke et al. [10] developed four variants of an ant colony opti-
mization approach for the TOP. Vansteenwegen et al. [11, 12] implemented a Guided
Local Search (GLS) and a skewed Variable Neighbourhood Search (SVNS) algo-
rithm. Souffriau et al. [13] designed a path relinking metaheuristic approach. Bouly et
al. [14] proposed a simple hybrid genetic algorithm.
However, most of the previous research for TOP in the literature seldom takes
into account changes to the network over time. Clearly, the route between two loca-
tions does not depend only on the distance traveled, but on many other time depend-
ent properties of the network such as congestion levels, incident location, and
construction zone on certain road segments, which would change the travel cost on
that segment. Therefore, based on above literature, this paper will consider the time-
dependent team orienteering problem (TDTOP for short) which meets the needs to
real-world problems. Here, the transportation cost of traveling (time cost in our termi-
nology) varies with time and the travel cost from one location to another depends on
the start time. So decision-makers could choose the right route, locations and depar-
ture time according to their own situation.
The remaining of this paper is structured as follows: the time-dependent team ori-
enteering problem is described in Section 2. A mixed integer programming model for
TDTOP is proposed, and an optimal dynamic labeling algorithm is designed in Sec-
tion 3. Moreover, in Section 4, a numerical example is introduced to show the validity
and feasibility of the algorithm. Finally, the concluding remarks and further research
are included in Section 5.
2 Problem Description
Given a transportation network
, where
is the node set,
G
=
(
V
,
E
)
V
=
{
v
|
i
=
1
2
,
n
}
L
i
is the edge set, if
v
is adjacent with
v
, then there is one edge
i
e
be-
E
=
{
e
|
v
,
v
∈
V
}
ij
i
j
: Set of predecessor nodes of node
v
;
tween them.
: Set of successor nodes
P
(
i
)
S
(
i
)
of node
i
v
;
R
: Set of multiple routes,
;
V
: Set of unvisited
R
=
{
r
|
d
=
1
2
,
m
}
L
d
v
;
nodes;
T
: The total time budget of the route;
s
: Score of node
vt
: Visiting time
i
on node
v
;
b
: Departure time from node
v
;
a
: Arrival time at node
v
;
t
ij
(
t
)
:
Search WWH ::
Custom Search