⚡ electrical engineering

Route-Phasing-Split-Encoded Genetic Algorithm for Multi-Satellite On-Orbit Servicing Mission Planning

本文提出了一种路由 - 相位 - 分裂编码遗传算法（RPS-GA），通过统一编码目标序列、离散相位旋转及多服务航天器路径划分，在满足轨道相位耦合与燃料约束的前提下，显著降低了地球同步轨道多服务在轨任务规划的总速度增量（ $\Delta V$ ）。

原作者： Shridhar Velhal, Avijit Banerjee, George Nikolakopoulos

发布于 2026-03-24

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Shridhar Velhal, Avijit Banerjee, George Nikolakopoulos

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇文章介绍了一种名为 RPS-GA（路线 - 相位 - 拆分遗传算法）的新方法，旨在解决一个非常烧脑的问题：如何安排多艘“太空维修船”在地球同步轨道上，高效地给多颗卫星“看病”和“加油”。

为了让你轻松理解，我们可以把整个任务想象成**“在一条巨大的环形高速公路上，安排几辆超级出租车去接载分散在不同位置的乘客”**。

1. 核心挑战：这不是普通的打车

在地球上，出租车去接人，距离是固定的，只要算好路程就行。但在太空中（特别是地球同步轨道），情况要复杂得多：

轨道是动态的： 卫星都在高速绕地球转。就像乘客在环形跑道上跑步，你的车（维修船）必须算准时间，在特定的“交汇点”才能接上乘客。
等待很烧油： 如果乘客还没跑到交汇点，你的车就得在轨道上多转几圈（这叫**“相位调整”**）。转得圈数不对，要么接不到，要么浪费大量燃料（ $\Delta V$ ）。
多车协作难： 你有好几辆出租车（多艘维修船），要把所有乘客分给谁？谁先接谁后接？如果分配不好，有的车累死，有的车闲死，或者大家为了抢时间都烧光了油。

以前的难题： 以前的算法就像是一个笨拙的调度员，先决定“谁去接谁”，再决定“等几圈”，最后发现分配不均，或者油不够了，只能推翻重来。这就像先定好路线，再强行塞进时间，结果发现根本跑不通。

2. 我们的新方案：RPS-GA（三位一体的超级大脑）

这篇论文提出了一种聪明的算法，它不再把“路线”、“等待时间”和“分派任务”分开处理，而是把它们打包成一个**“三位一体”的超级指令包（RPS 染色体）**。

我们可以把这个指令包想象成**“一份完美的旅行攻略”**，它包含三个部分：

路线（Route）： 先接 A，再接 B，最后接 C。
相位（Phasing）： 在去 B 的路上，为了配合 B 的位置，需要多转几圈（比如多转 2 圈）。
拆分（Split）： 这一长串任务，前 3 个归出租车 1，后 4 个归出租车 2。

它的厉害之处在于：

整体思考： 它不会先定路线再硬改时间，而是一开始就同时考虑这三者。就像一位老练的司机，一边规划路线，一边心里盘算着“这里多绕两圈反而能省油，因为下一站乘客刚好在那”。
智能“修补”： 如果算法发现某个方案油不够了，它不会直接扔掉，而是像玩拼图一样，把任务块（Route Blocks）整体移动，或者调整等待的圈数，确保方案依然“可行”。

3. 算法的“进化”过程

这个算法模仿了生物进化（遗传算法）：

优胜劣汰： 它生成成千上万个“旅行攻略”（方案）。
残酷筛选： 它有一个严格的“考官”（适应度函数）。
- 第一关： 必须能按时完成任务，且每辆车都不能“爆缸”（燃料超限）。如果超时或没油，直接淘汰。
- 第二关： 在都合格的前提下，谁省的油多，谁就是冠军。
- 特别规则： 它特别讨厌“偏科”。如果一辆车省了油，另一辆车却累到没油了，这个方案也会被惩罚。它追求的是**“团队整体最省油”**。
杂交与变异： 把两个好方案的“路线”和“等待策略”交换组合，或者随机微调一下“多转几圈”的数字，看看能不能产生更棒的方案。
局部精修（LNS）： 对于已经不错的方案，它还会用一种“后悔策略”进行微调：比如“如果把第 3 个乘客换给另一辆车，是不是能省更多油？”从而把方案打磨到极致。

4. 惊人的成果

在真实的模拟测试中（涉及 2 艘维修船和 14 颗卫星）：

以前的最佳方案： 总共需要消耗 1956.36 米/秒 的速度增量（相当于燃料消耗）。
RPS-GA 的新方案： 只需要 1476.32 米/秒。
结果： 省下了 24.5% 的燃料！

这就像以前送快递需要 100 升油，现在只需要 75 升，而且还能保证所有包裹都准时送达，没有任何一辆车超载。

总结

这篇论文的核心思想就是：在太空中修卫星，不能“走一步看一步”，必须把“去哪”、“等多久”、“分给谁”这三个问题一次性打包解决。

通过这种聪明的“三位一体”算法，我们能让未来的太空维修任务更省钱、更可靠，就像给太空交通系统装上了一个超级智能的导航大脑，让每一滴燃料都花在刀刃上。

1. 问题背景与挑战 (Problem Statement)

背景：
随着地球静止轨道（GEO）卫星价值的提升和寿命延长，在轨服务（OOS）成为未来太空基础设施的关键能力。多服务航天器（SSC）需要协同工作，依次访问多个目标卫星进行维修、加注燃料或维护。

核心挑战：
GEO 轨道的路由规划是一个高度复杂的时空多任务分配问题（STMTA），具有以下显著特征：

时间依赖性： 与地面车辆路径问题（VRP）不同，轨道转移的成本（ $\Delta V$ ）和可行性高度依赖于转移时间。由于卫星相对几何构型的连续演变，转移成本是非平稳的。
强耦合性： 任务访问顺序、相位调整（等待圈数/旋转圈数）和多星任务分割（Route Splitting）是紧密耦合的。改变访问顺序可能导致原本可行的相位窗口失效；重新分配任务可能破坏原有的轨道同步。
约束严格： 必须同时满足严格的燃料预算（ $\Delta V$ 上限）和任务截止时间（Mission Deadline）。
现有方法的局限： 传统方法往往将路由、相位和分割分开优化，或依赖惩罚机制处理不可行解，导致约束违规在不同服务星之间震荡，难以收敛到全局可行的多星协同方案。

2. 方法论：RPS-GA 算法 (Methodology)

论文提出了一种路由 - 相位 - 分割编码遗传算法（RoutePhasingSplit Genetic Algorithm, RPS-GA），旨在联合优化任务排序、相位旋转决策和多星任务分割。

2.1 核心编码：RPS 三元组染色体

为了解决耦合问题，作者设计了一种统一的染色体结构，包含三个部分：

Route (R)： 全局任务执行顺序的排列（Permutation）。
Phasing (n)： 每个任务转移对应的相位旋转圈数（整数变量，决定等待时间和转移成本）。
Split (L)： 路由分割向量，定义如何将全局任务序列分割成 $M$ 条独立的服务路径（即分配给不同的 SSC）。
这种编码方式使得遗传算法能够同时探索任务排序、相位调整和任务分配，且保证了每个任务仅被访问一次。

2.2 约束感知适应度函数 (Constraint-Aware Fitness)

为了引导搜索向可行解收敛，设计了特殊的适应度函数：

目标： 最小化总 $\Delta V$ 。
惩罚机制：
- 聚合惩罚： 惩罚所有 SSC 的总约束违规量。
- 不平衡惩罚： 特别惩罚由单个 SSC 承担大部分违规的情况，防止违规在不同路径间转移。
- 不可行性二元惩罚： 如果存在任何硬约束违规（如超时或超燃料），施加一个巨大的固定惩罚值（ $\kappa$ ）。
前向不变性（Forward-Invariance）： 一旦找到可行解，该解在后续进化中将被视为“可行”并优先保留，防止算法退回到低 $\Delta V$ 但不可行的解。

2.3 专用遗传算子

为了适应 RPS 编码，设计了特定的算子：

分块感知交叉（Route-Block Crossover, RBC）： 交换完整的“路由块”（由分割向量定义的路径段），而非随机交换任务，从而保持路径的可行性和相位一致性。
自适应变异： 对路由顺序、相位圈数和分割长度进行独立变异。不可行个体的变异率更高，以跳出局部不可行区域。
基于遗憾的大邻域搜索（Regret-based LNS）： 作为局部增强模块，利用“2-遗憾插入”启发式算法破坏并重建部分任务序列，同时优化相位旋转，以利用有利的相位窗口。

2.4 停滞检测与多样性注入

引入停滞检测机制，当种群适应度压缩或改进停滞时，注入受控的多样性（替换部分个体），防止早熟收敛，同时保留精英解的结构特征。

3. 关键贡献 (Key Contributions)

RPS 三元组染色体表示： 首次提出将路由序列、相位旋转和任务分割统一编码在一个结构中，实现了耦合决策的高效联合优化。
前向不变性的约束感知适应度： 提出了一种惩罚机制，确保一旦找到可行解，搜索过程不会退回到不可行解，并引导种群向全局可行解收敛，减少了约束违规在个体间的震荡。
显著的 $\Delta V$ 优化： 在相同的评估场景下，相比最先进的 LNS-AGA 基线方法，总 $\Delta V$ 降低了 24.5%（从 1956.36 m/s 降至 1476.32 m/s），显著提升了燃料效率。

4. 实验结果 (Results)

实验设置： 基于真实的 GEO 在轨服务场景（2 颗服务星，14 颗目标卫星，30 天任务窗口，单星 $\Delta V$ 限制 1000 m/s）。
性能对比：
- LNS-AGA (基线)： 总 $\Delta V$ = 1956.36 m/s。
- RPS-GA (本文)： 总 $\Delta V$ = 1476.32 m/s。
- 标准 GA： 总 $\Delta V$ = 2285.59 m/s。
可行性： 在 100 次独立运行中，RPS-GA 均产生了可行解，且所有任务均在 720 小时（30 天）内完成。
消融实验： 移除了“不可行性惩罚”后，算法频繁在可行与不可行解之间震荡，且最终收敛到不可行解的概率增加，证明了该惩罚机制对维持可行解空间的重要性。
任务分配细节： 结果显示，RPS-GA 能够动态调整相位旋转圈数（例如从 1 到 5 圈不等），从而在满足时间窗的同时最小化转移成本。

5. 意义与结论 (Significance & Conclusion)

理论意义： 该研究证明了在轨道路由问题中，将任务排序、相位调整和任务分割进行联合优化（Co-optimization）比分步优化更有效。RPS 编码和分块感知算子为处理时间依赖性的轨道路径问题提供了新的范式。
工程价值： 提出的方法能够生成燃料效率极高且严格满足物理约束的多星协同任务计划。对于未来大规模的 GEO 星座维护、在轨加注和故障恢复任务，该算法提供了可扩展、近实时的规划工具。
核心洞察： 在轨道力学约束下，简单的路径优化是不够的；必须显式地处理“等待时间（相位）”和“多智能体任务分配”的耦合关系，才能避免次优解和不可行解。

总结： 本文通过创新的 RPS-GA 框架，成功解决了多星在轨服务中复杂的时空耦合优化问题，显著降低了任务成本，为未来可持续的太空操作提供了强有力的算法支持。