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).

 

Projektbeispiele: Zürcher Fruchtfolgeflächen, Patrouille des Glaciers und Geodaten für die Armee

In der Serie „Projekte“ möchten wir Ihnen in unregelmässigem Rhythmus einige Highlights aus der Arbeit von EBP Informatik vorstellen. Heute drehen sich die vorgestellten Projekte um die Nachführung von Daten über Fruchtfolgeflächen, die bekannte Patrouille des Glaciers und um die Bereitstellung von Geoinformationen für die Schweizer Armee.

F3N: Nachführung der Fruchtfolgeflächen-Karte des Kantons Zürich

© Fachstelle Bodenschutz des Kantons Zürich
© Fachstelle Bodenschutz des Kantons Zürich

Die Fachstelle Bodenschutz des Kantons Zürich hält die Daten zum qualitativ besten ackerfähigen Kulturland, den sogenannten, Fruchtfolgeflächen, aktuell.

Wir haben für den Kanton Zürich ein Nachführungskonzept entwickelt und darauf aufbauend die Applikation F3N umgesetzt.

F3N verbessert die Effizienz des Nachführungsprozesses und erlaubt daneben auch stets detaillierte Aussagen zu Bestand und Veränderungen der Fruchtfolgeflächen im Kanton.

→ mehr Informationen

 

Anmelde- und Zeitmessungsverfahren für die Patrouille des Glaciers

© Patrouille des Glaciers
© Patrouille des Glaciers

Die Patrouille des Glaciers ist ein internationaler Skialpinismus-Wettkampf der Schweizer Armee, an welchem auch zivile Patrouillen teilnehmen dürfen. Sie gilt als härtester Teamwettkampf der Welt und zieht alle zwei Jahre über 5’000 Teilnehmende an.

Ernst Basler + Partner ist zusammen mit der Firma race result verantwortlich für die Bereitstellung des Anmelde- und Zeiterfassungssystems für den Wettkampf im Jahr 2016 (und optional auch im Jahr 2018).

→ mehr Informationen

 

Geoinformationsportal für die Schweizer Armee

Die Schweizer Armee will die Nutzung von Geoinformationen mit der Realisierung einer „Nutzungsplattform Mil“ vereinfachen.

Ernst Basler + Partner unterstützt die Armee unter anderem bei der Konzeption eines Geoinformationsportals, welches mit klassifizierten Daten und mit Daten von weltweiter Ausdehnung umgehen können muss.

→ mehr Informationen

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.

Example projects: Project platforms, geodata for the DFA and automated data import

In the „projects“ series we would like to highlight from time to time some projects that our company conducted. Today, these projects encompass online collaboration platforms for projects, geodata infrastructures and services, and spatial ETL using FME.

Jinsha: Collaboration platform for an international project team

As part of an international team, our experts investigate the influence of climate change on water management in China. In order to support the project team, EBP built a collaboration platform based on Microsoft Sharepoint.

The Sharepoint platforms facilitates the communication between team members and project documentation, and simplifies project management. At any time, all team members can access common assets and documents can be edited collaboratively and simultaneously.

→ find out more

 

Project initiation of the Swiss Federal Department of Foreign Affairs Geodata Infrastructure

The Swiss Federal Department of Foreign Affairs (FDFA) requires a networked information landscape in order fulfill its tasks. Geographic information and data are an essential part of this information landscape for operational awareness. EBP assisted the FDFA in the initiation phase of the project „Geodata Infrastructure FDFE“ according to the federal standard for project management, Hermes 5.

We derived the requirements for such a system using interviews and stakeholder workshops. In a Hermes study we documented the situation analysis, aims, requirements and approaches, suggested and described various solutions and formulated a recommendation.

→ find out more

 

Cadastral surveying: Data import using FME

The geodata of the cadastral survey in the Canton of Schwyz is managed by the municipalities. The canton publishes these data centrally. In order to facilitate the canton’s task, we assisted Schwy in developping an automated import of Interlis data into the cantonal geodata infrastructure (Oracle and PostGIS) using FME as the state-of-the-art ETL tool.

Using our tool, the Canton of Schwyz can import survey data at the press of a button. The data is then served to the authorities and the public, e.g. in the cantonal WebGIS, from the central databases.

→ find out more

Projektbeispiele: Projektplattform in China, Geodaten im EDA und AV-Interlis in Schwyz

In der Serie „Projekte“ möchten wir Ihnen in unregelmässigem Rhythmus einige Highlights aus der Arbeit von EBP Informatik vorstellen. Heute drehen sich die vorgestellten Projekte um die Themen kollaborative Projektplattformen, Geodateninfrastruktur und Spatial ETL mit FME.

Jinsha: Projektplattform für ein internationales Team

Unsere Expertinnen und Experten untersuchen in einem internationalen Projektteam in China den Einfluss des Klimawandels auf das Wasser-Management. EBP hat zur Unterstützung des Vorhabens eine kollaborative Projektplattform auf Basis von Microsoft Sharepoint aufgebaut.

Die Sharepoint-Plattform dient dem Austausch, der Projektdokumentation und der Vereinfachung des Projektmanagements. Alle Beteiligten sind stets auf demselben Informationsstand und Dokumente können von mehreren Personen gleichzeitig bearbeitet werden.

→ mehr Informationen

 

Initialisierung der Geodateninfrastruktur des Eidgenössischen Departements für auswärtige Angelegenheiten

Das Eidgenössische Departement für auswärtige Angelegenheiten (EDA) benötigt für die Erfüllung seiner Aufgaben eine vernetzte Informationslandschaft. Geoinformationen sind ein essentieller Teil davon. EBP begleitete das EDA bei der Initialisierung des Projekts „Geodateninfrastruktur EDA“ gemäss Hermes 5-Methodik.

Im Rahmen von Interviews und Workshops ermittelten wir die Bedürfnisse des EDA an die geplante GDI. In einer Studie nach Hermes 5 haben wir Situationsanalyse, Ziele, Anforderungen und Lösungen dokumentiert, technologieneutral Varianten vorgeschlagen und schliesslich eine Empfehlung abgegeben.

→ mehr Informationen

 

Amtliche Vermessung: Datenimport mit FME

Die Geodaten der amtlichen Vermessung (AV) werden im Kanton Schwyz gemeindeweise bewirtschaftet. Der Kanton macht diese AV-Daten dann zentral verfügbar. Um dem Kanton Schwyz diese Aufgabe zu erleichtern, hat EBP den Import von Interlis-Daten der AV in die kantonale Geodateninfrastruktur mit dem state-of-the-art ETL-Werkzeug FME umgesetzt.

Die im Interlis-Format vorliegenden AV-Daten können so per Knopfdruck in die kantonalen Geodatenbanken (ORACLE und PostGIS) importiert werden. Mit diesen Datenbanken unterstützt der Kanton Schwyz den internen und öffentlichen Gebrauch der Vermessungsdaten und die Anzeige der Daten im kantonalen WebGIS.

→ mehr Informationen

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

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

Reibungslose Feld-Berechnungen mit dem GISconnector

Im letzten Blogpost habe ich aufgezeigt, wie der GISconnector for Excel Feld-Berechnungen in ArcGIS massiv vereinfacht. Der GISconnector verbindet nämlich auf intelligente Weise die Fähigkeiten von Esri ArcGIS Desktop mit jenen von Microsoft Excel. Wie Sie wissen, vertreiben wir seit September 2014 den GISconnector for Excel exklusiv in der Schweiz. Neben vielen fortgeschrittenen Funktionen können alle Arbeitsschritte, welche die Attributdaten betreffen und die normalerweise mit der Attributtabelle in ArcGIS gelöst werden, mit Excel erledigt werden. Damit hat man alle Möglichkeiten einer modernen Tabellenkalkulations-Software in ArcGIS zur Verfügung. (Eine ausführliche Beschreibung der übrigen Funktionen des GISconnector finden Sie hier.)

Schon im ersten Teil bin ich kurz auf die Benutzerfreundlichkeit der Feld-Berechnung in ArcGIS und der Feld-Berechnung mit dem GISconnector eingangen.In diesem zweiten Teil möchte ich diesen Aspekt vertiefen.

 

Feld hinzufügen

Der Dialog links präsentiert sich, wenn man in ArcCatalog eine neue Feature Class angelegt hat und dieser Felder hinzufügen möchte. Leider sind nicht allen Anwenderinnen und Anwendern alle erlaubten Feldtypen gleich geläufig. Die meisten Desktop-Anwenderinnen und -Anwender sind aber geübt darin, in Microsoft Excel den jeweils geeigneten Datentyp zu konfigurieren.

Um in einer Feature Class ein neues Feld anzulegen, fügt man einfach einer Excel-Tabelle eine weitere Spalte hinzu. Der GISconnector übersetzt den gewählten Datentyp dann intelligent in den passenden Datentyp in Esri ArcGIS.

Bestimmt wollten Sie bei Feld-Berechnungen auch schon vorsichtig sein oder haben einfach die Empfehlung von ArcGIS befolgt und deshalb eine Editier-Sitzung gestartet. Und sich dann prompt geärgert, weil in der Editier-Sitzung einer Attributtabelle keine neuen Felder hinzugefügt werden können. Mit GISconnector können Sie alle relevanten Schritte ins vertraute Excel auslagern – und Berechnungen und Felder-Hinzufügen kommen sich nicht mehr in die Quere.

 

Berechnungsfunktion suchen

Vergleich Field_Calculator_GISconnector

Das Finden der gesuchten Berechnungsfunktion gestaltet sich in Excel in der Regel einfacher als in ArcGIS. Und viele der Python-Funktionen in ArcGIS erscheinen vielen Anwenderinnen und Anwendern wohl relativ kryptisch, während die Bedeutung von Funktionen in Excel direkt unterhalb des Auswahlfensters kurz erläutert wird.

 

Berechnungsfunktion parametrisieren und Fehler beheben

Für das Parametrisieren von Funktionen bietet Excel wahlweise einen Wizard an. Dieser hilft einem mit kontextsensitiven Angaben, die Argumente der Funktion richtig zu befüllen.

Bereits bei der Eingabe kann Excel manche Fehler erkennen und weist deutlich erkennbar darauf hin. Bei Feld-Berechnungen in ArcGIS müssen wir auf diesen Komfortlevel verzichten: Weder führt uns ein Wizard interaktiv durch die Argumente einer Funktion, noch werden wir vor Ausführen einer Berechnung auf Falscheingaben hingewiesen. 

Die Fehlermeldungen von ArcGIS nach dem Ausführen der Berechnungen fallen zudem oft ziemlich allgemein und nicht sehr hilfreich aus. Mit dem GISconnector for Excel stehen diese Komfortfunktionen GIS-Nutzerinnen und -Nutzer endlich in vertrauter Umgebung für GIS-Arbeiten zur Verfügung.

 

Editor

Last but not least muss ich noch den Python-Editor für fortgeschrittene Funktionen in ArcGIS ansprechen. Die Skriptsprache Python verzichtet darauf, Codeblöcke z.B. mit { } und etwa Strichpunkten zu strukturieren. Stattdessen ist der sogenannte Whitespace (üblicherweise Tabulatoren oder Leerzeichen) von grosser Bedeutung. Wenn eine Einrückung nicht die richtige Grösse hat (z.B. ein Tabulator oder 4 Leerzeichen), funktioniert Python-Code in der Regel nicht. Nützlich für das Programmieren von kleinen Skripts wären ausserdem Syntax-Highlighting (also die farbliche Kennzeichnung von Code-Teilen), stetige Syntax-Prüfung, ein vergrösserbares Editor-Fenster und Code-Completion (d. h. das automatische Vorschlagen von Ergänzungen; die Idee also, dass z.B. der Editor „print“ vorschlägt, sobald ich „pri“ getippt habe).

Alle diese Bestandteile sind in besseren Python-Entwicklungsumgebungen wie zum Beispiel PyCharm standardmässig enthalten. Im Python-Editor sind diese Funktionen in ArcGIS leider gar nicht oder nicht benutzerfreundlich umgesetzt: Das Einrücken mit Tabulatoren funktioniert nicht, es müssen Leerzeichen verwendet werden. Syntax-Highlighting, Syntax-Prüfung und Code-Completion sind leider auch nicht vorhanden. Und – für mich eigentlich der schlimmste Aspekt: Das Code-Fenster verwendet eine proportionale Schriftart. Das ist eine Schriftart, wie Sie sie hier im Blog sehen, bei der z.B. „m“ oder „w“ breiter sind als „i“ oder „l“. Was schön ist zum Lesen, ist denkbar ungeeignet um in Python zu programmieren, da die Ausrichtung von Code-Blöcken so noch schwieriger zu sehen ist.

Ein Vergleich des ArcGIS-Python-Editors mit der Darstellung in einer Python-Entwicklungsumgebung:

 

Fazit

Ich hoffe, die gezeigten Vergleiche haben Ihnen vor Augen geführt, wie sehr GIS-Anwenderinnen und -Anwender von der Integration von ArcGIS und Excel mit dem GISconnector profitieren können. Das Hinzufügen, Umbennen und Löschen von Feldern ist so einfach wie man es sich in Excel gewohnt ist. Bei allen Berechnungen kann man sich, falls gewünscht, auf die Unterstützung durch einen intelligenten Wizard mit Kontexthilfe verlassen. Und bei komplizierten Berechnungen verliert man keine Zeit mehr beim Erstellen von Formeln oder mit dem Aufspüren von Fehlern. Und das hier Gezeigte ist nur ein Teil der Funktionen des GISconnectors, welche die Arbeit mit GIS beschleunigen.

Haben wir Ihr Interesse am GISconnector geweckt?

Kontaktieren Sie uns bei Fragen, für eine kostenlose Testversion oder eine unverbindliche Demonstration per Screensharing.

ArcGIS, GISconnector und Excel: Eine mächtige Kombi
ArcGIS, GISconnector und Excel: Eine schlagkräftige Kombination.