In interplanetary space missions, it is convenient to have a second departure opportunity in case the first is missed. Two distinct approaches to minimizing the maximum of the two Delta-V budgets of such a trajectory pair, are developed. The first (‘a priori’) approach optimizes the variables of both trajectories at once. The second (‘a posteriori’) approach first minimizes Delta-V budgets for a range of discrete departure epochs, and then selects the pair of which the highest Delta-V is minimum. Furthermore, five different pruning and biasing methods are developed, these prove critical for computational efficiency (number of objective function evaluations). Application to three different gravity-assist (and deep space maneuver) trajectories to Saturn, reveals that the a priori approach is more computationally efficient on a trajectory with few variables (3) and that the a posteriori approach is more computationally efficient on a trajectory with many variables (22).