TY  - JOUR
AU  - Azad, Abul Kalam
PY  - 2025
DA  - 2025/07/21
TI  - A 2-Step Nearest Neighbor Approach to TSP for Mobile Data Collection Route Optimization in IoT
JO  - ICCK Transactions on Mobile and Wireless Intelligence
T2  - ICCK Transactions on Mobile and Wireless Intelligence
JF  - ICCK Transactions on Mobile and Wireless Intelligence
VL  - 1
IS  - 1
SP  - 1
EP  - 10
DO  - 10.62762/TMWI.2025.370327
UR  - https://www.icck.org/article/abs/TMWI.2025.370327
KW  - traveling salesman problem
KW  - optimization
KW  - brute force
KW  - nearest neighbor
KW  - genetic algorithm
KW  - internet of things
AB  - 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.
SN  - 3069-0692
PB  - Institute of Central Computation and Knowledge
LA  - English
ER  - 

@article{Azad2025A,
  author = {Abul Kalam Azad},
  title = {A 2-Step Nearest Neighbor Approach to TSP for Mobile Data Collection Route Optimization in IoT},
  journal = {ICCK Transactions on Mobile and Wireless Intelligence},
  year = {2025},
  volume = {1},
  number = {1},
  pages = {1-10},
  doi = {10.62762/TMWI.2025.370327},
  url = {https://www.icck.org/article/abs/TMWI.2025.370327},
  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 = {traveling salesman problem, optimization, brute force, nearest neighbor, genetic algorithm, internet of things},
  issn = {3069-0692},
  publisher = {Institute of Central Computation and Knowledge}
}