Information Technology Reference
In-Depth Information
The other set defines the time interval for the visit to selective nodes. More
precisely,
γ
i
=1 if selective node
i
is visited during time window
s, s
=1
, ...,
|
S
|
and 0 otherwise. Continuous time decision variables,
w
i
and
e
i
,
i
P
,
indicate, respectively, the starting time of the operation and the waiting time
before starting the operation in city
i
.Let
y
represent the number of selective
cities that the traveling salesman must visit. Variable
y
depends on a predefined
periodicity
d
and on the value of variable
w
n
+
p
+1
that defines the arrival time
to the home city at the end of the route.
Problem TSPSNTW can be described through a MILP formulation where the
objective function is the minimization of a linear combination of two terms: the
total traveled time and the total waiting time.
∈
E
∪
min λ
1
(
i,j
)
∈A
t
ij
x
ij
+
λ
2
i
e
i
(1)
∈
V
x
ij
=1
j
∈
E
∪{
n
+
p
+1
}
,
(2)
i
:(
i,j
)
∈A
x
0
,j
=1
(3)
j∈E
x
ij
−
x
ji
=0
, j
∈
E
∪
(
P
−{
0
,n
+
p
+1
}
)
,
(4)
i
:(
i,j
)
∈A
i
:(
j,i
)
∈A
|H|
δ
i
=1
i
∈
E
(5)
h
=1
|
H
|
|
H
|
e
h
δ
i
≤
l
h
δ
i
w
i
≤
i
∈
E
(6)
h
=1
h
=1
|S|
γ
j
≤
1
j
∈
(
P
−{
0
,n
+
p
+1
}
)
(7)
s
=1
|S|
|S|
e
|H|
+
s
γ
j
≤
l
|H|
+
s
γ
j
w
j
≤
j
∈
(
P
−{
0
,n
+
p
+1
}
)
(8)
s
=1
s
=1
|
S
|
γ
j
−
y
=0
(9)
s
=1
j∈
(
P−{
0
,n
+
p
+1
}
)
w
n
+
p
+1
d
y
≥
−
1
(10)
|S|
γ
j
=
i
:(
i,j
)
x
i,j
j
∈
(
P
−{
0
,n
+
p
+1
}
)
(11)
s
=1
∈
A
w
0
= 0
(12)
w
n
+
p
+1
≥
w
j
(
j, n
+
p
+1)
∈
A
(13)
