We study the Generalized Traveling Salesman Problem (GTSP), which is a variant of the well-known Traveling Salesman Problem (TSP). We are given a graph G = (V,E), where V is the set of nodes, and E the set of edges, each with an associated cost. The set of nodes V is partitioned into m clusters V(1), …,V(m). GTSP is to find an elementary cycle visiting at least one node for each cluster, and minimizing the sum of the costs of the traveled edges. We focus on the so-called Equality GTSP (E-GTSP), in which the cycle has to visit exactly one node for each cluster. The GTSP is a generalization of the TSP: we obtain the traditional TSP in the particular case where all the clusters are composed by just one node. Thus the GTSP is NP-Hard. Most of the literature focuses on heuristic approaches for solving the problem, due to its high complexity. However, in [FSGT97] Fischetti et al. present a Branch and Cut algorithm to solve the problem to optimality. The best state-of-the-art heuristic algorithms for the GTSP are the following: - the Generalized Initialization, Insertion and Improvement algorithm by Renaud and Boctor ([RB98]); - the Nearest Neighbor approach by Noon ([N88]); - the Reinforcing Ant Colony System by Pintea et al. ([PPC07]); - the heuristic algorithms by Fischetti et al. ([FSGT97]), which are computed at the root node of the branch-decision tree. We propose a multi-start heuristic algorithm, which iteratively starts with a randomly chosen set of nodes and applies a decomposition approach to the problem combined with improvement procedures. In a decomposition algorithm, the problem is subdivided into two subproblems. According to the classification introduced by Renaud and Boctor ([RB98]), there are two ways of decomposing the problem. One possibility is to select the nodes to be visited, and then construct a cycle that visits the selected nodes; another possibility is to determine the order in which the clusters are visited, and then construct the optimal cycle. Our method combines these two approaches, alternating the two ways of decomposing the problem and introducing also some randomness in order to explore a greater solution space. In particular, our approach considers a first phase to determine the visiting order of the clusters and a second phase to find the minimum cost cycle. The visiting order of the clusters is obtained as follows: we randomly choose, with uniform probability, one node in each cluster and then compute a TSP feasible solution by using the Farthest Insertion approach, followed by a 2-opt improvement procedure. Once the order of the clusters is fixed, the second phase starts: a Dynamic Programming algorithm is applied. It computes, in polynomial time, the shortest cycle which visits exactly one node in each cluster. This phase gives a new set of nodes, which can be different from the one obtained at the end of the first phase. Thus, we apply a 2-opt improvement procedure to the new sequence, allowing a change in the order of the clusters. If the order of the clusters is changed, we apply again the Dynamic Programming algorithm in an iterative way. Otherwise the current solution cannot be further improved, so we start again with a set of nodes, randomly chosen with uniform probability, one from each cluster. However, we also apply a probabilistic step: with probability p each node in the chosen set is substituted by the node corresponding to the same cluster in the best solution found so far. Our approach iteratively repeats these steps until a stop condition is reached (e.g., time limit). The algorithm was tested on a set of benchmark instances obtained by a clustering procedure introduced by Fischetti et al. ([FSGT97]) applied to instances from the TSPLIB library. These instances are generally used to test the efficiency of the algorithms for the GTSP. The results obtained by our approach are compared with the optimal solutions obtained by a Branch-and-Cut al...

A Multi-Start Heuristic Algorithm for the Generalized Traveling Salesman Problem

CACCHIANI, VALENTINA;TOTH, PAOLO
2008

Abstract

We study the Generalized Traveling Salesman Problem (GTSP), which is a variant of the well-known Traveling Salesman Problem (TSP). We are given a graph G = (V,E), where V is the set of nodes, and E the set of edges, each with an associated cost. The set of nodes V is partitioned into m clusters V(1), …,V(m). GTSP is to find an elementary cycle visiting at least one node for each cluster, and minimizing the sum of the costs of the traveled edges. We focus on the so-called Equality GTSP (E-GTSP), in which the cycle has to visit exactly one node for each cluster. The GTSP is a generalization of the TSP: we obtain the traditional TSP in the particular case where all the clusters are composed by just one node. Thus the GTSP is NP-Hard. Most of the literature focuses on heuristic approaches for solving the problem, due to its high complexity. However, in [FSGT97] Fischetti et al. present a Branch and Cut algorithm to solve the problem to optimality. The best state-of-the-art heuristic algorithms for the GTSP are the following: - the Generalized Initialization, Insertion and Improvement algorithm by Renaud and Boctor ([RB98]); - the Nearest Neighbor approach by Noon ([N88]); - the Reinforcing Ant Colony System by Pintea et al. ([PPC07]); - the heuristic algorithms by Fischetti et al. ([FSGT97]), which are computed at the root node of the branch-decision tree. We propose a multi-start heuristic algorithm, which iteratively starts with a randomly chosen set of nodes and applies a decomposition approach to the problem combined with improvement procedures. In a decomposition algorithm, the problem is subdivided into two subproblems. According to the classification introduced by Renaud and Boctor ([RB98]), there are two ways of decomposing the problem. One possibility is to select the nodes to be visited, and then construct a cycle that visits the selected nodes; another possibility is to determine the order in which the clusters are visited, and then construct the optimal cycle. Our method combines these two approaches, alternating the two ways of decomposing the problem and introducing also some randomness in order to explore a greater solution space. In particular, our approach considers a first phase to determine the visiting order of the clusters and a second phase to find the minimum cost cycle. The visiting order of the clusters is obtained as follows: we randomly choose, with uniform probability, one node in each cluster and then compute a TSP feasible solution by using the Farthest Insertion approach, followed by a 2-opt improvement procedure. Once the order of the clusters is fixed, the second phase starts: a Dynamic Programming algorithm is applied. It computes, in polynomial time, the shortest cycle which visits exactly one node in each cluster. This phase gives a new set of nodes, which can be different from the one obtained at the end of the first phase. Thus, we apply a 2-opt improvement procedure to the new sequence, allowing a change in the order of the clusters. If the order of the clusters is changed, we apply again the Dynamic Programming algorithm in an iterative way. Otherwise the current solution cannot be further improved, so we start again with a set of nodes, randomly chosen with uniform probability, one from each cluster. However, we also apply a probabilistic step: with probability p each node in the chosen set is substituted by the node corresponding to the same cluster in the best solution found so far. Our approach iteratively repeats these steps until a stop condition is reached (e.g., time limit). The algorithm was tested on a set of benchmark instances obtained by a clustering procedure introduced by Fischetti et al. ([FSGT97]) applied to instances from the TSPLIB library. These instances are generally used to test the efficiency of the algorithms for the GTSP. The results obtained by our approach are compared with the optimal solutions obtained by a Branch-and-Cut al...
Proceedings of the VII Cologne-Twente Workshop on Graphs and Combinatorial Optimization 2008 (CTW 2008)
136
138
V.Cacchiani; A.E.Fernandes Muritiba; M.Negreiros; P.Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/73201
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact