Matheuristics for Multi-UAV Routing and Recharge Station Location for Complete Area Coverage.

Area of Science:

• Robotics and Automation
• Operations Research
• Computer Science

Background:

• Coverage Path Planning (CPP) is crucial for Unmanned Air Vehicle (UAV) operations.
• Existing CPP research often overlooks heterogeneous vehicle capabilities and dual optimization objectives.
• Simultaneously minimizing coverage time and the number of refueling stations presents a significant challenge.

Purpose of the Study:

• To develop and evaluate matheuristics for efficient routing of heterogeneous UAV fleets for complete area coverage.
• To address the combined objectives of minimizing coverage time and the number of refueling stations.
• To explore the performance of different integration strategies between metaheuristics and exact methods.

Main Methods:

• A high-level path planning approach combining Multiobjective Variable Neighborhood Search (MOVNS) with an exact mathematical formulation.
• Evaluation of four distinct integration strategies for the metaheuristic and exact methods.
• Utilizing metrics such as execution time, coverage, cardinality, and hypervolume for performance assessment.

Main Results:

• The proposed matheuristics effectively handle heterogeneous UAVs and dual optimization objectives.
• Integration of the exact method as an intraroute operator within Variable Neighborhood Descent (VND) yielded highly efficient solutions.
• This strategy achieved results comparable to the closest-to-optimal methods but with significantly improved efficiency.

Conclusions:

• Matheuristics offer a powerful approach for complex UAV routing and coverage problems.
• The specific integration strategy of using exact methods within VND provides a strong balance between solution quality and computational efficiency.
• This research advances the field of autonomous systems by providing practical solutions for optimizing UAV deployment.