Email this article 
New Traveling Salesman Problem Approximation Algorithm
(*) Corresponding author
DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)
Abstract
The travelling salesman problem (TSP) has been studied by many researchers and a great variety of heuristics and implementations with varying solution quality/running time tradeoffs have been proposed. In this paper, we introduce a heuristic algorithm that uses nearest neighbour heuristic first to find an initial tour and then uses a local search component to improve the quality of the solution. The implementation of our algorithm is given. The local search consists of utilizing a combination of brute force and 2-Optimal techniques on small parts of the tour. The results of our implementation are compared with corresponding results using nearest insertion heuristic on the same instances. The effectiveness of our algorithm derives from the improved tour quality achieved with reasonable running times.
Copyright © 2016 Praise Worthy Prize - All rights reserved.
Keywords
References
G.Carpaneto, M.dell’Amico, P.Toth, Exact Solution Of Large-Scale Symmetric Traveling Salesman Problems, ACM Transactions on Mathematical Software, Volume 21, Issue 4, 1994.
D.S.Johnson, L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization (John Wiley and Sons, NY, 1997)
E. L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B.Shmoys, The Travelling Salesman Problem (John Wiley and Sons, 1985)
L. K. Platzman, J. J. Bartholdi, Space filling Curves and The Travelling Salesman Problem, J. ACM, 36, pp. 719-737, 1989.
Thomas Stutzle, Marco Dorigo, ACO Algorithms for The Travelling Salesman Problem, Evolutionary Algorithms in Engineering and Computer Science (Wiley, 1999, 163-183).
Gutin, Punnen, The Travelling Salesman Problem and Its Variations (Kluwer Academic publishers, 2002).
J.L.Bently, Fast Algorithms for Geometric Travelling Salesman Problems, ORSA Journal on Computing, 4, pp. 387-411, 1992.
N. Christofides, Worst Case Analysis of a New Heuristic for The Travelling Salesman Problem, Carnegie-Mellon University Pittsburgh, PA Technical Report, GSIA, 388, 1976.
G. Clarke, J.W. Wright, Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research , 12, pp. 568-581, 1964. h
B. L. Golden, W.R. Stewart, Empirical Analysis of Heuristics, in: E.L.Lawler, et al., (Eds.), The Travelling Salesman Problem (John Wiley & Sons, Chichester, 1985, 207-249).
Christian Nilsson, Heuristics for the Travelling Salesman Problem, Linkoping University Theoretical Computer Science Reports, 2003.
G. A. Croes, A Method for Solving Travelling Salesman Problems, Operations Research, 6 pp. 791-812, 1958.
G. A. Croes, The Travelling Salesman Problem, Operations Research 4 (1956) 61-75.
I. Hong, A.B.Kahng, and B. Moon, Improved Large Step Markov Chains for the Symmetric TSP, Journal of Heuristics, 3, pp. 63-81, 1997.
S. Lin, B. Kernighan, An Effective Heuristic Algorithm for the Travelling Salesman Problem, Oper. Res., 21, pp. 498-516, 1973.
O. Martin, S. W. Otto, and E.W.Felton, Large-Step Markov Chains for the TSP Incorporating Local Search Heuristics, Operations Research Letters, 11, pp. 219-224, 1992.
http://www. research.att.com/~dsj/chtsp. TSP Challenge Website.
A.B. Kahng, Sherief Reda, Match Twice and Stitch: A New TSP Tour Construction Heuristic, Operations Research Letters, 32, pp. 499-509, 2004.
G. Reinelt, The Travelling Salesman: Computational Solutions for TSP Applications, vol. 840 of LNCS, Springer Verlag, 1994.
J. Monnot, V. Th. Paschos, S. Toulouse, Approximation Algorithms for the Traveling Salesman Problem, Mathematical Models of Operations Research, 56, pp. 387-405, 2002.
Refbacks
- There are currently no refbacks.
Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize
