Humanity has long been fascinated with celestial bodies and space travel. In the current work, we investigate a novel approach to efficiently travel between planets. Specifically, we use a genetic algorithm to find a near optimal path between planets that are in a circular motion with different angular velocities under the gravitational attraction of a star. We develop mathematical expressions to find both the travel distance and the trajectory angle of the spaceship for the orbiting planets. Using derived analytical expressions derived and a carefully chosen bimodal fitness function, we demonstrate that our genetic algorithm rapidly converges to a near optimal solution for the shortest path between the planets. The experimental results show that our genetic algorithm converges consistently faster than an algorithm based on a unimodal fitness function. Further, the experimental results indicate the hypothesis that our algorithm is many orders of magnitude faster than an enumeration-based technique, while providing nearly as accurate results. We envision that, in the future, the results of our work could be used to program a space probe to efficiently travel between the faraway planets of a newly discovered solar system, and to collect scientific data from deep space that could provide answers to profound questions about our universe. In addition, our results can be put into use immediately for mining asteroids for natural resources that are rare on Earth, and to eliminate space junk that pose danger to space travel.