Theoretical Computer Science / Theoretische Informatik

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

User Tools

Site Tools


research:mosp

The Multiobjective Shortest Path Problem

Here you find the MOSP instances we use in our publications.

General Format

Each *.graph file contains one instance of the original set. The files are ASCII encoded. Each node has a natural number as id. The first line is a header line and has the format

<number of nodes> <number of arcs> <number of objectives> <start node id> <target node id>

The rest of the file is organized as an adjacency list of the arcs:

<tail node> <head node> <objective 1 value> <objective 2 value> <objective 3 value> …

The graph is to be interpreted as a directed graph, i.e., an arc from node 1 to node 2 does not imply a connection from node 2 to node 1.

The *.front files are the ASCII encoded nondominated points of the instance. Again, each row contains exactly one vector where the components are space separated.

Paixao and Santos (PS) Instances

More information can be found on http://www.mat.uc.pt/~zeluis/INVESTIG/MSPP/DataBase/instanceDataBase.htm and in [2].

We mirror the medium and large instances as well as the complete nondominated sets here. However, the instances are encoded in our format above instead the original.

Road Network (Road) Instances

The data for the road networks is kindly provided by the PTV group. The instances themselves were compiled by Delling and Wagner [1]. Since the data is owned by PTV Group, a license is required to use the instances. This is usually free of charge for academic use. For this reason, we cannot provide the instances here. But we can email them to you, after you got in touch with PTV group.

Power Grid (Power) Instances

The power grid instances can be found here: Power Grid Instances.

Be aware that due to security considerations by the German power grid provider Amprion, we are only able to release those instances that do not contain the objective function EPL (existing power lines).

The instances are constructed with a scenario number. They have a name according to power_SzXX.graph. The XX is replaced by a number between 5 and 17. They have the following objective functions:

XX Objective Functions
5 BPA, LPA, L
7 BPA, FW, L
8 BPA, SA, L
10 LPA, FW, L
11 LPA, SA, L
13 FW, SA, L

Where the abbreviations stand for:

Abbreviation Name
BPA Bird Preservation Area
LPA Landscape Preservation Area
FW Freeways
SA Settlement Areas
L Length

Copula-Grid (Copula) Instances

You will find the Copula grid instances here soon.

References

[1] Delling, D. and Wagner, D. "Pareto Paths with SHARC" in Proc. SEA (Springer, 2009), 125–136.

[2] Paixao, J. and Santos, J. "Labelling methods for the general case of the multiobjective shortest path problem: a computational study" in Computational Intelligence and Decision Making 489–502 (Springer, 2009).

research/mosp.txt · Last modified: 2023/02/08 11:27 by boekler