Optimization of near-space aerocraft track for regional coverage based on greedy algorithm

In order to covering any discretionary polygonal region, a novel method was proposed based on set covering problem model, which is a NP-hard problem. Random greedy algorithm strategy was applied in the method to achieve 100% regional coverage with minimum aerocrafts by designing and optimizing each aerocraft's track and beam position. Random greedy algorithm removed some aerocrafts from the solution of greedy algorithm randomly and added some new ones based on greedy strategy again. The method extended search range for more possible optimized solutions compared with traditional greedy algorithm. Simulation result on Wenchuan area shows good effectiveness and intelligence of the method. Reliable reference can be supplied for near-space regional coverage planning.