Multi-flyby and multi-rendezvous missions are becoming increasingly relevant, with applications in in-orbit servicing and refueling, active debris removal, as well as asteroid observation and mining. Beyond the local task of designing an optimal trajectory between consecutive targets, these missions contain a crucial global component: in which sequence should the targets be encountered in order to optimize the mission objective? This component bears high similarities with the well-known traveling salesperson problem and, thus, is very challenging from a combinatorial point of view. In fact, solving such problems optimally is infeasible already on instances of moderate size.

Common heuristics for solving multi-flyby and multi-rendezvous problems are variants of beam search and ant colony optimization. We focus on the former and observe that, while a beam search aggressively explores a part of the search tree, it discards many trajectories that locally outperform the best solution found by the search. More specifically, a beam search outputs the root-leaf path in the search tree that is optimal within the explored subtree, but not necessarily optimal within the entire tree. The beam search also encounters many other root-leaf paths, which are discarded since they achieve a lower objective value. However, some of these paths may locally outperform the found solution and may therefore be blended into a new path that leaves the explored subtree and outperforms the best solution found.

We propose an automated post-processing procedure, dubbed auto-slicing, that takes all the partial solutions explored by a beam search as input and that tries to combine them into a new, previously unexplored trajectory. This framework integrates three components: expert knowledge (e.g., promising phasing points at which trajectories can be "cut"), machine learning models that evaluate the feasibility of patching trajectory segments under mission constraints, and combinatorial optimization to identify the optimal way to recombine the sliced trajectories.

In this article, we provide the formal foundation of the auto-slicing framework and establish an integer programming formulation based on lazy constraint generation for the combinatorial part. We then demonstrate the effectiveness of auto-slicing on a concrete benchmark: the problem of the 13th Global Trajectory Optimization Competition, which inspired this line of research.  The results highlight the method's ability to generate better multi-flyby trajectories by utilizing intermediate partial solutions discarded by the primary beam search. We conclude with a discussion of further use cases and possible adaptations to other mission profiles.