航天测控调度问题的模型模型松弛

航天测控调度问题的模型模型松弛

1航天测控调度问题轨道计划问题是指在给定的可控源的配置下，采用合理的模型和算法，管理和规划不同类型卫星的跟踪、遥感和振动器的测量需求，最大限度地发挥场景卫星的测量需求。文献[1-2]分别建立了该问题的约束满足问题模型,以卫星任务、测控设备、时间资源等基本要素为调度对象。迭代修正算法本文构建了航天测控调度问题的0-1整数规划模型,在3种松弛策略的基础上构造了3种拉格朗日松弛问题,并分别用次梯度优化算法求解上界。通过仿真算例对基于不同松弛策略的上界求解算法性能进行比较,得出了给定测控需求配置下选择松弛策略的指导原则。2任务设置约束卫星集合为SAT={sat根据任务可用时间窗口可以得到任务可能开始时刻,即航天测控调度模型的决策变量。具体方法为:根据任务可用时间窗口得到任务可能开始时间区间式(1)为目标函数:最大化所有成功调度任务收益值。式(2)为任务约束:每个任务最多只能执行一次。式(3)为设备约束:每个设备某一时刻最多只能为一个任务服务,每个设备成功调度的任务满足设备最小切换时间要求。其中,G3拉格朗日松弛算法若将IP中的任务约束、设备约束、卫星约束中的任意2个约束去掉,IP可在多项式时间内求得最优解,定义:分别是松弛任务约束、设备约束和卫星约束的拉格朗日乘子,3种乘子两两组合(即(μ,ν)、(λ,μ)、(λ,ν))形成3种松弛策略及其对应的拉格朗日松弛问题。对给定的(μ,ν),定义松弛设备约束和卫星约束的拉格朗日松弛问题LR(μ,ν):在式(6)和式(7)中,G对给定的(λ,μ),定义松弛任务约束和设备约束的拉格朗日松弛问题LR(λ,μ):对给定的(λ,ν),定义松弛任务约束和卫星约束的拉格朗日松弛问题LR(λ,ν):对于LR(μ,ν),当(μ,ν)给定后,Z4z次梯度优化算法可以证明,对于∀(μ,ν)≥0,都有ZLR(μ,ν)≥ZIP;对于∀(λ,μ)≥0,都有ZLR(λ,μ)≥ZIP;对于∀(λ,ν)≥0,都有Z次梯度优化算法是求解Z定义θ为利用(s(λ),s(ν))更新(λ,ν)时的步长,本文中步长设置为:其中,上标k表示次梯度优化的第LR(λ,ν)次迭代;π实际计算中最优上界可能无法求得,本文规定得到最优上界或迭代500次后,算法停止。次梯度优化算法的基本步骤如下:Step1初始化:λStep2根据(λStep3若满足停止准则,算法停止,否则,转Step4。Step4根据(s(λ通过上述次梯度优化算法可以得到采用(λ,ν)松弛策略的IP上界Z5主要测试参数利用STK软件设计2个场景:场景1有5个设备18颗卫星,场景2有5个设备35颗卫星,设计了4种测控需求配置。限于篇幅,本文只给出场景1的部分参数。选取的部分(3台)设备基本参数见表1,选取的部分(4颗)卫星轨道参数见表2(用ApogeeAltitiude(Ap)、PerigeeAltitude(P)、Inlination(I)、ArgumentofPerigee(Ar)、RAAN(R)、TrueAnonaly(T)表示),测控需求配置参数见表3(用需求收益值(S)、测控任务持续时间(T)/m、每天升轨测控任务数(SN)、每天降轨测控任务数(JN)、卫星最小测控间隔时间(SM)/m)、设备最小切换时间(JM)/m表示),调度周期设为1天:2010-11-260:00:00至2010-11-270:00:00。用文献[6]给出的综合优先度算法的可行解目标函数值作为问题下界对所求上界进行比较验证,限于篇幅,本文只列出场景1的调度结果,如表4所示。由调度结果可以看出,在求解效果方面,经过充分迭代,3种松弛策略下运用次梯度优化算法得到的上界(目标函数值)几乎没有差别,都可以用来评价启发式算法可行解的优劣和场景配置的合理性。以配置1(con在运算时间方面,当场景配置没有卫星最小测控间隔时间和设备最小切换时间要求(con6弛策略上界求解在航天测控调度上界求解过程中,需要根据测控需求配置情况选