A resource-efficient open source routing library
A resource-efficient open source routing library
The Bliksem Consortium, of which Conveyal is a member, has released its C implementation of a timetable-based public transport routing algorithm under an open source license at http://github.com/bliksemlabs/rrrr. The code is compact and fast enough to run directly on a mobile phone, providing routes even without an internet connection.
For the past year, five consortia of specialized companies have been rethinking journey planning in the multi-modal travel information (MMRI) project in the Netherlands. Piloted by the Noord-Brabant region, this project is part of the Dutch infrastructure and environment ministry’s Beter Benutten program, which aims to utilize existing transport systems more efficiently rather than construct new infrastructure. Three of these consortia elected to work on OpenTripPlanner, and a fourth elected to experiment with an alternative open source router implementation.
In parallel with our work bringing real-time routing to OpenTripPlanner and simplifying OTP installation and deployment, as part of the Bliksem consortium Conveyal began developing a new routing core with a radically different design. It was inspired by a desire to experiment with recent round-based routing algorithms and simultaneously return to code that is concise and close to the metal, using libraries, languages, and design principles that are both technically sound and enjoyable to work with.
The result of that work is RRRR, a recursive acronym for “RRRR Rapid Real-time Routing”. The third R originally stood for “round-based”, but RRRR is expected to also perform multiobjective A* on the same underlying timetable structures at which point that adjective will no longer apply. It has the ability to consider real-time trip updates when routing, hence the change. RRRR is written in C with Python utilities for auxiliary tasks like preparing timetable data. It is intended to be used both on servers (with multiple load-balanced worker processes) and as a library directly on embedded or mobile devices. The second use case solidified early design decisions in favor of compactness and generally low resource consumption.
The difference is striking: a data file for all of the Netherlands is around 20MB in size, about half of which is just route and stop names. This is two orders of magnitude smaller than a comparable OpenTripPlanner graph. Startup time is negligible since we simply ask the OS to page the timetable file in from disk. On a recent multicore machine, throughput is around 50 requests per second. Of course these advantages do not come for free: we are not explicitly modeling the street network, there is less flexibility in weighting etc. but the router is nonetheless a good fit for many applications. Most notably, one can find routes quickly on a mobile device even when no internet connection is available (in tunnels, while on a flight, etc.)
OpenTripPlanner has targetted detailed and highly flexible routing in a server-side environment where resources are plentiful. In RRRR we have sought to create a complementary routing engine with a more narrowly defined purpose and a particular emphasis on efficiency. The router exposes an OTP-compatible REST API, making it a drop-in replacement: OTP clients can communicate transparently with the RRRR back end. RRRR is still under development and not yet production quality, but we already have several users and contributors in the Netherlands and elsewhere in Europe providing feedback.
Following the PlanLab event last Thursday in Amersfoort where we met with transport operators, policy makers, designers, researchers and transport professionals to advance multimodal journey planning, the Bliksem consortium is opening the source of the RRRR project under a permissive (two-clause BSD) license. The repository is at http://github.com/bliksemlabs/rrrr.
