This paper proposes a method for designing Multi-Target Rendezvous (MTR) trajectories, focusing on addressing uncertainties due to observational errors in target spacecraft’s state. By integrating Gaussian Process (GP) surrogate models with Genetic Algorithms (GA), the method predicts spacecraft state evolution post-impulsive maneuvers, reducing computational costs while maintaining prediction accuracy. Applied to MTR missions in geostationary orbit, the GA+GP method’s results closely match real performance, with errors of 0.84% in velocity increment and 0.31% in rendezvous distance. Furthermore, the surrogate-based optimization reduces computational time to one-thousandth compared to pure GA, offering a feasible solution for online trajectory optimization.