SIMULATED ANNEALING FOR SOLVING THE TRAVELLING SALESMAN PROBLEM
DOI:
https://doi.org/10.51406/jnset.v10i2.1374Keywords:
Global minimum, Local Minimal, NP-complete problem, Optimal Solutions, Simulated Annealing, Traveling Salesman ProblemAbstract
In this paper we considered the use of Simulated Annealing for solving the Travelling Salesman Problem (TSP) which is NP-Complete. The algorithm searches solutions for the global minimum by perturbing existing solutions and replace if the new solution is better than the existing solution. The annealing process is controlled by some algorithmic parameters and thus the solution relies on the parameters set. Different parameters were used to know the best set of parameters. Generally the algorithm was tested and proved to be a good solver of TSP.
References
Ali, Hamdar 2008. Simulated Annealing-Solving the Travelling Salesman Problem,www.codeproect.com.
Anthony Ralston, Edwin D. Reilly 1993. Encyclopedia of Computer Science, Chapman and Hall.
Korte, B. 1988. Applications of combinatorial optimization, talk at the 13th International Mathematical Programming Symposium, Tokyo.
Bertsimas, D., Tsitsiklis J. 1993. Simulated Annealing, Journal of Statistical Science, 8(1): 10-15.
Rosenkrantz, D.J., Stearns, R.E., Philip, Lewis M. 1977. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3): 563-581.
Lawler, E.L., Lenstra, J.K., RinnooyKan, A.H.G., Shmoys, D.B. 1985. The Traveling Salesman Problem, John Wiley & Sons, Chichester.
SachinJayaswal, 2004. A comparative study of Tabu Search and Simulated Annealing for Travelling Salesman problem.
Anthony Ralston, Edwin D. Reilly 1993. Encyclopedia of Computer Science, Chapman and Hall.
Korte, B. 1988. Applications of combinatorial optimization, talk at the 13th International Mathematical Programming Symposium, Tokyo.
Bertsimas, D., Tsitsiklis J. 1993. Simulated Annealing, Journal of Statistical Science, 8(1): 10-15.
Rosenkrantz, D.J., Stearns, R.E., Philip, Lewis M. 1977. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3): 563-581.
Lawler, E.L., Lenstra, J.K., RinnooyKan, A.H.G., Shmoys, D.B. 1985. The Traveling Salesman Problem, John Wiley & Sons, Chichester.
SachinJayaswal, 2004. A comparative study of Tabu Search and Simulated Annealing for Travelling Salesman problem.
