Stochastic Optimisation for Complex Mixed-Integer Programming Problems in Asteroid Tour Missions

Abstract

Deep space exploration is key to understand the origin of our Solar System and address the Earth impact risk. Space Trajectory Design (STD) has evolved and incremented in complexity due to the interest within the space community to explore multiple celestial bodies in a single mission. This thesis focuses on an Asteroid Tour Trajectory in the context of the CASTAway mission. CASTAway is a mission proposal for European Space Agency’s 5th call of medium-size missions to explore the Asteroid Main Belt.

The objective is not to find the global optima but find feasible sequences of asteroid fly-bys, as per feasible tours of 12 asteroids of a total Δv of less than 9 km/s is meant. The complexity of the problem is given by the large number of possible permutations of 12-asteroid tour solutions – even with a reduced catalogue of 158 asteroids – and because of being a Mixed-Integer Non-Linear Programming (MINLP) problem. Because of this, metaheuristics are used to tackle the problem. A novel problem modelling that achieves uniqueness on the cost paths of the Search Space and a novel ACO solver is presented, with the general objective for the whole CASTPath project of finding a robust low computational heuristic. Due to the scientific interest on having diversity in the sequences, a similarity measurement tool is also developed.

Several test cases with different ACO tuning parameters are run on a High Performance Computer. Results show that this algorithm outperforms the previous heuristics on CASTPath obtaining the lowest Δv (7.27 km/s) achieved by an heuristic and finding multiple feasible sequences (97 in 1 h). Moreover, the new problem modelling has allowed within the research group, to find the global optima (6.98 km/s) for this asteroid catalogue by Dynamic Programming.