需求牵引的北斗星地时间同步任务规划问题建模与求解

Precise satellite-ground time synchronization task planning is a guarantee of soft power to improve the positioning accuracy of the Beidou Navigation system. Compared with traditional scheduling problems, the satellite-ground time synchronization task planning problem has complex characteristics such as multi-objective, complex decision variables and diversified requirements. Through the analysis of the commonality and personality characteristics under different needs of the problems, a centralized solving framework under diversified needs is established. Aiming at the strong application requirements and weak application requirements in the experimental phase, the knapsack problem model and the first-come-first service model are established respectively. The intelligent optimization method and the rule-based heuristic scheduling method are designed to solve the problem. Aiming at the complex task requirements in daily operation, the meta-task model is designed to solve the problem, and a multi-objective evolutionary algorithm based on decomposition-integration is proposed. According to the user's preference needs, this paper studies the preference expression form and designs the preference-inspired multi-objective co-evolutionary algorithm. Considering that the contradiction between the time-consuming evolutionary algorithm and the rapid response of the actual application, it designs the rolling task planning method of dynamic learning, alternative evolutionary mechanisms through rolling learning, which could quickly obtains the satisfactory solution of the user. Finally, based on the design and application examples of the Beidou-3 Navigation system, semi-physical and physical simulations are carried out to verify the rationality of the model and algorithm. The key technologies of this project can quickly enter the engineering application and provide support directly for the operation of the Beidou Navigation system.

精确的星地时间同步任务规划是提升北斗系统定位精度的软实力保障。星地时间同步任务规划问题相比传统调度问题具有多目标、决策变量复杂、需求多样化等复杂特性。本项目通过对不同需求下问题共性和个性特征的分析，构建可融合多样化需求的集成求解框架。针对试验阶段的强应用需求和弱应用需求，分别建立背包问题模型和先到先服务模型，设计智能优化方法和基于规则的启发式调度方法求解。针对日常运行中复杂任务需求，设计元任务模型进行问题分解，提出基于分解-整合的多目标进化算法求解。针对用户偏好需求，研究偏好表达形式，设计可融合偏好的多目标协同进化算法，并针对进化算法耗时长与实际应用要快速响应的矛盾，设计动态学习的滚动任务规划方法，通过滚动学习替代进化机制，快速得到满意解。基于北斗三号系统设计应用实例，利用真实数据和模拟数据验证模型和算法的可行性。本项目关键技术的突破可加快工程化应用，为北斗系统业务运行提供直接支撑。

星地时间同步业务是北斗导航系统的核心业务，精确的星地时间同步任务规划是提升北斗系统定位精度的软实力保障。星地时间同步任务规划相比传统地面站调度问题具有多目标、决策变量复杂、需求多样化等复杂特性。本项目通过对试验环境下特定应用需求、常规运行中复杂任务需求、特定场景下不同偏好需求等不同需求下问题共性和个性特征进行分析，建立了多样化需求下的分阶段求解框架，设计了基于分解与整合的星地时间同步任务规划模型。针对试验阶段的强应用需求和弱应用需求，分别建立背包问题模型和先到先服务模型，设计了智能优化方法和基于规则的启发式调度方法求解。针对日常运行中复杂任务需求，设计元任务模型进行问题分解，提出基于分解-整合的多目标进化算法求解。针对用户偏好需求，研究偏好表达形式，设计可融合偏好的多目标协同进化算法，并考虑到进化算法具有搜索空间大、耗时长等缺陷，设计动态学习的滚动任务规划方法，快速得到用户满意解。最后基于北斗三号系统设计应用实例，开展基于数据的模拟仿真，经验证，模型和算法合理可行，部分成果已进入工程化应用，为北斗三号系统业务运行提供了直接支撑。