多星联合对地观测调度问题的列生成算法

作     者：王沛 谭跃进 WANG Pei;TAN Yue-jin

作者机构：国防科学技术大学信息系统与管理学院长沙410073 

基　　金：国家自然科学基金(70601035 70801062) 

出 版 物：《系统工程理论与实践》 (Systems Engineering-Theory & Practice)

年 卷 期：2011年第31卷第10期

页      码：1932-1939页

摘      要：多星联合对地观测调度问题作为一类大规模组合优化问题,其求解算法往往采用启发式或超启发式.运用列生成思想对该问题设计了完全搜索算法.在建立了问题的整数规划模型之后,将原问题分解为集合配置主问题和含时间窗口的最短路径子问题,其中集合配置主问题采用主单纯型法通过CPLEX求解,含时窗的最短路径子问题采用动态规划求解,该动态规划算法围绕观测冲突时段这一关键资源进行最优子路径的扩展.只有在子问题的最优解对主问题的优化目标仍有改进时,主问题的约束矩阵列才被扩展.该算法针对部分算例得到了最优解,其余算例也在指定的时间内得到了相比一种基于优先级的启发式算法更优的解.

主 题 词：对地观测调度 组合优化 列生成 动态规划 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 0709[理学-地质学] 07[理学] 0708[理学-地球物理学类] 070105[070105] 0802[工学-机械学] 0811[工学-水利类] 0701[理学-数学类] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203757873...