1. 标题

· An improved fusion crossover genetic algorithm for a time-weighted maximal covering location problem for sensor siting under satellite-borne monitoring

· 一种顾及卫星观测的时间加权最大覆盖选址问题的改进遗传算法

2. 成果信息

· Wang, K., Gong, Y., Peng, Y., Hu, C. and Chen, N., 2020. An improved fusion crossover genetic algorithm for a time-weighted maximal covering location problem for sensor siting under satellite-borne monitoring. Computers & Geosciences, 136: 104406.

· https://www.sciencedirect.com/science/article/pii/S0098300419304340

· DOI: 10.1016/j.cageo.2020.104406

3. 成果团队成员

· 王珂，博士，中国地质大学（武汉）地理与信息工程学院，副教授，硕士研究生导师。主要研究方向包括地理空间传感网，智慧城市综合感知、时空优化模型与算法。

· 龚悦，硕士生，武汉大学测绘遥感信息工程国家重点实验室，主要研究方向包括传感网时空优化与智能计算。

· 胡楚丽，博士，中国地质大学（武汉）地理与信息工程学院，副教授，硕士研究生导师。主要研究方向包括地理空间传感网、地学传感器集成管理以及智慧城市感知相关研究。

4. 成果介绍

本文针对卫星观测下的地面传感器布局问题，引入了一种考虑部分覆盖的时间加权最大覆盖模型（TMCLP-PC），旨在确定有限数量的地面站使得在连续观测期间内的星地传感器提供最大的覆盖范围。该模型在TMCLP模型基础上增加了部分覆盖判定（图1），能够精确计算地面站点和卫星传感器提供给每个需求单元的覆盖百分比，从而提高模型的计算精度，有利于获得更可靠的布局方案。

图1. 考虑部分覆盖的星地传感器时间加权最大覆盖问题

为了求解TMCLP-PC模型，本文提出了一种基于时空融合交叉的改进遗传算法ST-swap GA。该方法充分考虑了星地传感器覆盖问题中的时空分布特征，采用时空离散化思想，设计了基于时空覆盖度的新型融合交叉算子ST-swap。通过降低地面站点与卫星传感器的重复覆盖，预测地面站点选址对卫星时空覆盖率较小区域的倾向性，从而缩小搜索空间并加快收敛速度。

以金沙江下游流域雨量站网布局为例，对所提出的改进遗传算法进行了验证。实验结果表明，与商业数学规划软件CPLEX相比，ST-swap GA能够显著降低计算的时间开销，大幅提高求解效率。同时，GA结果与CPLEX结果的偏差度（Gap）表明ST-swap GA的性能优于传统遗传算法。从与采用传统交叉算子（单点交叉、均匀交叉、融合交叉）的遗传算法在不同待布设的雨量站总数量p下输出的最优解的对比图中（图2）可以看出，ST-swap GA最优解的误差值小于使用传统交叉算子的遗传算法。因此，本文所提出的改进遗传算法能够快速准确地求解时间加权的星地时空最大覆盖问题。

图2. 改进遗传算法与传统交叉算子的对比结果