Zur Seite der TU

Seminar: Netzwerkoptimierung in Verkehr und Telekommunikation

 Zur Seite des Instituts für Mathematik
 

Sommersemester 2007

  
 

Prof. Dr. Dr. h.c. Martin Grötschel    Marika Neumann    Christian Raack    Thomas Schlechte   
 


crew scheduling    p-cycles    train timetable llsolution

Inhalt

Sowohl bei der Planung im Nah- und Fernverkehr als auch bei der Dimensionierung von Netzwerken für die Übertragung von Daten in der Telekommunikation werden heutzutage verstärkt Methoden der linearen und ganzzahligen Programmierung angewendet. In diesem Seminar sollen aktuelle Modelle, Algorithmen und Techniken vorgestellt werden. Im Fokus stehen dabei praxisrelevante Fragestellungen wie z.B. die Gestaltung der Tarife in Verkehrsnetzen (bilevel programming), die Behandlung von unsicheren Daten (robust optimization), das Lösen von Problemen mit Millionen von Variablen (column generation) sowie der Schutz gegen physikalische Ausfälle in Telekommunikationsnetzen (survivable networks).

Voraussetzungen

Lineare Algebra, Graphen- und Netzwerkalgorithmen, Lineare Optimierung.

Anmeldung

Interessenten am Seminar kommen zur Vorbesprechung oder wenden sich (möglichst frühzeitig) an Christian Raack: raack@zib.de.

Termine

Die erste Vorbesprechung zum Seminar mit Vergabe von Seminarthemen fand statt am

Montag, dem 5. Februar 2007, um 16:00 Uhr im MA 313.


Eine zweite Vorbesprechung zum Seminar mit Vergabe weiterer Seminarthemen findet statt am

Mittwoch, dem 18. April 2007, um 12:00 Uhr im MA 313.


Dabei wird jedem Teilnehmer ein Thema/Artikel plus Betreuer zugeordnet. Um für alle Beteiligten ein gutes Gelingen des Seminars zu ermöglichen, wird jeder Teilnehmer in einem fünfminütigen Kurzvortrag sein Thema vorstellen. Die Seminarkurzvorträge finden statt am

Mittwoch, den 16. Mai 2007, um 16:00 Uhr im MA 313.


Das Seminar wird als Blockseminar an dem Wochenende 15.-17. Juni 2007 am Konrad-Zuse-Zentrum durchgeführt. (Lageplan).

Hinweise zu den Vorträgen

Richtlinien für die Vortragsgestaltung und die Scheinvergabe: Bei der Literatursuche sind folgende Links nützlich:

Vergebene Themen

  1. Torsten Klug: Wartungsplanung des Rollmaterials
    Maintenance Routing for Train Units: The Transition Model (Maroti & Kroon [2004])
    Maintenance Routing for Train Units: The Scenario Model (Maroti & Kroon [2005])

  2. Sorana Goetzke: Routingplanung in Bahnstationen
    Routing Trains through a railway station based on a node packing model (Zwaneveld, Romeijn & Kroon [2001])
    Routing Trains through railway stations: complexity issues (Kroon, Romeijn & Zwanefeld [1997])

  3. Bejamin Krämer: Umplanung von Bahnpersonal
    A column generation approach to solve the crew re-scheduling problem (Huisman [2007])

  4. Urs Kramer und Robert Waniek: Planung von ausfallsicheren Netzwerken: directed cycles und p-cycles
    Designing capacitated survivable networks: Polyhedral analysis and algorithms (Rajan [2004])

  5. Josephine Müller: "Mautgebührenmodell" mit Bilevel Programming
    A Bilevel Model of Taxation and its Application to Optimal Highway Pricing (Labbé, Marcotte & Savard [1998])

  6. Siddharth Naik: Branch and Bound Algorithmus für ein "Maut-/Netzgebührenmodell"
    Tariff Optimization in Networks (Bouhtou, van Hoesel, van der Kraaij & Lutton [2003])
    Linear Tarification in Multi-Commodity Telecommunications Networks (Bouhtou, van Hoesel, van der Kraaij & Lutton [2002])

Weitere Themen

  1. Umlaufplanung des Rollmaterials
    Efficient circulation of railway rolling stock (Alfieri, Groot, Kroon & Schrijver [2006])
  2. Robuste Optimierung - Überblick
    Robust optimization - methodology and applications (Ben-Tal & Nemirovski [2002])
  3. Robuste Optimierung - Netzwerkflüsse
    Robust discrete optimization and network flows (Bertsimas & Sim [2003])
  4. Robuste Optimierung - Netzwerkflüsse
    Routing of Uncertain Demands (Ameur & Kerivin Bertsimas Sim [2005])
  5. Robuste Dienstplanung im Luftverkehr
    Bicriteria robustness versus cost optimization in tour of duty planning at Air New Zealand (Ehrgott & Ryan [2000])
    Constructing robust crew schedules with bicriteria optimization (Ehrgott & Ryan [2002])
  6. Robuste Optimierung - Netzwerkplanung
    Provisioning Virtual Private Networks under Traffic Uncertainty (Altin & Amaldi & Belotti & Pinar [2005])
  7. Metrische Ungleichungen
    Metric Inequalities and the Network Loading Problem (Avella & Mattia & Sassano [2004])
  8. Facetten des Netzwerk Design Polyeders
    k-partition-based facets of the network design problem (Agarwal [2006])
  9. Approximationsalgorithmus für das "Mautgebührenmodell"
    An Approximation Algorithm for Stackelberg Network Pricing (Roch, Savard & Marcotte [2005])
  10. Erweitertes "Mautgebührenmodell" (inkl. Netzdimensionierung)
    Joint Design and Pricing on a Network (Brotcorne, Labbé, Marcotte & Savard [2003])
  11. Uberblick über Bilevel Programming
    Bilevel and Multilevel Programming: A Bibliography Review (Vicente & Calamai [1994])
    Bilevel Programming: A Survey (Colson, Marcotte & Savard [2005])
  12. Einführung und Optimierung eines Zonenpreissystems
    Design of Zone Tariff Systems in Public Transport (Hamacher & Schöbel [2004])

Kontakte

 
Sprechstunde
 Raum Telefon email
Prof. Dr. Dr. h.c. Martin Grötschel n.V. MA 302 84185-210 groetschelzib.de
Marika Neumann n.V. ZIB 84185-294 marika.neumannzib.de
Christian Raack n.V. ZIB 84185-369 raackzib.de
Thomas Schlechte n.V. ZIB 84185-139 schlechtezib.de

Zuletzt aktualisiert: 12. Januar 2007