How far do you live from work?

Did you answer this question in minutes or in kilometers? Many answer this in minutes. Now, imagine how machines would have to get to know the answer to such question for you: it would need a lot of data.

That data is in some cases, e.g., for Amsterdam, already sufficiently available as open data: open street map and the openOV initiative in The Netherlands help. Yet, to achieve this system, we need to do a huge job in integrating data and integrate these datasets on 1 machine. What if we can advance on the state of the art and use Semantic Web/Linked Data technologies to facilitate all this?

This is what I need for my PhD as well. So, we have started creating 4 vocabularies: one for transit feeds or timeschedules, one for categorizing transport datasets, one for road traffic events and one for real-time arrivals and departures of public transport.

One of these vocabularies has now been released: http://vocab.gtfs.org/terms# – the Linked GTFS vocabulary. You can help out building these vocabularies at our github repository, or you can just dig in and start using our terms. You can now browse this at our Linked Open Vocabularies project:

http://lov.okfn.org/dataset/lov/details/vocabulary_gtfs.html

During the OKFN meetup in Athens, Greece, I gave a presentation on the 4 focuses for the Open Transport working group. It is at the same time an open call to collaborate with us in various projects. Everyone needs the 4 focus points described in the presentation. The Open Transport working group aims to bring together everyone who needs this.

A comprehensive Q&A session as well as a networking session with catering & drinks completed the OKF-AT MeetUp on Open Transport (Data). So what about the findings of this event? Lets say the information- and data system of Austria in the field seems to be on a good way to be harmonised accross our 9 provinces and also some Cities already provide open transport data (as geoinformation, traffic routes or timetable information) in their respective data catalogues – BUT: A) there is no discussion how open data can change environmental problems of transport data in Austria, B) there are NO plans on how to open up the data of the Austrian central transport information system and C) there are only little thoughts about how to follow standardisation on European level (beside INSPIRE) to enable cross border services on (open) transport data – so a lot work still in front of us!

Introduction

This is a cross-post from http://blog.tristramg.eu/short-history-of-routes-computation.html

I wrote a blog post in French that had some unexpected success (by success I mean that people actually read it). At least two people asked for an English translation. So here it goes, with some of the errors of the French version corrected.

Formally we would speak of “shortest path in a graph problem”. The goal is the same: what is the shortest way to go from A to B.

Route computation are nice as the actual use cases can be explained to anyone:

• the GPS end user
• the computer science student that at some point learnt the basic algorithms
• there is still research going on, but it can be explained to anyone interested within a few pints

Personally, what I find interesting is how those algorithms evolved through time. Sorry for punctual technical details.

1956 – 1958: Ford, Moore and Bellman

The first suggested algorithm was published independently by those authors.

It is nowadays usually called the Bellman-Ford algorithm.

1959: Dijkstra

Edgard Dijkstra is Dutch.

He is one of the big names in computer science. He is know for his handwriting and quotes such as:

• Simplicity is prerequisite for reliability
• The question of whether Machines Can Think... is about as relevant as the question of whether Submarines Can Swim
• Object-oriented programming is an exceptionally bad idea which could only have originated in California

He is the author of — brace yourself — Dijkstra’s algorithm published in 1959. It has been described in a two pages only article but the name stuck as the fundamental brick of route computations.

However, the algorithm we learn at school is not the one published by Dijkstra. It has a complexity of O(n²) while we are teached that complexity of the algorithm is O(n·log(n)).

We had to wait 28 year to get to it.

1987: Tarjan

The weakness of Dijkstra’s algorithm is its priority queue that returns what node to visit next. An article from 1987 by Tarjan (an other reference in the world of graphs) brings us to the “modern” Dijkstra’s algorithm.

Many variations have been tested to speed up the algorithm with mitigated success, such as A*, bi-directional searches, sacrificing the optimality or a combination of all that.

On a recent computer, computing a route across France takes around a second. Therefor back in the 90’s it was way to slow. There was a need to speed up the computation.

We had to wait 18 year to get to it.

2005: Dimacs challenge and rise of the KIT

The 9th Dimac Challenge was about routes computation. For this event the road network of the United States was published.

A large number of publications pulverised all the records. The algorithms are now fast enough to compute a route between two points on earth in less than a millisecond (more than a thousands times faster than the Dijkstra’s algorithm).

An overwhelming share of publications come from from the Karlsruhe Institute of Technology.

The team members suggested many algorithms, but also tested nearly every possible combination between those algorithms.

There were so many publications it was hard to know where to look.

2008: consolidation with the Contraction Hierarchies

After this phase of exuberant creativity, we could extract the core substance to make the algorithm that will probably become the new reference: the contraction hierarchies.

It has been presented in a master thesis (so I am somewhat ashamed of my PhD thesis…) by Geisberger.

There is nothing really new, only the removal of superfluous ideas that made other algorithms too complicated to keep the smallest core that works well.

Everybody that is interested in algorithmic should read the algorithm and its demonstration of optimality. The first time I read it, I could not grasp how it worked. I had to walk through the demonstration to be convinced.

That algorithm is used in OSRM, a free route calculator based on OpenStreetMap data.

2009: public transit are still forgotten

At last we know to efficiently compute a route on a street network. What about public transit? Not so bright here.

The question was already studied in 1991 in the great PhD thesis of Eduard Tulp. But little happened since.

Performances are deceiving and trying to use the successes in street network failed.

In the article Car or Public Transport—Two Worlds H. Bast show the differences that exist between both means of transportation and that is not interesting to try to use the same techniques.

2010: transfer patterns, performance, at last!

It was summer, I had just sent my thesis manuscript to the examiners. Because of over-zealousness I read the latest article from H. Bast.

For the first time it was possible to compute routes using public transit within a few milliseconds in a large city as New-York.

If you looked closely, the was still a slight twist: the authors used the computing power of thousands of computers from Google. A massive pre-processing is the key to such good results.

Just two more years to wait to have an effective algorithm.

2012: Delling’s Raptor

Daniel Delling likes cool names (a previous algorithm was called Sharc). He chose Raptor for his new algorithm.

The proposed approach has no need for pre-processing and has better performances than the transfer patterns.

Hooray! Cars do not have any more the monopole on efficient algorithm. Raptor has the advantage to be rather simple and to have nice properties (too technical to bother you with them).

Intermission: opendata and science

Science needs data to be easily available. The DIMACS challenge was a success because big real life data set were published.

It took six years from the first high-performance street network routing algorithm to the first high performance algorithm on public transit. We had to wait so long until data sets were at last released.

It is the opendata movement applied to transportation that allowed that scientific progress.

2013: Connection Scan Algorithm

A last one! In an article very modestly called Intriguingly Simple and Fast Transit Routing the authors present the connection scan algorithm. It is slightly more efficient than Raptor but is considerably more simple.

When reading the article, and once again when implementing it, I was struck how braindead simple it is, but it works.

We went through 57 years of research to end up with an algorithm that could have been written at the same time as Dijkstra’s.

Hence a last quote of Dijkstra that seems very appropriate:

Simplicity is a great virtue but it requires hard work to achieve it and education to appreciate it. And to make matters worse: complexity sells better

It’s the 18th of September and 40 open transport experts gather in a small room in a conference center in Geneva (Switzerland). It’s precisely 1 year and 1 day ago that we were gathered in Helsinki to write the Open Transport Data Manifest. In meantime, this manifest has been used in the Italian Parliament, has been presented at several Open Data conferences and has been used to convince smaller transport agencies that this is the right way forward.

This one year has been a quest for problems and potential solutions. During the next year we will focus on a couple of projects we have identified as being the next steps. How we got there will be posted in a couple of blog posts during the next weeks.

Tristram at OKCon

What’s next?

• Focus on small helpful tools: stations.io, an open transport data portal and a vocabulary
• Talk, convince, innovate: using the Open Transport Data Manifest and continue working on the Open Transport Data Handbook (more soon).

Pieter

Next week it’s OKCon! *cheers*

When you check out the program you can see that there are a lot of Open Transport sessions happening. You’re of course most welcome to join in!

On Wednesday between 14:45 and 16:00, we are organising a workshop with various people from our community giving a short lightning talk, but mainly with a discussion on what our future vision should be. This is the program of this workshop:

Just a short note about the Transport Hack Day [Open Knowledge Foundation Germany](http://okfn.de/) just ran last week.

We ran the event together with the local transport provider, the Berlin government and the FH Potsdam.
The VBB released GTFS data, opened up their API and provided some geo datasets about entrances to stations.

We had over 120 people registered, lots of them were developers/designers and we had a really inspired atmosphere.
The output in numbers of apps was not as great as we would have liked due to broken datasets and the complicated API, but I think we will see some nice apps in the coming months.

* Website:
* Data:
* Source:

Transportation is a major contemporary issue, which has a direct impact on economic strength, environmental sustainability, and social equity. Accordingly, transport data – largely produced and/or gathered by public sector organisations or semi-private entities, quite often decentrally – represents one of the most valuable sources of (Public Sector) Information (PSI, also called ‘Open Data’), a key policy area for many, including the European Commission.

This is the first paragraph of the Open Transport Data Manifest. During the OKFestival in Helsinki, we organised a PSI sectoral meeting on transport data. The manifest is a summary of the entire day, where all kind of stakeholders from over 15 different countries were invited to help think about informing European travelers as good as possible.

The first slide of the manifest. More on github

The manifesto document was then transformed into an infographic by Miet Claes and Michael Vanderpoorten (both members of iRail). The infographic is also available in slides style. Because we want everyone to be able to help with the manifest, and to reuse this work, we have published the source files on github. We invite you to fork the infographic and use it for your own slides on open transport.

Help sending this infographic to the policy makers who need to see it and let us know on the mailing list.

Pieter