Solving Combinatorial Space-Routing Problems Using Mixed-Integer Linear Problem Solvers

Abstract

With the development of space research into novel areas, new complex problems arise. The interest in solving space routing problems considering large numbers of targets has recently grown. This paper proposes a novel method to solve the optimal trajectory in such combinatorial space routing problems. This paper focuses on a global optimisation algorithm implemented to solve the problem posed in the 4th Global Trajectory Optimisation Com- petition (GTOC4). The solution is a trajectory of multiple legs, where each leg links two targets and has a specific flight time. To enable the use of the powerful mixed-integer linear problem solver software, Solving Constraint Integer Programs (SCIP), the routing problem concerned with visiting as many target bodies with a predetermined fuel and time budget is split into linear sub-problems. The Fixed Budget sub-problem selects a subset of the given set of targets. The Full Tour sub-problem orders the targets in the subset, and the Fixed Tour sub-problem optimises the flight time for every leg of the given trajectory to find the solution with the lowest total fuel consumption. Each of these sub-problems is formulated in a linear form and is solved using SCIP. The global optimisation algorithm evolves a population where every individual exists of a set of initial guesses for the time of flight values. Analysis shows that initialising this population with a mix of randomly generated individuals and individuals containing a constant value for all entries leads to the fastest convergence towards the optimal solution. In a population of 20, seeding ten individuals is found to be optimal. It is also found that the algorithm performance can be further increased by evolving individuals with infeasible solutions instead of iterating them until a feasible solution is found and eliminating the Full Tour sub-problem. These simplifications allow for an increase in the cost budget multiplier, which leads to finding better objective values without further increasing computational time. The best-performing setup, which uses a cost budget multiplier of 10, can find the optimal solution to the test problem in 100% of the runs, on average in 9 iterations, with a computation time of 5.82 seconds per evaluation. The results show that the global optimisation algorithm produces results that closely match known results for GTOC4 consistently and accurately.