Temporal Map Labeling: A New Unified Framework with Experiments - Additional Material

General

This software accompanies the paper “Temporal Map Labeling: A New Unified Framework with experiments” by Lukas Barth, Benjamin Niedermann, Martin Nöllenburg and Darren Strash.[1]

All software used for the experiments in that paper is included in this bundle. You may use, modify and redistribute it in accordance with the license stated in LICENSE.TXT.

The software is meant to be fed with OpenStreetMap data and can either be used in GUI mode in which you will be able to see the results of the various models and algorithms, or in CLI mode which can be used to run experiments and retrieve quality measures of the various algorithms and their solutions.

Contents

The package that you can download contains different programs as well as data:

• The main software package used to run the bulk of the experiments
• A separate program used to run the Phased Local Search heuristic (currently missing - see the note at the top of this file)
• The input map data we used
• Our results as CSV files

To preprocess the OpenStreetMap data, a tool is needed that can be obtained here:

• Converter by Andreas Gemsa

NOTE: The Phased Local Search software is still missing from this tarball. We will add it as soon as possible. If you are interested in it, please drop us a short email (find our addresses under [1]) and we will notice you as soon as we published it.

Requirements

The software has a number of requirements. Aside from things that are probably available on most Linux machines, these are:

• Qt (including development headers and tools)
• libosmium (at the time of writing, the official libosmium had a bug causing OSM files to be read incorrectly on machines with non-american locales. You can find a fixed (although old) version in the “fixatof” branch of [2].)
• Gurobi

Having all of this installed, you should be able to build the software by first executing “qmake”, then executing “make” in the source directory.

Workflow

To perform experiments, here is what you’ll usually do:

1. Get a map file from OpenStreetMap (or use the one provided by us)
2. Convert it into a .pycgr using the provided python script (or use the one provided)
3. Run the main software package in CLI mode, and output the conflict graphs as well as the results (see command line switches on how to do that)
4. Run the PLS standalone program on the generated output graphs

Main Software: Command Line Arguments

In CLI mode, no user input besides the command line flags (and the files supplied via these) is expected. All algorithms will then be run on the resulting AM1, AM2 and AM3 instances and results will be output according to the flags you set. The command line switches are:

–map / -m

Set the map (OSM XML file) to be used

–pycgr / -p

Set the road graph (PCGR) map file. This file can be generated by the provided python script.

–out / -o

Set the output CSV file name. Quality and timing measures will be written into this file

–seed / -s

Set the initial seed. The actual instance seeds for every iteration will be generated from this seed (unless you specify –fixseed, see below) and reported for every instance in the results file.

–k-restriction / -k

Set the k value for the k-restricted model. Not setting this parameter (or setting it to -1) causes the GMT model to be computed

–graph / -g

Set the prefix for conflict graph output files. To this prefix, the instance seed will be appended to create the actual output GraphML files.

–ilpout / -d

Set the prefix for ILP model output files. To this prefix, the instance seed will be appended to create the actual Gurobi model files.

–intervals / -v

Set the prefix for interval output files. To this prefix, the instance seed will be appended to create the actual interval files. These contain the computed presence, conflict and activity intervals for all labels.

–gui

Run in GUI mode instead of CLI mode. Here, you can graphically view computed trajectories as well as results of the various heuristics.

–fixseed / -f

Use the seed specified with -s directly instead of computing instance seeds from it. Useful to reproduce the result for one specific instance. Note that this switch is not useful in combination with -i.

–threads / -t

Specify how many threads should be used for computation. Note that currently, only the ILP optimization is multithreaded.

–iterations / -i

Set the number of instances to be computed.

Preprocessing script

To convert a OSM xml file into the road graph file, execute the “OSMtoRoadGraph” like this:

python -n c -f

This will create a .pycgr file in the same directory as the XML file which can be used.

Results

You can find our results on the data that we provide with this archive in the “results” folder. These are CSV files. Every line contains results for one instance, i.e. one trajectory. Most columns should be self-explanatory and either contain timings of various parts of the computation for that respective instance, or the quality of the heuristics / the ILP on that instance. Some interesting columns that do not fall in these categories are:

K

The k value in a k-restricted setting. A -1 here indicates the GMT model.

SEED

The seed of this instance. Set the seed with -f -s as shown above to reproduce this exact instance.

AMx GRAPH NODES / EDGES

Indicates the size of the AMx conflict graph

Most timing columns that do not carry the name of a heuristic / the ILP contain timings of internal precomputation steps and are probably not interesting.

Footnotes

[1] Contact: lukas.barth@kit.edu or benjamin.niedermann@kit.edu
[2] https://github.com/tinloaf/libosmium