Verkehrslinienpläne

Linienpläne sind schematische Karten für Verkehrsnetze wie z.B. U-Bahnen in Großstädten. Der Fokus liegt beim Zeichnen dieser Linienpläne allerdings, im Gegensatz zu herkömmlichen Karten, weniger auf geographischer Genauigkeit als auf einer möglichst übersichtlichen Darstellung der Netztopologie. Wir formulieren ein gemischt ganzzahliges Programm (MIP), das zu einem gegebenen geographischen Liniennetz einen schematischen Linienplan erzeugt, der mehrere Qualitätskriterien optimiert. Außerdem zeigen wir die NP-Schwere des Problems.

Geographische Karte der U-Bahn in Sydney.

Von unserer Methode erzeugter Linienplan.

Das Beispiel des Linienplans von Sydney, Australien zeigt zu welchem Ergebnis unsere Methode ausgehend von einem geographischen Eingabegraphen kommt. Links ist die Eingabezeichnung abgebildet, auf der rechten Seite befindet sich der Linienplan wie er von unserer Methode berechnet wurde.

Die Anforderungen an einen Linienplan unterteilen wir dabei in harte und weiche Kriterien. Die harten Kriterien müssen von jeder Zeichnung erfüllt werden. Dazu gehören u.a. (a) die Einhaltung einer Mindestkantenlänge, (b) der Erhalt der Eingabetopologie und (c) die Oktilinearität der Zeichnung, d.h. die Beschränkung aller Kanten auf horizontale, vertikale und 45-Grad diagonale Strecken.

Die weichen Anforderungen sollen so gut wie möglich erfüllt werden. Die Ziele sind hier (a) Minimierung der Knicke entlang der einzelnen U-Bahn-Linien, (b) Beibehaltung der relativen Lage benachbarter Stationen und (c) Minimierung der Gesamtkantenlänge. Am gezeigten Beispiel sieht man, wie sich die harten und weichen Qualitätskriterien auf das Ergebnis auswirken.

• Am 3. Mai 2006 erhielt Martin Nöllenburg den NRW Undergraduate Science Award 2005 für die Veröffentlichung „A Mixed-Integer Program for Drawing High-Quality Metro Maps“.

• Am 21. Juli 2006 erhielt Martin Nöllenburg den Absolventenpreis 2005/06 der Fakultät für Informatik für seine Diplomarbeit „Automated Drawing of Metro Maps“.

• In der Ausgabe 4/2009 des Kundenmagazins bulletin der Schweizer Bank Credit Suisse wird über die gemeinsame Arbeit von Martin Nöllenburg und Alexander Wolff über das Zeichnen von Linienplänen informiert.

• Am 16. Juli 2006 erschien in der Frankfurter Allgemeinen Sonntagszeitung Nr. 28/06 der zweiseitige Artikel „Die Schönheit des Untergrundes“ von Klemens Polatschek. Erhältlich über das Archiv der FAZ und bei txtr.

1. Martin Nöllenburg, and Alexander Wolff.
   Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming.
   IEEE Transactions on Visualization and Computer Graphics, 17(5):626-641, May 2011.
   [ html ][ pdf ]

1. Martin Nöllenburg.
   An Improved Algorithm for the Metro-Line Crossing Minimization Problem.
   In: Proceedings of the 17th International Symposium on Graph Drawing (GD'09) volume 5849 of Lecture Notes in Computer Science, pages 381-392. Springer, 2010.
   [ html ][ pdf ]
2. Marc Benkert, Martin Nöllenburg, Takeaki Uno, and Alexander Wolff.
   Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transportation Maps.
   In: Proceedings of the 14th International Symposium on Graph Drawing (GD'06) volume 4372 of Lecture Notes in Computer Science, pages 270-281. Springer, January 2007.
   [ html ][ pdf ]
3. Martin Nöllenburg, and Alexander Wolff.
   A Mixed-Integer Program for Drawing High-Quality Metro Maps.
   In: Proceedings of the 13th International Symposium on Graph Drawing (GD'05) volume 3843 of Lecture Notes in Computer Science, pages 321-333. Springer, January 2006.
   [ html ][ pdf ]

1. Automated Drawing of Metro Maps.
   Martin Nöllenburg.
   Master's thesis, Universität Karlsruhe, August 2005.
   [ pdf ]

1. Martin Nöllenburg.
   Automated Drawing of Metro Maps.
   Technical Report 2005-25, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2005.
   [ html ][ pdf ]