Asteroid billiard: most asteroid flybys before a rendezvous (GTOC4)

Fly an electric-propulsion spacecraft past as many near-Earth asteroids as possible in ten years, then end with a rendezvous at one more. The problem of the fourth Global Trajectory Optimisation Competition (2009) is a low-thrust cousin of the travelling-salesman problem: the hard part is choosing a long sequence of reachable asteroids from a list of 1436.

Task

Asteroids: 1436 near-Earth asteroids with Keplerian elements in the heliocentric J2000 ecliptic frame, given in the statement's data file; Earth's orbit and all constants are also given.
Launch: from Earth in the years 2015 to 2025, with hyperbolic excess speed of up to 4.0 km/s in any direction; initial mass 1500 kg, dry mass 500 kg.
Propulsion: specific impulse 3000 s, thrust from 0 to 0.135 N in any direction, independent of the distance from the Sun.
Dynamics: two-body motion about the Sun ( $\mu=1.32712440018\times10^{11}\ \mathrm{km^3/s^2}$ ) plus thrust; no gravity assists.
Encounters: a flyby matches the asteroid's position; the final rendezvous matches position and velocity, within 1000 km and 1 m/s. Each asteroid is visited at most once, and the rendezvous asteroid must not have been flown by before. The mission lasts at most 10 years from launch to rendezvous, and the final mass $m_f$ must be at least 500 kg.

The score is the number of asteroids flown by before the rendezvous,

J=\sum_{j=1}^{1436}\alpha_j,\qquad \alpha_j\in\{0,1\},

where $\alpha_j=1$ if asteroid $j$ was flown by. Higher is better; ties are broken by the larger final mass $m_f$ .

Background

GTOC4 was organized by Régis Bertrand, Richard Epenoy and Benoît Meyssignac of CNES, winners of the third edition, and released on 2 March 2009 with four weeks to solve it. Before this edition there was no agreement on how many asteroids a low-thrust mission could encounter; the portal describes the winning count of 44 in ten years as a positive surprise. Because the dynamics use fixed conics and all data are given, any new tour can be checked exactly against the original rules; later work on choosing long target sequences has used it as a test case (Grigoriev and Zapletin, 2013).

Data and evaluation

Instance: one fixed problem: the problem statement and its asteroid file.
Evaluation: there is no public verifier. A check must re-integrate the submitted trajectory, given at one-day steps and at every encounter as the statement requires, confirm each flyby and the rendezvous within the tolerances, and recount $J$ .
Hardware: none assumed; the score does not depend on run time.

What is known

Final ranking (GTOC portal): Moscow State University, led by Ilia Grigoriev, won with $J=44$ and $m_f=553.46$ kg, ending at asteroid 2000 SZ162. The Aerospace Corporation also reached 44 flybys with 516.83 kg, and ESA's Advanced Concepts Team was third with 42.
A team that reported 54 flybys was not ranked because of major constraint violations.
The winning team later published its method for choosing promising asteroid sequences for this problem (Grigoriev and Zapletin, 2013).
Unverified later claims: the page of Ingo Althöfer's group at the University of Jena shows tours with 46 flybys (2015) and, by Dietmar Wolz, 47 (September 2017) and 49 (April 2018), as videos with details on request (page). Zhang et al. (2025, unrefereed preprint) re-optimized that 49-flyby sequence and list every flyby, ending the rendezvous with 519.9 kg. None of these has been checked by the organizers or in a refereed paper.

What would count as progress

A tour with more than 44 flybys, with a full trajectory file that passes an independent re-integration; that would be the first verified improvement, and 50 or more would beat every claim.
An open-source verifier for GTOC4 trajectories, validated on a published solution.
An upper bound on $J$ , for example from a relaxation of the sequencing problem, to show how far 44 is from the best possible.

References

R. Bertrand, R. Epenoy, B. Meyssignac. Problem description for the 4th Global Trajectory Optimisation Competition. CNES, 2009. Archived PDF
GTOC4 final ranking. Archived PDF
I. S. Grigoriev, M. P. Zapletin. Choosing promising sequences of asteroids. Automation and Remote Control 74, 1284–1296 (2013). doi:10.1134/S0005117913080055
Z. Zhang, X. Guo, D. Wu, H. Baoyin, J. Li, F. Topputo. Global optimality in multi-flyby asteroid trajectory optimization: theory and application techniques. 2025. arXiv:2508.02904

Source

Imported from GTOC Portal, GTOC 4 – Asteroids billiard, curated by the ESA Advanced Concepts Team. The competition closed on 30 March 2009; the problem stays public and is used as a benchmark. The portal could not be reached on 2026-10-20, so this write-up relies on an archived copy of the page. The statement above is written in our own words; see the source for the original wording, history and discussion.