Premium
Accelerated branch exchange heuristics for symmetric traveling salesman problems
Author(s) -
Stewart William R.
Publication year - 1987
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230170405
Subject(s) - travelling salesman problem , heuristics , mathematical optimization , heuristic , lin–kernighan heuristic , mathematics , computer science , euclidean geometry , bottleneck traveling salesman problem , traveling purchaser problem , branch and bound , combinatorial optimization , combinatorics , geometry
A method for accelerating the computational performance of branch exchange heuristics for symmetric traveling salesman problems (TSP's) is presented. The improvement in performance is obtained by considering only exchanges that have a good chance of producing a better solution. In the instance of the 3–optimal heuristic, the approach reduces the number of operations required to obtain a good solution to a TSP with N nodes from O(N 3 ) to O(N 2 ) , without a corresponding degradation in the quality of the solution. Most of the results are produced for Euclidean TSP's, but evidence is presented that indicates that thes results apply equally well if not more strongly to the general symmetric TSP.