NOTE: This repository is outdated. Please refer to https://github.com/kit-algo/ULTRA.

---

Integrating ULTRA and Trip-Based Routing

This C++ framework contains a variant of the Trip-Based Routing algorithm that was combined with ULTRA in order to enable efficient journey planning in multi-modal transportation networks. Both the preprocessing algorithms and the query algorithm have a special focus on integrating unlimited paths in the transfer graph and the Trip-Based query algorithm. The framework was developed at KIT in the group of Prof. Dorothea Wagner.

Usage

This framework contains code for generating Trip-Based transfer shortcuts using two alternative approaches. First, shortcuts computed by ULTRA can be used as input for the standard Trip-Based preprocessing algorithm. Secondly, an integrated variant of the ULTRA and Trip-Based preprocessing steps can be used to directly compute the Trip-Based transfer shortcuts. Additionally, the framework contains code for the ULTRA-Trip-Based query algorithm, which computes Pareto-optimal journeys when given the transfer shortcuts generated by either of the preprocessing approaches. Finally, the framework contains code for the standard transitive variant of the Trip-Based query algorithm and the ULTRA-RAPTOR algorithm for comparison. These components are compiled into the console application UltraTripBased, using the Makefile that is located in the Runnables folder. Within this application the following commands are available:

• buildCH computes a normal CH needed for the ULTRA query algorithms.
• coreCH computes a core-CH need for the preprocessing steps.
• computeEventToEventShortcuts computes stop-to-stop ULTRA shortcuts needed for the ULTRA-RAPTOR query and the sequential preprocessing.
• raptorToTripBased converts stop-to-stop ULTRA shortcuts to Trip-Based ULTRA shortcuts using the sequential preprocessing.
• computeEventToEventShortcuts computes Trip-Based ULTRA shortcuts using the integrated preprocessing.
• generateUltraQueries generates random triples of source location, target location, and departure time.
• generateGeoRankQueries generates random queries, grouped by their query distance (geo-rank).
• runUltraQueries evaluates a query algorithm on queries generated with the commands above.

All of the above commands use custom data formats for loading the public transit network and the transfer graph. As an example we provide the public transit network of Switzerland together with a transfer graph extracted from OpenStreetMap in the appropriate binary format at https://i11www.iti.kit.edu/PublicTransitData/Switzerland/binaryFiles/.

Additionally, we provide a second console application, Network, to aid with converting public transit data to our custom format. It includes the following commands:

• parseGTFS converts GFTS data in CSV format to an intermediate binary format.
• gtfsToIntermediate converts GFTS binary data to an intermediate network format that allows for easier manipulation of the network components.
• intermediateToRAPTOR converts a network in intermediate format to RAPTOR format.
• loadDimacsGraph converts a graph in the format used by the 9th DIMACS Implementation Challenge to our custom binary graph format.
• duplicateTrips duplicates all trips in the network and shifts them by a specified time offset. This is used to extend networks that only comprise a single day to two days, in order to allow for overnight journeys.
• addGraph adds a transfer graph to a network in intermediate format. Existing transfer edges in the network are preserved.
• replaceGraph replaces the transfer graph of a network with a specified transfer graph.
• reduceGraph contracts all vertices with degree less than 3 in the transfer graph.
• reduceToMaximumConnectedComponent reduces a network to its largest connected component.
• applyBoundingBox removes all parts of a network that lie outside a predefined bounding box.
• applyCustomBoundingBox removes all parts of a network that lie outside a specified bounding box.
• makeOneHopTransfers computes one-hop transfers for all stops whose distance is below a specified threshold. This is used to create a transitively closed network for comparison with non-multi-modal algorithms.
• applyMaxTransferSpeed applies a maximum transfer speed to all edges in the transfer graph.
• applyConstantTransferSpeed applies a constant transfer speed to all edges in the transfer graph and computes the travel times accordingly.

An example script that combines all steps necessary to load a public transit network is provided at Runnables/BuildNetworkExample.script. It can be run from the Network application using runScript BuildNetworkExample.script. It takes as input GFTS data in CSV format located at Networks/Switzerland/GTFS/ and a road graph in DIMACS format located at Networks/Switzerland/OSM/dimacs.

Literature

The algorithms in this framework are mainly based on two previously published algorithms: ULTRA and Trip-Based Routing.

• UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution
  Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, Tobias Zündorf
  In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19), Leibniz International Proceedings in Informatics, pages 14:1–14:16, 2019
  pdf arXiv

• Trip-Based Public Transit Routing
  Sascha Witt
  In: Proceedings of the 23rd Annual European Symposium on Algorithms (ESA'15), Lecture Notes in Computer Science volume 9294, pages 1025--1036, 2015
  html arXiv