A 2-Step Nearest Neighbor Approach to TSP for Mobile Data Collection Route Optimization in IoT
Abul Kalam Azad · ICCK Transactions on Mobile and Wireless Intelligence · 2025
The Traveling Salesman Problem (TSP) is a well-known NP-hard problem that aims to find the optimal tour among cities, visiting each exactly once and returning to the origin. Over the years, many researchers have proposed various approaches to find near-optimal solutions for TSP. This paper proposed a variant of the nearest neighbor algorithm termed the 2-step nearest neighbor algorithm. Unlike the original nearest neighbor approach, this algorithm considers two nearest nodes as potential next nodes. For each of those nearest nodes, the two nearest nodes have been considered. The sub-tour with the minimum cost among the resulting four has added to the final tour. This process continues until all nodes are covered. The performance of the proposed algorithm compared with that of existing brute-force, nearest-neighbor, and genetic algorithms. The proposed algorithm's utility extends from classical TSP instances to route planning for mobile data collectors in Internet of things (IoT) environments. In such scenarios, a mobile collector visits distributed IoT sensor nodes to gather data and return to its base station, minimizing total travel costs and making the problem analogous to TSP. Result analysis shows that in most scenarios, the proposed approach yields a shorter distance tour than the existing nearest neighbor approach, though with slightly increased computational time. The approach could also be adapted based on the number of nodes, the optimal solution requirement, and available computational resources. The code is available at https://github.com/azad-nstu/CS570-Proj-1-Traveling-Salesman-Problem-TSP.