Inspired by the recent 11th Global Trajectory Optimisation Competition, this paper presents the asteroid routing problem (ARP) as a realistic benchmark of algorithms for expensive bound-constrained black-box optimization in permutation space. Given a set of asteroids’ orbits and a departure epoch, the goal of the ARP is to find the optimal sequence for visiting the asteroids, starting from Earth’s orbit, in order to minimize both the cost, measured as the sum of the magnitude of velocity changes required to complete the trip, and the time, measured as the time elapsed from the departure epoch until visiting the last asteroid. We provide open-source code for generating instances of arbitrary sizes and evaluating solutions to the problem. As a preliminary analysis, we compare the results of two methods for expensive black-box optimization in permutation spaces, namely, Combinatorial Efficient Global Optimization (CEGO), a Bayesian optimizer based on Gaussian processes, and Unbalanced Mallows Model (UMM), an estimation-of-distribution algorithm based on probabilistic Mallows models. We investigate the best permutation representation for each algorithm, either rank-based or order-based. Moreover, we analyze the effect of providing a good initial solution, generated by a greedy nearest neighbor heuristic, on the performance of the algorithms. The results suggest directions for improvements in the algorithms being compared.

1. 1.

   The trajectory of the second object could also be linear, but this is not of practical interest, because this would end with the object destroyed in the Sun.

2. 2.

   The periapsis is the nearest point of an elliptic orbit to the object in the focus. When the object is the Sun, the periapsis is also called perihelion.

3. 3.

   We previously useda to mean the semi-major axis of an orbit, from now on we will use it to denote the complete orbit of an asteroid.

This work is partially funded by the Universidad de Málaga, Consejería de Economía y Conocimiento de la Junta de Andalucía and FEDER (grant UMA18-FEDERJA-003) and MCIN/AEI/10.13039/501100011033 (grant PID 2020-116727RB-I00). Thanks to the Supercomputing and Bioinnovation Center (SCBI) of the University of Málaga for their provision of computational resources and support. M. López-Ibáñez is a “Beatriz Galindo” Senior Distinguished Researcher (BEAGAL 18/00053) funded by the Spanish Ministry of Science and Innovation (MICINN).

Authors and Affiliations

1. ITIS Software, Universidad de Málaga, Málaga, Spain

   Manuel López-Ibáñez, Francisco Chicano & Rodrigo Gil-Merino

Corresponding author

Correspondence toManuel López-Ibáñez.

Editors and Affiliations

1. Université Le Havre Normandie, Le Havre, France

   Juan Luis Jiménez Laredo

2. Universidad Complutense de Madrid, Madrid, Spain

   J. Ignacio Hidalgo

3. Edinburgh Napier University, Edinburgh, UK

   Kehinde Oluwatoyin Babaagba

Reprints and permissions

© 2022 Springer Nature Switzerland AG

Policies and ethics