Research output: Working paper
Research output: Working paper
}
TY - UNPB
T1 - The compatible tour heuristic for the symmetric traveling salesman problem
AU - Fortini, M.
AU - Letchford, Adam N.
AU - Lodi, Andrea
AU - Wenger, K. M.
N1 - This was eventually published as: M. Fortini, A.N. Letchford, A. Lodi & K.M. Wenger (2011) Computing compatible tours for the traveling salesman problem. Math. Program. Comput., 3(1), 59-78.
PY - 2010
Y1 - 2010
N2 - 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 extensive computational results for TSPLIB instances. It turns out that, in practice, the tour can be found quickly and is usually of very good quality.
AB - 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 extensive computational results for TSPLIB instances. It turns out that, in practice, the tour can be found quickly and is usually of very good quality.
KW - traveling salesman problem
KW - heuristics
KW - branch-and-cut.
M3 - Working paper
T3 - Management Science Working Paper Series
BT - The compatible tour heuristic for the symmetric traveling salesman problem
PB - The Department of Management Science
CY - Lancaster University
ER -