On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices
Deineko, Vladimir G., Shabtay, Dvir and Steiner, George. (2011) On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices. Journal of Heuristics, Vol.17 (No.1). pp. 61-96. ISSN 1381-1231Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s10732-010-9127-1
We examine the performance of different subtour-patching heuristics for solving the strongly NP-hard traveling salesman problem (TSP) on permuted Mange matrices. We prove that a well-known heuristic is asymptotically optimal for the TSP on product matrices and k-root cost matrices. We also show that the heuristic is provably asymptotically optimal for general permuted Monge matrices under some mild conditions. Our theoretical results are strongly supported by the findings of a large-scale experimental study on randomly generated numerical examples, which show that the heuristic is not only asymptotically optimal, but also finds optimal TSP tours with high probability that increases with the problem size. Thus the heuristic represents a practical tool to solve large instances of the problem.
|Item Type:||Journal Article|
|Divisions:||Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences
Faculty of Social Sciences > Warwick Business School
|Journal or Publication Title:||Journal of Heuristics|
|Publisher:||Springer New York LLC|
|Page Range:||pp. 61-96|
|Funder:||Centre for Discrete Mathematics and Its Applications, University of Warwick , Engineering and Physical Sciences Research Council (EPRSC) UK , Paul Ivanier Center for Robotics and Production Management, Ben-Gurion University of the Negev , Natural Sciences and Engineering Research Council of Canada|
Actions (login required)