Home > Research > Publications & Outputs > Computing compatible tours for the traveling sa...

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

Computing compatible tours for the traveling salesman problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Computing compatible tours for the traveling salesman problem. / Fortini, M; Letchford, A N; Lodi, A et al.
In: Mathematical Programming Computation, Vol. 3, No. 1, 2011, p. 59-78.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Fortini, M, Letchford, AN, Lodi, A & Wenger, KM 2011, 'Computing compatible tours for the traveling salesman problem', Mathematical Programming Computation, vol. 3, no. 1, pp. 59-78. https://doi.org/10.1007/s12532-010-0021-5

APA

Fortini, M., Letchford, A. N., Lodi, A., & Wenger, K. M. (2011). Computing compatible tours for the traveling salesman problem. Mathematical Programming Computation, 3(1), 59-78. https://doi.org/10.1007/s12532-010-0021-5

Vancouver

Fortini M, Letchford AN, Lodi A, Wenger KM. Computing compatible tours for the traveling salesman problem. Mathematical Programming Computation. 2011;3(1):59-78. doi: 10.1007/s12532-010-0021-5

Author

Fortini, M ; Letchford, A N ; Lodi, A et al. / Computing compatible tours for the traveling salesman problem. In: Mathematical Programming Computation. 2011 ; Vol. 3, No. 1. pp. 59-78.

Bibtex

@article{f94707b4b98542438b7cc911a7e8b516,
title = "Computing compatible tours for the 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-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.",
keywords = "traveling salesman problem, heuristics, branch-and-cut",
author = "M Fortini and Letchford, {A N} and A Lodi and Wenger, {K M}",
year = "2011",
doi = "10.1007/s12532-010-0021-5",
language = "English",
volume = "3",
pages = "59--78",
journal = "Mathematical Programming Computation",
issn = "1867-2957",
publisher = "Springer Verlag",
number = "1",

}

RIS

TY - JOUR

T1 - Computing compatible tours for the traveling salesman problem

AU - Fortini, M

AU - Letchford, A N

AU - Lodi, A

AU - Wenger, K M

PY - 2011

Y1 - 2011

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

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

KW - traveling salesman problem

KW - heuristics

KW - branch-and-cut

U2 - 10.1007/s12532-010-0021-5

DO - 10.1007/s12532-010-0021-5

M3 - Journal article

VL - 3

SP - 59

EP - 78

JO - Mathematical Programming Computation

JF - Mathematical Programming Computation

SN - 1867-2957

IS - 1

ER -