Information Technology Reference
In-Depth Information
2 Mathematical Programming Formulation
Given a planning horizon
H
,asetof
n
mandatory cities and a set of
p
selective
cities, the TSPSNTW, consists of determining a circuit that minimizes an overall
time function, that depends on the traveled distance and the waiting time before
starting each visit, and satisfies the following constraints:
-
it starts, at the home city, at day 1 and ends, at the home city, before the
|
th day.
-
visits each mandatory city exactly once within one of the required time
windows. If the traveling salesman arrives at a city location before the cor-
responding time window lower bound, then he has to wait before starting
the sales operation. The duration of the sales operation depends on the city
being visited.
-
according to a predefined periodicity, a selective city must be visited within
one of the corresponding time windows. The duration of such visits is set
out a priori.
H
|
More formally, consider a directed graph
G
=(
V,A
). The set
V
=
E
∪
P
is
the vertex set where each vertex
i
∈
E
=
{
1
, ..., n
}
corresponds to a mandatory
city and each vertex
i
corresponds to
a selective city or to the home city. The home city has been split into two
vertices: 0 and
n
+
p
+1 which correspond, respectively, to the starting and ending
location of the route. The arc set
A
includes the arcs
∈
P
=
{
0
,n
+1
, ..., n
+
p,n
+
p
+1
}
{
(0
,i
)
,i
∈
E
}∪{
(
i,j
):
(
i,j
)
∈
E
×
E,i
=
j
}∪{
(
i,j
):(
i,j
)
∈
E
×
(
P
−{
0
}
)
}∪{
(
i,j
):(
i,j
)
∈
(
P
. In any feasible solution, each vertex
associated with a mandatory city has degree two, each vertex corresponding
to the home city has degree one and the remaining vertices, corresponding to
selective nodes, have degree 0 or 2.
A travel time
t
i,j
, indicating the time spent to travel from location
i
to location
j
, is associated to each arc (
i,j
)
∈ A
. Note that travel times need not satisfy the
triangle inequality and need not be symmetric.
For each day
h
=1
, ...,
−{
n
+
p
+1
}
)
×
E
}∪{
(
i, n
+
p
+1):
i
∈
E
}
a time window [
e
h
,l
h
] is defined to ensure that, for
each city visited on day
h
, the sales operation starts within the times
e
h
and
l
h
and occurs before the end of the
|
H
|
|
H
|
th day. Each vertex
i
∈
E
has to be visited
in exactly one of the
time windows.
For each of the predefined time periods where the traveling salesman needs
to reach a selective city,
s
=1
, ...,
|
H
|
, time windows (
e
|H|
+
s
,l
|H|
+
s
)aregiven.
|
S
|
For each vertex
i
∈
E
∪
P
the time spent during the corresponding visit is given
and denoted by
prof
i
.
To model the problem we consider three types of decision variables: route
variables, time window variables and time variables. As for the route variables,
let
x
i,j
=1 if the salesman travels directly from city
i
to city
j
and 0 otherwise.
Two sets of decision variables are used to represent the time windows. One
set defines the time interval for the visit to each mandatory city. That is,
δ
i
=1
if city
i
∈
E
is visited during time window
h,h
=1
, ...,
|
H
|
and 0 otherwise.
