Using close-enough neighborhood search heuristic for automated meter reading

Close Enough Travelling Salesman Problem (CETSP) gained popularity with coronavirus pandemic, where direct contact between each other is being reduced, social distance practices are being applied and new communication protocols becoming more accessible with the recent advances in technology. In this problem, unlike classical Travelling Salesman Problem (TSP), a seller is only required to be "close enough" to customers in order for customers to be considered visited by the salesman. All customers have a disk shaped neighborhood area and salesman will use these areas to sequence the visits. Cases in which a route is to be constructed for maintenance and reconnaissance flights by an UAV, where imaging from a distance is enough, and a shipment delivery model where recipients can travel to certain points to receive their packages, a utility meter reading problem in which necessary technologies are integrated to both meters and readers can be considered CETSP. In this study, utility meter reading process is defined as CETSP. Improvement potential of CETSP versus classical TSP is measured. Problem is solved by a heuristic based on nearest neighborhood search heuristic. To measure the performance, 22 data sets are used, varying in nodes between 36 and 250. Also, to measure the performance of CETSP in real life applications, a residential area in Ankara-Turkey is selected as a case to apply CETSP solution. Close Enough Neighborhood Search (CENS) heuristic is developed for this study. Results obtained from this algorithm is compared with classical TSP solution. Improvements as high as 49% are obtained using CETSP over TSP. In real life application, improvement rate is 26%. This study showed the effectiveness of using CETSP, even with using a constructive heuristic instead of exact solutions methods or metaheuristics.