An Exact Algorithm for the Close Enough Vehicle Routing Problem Applied to Spraying Drones

This paper introduces an exact algorithm capable of planning drone routing for agricultural resource spraying. Since spot spraying covers an area around it, the device's trajectory was modeled as a solution to the Close Enough Vehicle Routing Problem, which the objective is to optimize routes that cover a set of coordinates by passing near them, as well as their launching and return points. Thus, a Branch-and-Bound algorithm is proposed, initialized with a heuristic solution based on coverage zones, capable of solving instances to their optimality, with a Dynamic Programming strategy embeded. Experimental results showed that the algorithm is capable of solving plausible instances, with different levels of spray point dispersion, within the stipulated limit of 10 minutes, allowing wide application in precision agriculture.