Improvement of the Nearest Neighbor Heuristic Search Algorithm for Traveling Salesman Problem
DOI:
https://doi.org/10.38032/jea.2024.01.004Keywords:
Combinatorial Optimization, Traveling Salesman Problem (TSP), Heuristic Algorithm, Nearest Neighbor Algorithm, Improved Nearest Neighbor AlgorithmAbstract
The Traveling Salesman Problem (TSP) is classified as a non-deterministic polynomial (NP) hard problem, which has found widespread application in several scientific and technological domains. Due to its NP-hard nature, it is very hard to solve effectively and efficiently. Despite this rationale, a multitude of optimization approaches have been proposed and developed by scientists and researchers during the last several decades. Among these several algorithms, heuristic approaches are deemed appropriate for addressing this intricate issue. One of the simplest and most easily implementable heuristic algorithms for TSP is the nearest neighbor algorithm (NNA). However, its solution quality suffers owing to randomness in the optimization process. To address this issue, this study proposes a deterministic NNA for solving symmetric TSP. It is an improved version of NNA, which starts with the shortest edge consisting of two cities and then repeatedly includes the closest city on the route until an effective route is established. The simulation is conducted on 20 benchmark symmetric TSP datasets obtained from TSPLIB. The simulation results provide evidence that the improved NNA outperforms the basic NNA throughout most of the datasets in terms of solution quality as well as computational time.
References
Rahman, M.A. and Parvez, H., 2021. Repetitive nearest neighbor based simulated annealing search optimization algorithm for traveling salesman problem. Open Access Library Journal, 8(6), pp.1-17. DOI: https://doi.org/10.4236/oalib.1107520
Applegate, D., Bixby, R., Cook, W. and Chvátal, V., 1998. On the solution of traveling salesman problems. DOI: https://doi.org/10.4171/dms/1-3/62
Dantzig, G., Fulkerson, R. and Johnson, S., 1954. Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4), pp.393-410. DOI: https://doi.org/10.1287/opre.2.4.393
Deng, W., Chen, R., He, B., Liu, Y., Yin, L. and Guo, J., 2012. A novel two-stage hybrid swarm intelligence optimization algorithm and application. Soft Computing, 16, pp.1707-1722. DOI: https://doi.org/10.1007/s00500-012-0855-z
Hore, S., Chatterjee, A. and Dewanji, A., 2018. Improving variable neighborhood search to solve the traveling salesman problem. Applied Soft Computing, 68, pp.83-91. DOI: https://doi.org/10.1016/j.asoc.2018.03.048
Matai, R., Singh, S.P. and Mittal, M.L., 2010. Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling Salesman Problem, Theory and Applications, 1(1), pp.1-25. DOI: https://doi.org/10.5772/12909
Naser, H., Awad, W.S. and El-Alfy, E.S.M., 2019. A multi-matching approximation algorithm for Symmetric Traveling Salesman Problem. Journal of Intelligent & Fuzzy Systems, 36(3), pp.2285-2295. DOI: https://doi.org/10.3233/JIFS169939
Halim, A.H. and Ismail, I., 2019. Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem. Archives of Computational Methods in Engineering, 26, pp.367-380. DOI: https://doi.org/10.1007/s11831-017-9247-y
Bentley, J.J., 1992. Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing, 4(4), pp.387-411. DOI: https://doi.org/10.1287/ijoc.4.4.387
Klug, N., Chauhan, A., V, V. and Ragala, R., 2019. k-RNN: Extending NN-heuristics for the TSP. Mobile Networks and Applications, 24, pp.1210-1213. DOI: https://doi.org/10.1007/s11036-019-01258-y
Bakar, S.A. and Ibrahim, M., 2017, August. Optimal solution for travelling salesman problem using heuristic shortest path algorithm with imprecise arc length. In AIP Conference Proceedings, 1870(1). AIP Publishing. DOI: https://doi.org/10.1063/1.4995893
Lin, S. and Kernighan, B.W., 1973. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), pp.498-516. DOI: https://doi.org/10.1287/opre.21.2.498
Chen, Y. and Zhang, P., 2006. Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution. Physica A: Statistical Mechanics and Its Applications, 371(2), pp.627-632. DOI: https://doi.org/10.1016/j.physa.2006.04.052
Raya, L., Saud, S.N., Shariff, S.H. and Bakar, K.N.A., 2020. Exploring the performance of the improved nearest-neighbor algorithms for solving the euclidean travelling salesman problem. Advances in Natural and Applied Sciences, 14(2), pp.10-19.
Rosenkrantz, D.J., Stearns, R.E. and Lewis, II, P.M., 1977. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3), pp.563-581. DOI: https://doi.org/10.1137/0206041
Sahin, M., 2023. Solving TSP by using combinatorial Bees algorithm with nearest neighbor method. Neural Computing and Applications, 35(2), pp.1863-1879. DOI: https://doi.org/10.1007/s00521-022-07816-y
Pop, P.C., Cosma, O., Sabo, C. and Sitar, C.P., 2023. A comprehensive survey on the generalized traveling salesman problem. European Journal of Operational Research, 314(3), pp.819-835. DOI: https://doi.org/10.1016/j.ejor.2023.07.022
Gutin, G., Yeo, A. and Zverovitch, A., 2002. Exponential neighborhoods and domination analysis for the TSP. In The Traveling Salesman Problem and Its Variations (pp. 223-256). Boston, MA: Springer US. DOI: https://doi.org/10.1007/0-306-48213-4_6
Downloads
Published
- Abstract view0
How to Cite
Issue
Section
License
Copyright (c) 2024 Md. Ziaur Rahman, Sakibur Rahamn Sheikh, Ariful Islam, Md. Azizur Rahman
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.