Table of Contents
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.
| Name | medium | large |
|---|---|---|
| CompleteK | instances/output | instances/output |
| CompleteN | instances/output | instances/output |
| GridK | instances/output | instances/output |
| GridN | instances/output | instances/output |
| RandomD | instances/output | instances/output |
| RandomK | instances/output | instances/output |
| RandomN | instances/output | instances/output |
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).