This repository contains the C++20 implementation of KaRRiT, a state-of-the-art dispatcher for the dynamic taxi sharing problem with transfers. KaRRiT uses engineered on-the-fly shortest path queries to allow for fast query times with maximum flexibility.
All files in this repository except the files in the directory External are licensed under the MIT
license. External libraries are licensed under their respective licenses.
This source code is a fork of https://github.com/molaupi/karri, which is itself based on a fork of https://github.com/vbuchhold/routing-framework. Large parts of the project structure as well as basic data structures and shortest path algorithms are directly taken or adapted from the original framework. The copyright statements in each file state the respective author or authors of the file.
To build KaRRiT, you need to have some tools and libraries installed. On Debian and its derivatives
(such as Ubuntu) the apt-get tool can be used:
$ sudo apt-get install build-essential
$ sudo apt-get install cmake
$ sudo apt-get install python3 python3-pip; pip3 install -r python_requirements.txt
$ sudo apt-get install zlib1g-dev
$ sudo apt-get install sqlite3 libsqlite3-dev
$ sudo apt-get install intel-oneapi-tbb intel-oneapi-tbb-devel
$ sudo apt-get install hwloc libhwloc-dev
Next, you need to clone the libraries in the External subdirectory and build the RoutingKit library. To do so,
type the following commands at the top-level directory of the framework:
$ git submodule update --init
$ make -C External/RoutingKit lib/libroutingkit.so
We provide bash scripts to generate the input data for the Berlin-1pct, Berlin-10pct,
Ruhr-1pct, and Ruhr-10pct problem instances for the KaRRi algorithm.
Inputs are generated based on OpenStreetMap (OSM) data, which requires the osmium tool.
On Debian and its derivatives osmium can be installed using
sudo apt-get install osmium-tool
As an example, you can generate the input data for the Berlin-1pct instance by typing the following commands
at the top-level directory: (Downloads multiple GiB of raw OSM data and requires at least 10 GiB of RAM.)
$ cd Publications/KaRRiT/
$ bash DownloadGermanyOSMData.sh .
$ bash FilterGermanyOSMData.sh .
$ bash PreprocessOSMData.sh . Germany Berlin BoundaryPolygons
$ bash GenerateKnownInstanceInputData.sh . Berlin-1pct pedestrian
To generate the input data for the other instances, simply replace Berlin-1pct with the instance name
(Berlin-10pct, Ruhr-1pct, Ruhr-10pct) and replace Berlin with Ruhr for the
Ruhr instances.
To run KaRRiT in the exact and heuristic configurations, use the provided bash script by typing the following commands at the top-level directory. The bash scripts describe additional parameters (e.g. number of threads) at the top.
$ cd Publications/KaRRiT/
$ bash RunKaRRiTExact.sh . <instance-name> <output-dir>
$ bash RunKaRRiTHeuristic.sh . <instance-name> <output-dir>
Here, <instance-name> can be any of Berlin-1pct, Berlin-10pct, Ruhr-1pct,
and Ruhr-10pct, and <output-dir> is the path to the directory where the output files
will be stored.
We provide functions for a basic evaluation of results in Publications/KaRRiT/eval.R.