GeoHipster interview with Ralph

Did you know that our very own Ralph Straumann is on the advisory board of the international GIS community website „GeoHipster“? And if you also want to become an advisor to an international community, you may have to start with producing brilliant maps: One of Ralph’s maps has been published last year in the 2015 GeoHipster calendar (check out the month of February).

Today, an interview about the story behind his map has been published on GeoHipster. If you are only remotely interested in maps and information visualization, I strongly urge you to read the short interview here.

Infoviz: Population of Swiss cities and cantons
Infoviz: Population of Swiss cities and cantons

By the way: GeoHipster published another calendar for 2016 with new maps submitted by the community. Check it out and order it here (spoiler: also this one will contain a map by Ralph).

 

Swiss GIS network on Twitter

Out of curiosity and 2.5 years ago, I analysed the network of Swiss GIS twitterers (article in German, French, Italian). That analysis inspired the creation of the GeoBeer event series (of which we had the 11th instalment just a few days ago) and the Twitter list by the name of ‚SwissGIS‘. You can find that one here.

If you follow my private blog, you might have seen that I also made Twitter maps sometimes, e.g. here for GeoHipster (thumbs up for Atanas & Co.’s initiative!) and here for SwissGIS:

The day before yesterday I updated the SwissGIS Twitter map. In doing so I thought: heck, I should probably renew the old network visualisation of a few dozen Twitter accounts as well! I keep adding people to the list when I come across their accounts; hence the list has now grown to over 200 members.

So, I dusted off my Python code for querying the Twitter API, obtaining profile metrics and building the follower network between the accounts on the SwissGIS list. I plugged the resulting dataset into Gephi, configured the visualisation, and used the superb add-on by OII’s Scott Hale to export the whole shebang to sigma.js.

You can find the result by clicking here or on this graphic (best viewed on desktop, tablet also okay):

Each node in this network is a Twitter account. Links represent follower-relationships between the accounts, the link having the colour of the account that follows the other. The network is clustered into so-called modularity classes based on its topology. Similarly to the last time I plotted a (much younger) SwissGIS network, you can find, e.g., that the blue cluster encompasses mostly French-speaking Twitter users. Also similarly to last time, Esri Switzerland becomes a rather distinct and marked cluster (in purple) with very few errors of omission and commission. This is the inherent (and at times very revealing) power of networks and the strong homophily in all of us – also, the origin of concepts like that of the filter bubble.

The nodes in the visualisation are sized according to the number of followers a node or account has within the SwissGIS network. Not within Twitter at large! E.g., in ‚general Twitter‘, @swiss_geoportal has many more followers than @geobeerch, however, within SwissGIS the two are very similar regarding this metric.

Clicking onto a node reveals additional attributes such as the account name, the profile picture, the age of the account, number of tweets, and average number of tweets per month. It also shows mutual following relationships, which followers follow this account, and which accounts this account follows (both one-directional). The accounts in these lists are themselves clickable, i.e. you can navigate through the network via the users that are contained in it. There’s also a very basic search function that acts on account names for when you can’t find a user that you are interested in.

Importantly, Twitter accounts who were not accessible at the time of data collection (e.g., accounts that are configured to be private) cannot show up in this network, as – simplifying here – no data can be collected about them through the Twitter API.

Enjoy exploring the network of Switzerland-based geo and GIS enthusiasts. And shoot me a tweet or an e-mail if you discover anything interesting (or if you simply enjoyed the visualisation or this post)!

 

PS: You can easily subscribe to the SwissGIS Twitter list in, for example, Tweetdeck or Hootsuite in order to stay on top of geo/GIS news from Switzerland (expect a mix of (predominantly) English, German, French and a little Italian). By the way: following a list means you get to see all the tweets by the list members, whether you follow them personally or not.

Data Value and Expertise Value

These days, data and data scientists (and data engineers?) seem to rule the world. Companies are data-driven, problems are solved using data-driven methods and national intelligence agencies (arguably: also online retailers) extensively collect all the data they can get hold of.

The data-driven approach is formalised in the Jurney-Warden Data-Value Stack:

The Jurney-Warden Data-Value stack Source: https://www.safaribooksonline.com/library/view/agile-data-science/9781449326890/ch05.html
The Jurney-Warden Data-Value stack (source)

The data-value stack is to be read from the bottom up to the top. The idea of the stack suggests: the value of the data arises from raw data through various steps up the pyramid. The link to Maslow’s hierarchy of needs that the authors make implies that the upper levels of the pyramid build and rely upon the lower levels, i.e. you cannot effect actions without first collecting data at the records level, then cleaning and aggregating, exploring and inferring. In my opinion, this is a feasible approach and obviously the framework works well for some cases.

However: looking at the stack, the approach reminds me of a blind chicken which randomly picks and picks until it eventually finds a valuable corn to eat. More intelligent animals have some expertise to enhance the „random-pick“ – i.e., purely bottom-up – approach: Based on its experience, intelligence and/or guts, the intelligent chicken efficiently picks the most valuable food right from the start.

I admit, I know nothing about behavioural biology to support the claims in the previous paragraph. And yes, millions of blind chickens may help. But what I really want to say is: expertise matters, also in the data-driven world – we cannot yet proclaim the end of theory.

But how does expertise come into play in the above mentioned data-value stack? Its design principle is that higher levels depend on lower levels. I would propose a similarly shaped expertise-value stack, which aligns alongside the data-value stack. That stack would look as follows (on the left):

Expertise-Value stack (left) and Data-Value stack (right)
Expertise-Value stack (left) and Data-Value stack (right)

The expertise-value stack complements the steps in the data-value stack with the following levels of expertise:

  • Wisdom: Use your wisdom for strategic decisions.
  • Application of Interdisciplinary Knowledge: Use and combine your knowledge from different subject matter domains.
  • Application of Domain Knowledge: Apply your subject matter knowledge to the problem.
  • Information Collection: Conduct targeted collection and filtering of relevant information, like reports, opinions or results of relevant research.
  • Problem Comprehension: Before doing anything, make sure you understand the problem at hand from one or several perspectives: e.g. from the perspective of the user, provider or politician.

Obviously, the idea of domain experts collaborating with, and supporting, data scientists is not new. Indeed it has been noted that subject experts may make the difference. And this is why an interdisciplinary approach (edit 2016-02-23: i.e. leveraging both expertise-value and data-value) has advantages over a pure data driven approach. Unfortunately, the benefit of including subject experts does not come for free: It takes much time to talk to each other and you need to find good counterparts to succeed. But in the long run, this interaction will pay off.

If you are interested talking to Swiss data and information experts with an interdisciplinary approach, come and talk to the team at EBP. Contact me for details. (And thanks to Ralph for editing this post)

14 Milliarden Punkte offengelegt: Zürichs Open Data-DTM

Seit einigen Monaten stellt der Kanton Zürich seine durch Laserscanning erhobenen, hochaufgelösten Höhendaten kostenlos und ohne Einschränkungen in der Benutzung zur Verfügung. Erhältlich sind die folgenden Produkte:

  • Digitales Oberflächenmodell (DOM), Rasterformat mit 0.5 m Auflösung
  • Digitales Terrainmodell (DTM), Rasterformat mit 0.5 m Auflösung
  • Digitales Terrainmodell (DTM) als Punktwolke im Format ASCII-xyz
  • LIDAR-Rohdaten als Punktwolke im Format LASzip

Der Datenbezug läuft über den GIS-Browser des Kantons, mit Kachelauswahl in der Karte. Der Zugriff auf das Download-Verzeichnis der Kacheln steht ebenfalls offen. Dieser hindernisfreie Zugang und die Open Data-Lizenz machen unsere Arbeit wesentlich einfacher und effizienter. Wir haben stets die aktuellen Daten ohne langwierige Bestellungen verfügbar. Entsprechend intensiv nutzen wir die Höhendaten, seitdem sie als Open Data verfügbar sind. (Unsere Nutzung spiegelt sich sicherlich auch in den Zugriffsstatistiken des Kantons wieder). In diesem Artikel möchte ich einen Überblick über die verschiedenen Anwendungen dieser Daten bei EBP geben.

Breite Verwendungsmöglichkeiten

Als interdisziplinäres Ingenieurunternehmen können wir die Daten in den meisten unserer Geschäftsbereiche nutzen: Im Bereich Verkehrsbau beispielsweise dienen diese hochgenauen Daten als Grundlage für die Trassierung von Strassen. Die Genauigkeit der Höhenpunkte lässt eine Verwendung in allen Projektphasen zu, mit Ausnahme des Ausführungsprojekts. Die LIDAR-Daten ersetzen damit terrestrische Vermessungen und helfen so den Auftraggebern, Kosten zu sparen. Im Bereich Wasserbau und Naturgefahren setzen wir diese Art von Daten für die Modellierung von Hochwasser ein. Das Resultat sind Gefahrenkarten, Schutznachweise oder Dimensionierungen notwendiger Schutzbauten.

punkte_thalwil
Gebäude- und Bodenpunkte beim Bahnhof Thalwil (Grundlage: Geodaten © GIS-ZH)

Weitere Anwendungen sind die Lärmmodellierung  sowie die Erstellung von Gebäudeprofilen und Visualisierungen im Rahmen der Arealentwicklung. Sogar als Grundlage für den Bau eines ausgesprochen un-digitalen Gipsmodells für einen Architekturwettbewerb haben wir die Höhendaten des Kantons Zürich schon genutzt.

Raster vs. TIN

Sehr oft verwenden wir die Höhendaten in ihrer Rohform als Punktwolke. Dank der Klassierung der Punkte in u. a. Bodenpunkte, Vegetation und Gebäude lassen sich spezifische Produkte erstellen. Häufig ist eine Kombination aus Boden- und Gebäudepunkten gefragt, jedoch ohne Vegetation. Das Raster-DOM kann diese Anforderung nicht abdecken, da es keine explizite Unterscheidung von Gebäude und Vegetation zulässt.

Ein zweites Argument für die Rohdaten ist, dass die weitere Verwendung in Programmen erfolgt, die nur mit Dreiecksvermaschungen arbeiten (Allplan, Stratis). Diese Datenstruktur – auch trianguliertes irreguläres Netzwerk (TIN) genannt – hat gegenüber Rasterdaten den Vorteil, dass die Informationsdichte über den Raum variieren kann. Dort wo das Gelände sehr variabel ist, ist eine hohe Informationsdichte wünschenswert. Bei uniformen Flächen hingegen reichen wenige Höhenpunkte, um das Gelände mit genügender Genauigkeit und wenig Datenvolumen zu beschreiben. Wenn man Rasterdaten als Grundlage für die Erstellung eines TINs verwendet, beraubt man sich dieses Vorteils.

Und die Prozessierung?

Zum Schluss noch ein paar technische Details zur Aufbereitung der Daten: Die Verarbeitung der Daten haben wir automatisiert und parametrisiert innerhalb eines FME-Workspaces. Die dafür erforderlichen Kacheln werden mit einer Überlagerung des Kachelblattschnitts mit dem gewünschten Perimeter ausgewählt und direkt vom Server des Kantons heruntergeladen.

Danach werden die erforderlichen Punkte aufgrund der Klassierung (Gebäude, Boden, etc.) gefiltert und situativ ausgedünnt, um den resultierenden Datenumfang zu reduzieren. Abschliessend wird die Punktwolke in einem für das Zielprogramm lesbaren Format (meist DWG) gespeichert. Solche massgeschneiderten Modelle sind von handlicher Grösse und damit effizient nutzbar.

Ausduennen_vorher_nachher
Ausdünnen des Modells: Vorher und nachher
  • Möchten Sie für Ihre Ingenieurarbeiten ebenfalls hochaufgelöste Geländedaten effizient einsetzen, kämpfen aber mit Problemen aufgrund von Formaten und Dateigrössen?
  • Oder sind sie interessiert am automatisierten Download und der Weiterverarbeitung von Daten?
  • Oder überlegen Sie sich, Ihre Fachdaten ebenfalls für die Allgemeinheit zu öffnen?

Dann nehmen Sie Kontakt mit uns auf. Wir helfen Ihnen gerne bei allen diesen Fragen.

Das Briefträgerproblem im Tramnetz der Stadt Zürich (3/3)

In zwei früheren Blogposts haben wir das Briefträgerproblem und das Konzept der Eulertour eingeführt und eine Lösung für das Tramnetz der Stadt Zürich präsentiert. Wie auf Twitter angekündigt, ging es dann am 20. Juni um 07:57 Uhr ab Bellevue auf Eulertour durch Zürich! Wir sind mit GPS und Notizblock gereist und haben fleissig Daten gesammelt. In diesem Blogbeitrag möchten wir nun einen datenzentrierten Rückblick auf unsere Erlebnisse geben.

Durchführung – Die Eulertour in Zahlen

Nachdem das Briefträgerproblem für das Tramnetz der Stadt Zürich theoretisch gelöst war, ging es am 20. Juni 2015 an die praktische Umsetzung.

12 Stunden und 22 Minuten

später sind wir wieder am Bellevue gestanden (zum vierten Mal an diesem Tag). Die reine Fahrzeit hat 8 Stunden und 12 Minuten betragen, 4 Stunden und 10 Minuten haben wir an Haltestellen wartend verbracht.

Eulertour nach Uhrzeit

 

Statt einen Tag lang in der Stadt Zürich im Kreis herumzufahren, wären wir in der gleichen Zeit

mit dem Flugzeug bis Los Angeles oder Singapur gekommen,

mit dem Auto bis Kopenhagen, Warschau oder Barcelona,

mit dem Fahrrad bis Stuttgart und

zu Fuss bis Schaffhausen:

Euler-Isochronen
Isochronen: In rund 12h 30min erreichbare Orte je nach Verkehrsmittel

 

Insgesamt sind wir

147 km Tram gefahren,

wovon wir rund 57 km Strecke doppelt befahren haben. Diese doppelt befahrene Streckenlänge haben wir mit der Eulertour optimiert (und nicht etwa die Fahrzeit!). 47 km der Strecke entfielen auf die Sackgassen (z.B. Bahnhof Enge – Wollishofen) und waren somit nicht Teil des Optimierungsproblems:

Graph der effektiv durchgeführten Eulertour (die Farben entsprechen der benutzten Tramlinie)

 

Wir sind auf unserer Tour insgesamt

55 Mal umgestiegen.

An den Haltestellen Stauffacher, Central und Milchbuck sind wir am meisten umgestiegen (je 3-mal). Alle Umsteigeaufenthalte pro Haltestelle aufsummiert, sind wir am längsten am Central gestanden (fast 35 Minuten, allerdings wegen Umleitungen und den damit verbundenen Wartezeiten) und am kürzesten am Bahnhof Stettbach (nur eine halbe Minute):

Sum_Halt_pro_Haltestelle
Aufsummierte Wartezeit (in Minuten) pro Haltestelle

 

stops
Anzahl Umsteigevorgänge und Wartezeit pro Haltestelle

 

Die längste Etappe dauerte 24 Minuten (Frankental – Bahnhofstrasse), die kürzeste 1 Minute (Bahnhof Enge/Bederstrasse – Bahnhof Enge). Im Mittel war eine Etappe fast 9 Minuten lang. Die längste Wartezeit am Stück verbrachten wir am Central (23 Minuten), die kürzeste am Bahnhof Enge (nur wenige Sekunden). Die mittlere Wartezeit betrug 4.5 Minuten.

Fahrzeit_Wartezeitverteilung
Fahrzeit- und Wartezeitverteilung

 

Am längsten sind wir mit der Tramlinie 14 gefahren. Insgesamt 6 Mal, total 1 Stunde und 6 Minuten. Am kürzesten sind wir mit der Linie 15 gefahren (2 Mal, insgesamt 12 Minuten).

Fahrten_pro_Linie
Anzahl Fahrten pro Tramlinie
Fahrzeit_pro_Linie
Aufsummierte Fahrzeit pro Tramlinie

 

Eulertour nach Tramlinien

 

12 verschiedene Personen haben uns während unserer Fahrt durch die Stadt zumindest ein Stück begleitet. Nur 3 Stunden und 54 Minuten waren wir zu zweit unterwegs. Zeitweise waren wir 7 Personen auf Eulertour. Vom Arbeitskollegen gab es eine Lieferung zum Mittagessen:

Und von Eulertour-Fan Thomas Bruderer einen feinen Apfelstrudel:

 

Eulertour nach Anzahl Begleitpersonen

 

Im Mittel waren wir mit 12 km/h unterwegs

mit 18 km/h, wenn wir die Haltezeiten nicht berücksichtigen. Das heisst, für die gleiche Strecke hätten wir zu Fuss etwas mehr als doppelt so lange gebraucht.

Eulertour nach Geschwindigkeit

 

Auf unserer Tour war gemäss GPS-Gerät (!!) der

tiefstgelegene Punkt auf 391 m.ü.M. (Bürkliplatz) und
der höchstgelegene auf 621 m.ü.M. (Zoo)
.

Werden nun entlang der Tour nur die Steigungen aufsummiert (und das Gefälle ignoriert), so haben wir etwa 1’500 Höhenmeter zurückgelegt. Damit ergibt sich der

Energieverbrauch unserer Eulertour von 1.61 kWh.

Dafür hätten wir uns beide etwa je 35 Minuten lang die Haare trockenföhnen können.

Eulertour nach Höhenlage

Noch ein paar mehr Eindrücke gibt’s auf dem nun stillen Eulertour-Twitterfeed. Vielen Dank an alle, die uns unterstützt und sich für die Eulertour interessiert haben (und schon über Ausdehnungen auf andere Städte oder das SBB-Netz nachdenken)!

Wir danken Marcel Rieser von senozon für die Erstellung der Videosequenzen!

Nadine Rieser + Bence Tasnády

 

Teil 1: Aufgabenstellung und allgemeine Lösung des Problems

Teil 2: Anwendung auf das Tramnetz der Stadt Zürich

Teil 3: Durchführung – Die Eulertour in Zahlen

Jenseits von Standard-Darstellungen

Vielleicht haben Sie den Beitrag im Tagesanzeiger-Datenblog oder andernorts in der Presse bzw. online gesehen: Ich habe in meiner Funktion als Visiting Researcher mit Kollegen am Oxford Internet Institute kürzlich zwei Karten zum globalen Internetzugang publiziert:

Die Internet-Bevölkerung 2013 (Geonet Project, Oxford Internet Institute)
Die Internet-Bevölkerung 2013 (Geonet Project, Oxford Internet Institute)
Relativer Zuwachs der Bevölkerung mit Internet-Zugriff, 2009–2013 (Geonet Project, Oxford Internet Institute)

Mehr zum Thema der Karten können Sie in den folgenden zwei Blogbeiträgen (in Englisch) oder beim Tagesanzeiger lesen:

Hier möchte ich etwas mehr auf die Art der Visualisierung eingehen. Die Karten oben verzerren die Fläche jedes Landes so, dass sie proportional zur Anzahl Personen mit Internetzugang wird. Die Karten enthalten im südlichen Atlantik eine kleine unverzerrte Referenzkarte, welche es noch deutlicher macht, wie sehr zum Beispiel Europa online über- und Afrika unterrepräsentiert ist.

Es handelt es sich bei diesem Kartentyp um sogenannte Kartenanamorphosen oder -anamorphoten bzw. – einfacher in Englisch – um Cartograms. In diesem Fall sind es hexagonal cartograms, das heisst jedes Land ist aus einer Zahl kleiner Hexagone als Bausteine zusammengesetzt. Ich habe das Vorgehen hierzu schon andernorts detailliert erläutert, mittlerweile habe ich aber noch einige Optimierungen des Vorgehens umgesetzt. Um die Verzerrungen der Formen der Länder möglichst gering zu halten, ist einiges an Handarbeit erforderlich, die einem auch die gängigen Kartogramm-Algorithmen nicht abnehmen können.

Viele Personen fühlen sich von solchen Darstellungen unmittelbar angesprochen. Sie können bisweilen ziemlich plakativ wirken, etwa wenn die zugrundeliegende Grösse sehr ungleich verteilt ist. Ein Nachteil von solchen Darstellungen ist sicherlich, dass die Einschätzung von relativen Grössen keine genaue Einordnung erlaubt. Beispielsweise wäre zwar nicht unmöglich, aber sehr schwierig zu sagen, wieviele Menschen in Japan online sind oder – in dieser Darstellung der Schweizer Kantone und Städte – wieviele Personen im Kanton Graubünden leben. In beiden Fällen ist dies aber auch ganz klar nicht eines meiner Ziele.

Die automatisch berechenbaren Verzerrungen der Länder in den Darstellungen oben habe ich mit einer spezialisierten Software erstellt. Für die Umlegung auf die Hexagone, die Minimierung der Verzerrungen, das manuelle (!) Setzen der Labels und das gesamte endgültige Layout habe ich ArcGIS verwendet. Die fertigen Karten, so finde ich, sehen aber nicht mehr nach Standard-„GIS-Karten“ aus.

Mit diesem Post möchte ich dazu aufrufen, (geo)graphische Konventionen und ‚best practices‘ auch mal zu hinterfragen. Vielleicht lässt sich etwas besser als mit einer Choroplethen- oder Symbolkarte, womöglich noch mit einer Standardlegende, visualisieren. „Besser“ kann hier etwa heissen,

  • dass ein Fakt exakter kommuniziert werden kann oder
  • dass eine Darstellung Interesse weckt beim Publikum oder
  • dass eine Darstellung zu weiteren Fragen anregt oder
  • dass eine Darstellung ausgewählte Punkte vielleicht nicht exakt aber in ihren grossen Linien aufsehenerregend vermittelt.

Vielleicht möchten Sie ihre Darstellungen auch vom langweiligen Standard-Look befreien? –
Gerne berate ich Sie dabei.

 

Artikel: Die Zukunft von GIS ist smart und vernetzt

Vor kurzem hat in unserem Blog Ivo Leiss über die Evolution von GIS und GIS 5.0 berichtet. In GIS 5.0 werden das Internet der Dinge, Indoor-Navigation und Echtzeit-Informationssysteme Schlüsselelemente sein. GI-Systeme 5.0 werden smarter und vernetzter sein als die Systeme, die wir heute kennen. Dies zieht auch neue Infrastruktur-Bedürfnisse nach sich. Wie die einzelnen Elemente zusammenspielen, hat Ivo Leiss im oben verlinkten Blogpost anhand dieser Grafik erläutert (nach Porter und Heppelmann, abgeändert):

Wenn Sie sich wie wir für die Zukunft von Informationssystemen interessieren, empfehle ich Ihnen die Lektüre unseres Geomatik Schweiz-Artikels mit dem Titel „GIS 5.0 – Smart und vernetzt“ (pdf). Darin hat Ivo Leiss drei unserer Mitarbeitenden (u.a. mich) zum Thema interviewt. Die drei Interviewten nähern sich dem Thema aus drei unterschiedlichen Richtungen: Internet of Things, Erkenntnisgewinne aus Datenanalysen und Cloud-Technologien.

GIS 5.0 – Smart und vernetzt (pdf), erschienen in Geomatik Schweiz 5/2015.

Das Briefträgerproblem im Tramnetz der Stadt Zürich (2/3)

Anwendung auf das Tramnetz der Stadt Zürich

Der Graph unserer Aufgabenstellung (reduzierter Netzplan in Abbildung 1 bzw. als Graph in Abbildung 2 des letzten Posts) besteht aus 29 Knoten und 43 Kanten. Die Gewichte der Kanten entsprechen der Fahrzeit in Minuten und sind in Abbildung 2 den Kanten zugeordnet.

Die Anzahl ungerader Knoten (r) ist zehn (Knotennummern 1 bis 10, rot eingefärbt). Für diese zehn Knoten wird ein vollständiger Graph erstellt, d.h. jeder ungerade Knoten wird mit jedem anderen ungeraden Knoten durch eine Kante verbunden (Abbildung 3). Die Gewichte (Fahrzeiten) der Kanten entsprechen der kürzesten Verbindung zwischen den jeweiligen Knoten im ursprünglichen Graphen gemäss Abbildung 2.

Abb3
Abbildung 3: Vollständiger Graph für ungerade Knoten mit der kostenminimalen perfekten Paarung (fünf farbige Matchingkanten)

Beispiel (Abbildung 4): Von der Tunnelstrasse zum Bürkliplatz sind gemäss Abbildung 2 folgende zwei direkte Routen denkbar: Entweder Tunnelstrasse – Stockerstrasse – Paradeplatz – Bürkliplatz (violett in Abbildung 4) oder Tunnelstrasse – Bahnhof Enge – Bürkliplatz (orange in Abbildung 4). Die Fahrzeit der ersten Verbindung beträgt 5 Minuten (1 + 2 + 2), der zweiten Verbindung 6 Minuten (2 + 4). Im vollständigen Graphen in Abbildung 3 wird jeweils die kürzeste Verbindung, in diesem Fall also 5 Minuten, eingetragen.

Abb4
Abbildung 4: Beispiel kürzeste Verbindung für vollständigen Graphen

Die grösste Schwierigkeit der Aufgabe besteht nun darin, die kostenminimale perfekte Paarung zu finden. Dabei müssen fünf Kanten im vollständigen Graphen in Abbildung 3 ausgewählt werden, sodass jeweils zwei Knoten miteinander verbunden werden. Die Paarung ist so zu wählen, dass die Summe der Kantengewichte der verbundenen Knoten minimal wird. Es gibt 945 verschiedene Möglichkeiten, aus den zehn Knoten fünf Paare zu bilden. Für jede dieser Kombinationen können die Kantengewichte aufsummiert und schliesslich diejenige Kombination mit der minimalen Summe ausgewählt werden.

Die Lösung dieses Matching-Problems ist in Abbildung 3 dargestellt: Breit gezeichnete farbige Matchingkanten entsprechen jeweils einer Paarung. Folgende fünf Verbindungen müssen im reduzierten Netzplan demnach ergänzt werden (in Klammern sind jeweils die Zwischenknoten der kürzesten Verbindungen angegeben):

Bahnhof Enge – Tunnelstrasse (rot), Stockerstrasse – Stauffacher (blau), Bürkliplatz – Kantonsschule (violett, Bellevue – Kunsthaus), Bahnhofplatz/HB – Bahnhofstrasse (gelb, Bahnhofquai/HB) und Haldenegg – Leutschebach (grün, Schaffhauserplatz – Milchbuck – Sternen Oerlikon)

Mit der Ergänzung des ursprünglichen Graphen in Abbildung 2 durch die fünf Matchingkanten gemäss Abbildung 3 wurde der ursprünglich nicht-eulersche Graph eulersch gemacht und es existiert eine Eulertour (Abbildung 5).

Abb6
Abbildung 5: Eulerscher Graph; mit fünf Matchingkanten (farbig) ergänzert ursprünglicher Graph (reduzierter Netzplan)

Als letzter Schritt muss nun eine Eulertour gefunden werden, d.h. ein geschlossener Zyklus, der alle Kanten genau einmal enthält. Hierzu wird vom gewünschten Startknoten aus (z.B. 12) ein beliebiger Zyklus K gewählt, der jede Kante genau einmal enthält. Der rote Zyklus in Abbildung 6 ist ein solcher: Krot = (12, 4, 1, 2, 11, 1, 2, 3, 5, 6, 17, 7, 16, 5, 3, 16, 4, 12). Nun wird von einem beliebigen Knoten des roten Zyklus, an dem Kanten zusammenlaufen, die nicht Teil von Krot sind, ein neuer Zyklus gewählt: Kblau = (6, 18, 7, 18, 17, 9, 21, 18, 6). Auf die gleiche Weise entstehen die Zyklen Kgrün = (17, 15, 12, 15, 14, 13, 12), Kviolett = (9, 21, 23, 19, 20, 8, 15, 8, 19, 9), Kgelb = (21, 22, 24, 23, 24, 10, 27, 28, 29, 26, 23, 21) und Kmagenta = (24, 10, 25, 24). Die Teilzyklen werden am Schluss ineinander kopiert: der magentafarbene in den gelben, der grüne, violette und gelbe in den blauen und der blaue schliesslich in den roten.

Abb7
Abbildung 6: Herleitung Eulertour

Die so entstandene Eulertour beginnend beim Knoten 12 (Bellevue) ist nur eine von vielen möglichen und sieht wie folgt aus (in Abbildung 7 mit Haltestellennamen):

12–4–1–2–11–1–2–3–5–6–18–7–18–17–15–12–15–14–13–12–17–9–21–23–19–20–8–15–8–19–9–21–22–24–23–24–10–25–24–10–27–28–29–26–23–2118–6–17–7–16–5–3–16–4–12

In einem weiteren Schritt könnte auch noch die Zahl der Umsteigevorgänge optimiert und auf diese Weise die Dauer der Tour etwas reduziert werden. Diese Fragestellung aber wurde bei der vorliegenden Lösung des Problems ausgeklammert, da lediglich Strecken und keine Linien berücksichtigt wurden.

Abb9
Abbildung 7: Eulertour mit Start am Bellevue

 

Teil 1: Aufgabenstellung und allgemeine Lösung des Problems

Teil 2: Anwendung auf das Tramnetz der Stadt Zürich

Teil 3: Durchführung – Die Eulertour in Zahlen

Das Briefträgerproblem im Tramnetz der Stadt Zürich (1/3)

[Bence Tasnády ist Spezialist in den Themenfeldern Verkehrsgrundlagen und Verkehrstechnik unseres Geschäftsbereichs Verkehr. In seinen Gastbeiträgen in den nächsten Tagen beschreibt er eine klassische Problemstellung für Graphen (vereinfacht: Netzwerke) und deren Lösung für eine Tramreise durch die Stadt Zürich. Die Lösung wird es ihm erlauben, das gesamte Tram-Streckennetz Zürichs in einer Tour abzufahren.]

Das Briefträgerproblem ist ein Begriff aus der Graphentheorie. Ein Briefträger hat die Häuser eines Quartiers mit Post zu beliefern und muss dabei jede Strasse mindestens einmal durchlaufen. Je nach Strassennetz kann es notwendig werden, einige Strassen erneut zu durchlaufen, ohne Post zu verteilen, um andere Teile des Zustellbezirks zu erreichen. Der Briefträger ist an einem geschlossenen Weg interessiert, der alle Strassen mindestens einmal enthält und minimale Länge hat.

 

Aufgabenstellung

Das Briefträgerproblem soll für das Tramnetz der Stadt Zürich gelöst werden. Die Aufgabenstellung lautet: Das gesamte Streckennetz (nicht Liniennetz) ist als geschlossene Tour (Endpunkt = Startpunkt) abzufahren und zwar in der Art, dass dabei möglichst wenige Strecken (gemessen in Minuten Fahrzeit gemäss Fahrplan) doppelt befahren werden. Da es lediglich um die Strecken geht, spielt es keine Rolle, mit welcher Linie und in welche Richtung eine bestimmte Strecke befahren wird. Mathematisch ausgedrückt ist eine Eulertour im Streckennetz der Stadt Zürich gesucht.

 

Reduktion des Problems

Für die Lösung des Problems kann das Streckennetz stark vereinfacht werden: Alle Haltestellen können ausgeklammert werden, die keine Knotenpunkte sind. Als Knotenpunkte sind Haltestellen zu verstehen, an denen auf andere Linien umgestiegen werden kann. Nicht als Knotenpunkte gelten Haltestellen mit Umsteigemöglichkeit, wenn zwei oder mehr Linien parallel geführt werden (z.B. Linien 2 und 4 zwischen Tiefenbrunnen und Bellevue). Im Folgenden wird der auf diese Weise vereinfachte Liniennetzplan als «vereinfachter Netzplan» bezeichnet (graue und schwarze Strecken in Abbildung 1). In einem nächsten Schritt können diejenigen Strecken aus dem Problem ausgeklammert werden, die Sackgassen bilden und damit unabhängig vom Optimierungsproblem doppelt befahren werden müssen. Diese Strecken sind im vereinfachten Netzplan grau dargestellt. Somit reduziert sich das zu lösende Optimierungsproblem auf das schwarz dargestellte Netz (Abbildung 1). Im Folgenden wird dieses Netz als «reduzierter Netzplan» bezeichnet. Für die Lösung des Problems muss nur dieser reduzierte Netzplan genauer betrachtet werden.

Abb1
Abbildung 1: Vereinfachter (schwarze und graue Strecken) und reduzierter Netzplan (schwarze Strecken)

 

Allgemeine Lösung des Problems

Mathematisch betrachtet handelt es sich beim Tramstreckennetz der Stadt Zürich um einen ungerichteten, gewichteten Graphen (Abbildung 2). Gesucht ist die sogenannte Eulertour im Graphen. In einem eulerschen Graphen (zusammenhängender Graph mit geraden Knotengraden, d.h. ausschliesslich gerader Anzahl Kanten pro Knoten) entspricht die kürzeste Route einer Eulertour. Eine Eulertour ist eine Tour, die jede Kante genau einmal durchläuft. Ein Blick auf den reduzierten Netzplan in Abbildung 2 zeigt aber, dass es sich in diesem Fall nicht einen eulerschen Graphen handelt, da nicht alle Knotengrade gerade sind. Die rot eingefärbten Knoten weisen ungerade Knotengrade auf (jeweils drei Kanten pro Knoten).

Allgemein lässt sich das Problem lösen, indem man den nicht-eulerschen Graphen kostenminimal durch Einfügen weiterer Kanten eulersch macht und das Problem damit auf das Finden einer Eulertour zurückführt. Ist ein zusammenhängender Graph nicht eulersch, besitzt er r > 0 Knoten mit ungeradem Knotengrad. Da in jedem Graphen Knoten mit ungeradem Grad nur in gerader Anzahl auftreten, ist r immer gerade. Verbindet man jeweils zwei Knoten ungeraden Knotengrades durch eine zusätzliche Kante werden die ungeraden Knotengrade gerade, während die geraden Knotengrade gerade bleiben. Damit besitzt der ergänzte Graph ausschliesslich gerade Knotengrade und ist somit eulersch. Um den Graph eulersch zu machen müssen also insgesamt r/2 zusätzliche Kanten in den Graphen eingefügt werden.

Zur kostenminimalen Erweiterung des Graphen wird aus den Knoten ungeraden Grades ein vollständiger Graph (jeder Knoten ist mit jedem anderen Knoten durch eine Kante verbunden) erstellt. Als Kantengewicht wird jeweils die Fahrzeit des kürzesten Weges zwischen den beiden Knoten im ursprünglichen Graphen gewählt. In diesem vollständigen Graphen wird dann eine kostenminimale perfekte Paarung mit r/2 sogenannten Matchingkanten gesucht. Für jede eingefügte Matchingkante zwischen zwei Knoten werden im ursprünglichen (nicht-eulerschen) Graphen die Kanten des entsprechenden kürzesten Weges zwischen den beiden Knoten dupliziert. Auf diesen Kanten des Ursprungsgraphen muss der Briefträger also genau zweimal entlanggehen. Jede Eulertour in dem auf diese Weise erweiterten Graphen ist eine optimale Lösung des Briefträgerproblems.

Abb2
Abbildung 2: Reduzierter Netzplan als Graph (die Knotengrade der roten Knoten sind ungerade, die Zahlen auf den Kanten bezeichnen die Fahrzeit in Minuten)

 

Teil 1: Aufgabenstellung und allgemeine Lösung des Problems

Teil 2: Anwendung auf das Tramnetz der Stadt Zürich

Teil 3: Durchführung – Die Eulertour in Zahlen

Projektbeispiele: Geodatenmodelle, Unfallanalysen und Geoinformationsstrategie

In der Serie „Projekte“ möchten wir Ihnen in unregelmässigem Rhythmus einige Highlights aus der Arbeit von Ernst Basler + Partner (EBP) vorstellen. Heute drehen sich die vorgestellten Projekte um die Themen minimale Geodatenmodelle, Analysen des Unfallgeschehens im Strassenverkehr und die Formulierung einer modernen Geoinformationsstrategie.

Minimale Geodatenmodelle in INTERLIS

Minimale Geodatenmodelle machen es einfacher, Geodaten zu nutzen und Datensätze unterschiedlicher Herkunft miteinander zu kombinieren. Minimale Geodatenmodelle sind auch ein wichtiger Beitrag für die Harmonisierung von Daten zwischen verschiedenen Akteuren.

Diese Ziele sind im Geoinformationsgesetz (GeoIG) der Schweiz verankert. EBP unterstützt diverse Stellen bei ASTRA, BAFU und BFS bei der Erarbeitung minimaler Geodatenmodelle in der Modellierungssprache INTERLIS.

→ mehr Informationen

 

Verkehrssicherheitsgewinne aus strukturierten Datenanalysen

Die Sicherheit im Strassenverkehr ist ein drängendes Thema. Die Schweizerische Vereinigung der Verkehrsingenieure und Verkehrsexperten (SVI) hat 2013 das Projekt „Verkehrssicherheitsgewinne aus Erkenntnissen aus Datapooling und strukturierten Datenanalysen (VeSPA)“ aufgelegt.

In Phase 1 bearbeitete EBP zusammen mit der PTV Transport Consult zwei Teilprojekte zu Wetter-Einflüssen und zu Infrastruktur-Einflüssen auf das Unfallgeschehen im Strassenverkehr.

Von den identifizierten Einflussfaktoren und Zusammenhängen mit dem Unfallgeschehen lassen sich Massnahmenansätze ableiten und deren Wirkung abschätzen. Ferner können auf Basis der Resultate Unfallmodelle als Hilfsmittel zur Entscheidungsfindung im Sicherheitsmanagement formuliert werden.

Seit Januar 2015 bearbeiten EBP und PTV Transport Consult Phase 2 des Forschungsprojekts VeSPA.

→ mehr Informationen

 

Geoinformations-Strategie für den Kanton Schwyz

Daten und Informationen werden in unserer Gesellschaft immer wichtiger. Geodaten kommt dabei spezielle Bedeutung zu, angetrieben von Trends wie mobilem Internet, Cloud-Infrastruktur, Augmented Reality, Self-Tracking und dem Internet of Things.

Im Zuge dieser Entwicklungen möchte sich der Kanton Schwyz eine zukunftsorientierte Geoinformationsstrategie erarbeiten. EBP hat den Kanton Schwyz im Strategieprozess unterstützt mit der Durchführung von Workshops, der Schärfung des Strategiebegriffs und der Definition der Bestandteile einer Strategie. Ferner hat EBP relevante gesellschaftliche und technologische Entwicklungen aufgezeigt, welche in der Strategie aufgegriffen werden sollten.

→ mehr Informationen