Information Technology Reference
In-Depth Information
the cardinality of the arc set
A
. In the second phase, model (1)-(19) and a
generic MILP solver are used to obtain feasible solutions. In the third phase, an
Adaptive Neighborhood Search (ANS) heuristic is used to improve the feasible
solutions obtained previously as well as to incorporate some traveling salesman
preferences. Different temporal based neighborhoods, that prevent the violation
of time window constraints, are considered and combined with removal/insertion
operators.
3.1 Pre-processing
The directed graph
G
=(
V,A
) is complete. However, for each specific appli-
cation, the geographic location of the cities may suggest that arcs connecting
cities
i
and
j
whose
t
ij
exceeds a predefined parameter
M
have little chance
of being used in an optimal solution. To reduce the computational complexity
of TSPSNTW, we propose a pre-processing phase where clustering techniques
are used to decide which arcs may be removed from the arc set A. To partition
the cities into cluster sets, we applied function
pam
from Package
cluster
avail-
able at CRAN R (http://cran.r-project.org/). The
pam
, “partitioning around
medoids”, algorithm [3] is based on the search for
μ
representative objects or
medoids among the observations to be clustered. The algorithm iteratively alter-
nates between the assignment of each observation to a nearest medoid and the
re-computation of the set of medoids until medoids stop changing. The number
of clusters,
μ
, to be considered depends on the application under study.
Given matrix [
t
i,j
] and two parameters
tmax
1
and
tmax
2
such that
tmax
2
≥
tmax
1
,wehaveconsideredthatarc(
i,j
)
∈
A
if and only if
t
ij
≤
dmax
1
or
(
t
ij
≤
dmax
2
and cluster(
i
)=cluster(
j
)).
3.2 Heuristic Branch-and-Bound
In the second phase, the objective is to build feasible solutions. The model pre-
sented in Section 2 includes integer variables and branch-and-bound techniques
combined with variable fixing strategies are used to obtain optimal/near-optimal
solutions from an ecient standard MILP solver. We propose a heuristic branch-
and-bound that works in two steps. In the first step, the LP relaxation of model
(1) - (19) where (15) is replaced by
x
ij
≥
0 is solved. If the resulting solution
is not integer variable fixing strategies are used, within a truncated branch-and-
bound algorithm, to obtain a pool of feasible solutions. Consider the following
subsets of the decision variables
x
ij
≥
0, whose integrality has been relaxed:
-
XEP
contains
x
ij
with
i
P
, i.e., decision variables related to
the connection from a mandatory city
i
to a selective city or the home city
j
;
-
XPE
contains
x
ij
with
i
∈
E
and
j
∈
E
, i.e., decision variables related to
the connection from a selective city or the home city
i
to mandatory city
j
;
-
XEE
contains
x
ij
with
i,j
∈
P
and
j
∈
E
, i.e., decision variables related to the
connection from mandatory city
i
to mandatory city
j
;
∈
