Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

User Tools

Site Tools


research:msp

The Multistage Shortest Path Problem

Here you find the MSP instances we use in our publications, namely Multistage Shortest Path: Instances and Practical Evaluation (SAND 2023).

General Format

Each *.gml file contains one multistage graph instance. The files are ASCII encoded using the Graph Modelling Language (Specification). Each edge has a list of subgraph attributes, where a line "subgraph i" encodes that the edge is present in stage \(i\); the edge's label encodes the vector of weights (one value for each stage). The terminal nodes' labels contain the substring "source" or "target". In the geometric instances, the nodes' labels also contain the vector of 2D-coordinates for each stage. A filenames' suffix instId_s-t.gml hints at the query \((s,t)\). A real-world instance's filename instId.h.(f,l)_s-t.gml also encodes the selected resolution \(h\) and the first and last stage (\(f\), or \(\ell\), respecitvely) in consideration.

A file instId_algoId.sol contains the solution of the instance instId output by algorithm with ID algoId, where the \(i\)th line contains the ASCII encoded (unordered) edges of a shortest s-t-path for stage \(G_i\).

Two-stage runs sol_two.zip (68.2 MB)
Multi-stage runs sol_multi.zip (783 MB)

The corresponding algorithm IDs are interpreted slightly differently depending on the number of considered stages:

algoId two-stage runs multi-stage runs
\(\texttt1\)\(\texttt{ILP}\)\(\texttt{ILP}\)
\(\texttt2\)\(\texttt{A}\)\(\texttt{B-A}\)
\(\texttt3\)\(\texttt{Ad}\)\(\texttt{B-Ad}\)
\(\texttt4\)\(\texttt{A5}\)\(\texttt{B-A5}\)
\(\texttt5\)\(\texttt{G}\)\(\texttt{B-G}\)
\(\texttt6\)\(\texttt{Gd}\)\(\texttt{B-Gd}\)
\(\texttt7\)\(\texttt{Gi}\)\(\texttt{B-Gi}\)
\(\texttt8\)\(\texttt{-}\)\(\texttt{M-G}\)
research/msp.txt · Last modified: 2023/06/13 11:22 by troost