Otimização de rotas de meios navais em sistemas de coberturas de áreas geográficas com captação de pontos pelas rotas

Abstract

This work addresses the problem of naval routing with the goal of simultaneously optimizing the scanning process and the coverage of a specific maritime area. Currently, scanning patterns follow specific standards, but do not directly aim at route optimization. Therefore, the study proposes optimization models based on the Traveling Salesman Problem (TSP) methodology and heuristic approaches for problems of higher computational complexity. The first stage of the proposed model involves assigning initial points in the area to be scanned, using two initial approaches: random points and equidistant points. The points of interest are generated by a Maximum Coverage Location Problem (MCLP) model, or a model based on the GRASP heuristic. After the points are selected, the model performs routing using TSP modeling. Given that the models are reactive, and route coverage is determined at the end, an iterative model was proposed to perform routing until the desired minimum coverage is achieved. For a large number of points of interest, the iterative method employs heuristic solutions for route construction, using the GRASP and Nearest Neighbor methods. The results demonstrate that these approaches can be effective options for routing in scanning problems, aiming at the coverage of strategic geographic areas along the Brazilian coastline.