We consider the following natural heuristic for the Symmetric Traveling Salesman Problem: solve the subtour relaxation, yielding a solution x∗, and then find the best tour x ̄ that is compatible with x∗, where compatible means that every subtour elimination constraint that is satisfied at equality at x∗ is also satisfied at equality at x ̄. We prove that finding the best compatible tour is NP-hard and show that the tour can have a cost approaching 5/3 that of the optimal tour. We then describe a branch-and-cut algorithm for computing the best compatible tour, and present exten- sive computational results for TSPLIB instances. It turns out that, in practice, the tour is usually of very good quality. Moreover, the computational effort for computing the compatible tour is considerably smaller than that of solving the full problem with the best available software, i.e., Concorde.

Computing Compatible Tours for the Symmetric Traveling Salesman Problem

LODI, ANDREA;
2011

Abstract

We consider the following natural heuristic for the Symmetric Traveling Salesman Problem: solve the subtour relaxation, yielding a solution x∗, and then find the best tour x ̄ that is compatible with x∗, where compatible means that every subtour elimination constraint that is satisfied at equality at x∗ is also satisfied at equality at x ̄. We prove that finding the best compatible tour is NP-hard and show that the tour can have a cost approaching 5/3 that of the optimal tour. We then describe a branch-and-cut algorithm for computing the best compatible tour, and present exten- sive computational results for TSPLIB instances. It turns out that, in practice, the tour is usually of very good quality. Moreover, the computational effort for computing the compatible tour is considerably smaller than that of solving the full problem with the best available software, i.e., Concorde.
M. Fortini; A.N. Letchford; A. Lodi; K.M. Wenger
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/100435
 Attenzione

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

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