Von einem Ort zum anderen

Distanzmatrix der U6 in München.

Danke, Google Maps. Wer hätte vor zwanzig Jahren gedacht, dass man heute keinen Landkarten mehr lesen können muss, um an sein Ziel zu kommen? Aus journalistischer Sicht lassen sich mit Kartendaten zudem richtig coole Geschichten erzählen. Und damit meine ich nicht, irgendwelche Punkte auf eine Karte zu setzen, hinter denen sich Popups öffnen. Ich meine Geschichten, die mit geografischen Einheiten spielen.

Ein tolles Beispiel hat die Berliner Morgenpost (mal wieder) geliefert: „So schaffen Sie alle 78 Museen in der Langen Nacht“ (der Museen). Das Interaktivteam besorgte sich die Koordinaten aller Museen, die in dieser Nacht mit einem Ticket zugänglich waren und berechnete die kürzeste Route – für verschiedene Verkehrsmittel. Ich habe mich für München an eine ähnliche Berechnung gewagt.

Das „Problem des Handlungsreisenden“

Dahinter steckt eine mathematische Berechnung (oder ist es theoretische Informatik?!): Das „Problem des Handlungsreisenden“. Die Frage: Was ist die kürzeste Route für einen Handelsvertreter, bei der Start und Ende der gleiche Ort sind?

Dafür gibt es unter anderem den Concorde TSP (TSP = Travelling Salesman Problem) Solver. Gibt man die Daten da richtig rein, berechnet das Programm die kürzeste Route. Der Solver lässt sich in die gängigen Programmiersprachen einbinden. Die Morgenpost hat ihren dazugehörigen R-Code auf Github veröffentlicht.

Aus praktischer Sicht steckt hinter der Analyse des kürzesten Weges eine sogenannte Distanzmatrix. Man kann sich das ganze als Tabelle vorstellen, bei der Spaltennamen und Zeilennamen identisch sind. Der Wert gibt jeweils die Distanz oder die Reisezeit an.

Eine Distanzmatrix mit Münchner S-Bahnstationen

Tools für Distanzmatrizen

Es gibt einige Anbieter für solche Matrizen. Der bekannteste ist – na klar – Google. Die Google Distance Matrix nutzen beispielsweise Transportunternehmen, um die schnellsten Wege für ihre Fahrzeuge zu berechnen. Seit neuestem greift das Tool auch auf Googles Prognosen für den kommenden Verkehr zu.

Wie so eine Anfrage aussieht, hat Google auf seiner Webseite demonstriert. Die folgenden Header-Daten benötigt die Schnittstelle:

Wie lange dauert es mit dem Auto von Vancouver und Seattle nach San Francisco und Victoria, British Columbia? Der API-Key wird für die Abrechnung benötigt, denn kostenlos gibt es nur 2500 Abfragen pro Tag. Und der Weg von einem Ort zum anderen zählt als eine Abfrage.

Ein Auszug der Google-Antwort im JSON-Format:

Für jede der Verbindungen sieht die Antwort unter „elements“ gleich aus: Zuerst die Distanz in Kilometern und als Meter-Wert, danach die Zeit in Stunden und Minuten oder in Sekunden. Der „Status“ gibt an, ob alles geklappt hat.

Googles Tools kosten Geld – es geht auch gratis

Das Problem bei Google: Es kostet Geld. Für Journalisten ist das natürlich nie eine gute Nachricht. Zum Glück gibt es die Open Street Map (scheint mein Lieblingsthema hier zu werden). Das Project OSRM (Open Source Routing Machine) will mit den offenen Daten der Open Street Map im Grunde das gleiche, wie Google: Den schnellsten Weg zum Ziel anzeigen. Auf der Seite gibt es bislang eine Karte zum Testen, eine Anleitung, wie man selbst einen OSRM-Server hosten kann und – eine API. Damit lässt sich der schnellste oder kürzeste Weg für Auto, Fußgänger und Radfahrer berechnen (bisher nur für Autos, wie ich das sehe – beim Selberhosten gehts aber für alles). Außerdem gibt es eine „Table“-Funktion, die Distanzmatrizen ausgibt. Ein Traum.

Wie ich eine Geschichte mit Distanzdaten erzählt habe, zeige ich im nächsten Post.