Optimization of interplanetary space mission trajectories have been a long standing challenge. Here a novel approach is presented that considers several aspects of the space mission simultaneously as many-objective problem. Such problem is then solved by a decomposition approach in combination with a (massive) parallelization framework employing instances of Ant Colony Optimization algorithms. Numerical results show that the here presented approach has advantages over a classical weighted sum approach and is very suitable to efficiently exploit massive parallelization.