[Open-transport] A new resource-efficient open source public transport routing library

Mon Dec 16 18:11:03 UTC 2013

A post on the OpenTripPlanner mailinglist you might want to read ;)

Stefan

TL;DR: We have released our C implementation of a timetable-based public
transport routing algorithm and auxiliary tools in Python 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 without an internet connection.

Hello transit developers,

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 its installation and deployment, as part of the Bliksem
consortium I 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.

-Andrew