学位论文 > 优秀研究生学位论文题录展示

航天测控优化调度模型及其拉格朗日松弛求解算法

作　者: 康宁
导　师: 武小悦
学　校: 国防科学技术大学
专　业: 军事装备学
关键词: 航天测控优化调度拉格朗日松弛次梯度优化上界启发式算法分枝定界
分类号: V556
类　型: 博士论文
年　份: 2011年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  11-13
Abstract  13-16
第一章绪论  16-40
  1.1 研究背景与意义  16-19
    1.1.1 研究背景  16-18
    1.1.2 研究意义  18-19
  1.2 国内外相关研究现状  19-33
    1.2.1 航天测控优化调度模型研究现状  20-25
    1.2.2 航天测控优化调度算法研究现状  25-30
    1.2.3 拉格朗日松弛算法研究现状  30-33
  1.3 存在的问题和研究思路  33-36
    1.3.1 存在的问题  33-34
    1.3.2 论文研究的思路  34-36
  1.4 主要研究内容与创新点  36-40
    1.4.1 主要研究内容  36-38
    1.4.2 论文的主要创新点  38-40
第二章航天测控优化调度问题  40-60
  2.1 航天测控问题概述  40-44
    2.1.1 基本概念  40-41
    2.1.2 航天测控分类  41-42
    2.1.3 航天器分类及定义  42-44
  2.2 航天测控站分类及测控特点  44-49
    2.2.1 地基测控站分类及测控特点  44-45
    2.2.2 天基测控站工作原理及测控特点  45-48
    2.2.3 测控设备  48-49
  2.3 航天测控过程  49-52
    2.3.1 可见时间窗口  49-50
    2.3.2 航天测控过程的时间段  50-52
  2.4 航天测控需求  52-58
    2.4.1 具体测控需求的调度方法  52-53
    2.4.2 抽象测控需求定义  53-55
    2.4.3 航天测控任务定义及生成方法  55-57
    2.4.4 对航天测控需求中各个需求项的处理  57-58
  2.5 本章小结  58-60
第三章航天测控优化调度问题建模  60-82
  3.1 航天测控优化调度决策变量  60-72
    3.1.1 任务可见时间窗口  61-62
    3.1.2 任务可用时间窗口  62-67
    3.1.3 任务可能开始时间区间  67-69
    3.1.4 任务可能开始时刻  69-72
  3.2 航天测控优化调度约束分析  72-78
    3.2.1 基本假设  72-73
    3.2.2 时间窗口约束  73-74
    3.2.3 测控任务约束  74
    3.2.4 测控设备约束  74-77
    3.2.5 航天器约束  77-78
  3.3 航天测控优化调度模型  78-81
    3.3.1 调度目标  78-80
    3.3.2 数学模型  80-81
  3.4 本章小结  81-82
第四章航天测控优化调度的拉格朗日松弛问题  82-107
  4.1 基于拉格朗日松弛算法的求解策略  82-89
    4.1.1 航天测控优化调度问题的常用求解算法简介  82-84
    4.1.2 松弛算法原理  84-87
    4.1.3 航天测控优化调度问题求解框架  87-89
  4.2 航天测控优化调度问题的松弛策略  89-101
    4.2.1 拉格朗日乘子定义  90-91
    4.2.2 松弛策略1：松弛测控任务约束和测控设备约束  91-97
    4.2.3 松弛策略2：松弛测控任务约束和航天器约束  97-98
    4.2.4 松弛策略3：松弛测控设备约束和航天器约束  98-100
    4.2.5 松弛策略选择  100-101
  4.3 算例实验分析  101-105
    4.3.1 实验想定设计  101-103
    4.3.2 实验结果分析  103-105
  4.4 本章小结  105-107
第五章航天测控优化调度问题的上界求解  107-128
  5.1 航天测控优化调度拉格朗日对偶问题定义  107-109
  5.2 基于一般次梯度的航天测控优化调度问题上界求解  109-115
    5.2.1 次梯度定义及其意义  109-111
    5.2.2 拉格朗日乘子更新原理  111-113
    5.2.3 次梯度优化算法的收敛性  113-115
  5.3 基于历史次梯度的航天测控优化调度问题上界求解  115-120
    5.3.1 历史次梯度定义  115-116
    5.3.2 历史次梯度优化算法的收敛性  116-118
    5.3.3 拉格朗日乘子振荡示例  118-120
  5.4 算例实验分析  120-127
    5.4.1 实验参数设置  120-121
    5.4.2 一般次梯度优化算法与历史次梯度优化算法对比验证  121-125
    5.4.3 上界评价启发式算法  125-126
    5.4.4 上界评价想定配置合理性  126-127
  5.5 本章小结  127-128
第六章航天测控优化调度问题的可行解求解  128-162
  6.1 航天测控优化调度启发式信息分析  128-131
    6.1.1 上界提供的启发式信息  129-130
    6.1.2 伪调度提供的启发式信息  130-131
  6.2 航天测控优化调度问题的最优解求解  131-139
    6.2.1 基于线性规划松弛的分枝定界算法  131-132
    6.2.2 拉格朗日松弛和线性规划松弛对比  132-134
    6.2.3 基于拉格朗日松弛的分枝定界算法求解思路  134-135
    6.2.4 分枝策略  135-137
    6.2.5 算法流程  137-139
  6.3 航天测控优化调度问题的满意解求解  139-144
    6.3.1 基于固定-松弛策略的拉格朗日启发式算法求解思路  139-141
    6.3.2 固定变量选取方法  141-142
    6.3.3 航天测控优化调度问题更新方法  142-143
    6.3.4 算法流程  143-144
  6.4 根据软约束优化航天测控调度方案  144-151
    6.4.1 根据软约束优化航天器测控调度方案时的几种情况  145-146
    6.4.2 可被置换决策变量和可置换决策变量定义  146-150
    6.4.3 根据软约束优化航天测控调度方案的算法  150-151
  6.5 根据测控任务持续时间优化航天测控调度方案  151-155
    6.5.1 测控持续时间窗口和冗余时间窗口  152-154
    6.5.2 根据冗余时间窗口优化航天测控调度方案  154-155
  6.6 算例实验分析  155-161
    6.6.1 算法求解质量分析  155-157
    6.6.2 算法运行时间分析  157-158
    6.6.3 算法适用性分析  158-159
    6.6.4 航天测控调度方案优化效果分析  159-161
  6.7 本章小节  161-162
第七章结论与展望  162-165
  7.1 论文总结  162-163
  7.2 工作展望  163-165
致谢  165-167
参考文献  167-177
作者在学期间取得的学术成果  177-178
附录A 仿真运行环境  178
附录B 仿真想定主要参数  178-179

航天测控优化调度模型及其拉格朗日松弛求解算法

内容摘要

全文目录

相似论文