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.

Benchmark set	Instances
geom	geom_instances.zip (570.7 MB)
grid	grid_instances.zip (566.5 MB)
hybr	hybr_instances.zip (4.87 GB)
real	real_instances.zip (8.8 MB)

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}\)