Abstract
We formalize a Keplerian Travelling Salesperson Problem (ktsp) as a special version of tsp, where the " cities " correspond to objects on Keplerian orbits. In this context, the salesperson is modeled as a " spacecraft " tasked with achieving rendezvous (matching position and velocity) with each orbital object while minimizing the required Δí µí±£ from the propulsion system, subject to operational constraints such as time-of-flight limits. Unlike the classical tsp, which has been extensively studied, the Keplerian version introduces unique complexities that are relevant to real-world scenarios. These complexities arise from the dynamic movement of orbital objects and the resulting changes in transfer costs between them. The Keplerian Vehicle Routing Problem (kvrp) and Keplerian low-thrust Travelling Salesperson Problem (ktsp-lt) are also introduced, extending this framework further to scenarios involving multiple spacecraft that must collaboratively visit designated targets as well as spacecraft equipped with a low-thrust propulsion system. The specific problems modelled are related to design tasks that have gained prominence in the past decade as advanced trajectory optimization challenges, particularly highlighted in the Global Trajectory Optimization Competition series. These problems have been instrumental in automating the design of multi-rendezvous trajectories in asteroid belt missions, addressing challenges such as mission target selection. They have also been applied to plan active debris removal missions, design future asteroid mining strategies as well as ivestigate on-orbit servicing concepts. In this work, we explore different encodings of these problems into well-known combinatorial optimization tasks, focusing on Integer Linear Programming (ilp) formulations. We provide and study a umber of initial instances of various complexity. A key aspect of our work is the detailed process of unrolling time, which is critical for translating dynamic problems like ktsp into discrete optimization tasks. We also propose a possible strategy to mitigate the complexity involved in the resulting time-indexed formulations of ILPs: Interval-based Dynamic Discretization Discovery. We conclude with a preliminary experimental evaluation, comparing the performance of various ilp solvers to that of the beam search approach, commonly used to incrementally build mission plans in these cases.