Information Technology Reference
In-Depth Information
Let us first define the GTSP, a complete graph G =( V , E ) is a weighted undirected
whose edges are associated with non-negative costs. We denote the cost of an edge
e =( i , j ) by c ij . Then, the set of V nodes is divided into m sets or clusters such that
V =
. The problem involves two
related decisions- choosing a node from the subset and finding a minimum cost tour
in the subgraph of G. In other words, the objective is to find a minimum tour length
containing exactly single node from each cluster V j .
The GTSP was first addressed in [9, 24, 28]. Applications of various exact algorithms
can be found in Laporte et al. [12, 13], Laporte & Nobert [11], Fischetti et al. [7, 8], and
others in [4, 18]. Laporte & Nobert [11], developed an exact algorithm for GTSP by for-
mulating an integer programming and finding the shortest Hamiltonian cycle through
some clusters of nodes. Noon and Bean [18], presented a Lagrangean relaxation algo-
rithm. Fischetti et al. [8] dealt with the asymmetric version of the problem and devel-
oped a branch and cut algorithm to solve this problem. While exact algorithms are very
important, they are unreliable with respect to their running time which can easily reach
many hours or even days, depending on the problem sizes. Meanwhile several other
researchers use transformations from GTSP to TSP since a large variety of exact and
heuristic algorithms have been applied for the TSP [3],. Lien et. al. [15] first introduced
transformation of a GTSP into a TSP, where the number of nodes of the transformed
TSP was very large. Then Dimitrijevic and Saric [6] proposed another transformation
to decrease the size of the corresponding TSP. However, many such transformations
depend on whether or not the problem is symmetric; moreover, while the known trans-
formations usually allow to produce optimal GTSP tours from the obtained optimal
TSP tours, such transformations do not preserve suboptimal solutions. In addition, such
conversions of near-optimal TSP tours may result in infeasible GTSP solutions.
Because of the multitude of inputs and the time needed to produce best results, the
GTSP problems are harder and harder to solve. That is why, in such cases, applications
of several worthy heuristic approaches to the GTSP are considered. The most used con-
struction heuristic is the nearest-neighbor heuristic which, in its adaptation form, was
presented in Noon [17]. Similar adaptations of the farthest-insertion, nearest-insertion,
and cheapest-insertion heuristics are proposed in Fischetti et al. [8]. In addition, Renaud
& Boctor [20] developed one of the most sophisticated heuristics, called GI 3 (Gener-
alized Initilialization, Insertion, and Improvement), which is a gen-eralization of the I 3
heuristic in Renaud et al. [21]. GI 3 contains three phases: in the Initialization phase, the
node close to the other clusters is chosen from each cluster and greedily built into a tour
that passes through some, but not necessarily all, of the chosen nodes. Next in the Inser-
tion phase, nodes from unvisited clusters are inserted between two consecutive clusters
on the tour in the cheapest possible manner, allowing the visited node to change for the
adjacent clusters; after each insertion, the heuristic performs a modification of the 3-opt
improvement method. In the Improvement phase, modifications of 2-opt and 3-opt are
used to improve the tour. Here the modifications, called G2-opt, G3-opt, and G-opt,
allow the visited nodes from each cluster to change as the tour is being re-ordered by
the 2-opt or 3-opt procedures.
Application of evolutionary algorithms specifically to the GTSP have been few in
the literature until Snyder & Daskin [26] who proposed a random key genetic algorithm
{
V 1 ,.., V m
}
with V =
{
V 1
..
V m
}
and V j
V k =
φ
Search WWH ::




Custom Search