The compatible tour heuristic for the symmetric traveling salesman problem

Management Science

Keywords

traveling salesman problem, heuristics, branch-and-cut.

Research output: Working paper

Published

Standard

The compatible tour heuristic for the symmetric traveling salesman problem. / Fortini, M.; Letchford, Adam N.; Lodi, Andrea et al.
Lancaster University: The Department of Management Science, 2010. (Management Science Working Paper Series).

Research output: Working paper

Harvard

Fortini, M, Letchford, AN, Lodi, A & Wenger, KM 2010 'The compatible tour heuristic for the symmetric traveling salesman problem' Management Science Working Paper Series, The Department of Management Science, Lancaster University.

APA

Fortini, M., Letchford, A. N., Lodi, A., & Wenger, K. M. (2010). The compatible tour heuristic for the symmetric traveling salesman problem. (Management Science Working Paper Series). The Department of Management Science.

Vancouver

Fortini M, Letchford AN, Lodi A, Wenger KM. The compatible tour heuristic for the symmetric traveling salesman problem. Lancaster University: The Department of Management Science. 2010. (Management Science Working Paper Series).

Author

Fortini, M. ; Letchford, Adam N. ; Lodi, Andrea et al. / The compatible tour heuristic for the symmetric traveling salesman problem. Lancaster University : The Department of Management Science, 2010. (Management Science Working Paper Series).

Bibtex

@techreport{aceeca0531234c8985c57755c46ba669,

title = "The compatible tour heuristic for the symmetric traveling salesman problem",

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 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.",

keywords = "traveling salesman problem, heuristics, branch-and-cut.",

author = "M. Fortini and Letchford, {Adam N.} and Andrea Lodi and Wenger, {K. M.}",

note = "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.",

year = "2010",

language = "English",

series = "Management Science Working Paper Series",

publisher = "The Department of Management Science",

type = "WorkingPaper",

institution = "The Department of Management Science",

}

RIS

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 -

Research

Keywords