Study of 0-1 backpack planning based on simulated annealing algorithm and greedy algorithm for base station coverage and clustering problems

Abstract

For the base station siting and planning problem in the communication industry, we first establish a 0-1 backpack dynamic planning model, and then use the simulated annealing algorithm and greedy algorithm to continuously optimize the base station sitting under different requirements. Moreover, the coverage area of the considered base stations is closer to the actual one (i.e., three sectoral areas). In this regard, we first establish the polar coordinate system to study the relationship between the change of the main direction angle of a single base station and the coverage area and then use the hierarchical clustering algorithm to classify the main direction angles of the three areas into three categories based on the distribution of weak coverage points around the stations and find the three best main direction angles of a single base station. And the greedy algorithm is used to solve the problem from local to overall so that each base station can cover the weakest coverage points as much as possible, and finally get a more ideal result that the total weak coverage rate of all base stations reaches 79.8%.