⚡ electrical engineering

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

This paper proposes a Route-Phasing-Split Genetic Algorithm (RPS-GA) that simultaneously optimizes target sequencing, orbital phasing, and route partitioning for multi-servicer geosynchronous orbit missions, achieving a 24.5% reduction in total fuel consumption compared to state-of-the-art baselines while ensuring strict propellant and mission-duration constraints.

Original authors: Shridhar Velhal, Avijit Banerjee, George Nikolakopoulos

Published 2026-03-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Shridhar Velhal, Avijit Banerjee, George Nikolakopoulos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the director of a massive, high-stakes space cleanup crew. You have a fleet of robotic repair ships (let's call them "Space Mechanics") and a list of broken satellites floating in a giant, circular racetrack high above the Earth (Geosynchronous Orbit).

Your goal is simple: Fix all the broken satellites using the least amount of fuel possible, and finish before the deadline.

But here's the catch: Space isn't like driving a car on a highway.

The Problem: The "Moving Target" Racetrack

On Earth, if you need to drive from Point A to Point B, the distance is fixed. In space, everything is moving. The satellites are zooming around the Earth at thousands of miles per hour.

The Timing Game: If your Space Mechanic leaves too early or too late, the target satellite will have already zoomed past the meeting point. The mechanic has to wait, or do a complex dance (called "phasing") to catch up.
The Fuel Cost: Every time a ship changes its speed or angle to catch a target, it burns fuel. If the timing is off by even a tiny bit, the fuel cost skyrockets.
The Teamwork: You have multiple ships. You need to decide: Which ship goes to which satellite? In what order? And how long should each ship wait before moving to the next one?

If you get the order wrong, or if one ship gets stuck waiting too long, the whole mission could run out of fuel or time.

The Old Way vs. The New Way

The Old Way (The "Guess and Check" Approach):
Previous methods tried to solve this in steps. First, they'd pick a route. Then, they'd try to figure out the timing. If the timing didn't work, they'd go back and change the route. It was like trying to solve a puzzle by moving one piece at a time, often breaking the pieces you just fixed. This led to plans that looked good on paper but were impossible to execute in real life.

The New Way (The "RPS-GA" Approach):
The authors of this paper created a new "brain" for the mission planner called the RoutePhasingSplit Genetic Algorithm (RPS-GA). Think of it as a super-smart, evolutionary coach that learns by trial and error, but with a very specific trick.

1. The "All-in-One" ID Card (The Chromosome)

Instead of treating the route, the timing, and the team split as separate problems, this new method puts them all on a single "ID card" for every possible plan.

Route: The order of satellites to visit.
Phasing: How many times the ship should spin around the Earth to wait for the perfect moment to jump.
Split: Which ship does which part of the job.

It's like a chef who doesn't just write down the ingredients (route) but also writes down exactly when to turn on the oven (phasing) and which assistant does which dish (split), all on one recipe card.

2. The "No-Go" Zone (Constraint-Aware Fitness)

In many computer programs, if a plan is impossible (e.g., runs out of fuel), the computer just says, "Okay, that's a bad plan," and tries another. But sometimes, a plan looks great because it saves fuel, even if it breaks the rules (like arriving 10 minutes late).

This new algorithm has a strict rule: If a plan breaks the rules, it's disqualified immediately.
It uses a special scoring system that says, "We don't care how much fuel you saved if you broke the deadline." It also makes sure that the best plan found so far stays safe. Once the computer finds a plan that works perfectly, it locks it in as the "Champion" and refuses to let any "cheating" plans (that break rules but look cheap) take its spot.

3. The "Smart Swap" (Split-Aware Crossover)

When the algorithm tries to create new plans by mixing two good ones, old methods would often smash the schedule apart. Imagine taking a perfect train schedule and swapping the middle cars with another train, causing the whole thing to derail.

This new method uses "Route-Block Crossover." It treats a chunk of the schedule (a block of satellites assigned to one ship) as a solid brick. When it mixes plans, it swaps whole bricks instead of individual bricks. This ensures the new plan is still a working schedule, not a mess.

4. The "Regret" Check (Local Search)

Sometimes, the algorithm gets stuck in a "good enough" solution. To fix this, it uses a technique called Regret-Based Search.
Imagine you are packing a suitcase. You put in your shoes. Then you realize, "If I had put the shoes in the side pocket, I could have fit a jacket." That feeling of "I should have done it differently" is Regret.
The algorithm looks at the tasks it didn't assign and asks, "How much would we regret not putting this task here?" It then rearranges the plan to fix those regrets, polishing the schedule until it's perfect.

The Result: A Massive Fuel Savings

The team tested this new "brain" on a realistic scenario involving 14 broken satellites and 2 repair ships.

The Old Best: The previous state-of-the-art method required 1,956 meters per second of fuel (Delta-V).
The New Best: The RPS-GA found a plan requiring only 1,476 meters per second.

That is a 24.5% reduction in fuel.

Why This Matters

In space, fuel is life. Saving 25% of the fuel means:

Cheaper Missions: You can launch smaller, cheaper rockets.
More Satellites: With the saved fuel, those same ships could potentially fix more satellites.
Longer Life: The ships have more fuel left over for emergencies or future tasks.

In a nutshell: This paper teaches us how to organize a space repair crew so they don't just "get the job done," but do it with the absolute minimum amount of fuel, by treating the order, the timing, and the team split as one single, inseparable puzzle. It's the difference between a chaotic, fuel-hungry space race and a smooth, efficient ballet in the stars.

1. Problem Statement

The paper addresses the Multi-Servicer On-Orbit Servicing (OOS) mission planning problem within Geosynchronous Earth Orbit (GEO). The core challenge is to plan efficient transfer routes for multiple Servicing Spacecraft (SSCs) to visit and repair a set of target satellites.

Key characteristics and constraints of the problem include:

Time-Dependent Costs: Unlike terrestrial routing, orbital transfer costs ( $\Delta V$ ) and feasibility are non-stationary. They depend heavily on orbital phasing (the relative angular position of satellites) and the timing of maneuvers.
Tight Coupling: Decisions regarding route sequencing (which target to visit next), phasing rotations (how many orbits to wait/coast to synchronize), and route splitting (how to partition targets among multiple SSCs) are tightly coupled. Changing one often invalidates the feasibility or optimality of the others.
Constraints: The solution must satisfy strict limits on:
- Propellant ( $\Delta V$ ): Each SSC has a maximum fuel budget.
- Mission Duration: All tasks must be completed within a specific deadline (e.g., 30 days).
- Feasibility: Transfers must respect orbital mechanics (plane changes, phasing windows).
Complexity: The problem is a combinatorial, non-convex Multi-Traveling Salesman Problem (mTSP) variant with time-dependent edge costs, making exact optimization methods computationally intractable for realistic scenarios.

2. Methodology: RoutePhasingSplit Genetic Algorithm (RPS-GA)

The authors propose a specialized Genetic Algorithm (GA) framework designed to handle the unique coupling of routing, phasing, and splitting in orbital mechanics.

A. Chromosome Representation: The RPS Triplet

Instead of standard permutation encodings, the authors introduce a Route-Phasing-Split (RPS) triplet chromosome that encodes three distinct components in a unified structure:

Route ( $R$ ): A global permutation of all $N$ tasks (target satellites) defining the execution order.
Phasing ( $n$ ): A vector of integers specifying the number of phasing revolutions (waiting cycles) required for each transition between tasks.
Split ( $L$ ): A vector defining the lengths of segments in the global route, effectively partitioning the tasks among $M$ different SSCs.

This structure allows the algorithm to optimize task ordering, synchronization timing, and resource allocation simultaneously.

B. Constraint-Aware Fitness Function

To manage the strict feasibility requirements, a specialized fitness function is used:

Objective: Minimize total mission $\Delta V$ .
Penalty Structure:
- Aggregate Penalty: Penalizes the sum of violations across all SSCs.
- Imbalance Penalty: Specifically discourages solutions where a single SSC bears the majority of violations (preventing the "shifting" of infeasibility between agents).
- Binary Infeasibility Penalty: A large penalty ( $\kappa$ ) is applied if any constraint is violated. This ensures that feasible solutions are always ranked higher than infeasible ones, regardless of how low the infeasible solution's $\Delta V$ might be.
Forward Invariance: Once a feasible solution is found, the fitness function ensures it remains the "best" candidate, preventing the algorithm from regressing to infeasible states with lower raw costs.

C. Specialized Genetic Operators

Standard GA operators often destroy the delicate phasing and route-block structures required for orbital feasibility. The paper introduces Split-Aware operators:

Route-Block Crossover (RBC): Exchanges entire route blocks (segments assigned to specific SSCs) between parents while preserving the internal task order and associated phasing data. This maintains the integrity of feasible multi-servicer partitions.
Hybrid Order-Preserving Crossover (HOPC): Used for finer-grained recombination within specific routes.
Adaptive Mutation: Applies mutations to the Route, Phasing, and Split components independently. Infeasible chromosomes receive higher mutation rates to encourage escape from local minima.
Regret-Based Large Neighborhood Search (LNS): Embedded as a local intensification step. It uses a "destroy-and-repair" mechanism (removing high-cost tasks and re-inserting them based on 2-regret heuristics) and a rotation neighborhood search to fine-tune phasing integers, exploiting favorable orbital windows.

D. Stagnation Control

To prevent premature convergence in the highly constrained search space, the algorithm monitors population compression. If stagnation is detected, it injects diversity by replacing a portion of the population with structurally distinct but contextually related individuals, rather than random re-initialization.

3. Key Contributions

Novel RPS Triplet Chromosome: A unified encoding scheme that simultaneously represents route sequence, phasing rotations, and multi-agent splits, enabling the GA to explore the coupled decision space effectively.
Forward-Invariant Feasibility Mechanism: A penalty-based fitness design that guarantees the preservation of the best-found feasible solution across generations, preventing the search from drifting into infeasible regions.
Split-Aware Evolutionary Operators: Genetic operators (RBC, HOPC) specifically designed to respect orbital route blocks and phasing coherence, reducing the generation of infeasible offspring.
Significant $\Delta V$ Reduction: Demonstrated a substantial improvement in fuel efficiency over state-of-the-art baselines.

4. Experimental Results

The method was tested on a representative GEO servicing scenario involving 2 SSCs and 14 target satellites (including Beidou, Fengyun, and Tianlian satellites) over a 30-day horizon.

Performance Comparison:
- Baseline (LNS-AGA): Total $\Delta V$ = 1956.36 m/s.
- Proposed (RPS-GA): Total $\Delta V$ = 1476.32 m/s.
- Improvement: A 24.5% reduction in total fuel consumption.
Feasibility:
- The RPS-GA consistently produced feasible solutions in 100 independent runs.
- Both SSCs operated within their individual $\Delta V$ limits (1000 m/s) and the 720-hour mission deadline.
- Ablation Study: Removing the binary infeasibility penalty caused the algorithm to oscillate between feasible and infeasible states and converge to suboptimal infeasible solutions, validating the necessity of the proposed fitness design.

5. Significance

This paper makes a significant contribution to the field of space mission planning by addressing the non-stationary nature of orbital routing. Traditional Vehicle Routing Problem (VRP) heuristics fail in GEO because they assume static travel costs. By explicitly integrating phasing rotations and route splitting into the genetic encoding and operator design, the RPS-GA successfully navigates the complex, time-dependent constraints of orbital mechanics.

The demonstrated 24.5% fuel saving is critical for the economic viability of future on-orbit servicing missions, as it directly translates to extended mission lifetimes, the ability to service more satellites with the same fleet, or reduced launch mass requirements. The framework provides a robust, scalable approach for planning complex, multi-agent missions in dynamic orbital environments.