Gravity-Assist Trajectory Sequence Design
NP-Hard Combinatorial Optimisation · ESA GASP Algorithm
Interplanetary missions exploit planetary gravity assists to reach distant targets with far less propellant than a direct transfer. Choosing the optimal sequence of flyby bodies — which planets to visit, in what order, and when — is a combinatorial optimisation problem proven to be NP-hard.
Science Context
How gravity assists reshape interplanetary mission design
A gravity assist (or flyby) uses a planet's gravitational field to change a spacecraft's velocity and direction without expending propellant. By carefully timing the encounter geometry, mission designers can gain (or shed) kilometres per second of velocity for free — energy borrowed from the planet's orbital momentum.
The Cassini mission to Saturn (launched 1997) used the sequence Venus → Venus → Earth → Jupiter → Saturn (VVEJGA), accumulating 16.6 km/s of free velocity change over 7 years. Without gravity assists, a direct transfer would have required roughly 15.7 km/s of propulsive Δv — far beyond any chemical rocket's capability for the 5,700 kg spacecraft.
The sequence order matters enormously. With 8 candidate planets and up to 6 flyby legs per trajectory, and continuous launch windows spanning a 10-year epoch, the combinatorial search space exceeds 1012 candidate trajectories before even considering the continuous timing variables.
The Problem
Minimising propellant cost over an astronomical search space
The gravity-assist sequence design problem asks: given a launch body (Earth), a target body (e.g. Saturn, Jupiter), and a set of candidate flyby planets, find the ordered sequence of planetary encounters plus the departure epoch and leg transfer times that minimise the total propulsive cost Δv.
Decision variables include the discrete sequence of flyby bodies (b1, b2, …, bn), the continuous departure epoch t0, and the arrival/departure times at each encounter. The objective is to minimise total Δv: launch injection, deep-space manoeuvres between legs, and final orbit insertion.
Izzo et al. (2007) proved this problem NP-hard via reduction from the Travelling Salesman Problem. ESA's GASP algorithm (Gravity Assist Space Pruning) achieves practical tractability by pruning the search space by 6 orders of magnitude, using V-infinity matching constraints and Tisserand graphs to eliminate dynamically infeasible sequences before the expensive Lambert-arc evaluation.
Interactive Solver
Simplified 2D heliocentric patched-conic trajectory explorer
Flyby Sequence Builder
EARTH → ? → JUPITERSupporting Evidence
Key references in gravity-assist trajectory optimisation
References
Interested in combinatorial optimisation?
From trajectory design and resource allocation to scheduling and network flows, mathematical optimisation transforms complex decisions into actionable solutions.