An Enhanced Analog Nearest Neighbor Algorithm for Route Planning After a Major Disaster
Romulo B. Magnaye, Brian J. Sauser, Sohail S. , Chaudhry, Thierry Rakotobe-Joel · International Journal of Operations and Quantitative Management · 2021
As human-made and natural disasters become more severe, power and digitalcomputing capabilities become unavailable for longer periods of time in their aftermaths in villages across the developing countries.However, the need for village leaders and first-responders to promptly visit their residents, assess the damage and provide reassurances remain.They have to determine the shortest route which they have to take in order to visit all the residents and return to base to prepare their report for the town or provincial authorities and relief organizations.This paper describes a methodology for solving such a route planning problem without the need for digital computing power which is otherwise unavailable.The proposed approach is an enhanced version of the Nearest Neighbor Methodology algorithm used to solve the Traveling Salesman Problem.After the initial visit from the predetermined starting node (their home) is completed, the agent (village administrator or first-responder) chooses the succeeding destinations by determining the quickest way that the next 2 nearest neighbors can both be visited.This approach, called the Nearest Neighbor Methodology plus mini-tour, yields a shorter length for the tour when compared to the results from the Nearest Neighbor Methodology.It is, however, longer than the results produced by a computer-based genetic algorithm.