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

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