Information Technology Reference
In-Depth Information
w
j
=
w
i
+
prof
i
+
t
ij
+
e
j
−
M
(1
−
x
ij
)
i,j
)
∈
A
(14)
x
ij
∈{
0
,
1
}
(
i,j
)
∈
A
(15)
w
i
≥
0
, i
∈
E
∪
P
(16)
δ
i
∈{
0
,
1
}
i
∈
E
(17)
γ
i
∈{
0
,
1
}
i
∈
P
(18)
y
∈
IN
0
(19)
Coecients
λ
1
and
λ
2
allow us to attribute different weights to the components
of the objective function. Note that, when
λ
2
is equal to zero the objective func-
tion represents the total traveled distance while when both
λ
1
and
λ
2
are equal
to one the objective function represents the completion time. Constraints (2)
state that the traveling salesman enters once in each mandatory city as well as
in his city home (end). Constraints (3) guarantee that the circuit starts at the
home city. Constraints (4) are flow conservation constraints. These constraints
together with (2) ensure that the salesman enters and leaves exactly once each
mandatory city and each city chosen to be visited among the selective set. Con-
straints (5) ensure that each mandatory city is visited within exactly one time
window while (6) guarantee that the visit occurs within a feasible time window.
Constraints (7) state that each selective city is visited at most once and con-
straints (8) guarantee that when such visit occurs it must be within predefined
time windows. Constraints (9) and (10) are related to the number of visits to
selective cities. Constraints (11) guarantee the consistency between variables
x
i,j
and variables
γ
j
. Constraints (12) and (13), respectively, state that the traveling
salesman leaves the home city at time instant 0 and returns to it at the end of
the circuit. Constraints (14) link variables
x
and
w
. These constraints establish
the precedence relation between two consecutive vertices visited by the traveling
salesman and eliminate sub-tours. In detail, constraints (14) state that if the
salesman goes from location
i
to location
j
then the time at which he starts
visiting
j
,
w
j
, must be greater than the time at which he starts visiting
i
,
w
i
,
plus the time spent at city
i
, plus a function of the time spent in transit from
i
to
j
,
t
ij
whose expression is given by
t
ij
=
t
ij
if
i
E
.
Parameter
accounts to an extra time due to possible setbacks during a sales
operation at a mandatory city.
∈
P
or
t
ij
=
+
t
ij
if
i
∈
3 Solution Approach
Preliminary computational experiments showed that solving the TSPSNTW
with a standard MILP solver tends to spend considerable CPU time, most of
it spent at improving near-optimal feasible solutions, and often ends without
reaching an optimal solution. This behavior suggests to apply a standard MILP
solver, within a predefined time limit, to obtain feasible solutions followed by an
heuristic procedure that, taking advantage of some TSPSNTW features, is able
to improve the MILP solver solutions in short CPU time.
We propose a three phase algorithm to solve the TSPSNTW. The algorithm
starts with a pre-processing phase where clustering techniques are used to reduce