Dataset of Keplerian TSP Instances from ESA's ACT
DOI10.5281/zenodo.14850862Zenodo14850862MaRDI QIDQ6696092FDOQ6696092
Dataset published at Zenodo repository.
Giacomo Acciarini, Dario Izzo, Max Bannach
Publication date: 11 February 2025
Copyright license: Creative Commons Attribution 4.0 International
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: theAsteroid BeltandJupiter'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 in1_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 theproject website. If you find these problems useful please refer and quote the followingpaper: @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 standardDIMACS - like format consisting of three line types: -p-line: defines the problem parameters and has the form p ktsp t_min t_max mu, where mu is the standard gravitationalparameter of a central massive body, and t_min and t_max define the missionstart and end time, respectively. -c-lines: have the form c message 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 linesdefine 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 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 n k m, where n is the number of bodies, k the maximum number of time points for everybody, and m the numberof arcs in the network. - c-lines: have the form c message and have no semantics. - 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 the bodyalpha1 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 themission starts and ends). Time points are numbers in 0..k-1,i.e., there is no concept of time other than an enumeration of timepoints. The cost of an arc, i.e., dv above, can be consideredwithout 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 befound that visits at least one (alpha,t) for every alpha in 0..n-1.
This page was built for dataset: Dataset of Keplerian TSP Instances from ESA's ACT
