Instances of Orbit Slot Allocation Problems modeled as Directed Path Allocation Problems (DPAP)

Contents

This repository contains instances of Orbit Slot Allocation Problems modeled as Directed Path Allocation Problems (DPAP), defined in [1]. These instances represent orbit slot allocation problems encoded as V-DPAP (Vertex-Constrained Directed Path Allocation Problem) or R-DPAP (Resource-Constrained Directed Path Allocation Problem).

Each instance is provided as set of files, following the provided schema:

One instance__Graph_Request__.dot file per request, representing a graph, using the dot language, where is the instance number, is the id of the user emitting the request, and is the unique id of the request/graph. Each such file lists a set of vertices and and set of weighted edges (using the label property of the dot language to set the weights). In the current set of instances, there are 8 requests per instance (2 requests per user, with 4 users).

One instance_.inc file, listing the incompabilities between vertices, with one set of incompatible vertices per row.

Files are contained in subdirectories following the ___ pattern, where is the number of satellites per orbit plane (2, 4, 8, 16), is the number of requests per user (2 only in this dataset), satisfaction mode of the request (full or partial), and is the type of problem model used to encode the orbit slot allocation problems (vdpap or rdpap).

We redirect to the referenced paper for more details on the DPAP, V-DPAP and R-DPAP models.

Acknowledgements

This work has been performed with the support of the French government in the context of the "Programme d'Invertissements d'Avenir", namely by the BPI PSPC LiChIE project (Lion Chaine Image Elargie), coordinated by Airbus Defence and Space.

References

[1] S. Roussel, G. Picard, C. Pralet and S. Maqrot. Conflicting Bundle Allocation with Preferences in Weighted Directed Acyclic Graphs: Application to Orbit Slot Allocation Problems, in MDPI Systems, Special Issue on Frontiers in Practical Applications of Agents, Multi-Agent Systems and Simulating Complex Systems, 2023.