成像卫星集成调度的变邻域禁忌搜索算法

Variable neighborhood tabu search algorithm for integrated imaging satellites scheduling problem

探讨了一类涉及多星、多地面站的成像卫星系统集成调度问题,要求从可能过度订购的卫星观测需求中,选择一个能够无冲突完成的任务子集,并为相应的观测和数据下传活动安排资源和时间,以最大化对所有用户需求的总体满足程度.建立了该问题的变体形式车辆路线问题模型,没计了改进型和调整型两类邻域结构,并提出了一种变邻域禁忌搜索算法.通过交替使用两类邻域结构,增强了算法对解空间的探索能力和规避局部极值的能力.测试算例的计算结果和与其它算法的比较表明,该算法能够在相近的计算时间内显著改善求解质量.

This paper discusses a kind of integrated scheduling problem of imaging satellite system involv-ing multi-satellites, multi-ground stations. It required a subset of non-conflict tasks be selected among a group of over subscribed demands, and resources and execution times be arranged for the related imaging and data downloading activities, while maximizing the collective content of the total demands. We first construct a variant vehicle routing problem model for the problem. Then two kinds of different neighbor- hood structures named adjusting neighborhood and improving neighborhood are designed. Furthermore, we propose a variable neighborhood tabu search algorithm. By using two kinds of neighborhoods alter- natively, the algorithm＇s ability of exploring solution space and avoiding local optima are significantly improved. The calculation results of some test examples and comparison with other algorithms showed that the solution quality within similar time is notably improved.