12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Computing compatible tours for the traveling sa...
View graph of relations

« Back

Computing compatible tours for the traveling salesman problem

Research output: Contribution to journalJournal article

Published

Journal publication date2011
JournalMathematical Programming Computation
Journal number1
Volume3
Number of pages20
Pages59-78
Original languageEnglish

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-bar 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-bar. 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 extensive 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.