An Iterative Optimization Algorithm for Planning Spacecraft Pathways Through Asteroids

In this article, we explore the use of meta-heuristic algorithms for costly black-box permutation optimization problems. These combinatorial problems are defined by solution spaces that consist of permutations of elements, with an objective function that lacks a closed mathematical representation and is expensive to evaluate. The focus of our investigation is the Asteroid Routing Problem (ARP), which seeks to determine the optimal sequence of asteroids to be visited by a spacecraft while minimizing energy consumption and travel time. Specifically, we assess the performance of a simple algorithm called FAT-RLS, which primarily relies on a randomized local search approach, enhanced with a tabu structure and a mechanism to adjust the perturbation strength. We conducted a series of experiments on well-established instances of the ARP to compare the effectiveness of FAT-RLS against two recognized meta-heuristics designed for this problem, namely, UMM and CEGO. Experiments were conducted in both uninformed and informed settings, where the meta-heuristics are initialized with a specifically designed constructive algorithm for the ARP. The results demonstrate that FAT-RLS is consistently superior to UMM, while there is no conclusive evidence for the comparison with CEGO, though the FAT-RLS results seem slightly better.