Improvement of the Nearest Neighbor Heuristic Search Algorithm for Traveling Salesman Problem

Md. Ziaur  Rahman; Sakibur Rahamn  Sheikh; Ariful  Islam; Md. Azizur Rahman

doi:10.38032/jea.2024.01.004

Authors

Md. Ziaur Rahman Department of Mathematics, Bangladesh University of Engineering and Technology (BUET), Dhaka-1000, Bangladesh
Sakibur Rahamn Sheikh Mathematics Discipline, Khulna University, Khulna-9208, Bangladesh
Ariful Islam Mathematics Discipline, Khulna University, Khulna-9208, Bangladesh
Md. Azizur Rahman Mathematics Discipline, Khulna University, Khulna-9208, Bangladesh

DOI:

https://doi.org/10.38032/jea.2024.01.004

Keywords:

Combinatorial Optimization, Traveling Salesman Problem (TSP), Heuristic Algorithm, Nearest Neighbor Algorithm, Improved Nearest Neighbor Algorithm

Abstract

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