We study the Generalized Traveling Salesman Problem (GTSP), which is a variant of the well-known Traveling Salesman Problem. We are given an undirected graph G=(V,E), with set of nodes V and set of edges E, each with an associated cost. The set of nodes is partitioned into clusters. We focus on the so-called E-GTSP, where "E" stands for "Equality". E-GTSP is to find an elementary cycle visiting exactly one node for each cluster, and minimizing the sum of the costs of the traveled edges. We propose a multi-start heuristic algorithm, which iteratively starts with a randomly chosen set of nodes and applies a decomposition approach combined with improvement procedures. The decomposition approach considers a first phase to determine the visiting order of the clusters and a second phase to find the corresponding minimum cost cycle. We show the effectiveness of the proposed approach on benchmark instances from the literature.

A Multistart Heuristic for the Equality Generalized Traveling Salesman Problem

CACCHIANI, VALENTINA;TOTH, PAOLO
2011

Abstract

We study the Generalized Traveling Salesman Problem (GTSP), which is a variant of the well-known Traveling Salesman Problem. We are given an undirected graph G=(V,E), with set of nodes V and set of edges E, each with an associated cost. The set of nodes is partitioned into clusters. We focus on the so-called E-GTSP, where "E" stands for "Equality". E-GTSP is to find an elementary cycle visiting exactly one node for each cluster, and minimizing the sum of the costs of the traveled edges. We propose a multi-start heuristic algorithm, which iteratively starts with a randomly chosen set of nodes and applies a decomposition approach combined with improvement procedures. The decomposition approach considers a first phase to determine the visiting order of the clusters and a second phase to find the corresponding minimum cost cycle. We show the effectiveness of the proposed approach on benchmark instances from the literature.
NETWORKS
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/87195
 Attenzione

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

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