Uma meta-heurística híbrida para o problema da cobertura de disco de raio fixo

Abstract

The coverage problem in computational geometry has applications across a wide range of fields, including wireless communication networks, facility location planning, robotics, image processing, and machine learning. It plays a crucial role in optimizing resource allocation and infrastructure design, addressing challenges such as cost minimization while ensuring complete coverage in applications like cell towers and wireless access points. Furthermore, this problem is fundamental in logistics for optimizing distribution centers and in military defense for the strategic positioning of anti-missile defense systems or radio transmitters. Its broad applicability underscores its importance in tackling economic, social, and technological challenges, highlighting the need for innovative and efficient methodologies. This work presents a hybrid meta-heuristic Construct, Merge, Solve, and Adapt (CMSA) for the Fixed Radius Disk Coverage Problem, which is N P-hard. The objective is to determine the minimum set of disks, along with their locations, required to cover all given points. The proposed CMSA meta-heuristic was evaluated through experimental tests. The comparative analysis focused on the number of disks required and computational execution times. The experimental results demonstrate that the CMSA meta-heuristic significantly outperforms the most advanced methods in the literature, consistently obtaining the best solutions in almost all test cases, with competitive execution times.