Automated generation of transit maps

Wir behandeln das Problem der automatisierten Erstellung von ÖPNV-Karten aus Fahrplandaten. Die Karten können dabei sowohl geografisch korrekt, als auch schematisch sein. Insbesondere untersuchen wir folgende Teilprobleme: Wie können fehlende geografische Linienverläufe (Shapes) aus vorhandenem Kartenmaterial extrahiert werden? Wie kann aus einer Menge von Fahrten mit Shapes das darin enthaltene topologische Netzwerk so abgeleitet werden, dass Kanten mit darauf verkehrenden Linien versehen sind und sich später nicht überlappen? Wie können schnell Permutationen dieser Linien gefunden werden, so dass sie sich in der Karte so selten wie möglich kreuzen und/oder trennen? Wie können effizient schematische Karten erzeugt werden, die auch Hindernisse oder die ursprünglichen geografischen Linienverläufe berücksichtigen? Wir beschreiben zunächst einen auf einem Hidden-Markov-Modell basierenden Map-Matching-Ansatz für Fahrplandaten und führen eine Evaluation auf mehreren Fahrplandatensätzen durch. Vor diesem Hintergrund untersuchen wir auch Methoden um zu entscheiden ob Paare von Stationen ähnlich sind. Wir untersuchen und evaluieren außerdem mehrere Methoden zur Beschleunigung des Map-Matchings. Weiter beschreiben und evaluieren wir einen maßgeschneiderten Map-Construction-Ansatz zur Extraktion des toplogischen Netzwerks. Dieser Ansatz kann Abbiegeverbote von Linien berücksichtigen und ähnliche Stationen in einzelne Knoten überführen. Um optimale Permutationen der Linien zu finden, formulieren wir eine Variante des klassischen Metro Line Crossing Minimization Problems (MLCM), die das Rendern der Karten vereinfacht. Wir nennen diese Variante das Metro Line Node Crossing Minimization Problem (MLNCM) und beschreiben außerdem eine gewichtete Variante (MLNCM-W) sowie eine Variante die auch Linientrennungen berücksichtigt (MLNCM-WS). Letzteres erachten wir als sehr wichtig für die Kartenqualität. Wir beweisen die NP-Schwere dieser Probleme und beschreiben sowohl Näherungsmethoden, als auch ein ganzzahliges lineares Programm (ILP) zum Finden optimaler Lösungen. Zur schnelleren Optimierung und zur Qualitätsverbesserung der Näherungsmethoden formulieren wir verschiedene Transformationsregeln, die implizit optimale partielle Ordnungen auf den Linien berechnen und das Problem typischerweise in viele kleinere Unterprobleme teilen. Für die Schematisierung entwerfen wir eine neue Methode zum Erstellen oktilinearer Karten. Hier beschreiben wir sowohl ein ILP als auch einen schnellen Approximationsalgorithmus basierend auf der Berechnung kürzester Pfade in einem oktilinearen Gittergraphen. Wir untersuchen außerdem Beschleunigungsansätze und zeigen, dass unser Verfahren auch mit anderen Layouts (z.B. orthoradial oder hexalinear) funktioniert. In dieser Arbeit wird außerdem ein praxisorientierter Überblick über das ästhetisch ansprechende Rendern der Karten gegeben. Alle unsere Methoden wurden in separaten und öffentlich verfügbaren Tools implementiert, die zusammen eine einfach zu erweiternde Pipeline bilden.