In the 2-period Travelling Salesman Problem some nodes, called double nodes, are visited in both of two periods while the remaining ones, called single nodes, are visited in either one of the periods. In this paper we study the case in which a balance constraint is also introduced. We require that the difference between the number of visited nodes in the two periods must be below a fixed threshold. Moreover, we suppose that distances between nodes are Euclidean. The problem is NP-hard, and exact methods, now available, appear inadequate. Here, we propose three heuristics. Computational experiences and a comparison between the algorithms are also given.

Heuristic algorithms for the 2-period balanced Travelling Salesman Problem in Euclidean graphs

MASON, Francesco
2010-01-01

Abstract

In the 2-period Travelling Salesman Problem some nodes, called double nodes, are visited in both of two periods while the remaining ones, called single nodes, are visited in either one of the periods. In this paper we study the case in which a balance constraint is also introduced. We require that the difference between the number of visited nodes in the two periods must be below a fixed threshold. Moreover, we suppose that distances between nodes are Euclidean. The problem is NP-hard, and exact methods, now available, appear inadequate. Here, we propose three heuristics. Computational experiences and a comparison between the algorithms are also given.
File in questo prodotto:
File Dimensione Formato  
TSP mason bassetto.pdf

non disponibili

Tipologia: Abstract
Licenza: Accesso chiuso-personale
Dimensione 412.68 kB
Formato Adobe PDF
412.68 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA 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: https://hdl.handle.net/10278/24241
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact