Accelerated branch exchange heuristics for symmetric traveling salesman problems
- 1 January 1987
- Vol. 17 (4) , 423-437
- https://doi.org/10.1002/net.3230170405
Abstract
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(N3) to O(N2), 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.Keywords
This publication has 13 references indexed in Scilit:
- On the quality of heuristic solutions to a 19 × 19 quadratic assignment problemEuropean Journal of Operational Research, 1984
- Approximate Traveling Salesman AlgorithmsOperations Research, 1980
- Solving Large-Scale Symmetric Travelling Salesman Problems to OptimalityManagement Science, 1980
- An Effective Heuristic Algorithm for the Traveling-Salesman ProblemOperations Research, 1973
- Algorithms for Large-scale Travelling Salesman ProblemsJournal of the Operational Research Society, 1972
- A man-machine approach toward solving the traveling salesman problemCommunications of the ACM, 1971
- Expected Distances in Distribution ProblemsJournal of the Operational Research Society, 1969
- An Algorithm for the Vehicle-dispatching ProblemJournal of the Operational Research Society, 1969
- Computer Solutions of the Traveling Salesman ProblemBell System Technical Journal, 1965
- A Method for Solving Traveling-Salesman ProblemsOperations Research, 1958