Information Technology Reference
In-Depth Information
Step 3 (Calculation of arrival time on stage
k
).
For each node
v
in
L
, we find the
P
k
−
(
j
)
which is the predecessor nodes set of
v
; for
v
∈
P
(
j
)
, calculating
1
j
i
k
−
1
a
=
a
+
vt
+
t
(
i
b
)
, if
a
j
>
T
, then
U
(
j
,
a
)
=
0
, else go to step 4.
j
i
i
ij
k
j
Step 4 (Calculation of the collected score and labeling on stage
k
).
Calculating the
total collected score to node
U
(
j
,
t
)
=
max
(
U
(
i
,
a
)
+
s
)
v
at time
a
,
, labeling
k
k
−
1
i
i
j
i
∈
T
(
i
,
t
)
(
i
,
a
,
k
)
;
j
Step 5 (Judgment of the iteration on stage
k
).
Let
L
=
L
\
{
v
}
, if
L
=
φ
, then
k
k
j
the iteration is finished on stage
k
; if
k
=
K
, then go to step 6, else
k
=
k
+
1
, go to
step 3;
Step 6 (Calculation of the total collected score).
Calculating
;
U
(
n
)
=
max
U
(
n
,
a
)
k
n
k
Step7 (Backward the maximum collected score route).
According to the label, re-
verse deduction and find out the maximum collected score route:
(
)
(
)
(
)
)
(
P
(
v
,
v
)
=
{
v
,
a
,
b
,
v
,
a
,
b
,
,
v
,
a
,
b
,
v
,
a
,
b
}
, the visiting route is
L
d
1
n
1
1
1
d
d
d
d
d
d
n
n
n
1
1
1
w
w
w
r
=
{
v
,
v
,
,
v
,
v
}
;
L
d
1
d
d
n
1
w
Step 8 (Judgment of the iteration in route set
R
).
Update
V
=
V
\
{
v
,
,
v
}
, if
L
d
d
1
w
V
=
{
1
v
,
v
}
, then the iteration is finished, else if
d
=
m
, then the iteration is finished,
n
else
d
=
d
+
1
,go to step 2.
4 Numerical Example
The efficiency and feasibility of algorithm would be demonstrated by the following
numerical example in this section. Given a TDTOP directed graph, where there are 20
nodes and 189 edges, node 1 is the sourcing point, node 20 is the destination point. To
simplify the problem, we only consider the one-way travel. The time budget is
T
=80.
The graph parameters are set as follows: The average travel time on edges is random
integer in [3, 20]; The travel time on edges at each time is random integer of the fluc-
tuation range
=30% to edge average travel time; The average visiting time is ran-
dom integer in [5,15] as shown in table 1 where the average visiting time for node 1
and node 20 is 0; The score for every node is random integer in [1,10] as shown in
table 2.
α
Table 1.
The average visiting time for every node
nodes
1
2
3
4
5
6
7
8
9
10
vt
i
0
8
10
8
12
15
8
6
7
14
nodes
11
12
13
14
15
16
17
18
19
20
vt
i
13
5
8
6
9
5
5
8
9
0
Search WWH ::
Custom Search