General

This software accompanies the paper "Temporal Map Labeling: A New Unified Framework with experiments"[0] 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 data derived therefrom, see "Workflow" below) 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 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

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)
• CGAL (including development headers)
• Gurobi (this project is configured for Gurobi 7.5, but it should be straightforward to adapt it to versions startin from 6.5)
• If you want to use your own OpenStreetMap files for input, you need to convert them with the script from Andreas Gemsa [3]

Additionally, libosmium is added as a submodule in contrib/osmium. You need to run

git submodule init
git submodule update

to fetch it.

Building

This project is configured for builds in a separate build directory. Let '/path/to/tml' be the path to the temporal map labeling framework that you checked out from our repository. We then recommend to create a separate '/path/to/tml/build' directory. Inside that directory, issue these commands:

qmake /path/to/tml
make

If you have all required libraries etc. installed, it should build the TML framework. The binary will be called "tmlframework".

If linking fails complaining that it could not find gurobi, see below.

Troubleshooting

Problems with Gurobi during build

If Gurobi can't be found (during linking or translation), make sure that

• Your GUROBI_HOME environment variable is set correctly
• If you are not using Gurobi 7.5, you have to adapt the library that is linked in line 114 of tmlframework.pro. Look for the line containing "-lgurobi75" and adapt that to your installed version.

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 python script at [3]
3. Run the main software package in CLI mode, and output the conflict graphs as well as the results (see command line switches and the examples below 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.

There are many more parameters that can be changed, but which are currently hard-coded into the framework. See the file config.h, in which each of these settings is set and explained.

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 python script at [3].

--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.

Examples

This is an exemplary invocation of the framework, showing most of the features:

./tmlframework -m ~/daten/trajectories/maps/karlsruhe.osm -p ~/daten/trajectories/maps/karlsruhe.pycgr -o ~/daten/trajectories/out/results.csv -g ~/daten/trajectories/graphs_out -v ~/daten/trajectories/interval_out -k 10 -i 20

In this example

• ~/daten/trajectories/maps/karlsruhe.osm is the OSM XML file the map is being read from
• ~/daten/trajectories/maps/karlsruhe.pycgr is the PyCGR file derived from the map (see [3])
• ~/daten/trajectories/out/results.csv is the CSV file that the results will be written to (see below for its format)
• ~/daten/trajectories/graphs_out is the directory that the conflict graphs will be written to. On these conflict graphs, the PLS standalone heuristic can be run
• ~/daten/trajectories/interval_out is the directory that the actually computed presence, conflict and selected intervals for all labels will be written to
• 10 is the "k" parameter for the k-restriction.
• 20 random trajectories will be computed, resulting in 20 different instances

Preprocessing script

To convert a OSM xml file into the road graph file, execute the run.py script from [3] like this:

python run.py -n c -f <OSM XML file>

This will create a .pycgr file in the same directory as the XML file which can be used. For more details, see the readme file at [3].

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

[0] https://dl.acm.org/citation.cfm?id=2996957 / https://arxiv.org/pdf/1609.06327.pdf

[1] Contact: lukas.barth@kit.edu or niedermann@igg.uni-bonn.de

[2] https://github.com/tinloaf/libosmium

[3] https://github.com/AndGem/OsmToRoadGraph