面向灾害监测的多卫星与多载荷协同任务规划问题：一种双层元启发式方法

《Expert Systems with Applications》：Multi-satellite and multi-payload collaborative mission planning problem facing disaster monitoring: A bi-level metaheuristic approach

　　

•模型：设计了一个混合整数线性规划（MILP）模型，包含两个决策变量，用于分析灾害监测中的多星多载荷协同任务规划问题（SPCMPP-DM）；•算法：利用若干算子开发了一种双阶段进化算法；•基准：进行了广泛的仿真实验以验证所提出的模型和算法。引言多时相、多维度和多光谱观测数据是各类突发性自然灾害的预测、救援和重建的重要前提。具体而言，使用丰富的观测数据可以显著提高自然灾害应急管理（NDEM）的有效性。因此，通过多种载荷获取的观测数据十分珍贵。幸运的是，作为获取支持NDEM的地理信息数据的重要观测资源，地球观测卫星（EOSs）具有全方位视角的独特优势。此外，随着技术的发展，EOSs取得了显著进展，即所谓的3M特征，具体如下：1. 由于近年来大型星座建设计划（Jakhu, Pelton, 2014; Sai, Ren, Jidong, 2018b）相继启动，在轨EOS数量已达数百颗。大量EOS为获取多时相观测数据提供了可能，称为多时相观测；2. EOS的轨道高度（Shao, Madni, & Wertz, 2015）范围从300公里到30,000公里。分层轨道分布确保了所获观测数据的维度特征，称为多维度观测；3. 随着遥感技术的发展，出现了丰富的相机类型，包括合成孔径雷达（SARs，Moreira等，2013）、可见光数码相机（VLDCs，Kim, Hong, & Park, 2017）和红外相机（IRCs，Onaka等，2007）。它们可用于EOS中，从不同光谱波段获取地理信息。这一特征称为多光谱观测。由于仅对地面目标的一次性观测数据无法支持NDEM，因此需要具备3M特征的观测数据是必要的。为此，本研究主要关注3M观测，其中包括高频任务（HFM），如图1所示。HFM是地面目标观测任务的一种特殊类型，即在指定的时间间隔内（称为有效期ED）对目标进行多次观测。考虑到EOS的重访周期和传感器视场，可以得出结论，没有单一EOS能在ED内完成HFM，特别是在NDEM中，HFM的ED可能更短。因此，多星协同观测已成为近年来的主要发展趋势。此外，多光谱观测还为载荷引入了不同的需求。通常，如何协调多星和多载荷是满足NDEM期间多时相、多维度、多光谱观测要求的主要挑战，这被称为灾害监测中的多星多载荷协同任务规划问题（SPCMPP-DM）。SPCMPP-DM要求在使用多颗EOS与满足各种观测要求之间取得平衡。此外，由于地面目标是冗余的（Wang, Chen, & Han, 2016），根据EOS的成像能力，充分挖掘EOS性能代表了求解SPCMPP-DM的另一个重要挑战。求解SPCMPP-DM比求解经典卫星任务规划问题（SMPP）更为复杂，后者已被证明是一个NP难问题（Lemaitre, Verfaillie, Jouhaud, Lachiver, & Bataille, 2002）。换句话说，SPCMPP-DM代表了一个双层组合优化问题。本研究充分考虑了SPCMPP-DM的双重特性，并从问题分析、模型构建和求解算法的角度进行了研究。本工作的主要贡献可总结如下：1. 模型：设计了一个混合整数线性规划（MILP）模型，包含两个决策变量，用于分析SPCMPP-DM。与以往经常过度简化载荷异质性或动态约束的模型不同（Chen, Tian, Dai, Wang, Song, Xing, 2025d; Shang, Yuan, Song, Huang, Yang, Li, 2025），我们的模型明确解决了灾害监测中多载荷协同和高频观测要求的复杂性；2. 算法：利用若干算子开发了一种双阶段进化算法。与纯粹启发式方法（Qi, Hu, Xing, 2025a; Wang, Wu, Shi, Zhao, Jin, 2022）或仅限于小规模实例的精确算法（Li, Chen, Xing, Chen, Du, He, 2025b; Peng, Wang, Song, Gunawan, Xing, Vansteenwegen, 2025）不同，我们的方法将ALNS的全局探索能力与动态规划的精确性相结合，为大尺度、NP难问题提供了可扩展的解决方案；3. 基准：进行了广泛的仿真实验以验证所提出的模型和算法。我们在300个场景上验证了我们的方法，证明在解的质量（HV）和多样性（IGD）方面，相比DE、GRASP和BRKGA等最先进的元启发式算法具有优越的性能。然而，求解SPCMPP-DM问题是本研究的主要目标。本文其余部分的组织结构如下。第2节从问题建模和问题求解算法的角度简要概述了现有文献。第3节介绍了SPCMPP-DM问题的标准形式化描述。第4节提出了一种双阶段进化算法。第5节展示了仿真实验并分析了实验结果。最后，第6节总结了本文并指出了未来的研究方向。研究SPCMPP：模型和算法卫星任务规划问题（SMPP）是一个经典的组合优化问题，已被证明是一个NP难问题（Lemaitre等，2002）。最近，多星多载荷协同任务规划问题（SPCMPP）已成为空间任务管理领域的一个关键优化挑战，这得益于卫星星座（如COSMO-SkyMed和高分系列）的部署以及异构载荷（如光学、问题描述EOS与每个地面目标之间的可见时间窗口是有限的，因此EOS沿着建立的轨道绕地球逐圈飞行。求解SMPP的主要目标是通过有限的EOS（表示为??={1,2,…,??}）完成更多的观测任务（表示为?={1,2,…,??}），这与带时间窗的车辆路径问题（VRPTW）高度相似（Pecin, Contardo, Desaulniers, Uchoa, 2017; Shelbourne, Battarra, Potts, 2017）。具体而言，所有观测任务对应于VRPTW中的节点，每条弧代表一条……基于精确算法的双层元启发式方法在本研究中，SPCMPP-DM被分为两个子问题：资源分配问题（RAP）和时间调度问题（TSP）。在RAP中，目标是探索资源分配空间并确定EOS与所有任务之间的观测关系，其中观测要求约束被优先考虑。基于搜索到的分配方案，为所有任务生成观测窗口（OW），并确定姿态转换时间……实验分析在本节中，我们从不同角度对算法BLMHA-EA求解SPCMPP-DM进行了实验分析。此外，我们还生成了各种测试实例用于实验。所有算法均使用C#编码，使用Visual Studio 2013进行测试，测试环境为AMD Ryzen 5 5600U（配备Radeon显卡）CPU @ 2.3GHz和16 GB RAM。结论本研究系统地解决了SPCMPP-DM问题，这是面向NDEM的多星协同观测的核心挑战，并得出以下关键结论：首先，所提出的MILP模型有效地捕捉了SPCMPP-DM的双重特性。通过整合观测频率、可见时间窗口（VTW）和能耗等约束，该模型克服了现有研究的局限性（例如，忽略载荷异质性和过度简化动态……CRediT作者贡献声明Feng Yao：概念化，写作——审稿与编辑。Guang Yang：方法论，写作——原稿撰写。Zhongxiang Chang：资源，可视化，调查，软件，资金获取。Xiaolu Liu：写作——审稿与编辑。Xiaoming Wang：写作——审稿与编辑，数据整理。利益冲突声明作者声明他们没有已知的财务利益或个人关系可能影响本文所述的工作。Feng Yao | Guang Yang | Zhongxiang Chang | Xiaolu Liu | Xiaoming Wang