一种基于禁忌搜索算法的设站问题解决方案

摘要

A tabu search algorithm based on random factors to construct a neighborhood is designed, and a solution for setting up a station is proposed. Firstly, an example about basestation position selection is established, with objective function values including station cost, user connection cost, power coverage demand cost and station connection trunk cost as the solutions to the problem of station position. The minimum value of the objective function is the optimal solution to the problem. Then, the designed algorithm is used to calculate the optimal solution of the case. Finally, comparison validation of the exhaustive solution with the optimal solution of the algorithm is done. The comparison results indicate that the designed search algorithm has better convergence and can effectively avoid the falling of search into local optimal solution. In addition, the algorithm can acquire the global optimal solution of the station problem by searching for less times, thus greatly reducing the calculation of the problem of station setting-up.%设计了一种基于随机因子构造邻域的禁忌搜索算法,为设站问题提出了解决方案.首先构造设站问题实例,以包含设站成本、用户连接代价、功率覆盖需求代价和站点连接中继线成本的目标函数值作为设站问题的解,目标函数最小值即为问题最优解;其次利用所设计算法计算实例最优解;最后以穷举法解决方案与算法最优解作对比验证.对比结果显示,设计的搜索算法具有较好的收敛性,能有效避免搜索陷入局部最优解,且算法通过较少次数的搜索即可得到设站问题的全局最优解,大大减少了求解设站问题的计算量.