A Simple yet Effective Algorithm for the Asteroid Routing Problem

In this paper we investigate the application of meta-heuristic algorithms in the context of expensive black-box permutation optimization. These problems are characterized by solution spaces composed of permutations of items, where the objective function is not explicitly defined in a closed mathematical form and is costly to evaluate. The benchmark problem under investigation is the Asteroid Routing Problem (ARP), which aims to determine the optimal order for a spacecraft to visit asteroids, starting from Earth’s orbit, while minimizing both energy consumption and visit time. In particular, we examine the effectiveness of a simple algorithm, namely FAT-RLS, which is mainly based on the randomized local search scheme, equipped with a tabu structure and a mechanism to regulate the perturbation strength. A series of experiments were performed on accepted instances of the ARP in order to compare the effectiveness of FAT-RLS with respect to two established meta-heuristics for the ARP. The results clearly show that FAT-RLS achieves more effective results both considering a black-box setting and an informed setting, where the meta-heuristics are seeded with a purposely designed constructive algorithm for the ARP.