基于极大团模型的多星多站测控资源调度方法研究

针对实际应用中大量卫星测控需求不能得到满足这一瓶颈问题,为缓解地面站测控资源有限与不断增长的测控需求数量之间的矛盾,研究多星多站测控调度问题。考虑卫星-地面站可见测控弧段间的冲突及地面测控设备转换时间约束,同时考虑同一测控设备上可能存在多个满足需求的测控弧段,以测控需求是否分配到某一测控弧段为决策变量,建立了多星多站测控调度0-1整数规划模型。针对传统0-1整数规划模型约束众多、规模庞大、难以求解的不足,本文提出了测控弧段区间图描述,基于区间图描述构建了测控调度极大团模型,大幅减少了约束数量,有效提高问题求解效率。为了获取区间图的所有极大团,设计了一个多项式时间(O(nlogn))的极大团获取算法,并从理论上证明了算法的复杂度和最优性。此外,针对存在升降轨特定类型测控数量要求的调度问题,本文对极大团模型进行了拓展,建立了相应的线性整数规划模型。实验结果表明,对于满足实际应用需求的周计划调度问题(测控需求数量≥9000),极大团模型能够在数分钟内得到单次测控需求调度问题最优解。对于多次测控需求调度问题,拓展的极大团模型也能高效求解,得到问题最优解或近似最优解,满足实际应用需求。相对于目前...