Information Technology Reference
In-Depth Information
i
e
when the entry time is
t
;
Travel time on edge
x
ijd
(
t
)
: if edge
i
e
on route
r
is en-
tered at time
t
, then
x
ijd
=0.
This paper will study the team orienteering problem on transportation network with
a given source and destination node, in which the travel cost is dependent on time and
primarily on the start time on the edge. It is assumed that time is discredited into small
units (such as 1 hour or less 10 minutes). In the TDTOP, each location has a score. It
consists in visiting some of the locations in order to maximize the total collected score
of multiple tours within a given time budget. And each location can be visited at most
once. We don't consider the phenomenon of return and round in traveling road. The
road segments may not satisfy the “first-in-first out” property. On this basis, taking into
account the application in real world, this paper will consider time-dependent travel
cost, location stay time and total transportation time constraint to study the team orien-
teering problem. Therefore, the time-dependent team orienteering problem is actually a
multi-routes-selection one in the time-dependent network with the determination of the
departure time from each node on the selected route.
x
ijd
(
t
)
=1, else
(
t
)
Time and spatial dimensions are used to represent the selected routes, where time
is discrete time unit and space is expressed as
V
=
{
v
|
i
∈
[
|
V
|]}
. So, every selected
i
(
)
route is a list constitute in elements
, the selected route
r
is pre-
v
,
a
,
b
i
i
i
(
)
(
)
(
)
)
(
sented:
P
(
v
,
v
)
=
{
v
,
a
,
b
,
v
,
a
,
b
,
,
v
,
a
,
b
,
v
,
a
,
b
}
, where
v
is
L
d
1
n
1
1
1
d
d
d
d
d
d
n
n
n
1
1
1
w
w
w
the source node,
v
is the destination node, and
d
(
i
=
1
L
2
,
w
) is the node subscript
on route
r
. The route
r
is expressed as
r
=
{
v
,
v
,
L
,
v
,
v
}
.
d
1
d
d
n
1
w
3 Model and Algorithm
3.1 Mathematical Model
Choose node
v
as the source point and node
v
as the destination point. So we estab-
lish the following mixed integer programming model.
T
m
n
−
1
∑∑∑∑
==
max
s
x
(
t
)
(1)
i
ijd
t
11
d
i
=∈
2
j
S(i)
T
m
T
m
∑∑∑
∑∑∑
s
.
t
.
x
(
t
)
=
x
(
t
)
=
m
(2)
1
jd
ind
t
==∈
11
d
j
S
(
t
==∈
11
d
i
P
(
n
)
T
T
∑∑
∑∑
x
(
t
)
=
x
(
t
)
,
∀
k
=
2,
,
n
−
1
,
∀
d
=
1
,
,
m
(3)
L
L
ikd
kjd
t
=∈
1
i
P
(
k
)
t
=∈
1
j
S
(
k
)
T
m
∑∑∑
==∈
x
ijd
t
(
)
≤
1
,
∀
i
=
2,
,
n
−
1
(4)
L
t
11
d
j
S
(
i
)
Search WWH ::
Custom Search