Dataset of Keplerian TSP Instances from ESA's ACT

A collection of instances for the Keplerian Traveling Salesperson Problem, which requires finding a trajectory of minimum $\Delta V$ that rendezvous with multiple celestial bodies. The instances are designed to be instructive and with an incremental complexity so that researchers can test their solution methods at different levels.

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 the mission's starting and ending times (these are contained in the file 0_instances.tar).

For each of these continuous instances (see our paper for details), we also provide instances for which we already defined a discrete time grid and pre-computed the cost of all body-to-body transfers. Thus, these instances are Set Traveling Salesperson Problem instances. They can be solved also without any background in celestial mechanics. The files are stored in 1_time-expanded-networks.tar and contain multiple networks for different grids for every file in 0_instances.tar.

The file formats are described below. For more information about the benchmark set, and the solutions currently found for each instance, visit the project website.

If you find these problems useful please refer and quote the following paper:

@inproceedings{Bannach2024On,

address = {Milan, Italy},

author = {Bannach, Max and Acciarini, Giacomo and Izzo, Dario},

booktitle = {International {Astronautical} {Congress} ({IAC})},

year = {2024},

title = {On the {Keplerian} {TSP} and {VRP}: Benchmarks and {Encoding} {Techniques}}

File Format for the Keplerian Traveling Salesperson Problem

The default format is .ktsp, which follows a standard DIMACS - like format consisting of three line types:

- p-line: defines the problem parameters and has the form p ktsp , where is the standard gravitational parameter of a central massive body, and and define the mission start and end time, respectively.

- c-lines: have the form c and have no semantics.

- body: describe a celestial object around the central massive object via its 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 and , respectively.

Units

The units in .ktsp files are as follows:

- the gravitational parameter mu is given in m^3/s^2

- t_min and t_max are given in MJD

- 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 , where is the number of bodies, the maximum number of time points for everybody, and m the number of arcs in the network.

- c-lines: have the form c and have no semantics.

- arcs: describe a transfer in the network and have the form and the semantic that there is a transfer from the body  at time to body at time of cost .

In a time-expanded network, the bodies (e.g., and 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., 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.