A 2-Step Nearest Neighbor Approach to TSP for Mobile Data Collection Route Optimization in IoT
Open Access
- 21 July 2025
- journal article
- Published by Institute of Central Computation and Knowledge Inc. in ICCK Transactions on Mobile and Wireless Intelligence
- Vol. 1 (1) , 1-10
Abstract
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.Keywords
This publication has 19 references indexed in Scilit:
- A Survey on Intelligent Internet of Things: Applications, Security, Privacy, and Future DirectionsIEEE Communications Surveys & Tutorials, 2024
- Review of Traveling Salesman Problem Solution Methods2024
- A reliable method for data aggregation on the industrial internet of things using a hybrid optimization algorithm and density correlation degreeCluster Computing, 2024
- Implementation of drone technology for farm monitoring & pesticide spraying: A reviewInformation Processing in Agriculture, 2023
- Searching Extreme Paths Based on Travelling Salesman’s Problem for Wireless Emerging Networking2023
- State‐of‐the‐art technologies for UAV inspectionsIET Radar, Sonar & Navigation, 2018
- A survey on Hamilton cycles in directed graphsEuropean Journal of Combinatorics, 2012
- The school bus routing problem: A reviewEuropean Journal of Operational Research, 2010
- A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problemJournal of Statistical Physics, 1988
- Some Simple Applications of the Travelling Salesman ProblemJournal of the Operational Research Society, 1975