Keplerian TSP
Missions in which a spacecraft needs to match its position and velocity with multiple celestial bodies, so-called multi-rendezvous missions, are becoming increasingly relevant in near-term scenarios such as active debris removal and futuristic ideas such as asteroid mining. The underlying routing and scheduling problems were, for this reason, the topic of multiple incarnations of the Global Trajectory Optimization Competition (GTOC), which led to various hand-crafted methods that mix domain-specific intuition together with several meta-heuristics.
Theoretical Sound Guarantees with Constrained Optimization
These heuristic-based approaches have the huge advantage of being reasonable fast, while they have the disadvantage of not providing any theoretical guarantee of the quality of the result whatsoever. Constrained Optimization Problems (COP) deals with the assignment of discrete values to a set of variables in order to maximize or minimize a given function, i.e., to find the optimal solution in a search problem. The cost of finding optimal solutions is, of course, that these techniques are slower than their heuristic counterparts. However, thanks to the combined efforts of multiple contributing fields and intensive algorithmic engineering, amazingly fast tools for relevant subfields of COP are available, for instance for Integer Linear Programming (e.g. Gurobi or HiGHS) or for Maximum Satisfaction (e.g., MaxHS or Open-WBO).
The Keplerian Traveling Salesperson Problem
One of the poster-child problems of combinatorial optimization is the Traveling Salesperson Problem (TSP), which bears a high similarity to the multi-rendezvous problem. The main difference is that in the latter we deal with objects on orbits instead of cities, i.e., we deal with a highly dynamic version of the problem. This similarity was already observed in the past [1,2], but this initial research was ad-hoc, i.e., specific instances were mapped to very generic variants of TSP. The first part of the project is the development of an overreaching and unifying formal definition of a TSP variant that naturally captures multi-rendezvous mission. We dub this problem Keplerian TSP.
The Keplerian TSP is specifically challenging compared to its classical counterpart as it simultaneously offers a distinct combinatorial aspect (ordering and choosing the rendezvous), and a continuous optimization problem (finding transfers between celestial bodies). Typically, those two parts are dealt separately, leading to potentially-suboptimal mission designs. The second part of this project explores mathematical sound formulations of the Keplerian TSP in various constrained optimization frameworks such as integer linear programming (ILP), quadratic programming (QP), or maximum satisfaction (MaxSAT).
Objectives
The project has two main objectives: to formulate a unified framework to describe early-stage mission design problems involving multiple rendezvous (such as that of GTOC 12) as combinatorial optimization problems, and to leverage available exact tools to solve them. In particular, the goal is not to necessarily have the fastest algorithm possible, but the focus lies on providing theoretical guarantees on the quality of the found solutions. The primary direction of this project is the use of (integer) linear programming techniques, i.e., optimization problems in which the goal is to optimize a linear function over integer variables fulfilling a set of linear inequalities. However, the project is not limited to ILPs, we also explore alternative routes such as the use of quadratic programs, or tools from automated reasoning such as MaxSAT.
By linking problems from the early-stage design of multi-rendezvous missions with techniques from operations research and automated reasoning, this project intends to build new interdisciplinary bridges while powering research and cross-fertilization.
Benchmark Set
Within this project, a comprehensive benchmark set has been created and made available to the scientific community. This benchmark set is divided into two categories: the Asteroid Belt and Jupiter's Moons. In each category we provide various instances in the form of a set of bodies with a starting and end time of the mission. For each of these instances, we also provide instances to which we already added a time grid and computed the cost of all relevant transfers. These instances are, thus, Set Traveling Salesperson Problem instances and can be solved without any background in celestial mechanics.
File Format for the Keplerian Traveling Salesperson Problem
The default format is .ktsp, which follows a standard
DIMACS like
format consisting out of three lines types:
- p-line: Defines the problem parameters and has the form
p ktsp <t_min> <t_max> <mu>, where<mu>is the standard gravitational parameter of a central massive body, and<t_min>and<t_max>define the mission start and end time, respectively. - c-lines: Have the form
c <message>and have no semantic. - body: Describe a celestial object around the central massive object via it's cartesian position and velocity at the mission start time.
Every .ktsp file contains exactly one p-line that appears
before any line that is not a c-line. The body lines
define an ordered set of celestial objects, i.e., the first body line defines the first object, the second the second, and so on. The mission is assumed to start and end at the first body at time <t_min> and <t_max>, respectively.
Units
The units in .ktsp files are as follows:
- the gravitational parameter
muis given in m^3/s^2 t_minandt_maxare given in MJD- the the cartesian positions are given in m
- the cartesian velocities are given in m/s
File Format for Time-Expanded Networks
Time-expanded networks are also stored in a DIMACS like format
.ektsp. These files contain three line types:
- p-line: Defines the problem parameters and has the form
p ektsp <n> <k> <m>, where<n>is the number of bodies,<k>the maximum number of time points for every body, andmthe number of arcs in the network. - c-lines: Have the form
c <message>and have no semantic. - arcs: Describe a transfer in the network and have the form
<alpha1> <t1> <alpha2> <t2> <dv>and the semantic that there is a transfer from body<alpha1>at time<t1>to body<alpha2>at time<t2>of cost<dv>.
In a time-expanded network, the bodies (e.g., <alpha1> and <alpha2>
above) are numbers in 0..n-1 with 0 being the depot (where the
mission starts and ends). Time points are numbers in 0..k-1,
i.e., there is no concept of time other than an enumeration of time
points. The cost of an arc, i.e., <dv> above, can be considered
without a unit as well. A .ektsp file, thus, defines a directed
nxk grid graph, in which a tour from (0,0) to (0,k-1) needs to be
found that visits at least one (alpha,t) for every alpha in 0..n-1.
Asteroid Belt Instance with 5 Asteroids
The Asteroid Belt category contains benchmark instances that detail various asteroids within the belt between Mars and Jupiter. The first instance (asteroids_05.ktsp) in this category consists of a cluster of five asteroids. The benchmark set contains six time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
asteroids_05_06.ektsp | 5 | 6 | 12318.13 | 12318.13 | 0.00 |
asteroids_05_11.ektsp | 5 | 11 | 10938.92 | 10938.92 | 0.00 |
asteroids_05_21.ektsp | 5 | 21 | 10533.94 | 10533.94 | 0.00 |
asteroids_05_41.ektsp | 5 | 41 | 10459.16 | 10459.16 | 0.00 |
asteroids_05_81.ektsp | 5 | 81 | 10431.62 | 10431.62 | 0.00 |
asteroids_05_161.ektsp | 5 | 161 | 10431.60 | 10431.60 | 0.00 |
Asteroid Belt Instance with 10 Asteroids
The Asteroid Belt category contains benchmark instances that detail various asteroids within the belt between Mars and Jupiter. The second instance (asteroids_10.ktsp) in this category consists of a cluster of ten asteroids. The benchmark set contains five time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
asteroids_10_11.ektsp | 10 | 11 | 38734.94 | 38734.94 | 0.00 |
asteroids_10_21.ektsp | 10 | 21 | 28173.63 | 28173.63 | 0.00 |
asteroids_10_41.ektsp | 10 | 41 | 25290.47 | 25290.47 | 0.00 |
asteroids_10_81.ektsp | 10 | 81 | 24850.79 | 24850.79 | 0.00 |
asteroids_10_161.ektsp | 10 | 161 | 24718.40 | 24718.40 | 0.00 |
Asteroid Belt Instance with 20 Asteroids
The Asteroid Belt category contains benchmark instances that detail various asteroids within the belt between Mars and Jupiter. The third instance (asteroids_20.ktsp) in this category consists of a cluster of twenty asteroids. The benchmark set contains five time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
asteroids_20_21.ektsp | 20 | 21 | 118104.77 | 118104.77 | 0.00 |
asteroids_20_41.ektsp | 20 | 41 | 95033.47 | 95033.47 | 0.00 |
asteroids_20_81.ektsp | 20 | 81 | 92544.52 | 92544.52 | 0.00 |
asteroids_20_161.ektsp | 20 | 161 | 69629.40 | 91760.92 | 24.12 |
Asteroid Belt Instance with 40 Asteroids
The Asteroid Belt category contains benchmark instances that detail various asteroids within the belt between Mars and Jupiter. The fourth instance (asteroids_40.ktsp) in this category consists of a cluster of forty asteroids. The benchmark set contains three time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
asteroids_40_41.ektsp | 40 | 41 | 391076.40 | 391076.40 | 0.00 |
asteroids_40_81.ektsp | 40 | 81 | 265034.09 | 316923.28 | 16.37 |
asteroids_40_161.ektsp | 40 | 161 | 220652.06 | 316923.28 | 30.38 |
Asteroid Belt Instance with 80 Asteroids
The Asteroid Belt category contains benchmark instances that detail various asteroids within the belt between Mars and Jupiter. The last instance (asteroids_80.ktsp) in this category consists of a cluster of eighty asteroids. The benchmark set contains two time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
asteroids_80_81.ektsp | 80 | 81 | 1134954.64 | 1583172.32 | 28.31 |
asteroids_80_161.ektsp | 80 | 161 | 762357.31 | 1420767.83 | 46.34 |
Jupiter's Moons Instances with 4 Bodies
The Jupiter's Moons category includes benchmark instances focused on the major moons orbiting Jupiter. The first instance (jovianmoons_04.ktsp) in this category consists of four regular moons. The benchmark set contains six time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
jovianmoons_04_06.ektsp | 4 | 6 | 38705.57 | 38705.57 | 0.00 |
jovianmoons_04_11.ektsp | 4 | 11 | 20096.59 | 20096.59 | 0.00 |
jovianmoons_04_21.ektsp | 4 | 21 | 18618.00 | 18618.00 | 0.00 |
jovianmoons_04_41.ektsp | 4 | 41 | 17841.49 | 17841.49 | 0.00 |
jovianmoons_04_81.ektsp | 4 | 81 | 17623.63 | 17623.63 | 0.00 |
jovianmoons_04_161.ektsp | 4 | 161 | 17430.97 | 17430.97 | 0.00 |
Jupiter's Moons Instances with 10 Bodies
The Jupiter's Moons category includes benchmark instances focused on the major moons orbiting Jupiter. The second instance (jovianmoons_10.ktsp) in this category consists of ten moons. The benchmark set contains five time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
jovianmoons_10_11.ektsp | 10 | 11 | 19871.59 | 19871.59 | 0.00 |
jovianmoons_10_21.ektsp | 10 | 21 | 16268.25 | 16268.25 | 0.00 |
jovianmoons_10_41.ektsp | 10 | 41 | 15611.09 | 15611.09 | 0.00 |
jovianmoons_10_81.ektsp | 10 | 81 | 15443.86 | 15443.86 | 0.00 |
jovianmoons_10_161.ektsp | 10 | 161 | 15373.88 | 15373.88 | 0.00 |
Jupiter's Moons Instances with 20 Bodies
The Jupiter's Moons category includes benchmark instances focused on the major moons orbiting Jupiter. The third instance (jovianmoons_20.ktsp) in this category consists of twenty moons. The benchmark set contains four time-expanded networks for this instance, described in the following table (the lower bound indicates a minimum value every solution must have, and the upper bound is the currently best known solution; if both bounds match, the upper bound is the optimal solution for this time-expanded network):
| Instance Name | Number of Bodies | Number of Grid Points | Lower Bound | Upper Bound | Gap (%) |
|---|---|---|---|---|---|
jovianmoons_20_21.ektsp | 20 | 21 | 50283.81 | 50283.81 | 0.00 |
jovianmoons_20_41.ektsp | 20 | 41 | 46505.23 | 46505.23 | 0.00 |
jovianmoons_20_81.ektsp | 20 | 81 | 44797.84 | 44797.84 | 0.00 |
jovianmoons_20_161.ektsp | 20 | 161 | 38737.21 | 44340.50 | 12.64 |
Solution Files
Solution <foo>.sol, files for time-expanded networks may contain c-lines for comments as the
other files. To represent the solution, they contain the arcs of the
solution in the form <alpha1> <t1> <alpha2> <t2> (i.e., as in .ektsp files
but without the dv. The order of the arcs can be arbitary.
Should you find a new solution to one of the instances from above, please provide it in this format.
References
[1] Federici, Lorenzo, Alessandro Zavoli, and Guido Colasurdo
A time-dependent TSP formulation for the design of an active debris removal mission using simulated annealing
arXiv preprint arXiv:1909.10427 (2019).
[2] Federici, Lorenzo, Alessandro Zavoli, and Guido Colasurdo
Impulsive multi-rendezvous trajectory design an optimization.
8th European Conference for Aeronautics and Space Sciences (EUCASS), Madrid, Spain (2019).