【作者】 康宁；

【导师】 武小悦；

【作者基本信息】 国防科学技术大学 ， 军事装备学， 2011， 博士

【摘要】 航天测控优化调度是在给定的天地基测控资源配置下,将天地基测控资源及使用时间合理地分配给高中低轨道航天器,尽可能满足高中低轨道航天器的航天测控需求。航天测控优化调度问题是一个带时间窗口的组合最优化问题,具有约束种类繁多,涉及因素较多且关系复杂的特点。该问题的建模和求解都具有很大的困难。对航天测控优化调度问题模型及求解算法进行研究,可以支持航天测控系统的顶层规划与决策,为航天测控管理部门提供测控调度方案依据。全文主要的研究工作和创新点包括:(1)航天测控优化调度模型研究分析了任务可用时间窗口作为航天测控优化调度决策变量的不足之处,提出了任务可能开始时刻的概念。论述了以任务可能开始时刻作为航天测控优化调度决策变量的特点。根据约束的强度将所有约束区分为硬约束和软约束,并在航天测控优化调度中区别对待。根据约束的对象将所有硬约束归纳为四类约束:时间窗口约束、测控任务约束、测控设备约束和航天器约束。综合考虑了航天器用户方和测控设备管理方对航天测控优化调度的要求,提出了航天测控优化调度的目标函数。用任务可能开始时刻作为决策变量分别对各种类型硬约束和目标函数进行了形式化描述,建立了航天测控优化调度0-1整数规划模型。该模型能够更充分地利用测控设备资源,并克服了其它模型不易设计最优解求解算法的缺点,为设计航天测控优化调度问题上界和可行解的求解算法打下了模型基础。(2)航天测控优化调度问题上界求解方法研究针对航天测控优化调度0-1整数规划模型,设计了三种松弛策略及对应的航天测控优化调度拉格朗日松弛问题,并研究了具体的求解方法,讨论了松弛策略的选取方法。为了求解航天测控优化调度问题上界,论文构造了航天测控优化调度拉格朗日对偶问题。在一般次梯度优化算法的基础上,设计了历史次梯度优化算法求解拉格朗日对偶问题,并证明了历史次梯度优化算法在收敛性方面优于一般次梯度优化算法。运用历史次梯度优化算法得到的航天测控优化调度问题较优上界,可以评价其它启发式算法的优劣和当前想定配置的合理性。(3)航天测控优化调度问题最优解求解方法研究航天测控优化调度的目的是得到当前想定配置下的航天测控调度方案。当航天测控优化调度问题规模较小时,在可以接受的时间内得到航天测控优化调度问题的最优解是有可能的。论文分析了求解上界过程中得到的航天测控优化调度启发式信息,利用启发式信息设计了分枝策略,并在此基础上构造了求解航天测控优化调度问题最优解的基于拉格朗日松弛的分枝定界算法。(4)航天测控优化调度问题满意解求解方法研究当航天测控优化调度问题规模较大时,难以在可以接受的时间内求得问题的最优解。针对这种情况,论文利用航天测控优化调度启发式信息设计了固定变量选择策略,结合拉格朗日松弛算法设计了基于固定-松弛策略的拉格朗日启发式算法,在可以接受的时间内求得航天测控优化调度问题的一个满意解,可以较好地满足大规模航天测控优化调度问题的需要。(5)航天测控调度方案优化方法研究由于求解航天测控调度方案时没有考虑航天测控优化调度的软约束,因此,论文设计了根据航天测控优化调度的软约束对航天测控调度方案进行调整优化的方法。由于用任务可能开始时刻作为航天测控优化调度的决策变量时,人为地对测控任务执行时间增加了约束。因此,设计了通过去除增加的约束对航天测控调度方案的测控时间进行优化的方法。通过对航天测控调度方案的优化,减少了对软约束的违反情况,增大了测控设备利用率。更多还原

【Abstract】 The Space Tracking Telemetry and Command (TT&C) System optimal scheduling is to appropriately and effectively assign TT&C resource and their use time to various types of spacecrafts when given the configuration of both space and ground TT&C resource, so that TT&C requirements of all spacecrafts can be best satisfied. The Space TT&C System optimal scheduling problem is a combinatorial optimization problem with time windows and has various kinds of constraints, many involved elements and complex relations between elements. These characteristics make it difficult to describe and solve the problem. Research on model and algorithm of Space TT&C System optimal scheduling problem can support planning and decision-making of Space TT&C system and provide Space TT&C System scheduling alternatives for TT&C management department. The main research works are:(1) Research on the Space TT&C System optimal scheduling modelThe limitations of using task useable time window as decision variable for Space TT&C System optimal scheduling is analyzed, and the concept of task possible start time is proposed. The characteristics of using task possible start time as decision variable of Space TT&C System optimal scheduling is discussed. All constraints are divided into hard constraints and soft constraints according to the intensity of the constraint, and the constraints are distinctively treated in the process of Space TT&C System optimal scheduling. All hard constraints are classified into four categories according to constraints’object: time window constraint, TT&C task constraint, TT&C equipment constraint and spacecraft constraint. Both spacecraft user and TT&C equipment manager’s requirements on Space TT&C System optimal scheduling are jointly considered, and the objective function of Space TT&C System optimal scheduling is proposed. Based on using task possible start time as decision variable to formally describe all kinds of hard constraints and objective function, the Space TT&C System optimal scheduling 0-1 integral programming model is constructed. The model can more adequately utilize TT&C equipment resource, and overcome the other models’disadvantage on designing optimal solution algorithm. The model provides a basis for designing solution algorithm of Space TT&C System optimal scheduling problem’s upper bound and feasible solution.(2) Research on upper bound solution method of Space TT&C System optimal scheduling problemBased on the Space TT&C System optimal scheduling 0-1 integral programming model, three relaxation strategies and corresponding Space TT&C System optimal scheduling Lagrangian relaxation problem are designed and their solutions are investigated, then how to select an appropriate relaxation strategy is discussed. To obtain upper bound of Space TT&C System optimal scheduling problem, Space TT&C System optimal scheduling Lagrangian dual problem is constructed. Base on general subgradient optimization algorithm, history subgradient optimization algorithm is designed to solve Lagrangian dual problem, and it is proven that history subgradient optimization algorithm is better than general subgradient optimization algorithm on convergence. The upper bound of Space TT&C System optimal scheduling problem obtained from history subgradient optimization algorithm can evaluate the performance of other heuristics and the rationality of the current scenario’s configuration.(3) Research on optimal solution method of Space TT&C System optimal scheduling problemThe purpose of Space TT&C System optimal scheduling is to obtain Space TT&C System scheduling alternatives in current scenario’s configuration. When the scale of Space TT&C System optimal scheduling problem is relatively small, it is possible to obtain the optimal solution of Space TT&C System optimal scheduling problem in acceptable time. Space TT&C System optimal scheduling heuristic information obtained in the process of solving upper bound is analyzed, the branch strategy utilizing heuristic information is designed, and a branch and bound algorithm based on Lagrangian relaxation for solving Space TT&C System optimal scheduling problem is constructed.(4) Research on satisfactory solution method of Space TT&C System optimal scheduling problemWhen the scale of Space TT&C System optimal scheduling problem is large, obtaining the optimal solution in acceptable time is difficult. In view of this situation, a choosing strategy on fix variable utilizing Space TT&C System optimal scheduling heuristic information is designed, and a Lagrangian heuristic algorithm based on fix-relax strategy is designed combined with Lagrangian relaxation algorithm, then a satisfactory solution of Space TT&C System optimal scheduling problem can be obtained in acceptable time which can better satisfy the requirement of large scale Space TT&C System optimal scheduling problem.(5) Research on optimizing method of Space TT&C System scheduling alternativesBecause the soft constraints of Space TT&C System optimal scheduling is not onsidered when solving Space TT&C System scheduling alternatives, so an optimizing method of Space TT&C System scheduling alternatives according to soft constraints of Space TT&C System optimal scheduling is designed in the dissertation. When using task possible start time as decision variable of Space TT&C System optimal scheduling, additional constraint is imposed on TT&C task execution time. Therefore, a method of optimizing TT&C time of Space TT&C System scheduling alternatives by removing the increased constraint is designed. Through optimizing the Space TT&C System scheduling alternatives, the violation of soft constraints will decrease while TT&C equipment utilization rate will increase.更多还原