Menu
Labs

Labs (4)

Syn Lab

Forschungs- und Entwicklungsthemen

  • Basismethoden zur Modellierung und Lösung diskret-kontinuierlich-stochastischer Optimierungsprobleme

Projektbeschreibung

Ein wesentliches Ziel des Forschungscampus MODAL besteht in der Entwicklung und Nutzung von mathematischen Synergien zwischen den einzelnen Labs des Verbunds. Die Gebiete der diskreten, kontinuierlichen und stochastischen Optimierung sollen stärker miteinander vernetzt werden. Dies entspricht den Anforderungen der Praxis, in der diese Aspekte in der Regel gemeinsam auftreten. Der Forschungscampus erschließt relevante Anwendungsfälle und bietet die Möglichkeit der Übertragung und der gemeinsamen Entwicklung von Herangehensweisen, Standards, Datenpools, Methoden und Software. Industriepartner aus verschiedenen Branchen können dabei leichter miteinander kooperieren als mit ihren direkten Konkurrenten.

Ein erster Ansatzpunkt für eine solche Integration ist die Entwicklung von Methoden zur Lösung einer allgemeinen Klasse von diskret-stochastischen Optimierungsproblemen. Beim Entwurf von Infrastrukturnetzen wird oft eine Topologie gesucht, die eine Menge von betrieblichen Szenarien mit einer gewissen Wahrscheinlichkeit abdeckt. Wir planen im ersten Schritt die Entwicklung von Methoden der allgemeinen ganzzahligen diskret-stochastischen Constraint Programmierung (CIP) und deren Anbindung an weit verbreitete CIP-Löser, hier das am ZIB entwickelte Framework SCIP, um auf diese Weise ein mächtiges Standardwerkzeug zu schaffen. Dies entwickelt einen unmittelbaren Nutzen vor allem, aber nicht nur für das GasLab. Im weiteren Verlauf werden weitere Synergien identifiziert und genutzt.

Leitung: Prof. Dr. Thorsten Koch

 

Read more...

Gas Lab

Forschungs- und Entwicklungsthemen

  • Entwicklung eines mathematischen Modells für die dynamische Nominierungsvalidierung
  • Überführung dieses Modells in lösbare Teilaufgaben
  • Erforschung von Lösungsverfahren für diese Teilaufgaben
  • Ermittlung, Bereitstellung und Bereinigung der notwendigen Daten
  • Entwicklung eines prototypischen Optimierungsverfahrens

Projektbeschreibung

Das deutsche Hochdruck-Gas-Pipelinenetz hat eine Gesamtlänge von ca. 50.000 km. Pro Monat werden darüber bis zu 120 Mrd. kW/h Energie transportiert. Dies entspricht etwa dem 10-fachen der Stromerzeugung aller deutschen Kernkraftwerke. Erdgas trägt mit über 20% zur Gesamtenergieversorgung Deutschlands bei und ist damit neben Kraftstoffen der wichtigste Energieträger. Entsprechend ist das Gastransportsystem von hoher gesellschaftlicher und politischer Relevanz. Ausbaumaßnahmen haben einen langen Zeithorizont und sind ebenso wie Unterhaltung und Betrieb kostenintensiv. Die optimale Ausnutzung der vorhandenen Kapazitäten bietet daher hohe Sparpotentiale.

Die beteiligten Lieferanten und Abnehmer müssen derzeit dem Transportnetzbetreiber etwa einen Tag vor dem Bedarf ihre erwarteten Gasabnahmemengen melden. Diesen Vorgang bezeichnet man als Nominierung. Der Netzbetreiber steuert dann sein Netz entsprechend, dabei hat die Versorgungssicherheit höchste Priorität. Gleichzeitig wird ein Teil des Gases im Netz verwendet, um die Energie für den Transport zu liefern. Dem Netzbetreiber obliegt es nun, eine größtmögliche Menge von Bestellungen bei gleichzeitig möglichst geringem Eigenverbrauch zu bedienen. Die Steuerung des Netzes ist hochgradig nicht-linear komplex und durch das Speicherverhalten des Netzes zeitlich schwer zu überblicken. Es besteht immer das Risiko, dass eine jetzt getroffene Entscheidung zu einem Engpass zu einem späteren Zeitpunkt führt. Daher besteht der wichtigste Aspekt des Projekts darin, frühzeitig kritische Situationen zu erkennen und Gegenmaßnahmen zu ergreifen.

MODAL will die Grundlagen für die Entwicklung einer dynamischen Nominierungsvalidierung erforschen. Diese würde dann ausgehend vom aktuellen Netzzustand und den vorliegenden Nominierungen einen optimierten Steuerungsplan für das Netz für die kommenden 1 bis 3 Tage berechnen. Damit wäre die Grundlage für ein automatisches Verfahren zur Steuerung von Gasnetzen gelegt.

Ein solches Verfahren würde vielfältigen Nutzen generieren: Die Versorgungssicherheit würde deutlich erhöht, da nun frühzeitig gewarnt werden kann, wenn eine nicht betreibbare Situation im Netz zu entstehen droht. Dabei wären die Algorithmen in der Lage, Lösungen für Steuerungsprobleme zu finden, die für menschliche Disponenten schwer oder gar nicht erkennbar sind. Aus demselben Grund würde sich auch die Kapazität des Gasnetzes erhöhen, so dass Transportaufgaben durchführbar werden, die derzeit nicht überschaubar sind. Dies würde besonders die Bundesnetzagentur begrüßen, da es hiermit möglich wäre, freie Kapazitäten sehr kurzfristig anzubieten und auszunutzen.

Durch die Berechnung eines optimierten Steuerungsplanes wird es möglich sein, Betriebskosten einzusparen: Schon eine Reduktion der Transportenergiekosten um 10% würde der Leistung eines Kernkraftwerks entsprechen. Letztlich würden solche Verfahren auch wesentlich bessere Reaktionsmöglichkeiten auf geopolitische Ereignisse, wie verminderte Gaslieferungen aus Russland bieten.

Die Online-Berechnung einer optimierten Fahrweise für ein großes Gas-Transportnetz mit einem 1-3 -tägigen Zeithorizont ist eine mathematisch derzeit unlösbare Aufgabe. Ziel des GasLabs ist es, ein prototypisches Verfahren zu entwickeln, das anhand realer Daten die automatische Berechnung eines Steuerungsplans mit ausreichender Genauigkeit ermöglicht. Die Herausforderung dieses Projektes liegt gleichermaßen darin, geeignete Modelle zu entwerfen, neue Optimierungsalgorithmen zu entwickeln und einen Weg zu finden, die notwendigen, aber extrem umfangreichen Daten in geeigneter Weise bereitzustellen.

Projektleitung: Prof. Dr. Thorsten Koch

Read more...

Med Lab


Forschungs- und Entwicklungsthemen

  • Effiziente und robuste mathematische Verfahren zur Qualitätssicherung, Klassifikation und Mustererkennung in sensiblen medizinischen Massendaten
  • Integration moderner Auswertungsalgorithmen und neuartiger Datenbanktechnologien zur Massendaten-Analyse
  • Aufbau eines auf optimierter Auswertung von Massendaten beruhenden Diagnose-Portfolios


Projektbeschreibung

In Deutschland erkranken etwa 450.000 Menschen jährlich neu an Krebs. Eine frühe Diagnose sowie die schnelle Erfolgskontrolle von Therapiemaßnahmen können für diese Patienten lebensrettend sein. Dennoch nutzt lediglich ein geringer Teil der Bevölkerung Angebote der Früherkennung, weil zunächst selten Symptome spürbar und häufig Intimbereiche betroffen sind. Zudem sind die Unter-suchungen oft umständlich, teils schmerzhaft und werden in der Regel als bedrohlich empfunden.

Zusammen mit ihren medizinischen Partnern entwickelte die Biocomputing Group an der FU eine innovative Analyse-Pipeline, die erstmals die frühzeitige Erkennung von schwer diagnostizierbaren Krebsarten mittels einer kostengünstigen und unkomplizierten Blutuntersuchung erlaubt. Krebserkrankungen können so routinemäßig untersucht, bereits vor dem Auftreten von Symptomen diagnostiziert, im Schweregrad bestimmt und der Effekt von Therapien frühzeitig nachgewiesen werden.

Die neuartige Diagnostik beruht auf der massenspektometrischen Analyse von Proteinmustern im Blut (proteombasierte fingerprints). Durch die anschließende Auswertung der Ergebnisse mittels innovativer Algorithmen werden relevante Muster im Proteom sichtbar, die kranke von gesunden bzw. von Patienten mit anderen Krankheiten unterscheiden. Im Rahmen des hier vorgestellten Vorhabens soll das bestehende Verfahren deutlich weiterentwickelt und auf weitere Krebserkrankungen ausgedehnt werden. Dies geschieht in enger Zusammenarbeit mit bestehenden klinischen Kooperationspartnern, die die notwendige medizinische Expertise ins Projekt einbringen.

In einer ersten, akademisch orientierten Studie mit mehr als 1000 Patienten und einer weiteren, praxisorientierten Machbarkeitsstudie mit mehr als 150 Patienten konnte der Erfolg der Methode gezeigt werden, der sich in der Entwicklung von diagnostischen fingerprints für fünf verschiedene Krebsarten niederschlägt. Diese zweite, unter den realen Bedingungen des Klinikalltages durchgeführte Vorstudie hat zwei neue Problemfelder aufgezeigt: Zum einen sind die bisher verwendeten datenträgergestützten Datenbanksysteme bei den entstehenden riesigen Datenmengen (mehrere GigaByte pro Patient) für
komplexe Online-Analysen aufgrund der vergleichsweise langsamen Zugriffszeiten ungeeignet. Zum anderen haben wir bei der Implementierung der bestehenden Diagnose-Pipeline im klinischen Alltag festgestellt, dass eine sehr sorgfältige Probenbehandlung nach vorgeschriebenen Standard Operating Protocols (SOP) erfolgen muss, um reproduzierbare Ergebnisse zu erzielen. Die Einhaltung des SOP in der Praxis erfordert jedoch speziell geschultes Personal, was die praktische Anwendung derzeit auf Kompetenzzentren beschränkt. Bei Nichteinhaltung des SOPs entstehen bei der Weiterverarbeitung innerhalb des mehrstufigen Analyse-Prozesses Degradationseffekte, die die Diagnose verfälschen können.

Die Partner Biocomputing/FU, SAP, CiT und Inbion verfügen über die notwendige Kompetenz zur Überwindung dieser Problemfelder: Die SAP SE hat vor einiger Zeit mit der In-Memory Computing Engine eine neue Technologie auf den Markt gebracht, die es erlaubt, alle vorhandenen Daten vollständig im Speicher in Form einer Datenbank vorzuhalten und direkt innerhalb dieser Datenbank zu analysieren. Dadurch eliminiert diese Technologie den Flaschenhals des Datentransportes zwischen Datenträger und Speicher nahezu vollständig. Die CiT GmbH verfügt seit vielen Jahren über international herausragende Erfahrungen im Modellieren von biologischen Abbau-Prozessen. Biocomputing/FU, Inbion und CiT werden zusammen in der Lage sein, die beschriebenen Degradationseffekte zu modellieren und schließlich in den nachgelagerten Analyseschritten algorithmisch so zu behandeln, dass verlässliche Ergebnisse mit optimal-relaxiertem SOP möglich sind.

Projektleitung: Prof. Dr. Tim Conrad

Read more...

Bahn Lab

Im BahnLab wird in Kooperation des Konrad-Zuse-Zentrum und der DB Fernverkehr AG Software zur Automatisierung der Planungs- und Steuerungsprozesse des Eisenbahnsystems durch Verwendung leistungsfähiger mathematischer Optimierungsverfahren erforscht und entwickelt.

Das deutsche Eisenbahnnetz ist mit rund 33.500 km Schiene und 5.400 Personenbahnhöfen das größte in ganz Europa. Auf diesem Netz müssen täglich ca. 27.000 Zugfahrten im Nah- und Fernverkehr und ca. 5000 Zugfahrten im Güterverkehr mit etwa 5,5 Millionen Reisenden verplant werden. Das System ist damit von hoher gesellschaftlicher, verkehrs- und umweltpolitischer Relevanz. Ausbaumaßnahmen haben einen langen Zeithorizont und Unterhaltung und Betrieb sind kostenintensiv; deshalb ist die optimale Ausnutzung der vorhandenen Kapazitäten die Grundvoraussetzung zur Steigerung der Attraktivität des Bahnverkehrs und zur Erhöhung der Wettbewerbsfähigkeit der Bahnindustrie – nicht nur in Deutschland.
In vielen Bereichen werden die Abläufe noch manuell geplant und gesteuert. Die Anwendung von mathematischen Planungsmethoden ist bisher gering. Dies ist auf die Komplexität des Eisenbahnsystems in Verbindung mit der bisher nicht ausreichenden Leistungsfähigkeit mathematischer Lösungsmethoden zurückzuführen.

Bereits seit April 2009 arbeitet das Konrad-Zuse Institut mit großem Erfolg mit der DB Fernverkehr AG innerhalb eines Forschungsprojekts  zusammen und konnte bemerkenswerte Ergebnisse im Bereich der Umlaufoptimierung im Personenfernverkehr erzielen. In dieser Kooperation wurde das Optimierungstool ROTOR entwickelt, mit dem erstmals die strategische Umlaufplanung für den Fernverkehr in Deutschland automatisiert und optimiert werden kann. Damit ist ein Durchbruch bei der Behandlung eines relevanten Problems mit Signalwirkung für die gesamte Prozesskette erzielt worden. Der effiziente Einsatz des Rollmaterials im Schienenverkehr ist eine der größten und dynamischsten Herausforderungen eines Eisenbahnunternehmens.
Auf dem aktuellen Stand werden Umlaufpläne für Fahrpläne, die als zyklischen Musterwochen bereitliegen, optimiert, wobei die folgenden relevanten und andererseits schwierigen Aspekte berücksichtigt werden:

  • effizienter Fahrzeugeinsatz,
  • Instandhaltung der Fahrzeuge mit Berücksichtigung der Kapazitäten in den Werken,
  • Berücksichtigung von Gleichförmigkeiten im Fahrplan und Übertragung dieser auf den Umlaufplan.

Eine detaillierte Beschreibung zur Umsetzung findet sich beispielsweise in „Integrated Optimization of Rolling Stock Rotations for Intercity Railways“

Des Weiteren gibt das Optimierungstool seit kurzem auch die Möglichkeit zur Anpassung an bestehende Umlaufpläne mit geringen Unterschieden zum neuen Fahrplan, die beispielsweise aus Baustellen und dem Hinzufügen sowie Entfernen von Zugfahrten rühren. Bei dieser Anpassungsoptimierung wird zusätzlich das Ziel einer möglichst geringen Abweichung zum zugrunde liegenden Umlaufplan berücksichtigt („Re-optimization of Rolling Stock
Rotations“
). Auf diese Weise müssen bereits geplante Instandhaltungen sowie Leerfahrten nicht neu geplant und Ressourcen nicht neu beantragt werden. Zudem kann die auf die Umlaufplanung aufbauende Dienstplanung weitestgehend auf den neuen Umlaufplan übertragen werden.

Innerhalb des Forschungscampus MODAL zielen wir auf eine vollständige Unterlegung der Planungs- und Steuerungsprozesse in einem Eisenbahnsystem durch leistungsfähige mathematische Optimierungsverfahren ab. Dafür sind zunächst die folgenden Ziele im Bereich der Umlaufplanung angesetzt, welche sich zudem auf weitere Planungsprozesse ausweiten:

  • Tagesscharfe Umlaufplanung
  • Robuste Umlaufplanung
  • Angebotsorientierte Umlaufplanung

Wir planen eine Bearbeitung der genannten Themen in drei aufeinander aufbauenden Forschungsphasen von 4-5 Jahren. Jedes dieser Projekte umfasst Arbeitspakete zur Spezifikation, Datenerfassung und -analyse, Systemanalyse, Modellierung, algorithmischen Entwicklung, Implementierung, Tests, Systemintegration und der Entwicklung von Strategien zur nachhaltigen Wartung, Weiterentwicklung und zum Ergebnistransfer auf weitere Anwendungsgebiete.

Tagesscharfe Umlaufplanung

Je näher die Modelle für die Optimierung an der Praxis sind, umso wertvoller sind die Lösungen der angewendeten Optimierungsverfahren. Aktuell werden bei der Umlaufoptimierung sogenannte Musterwochen betrachtet. Aufgrund von wenigen Änderungen im Fahrplan zwischen verschiedenen Wochen im Jahr ist diese Art der Optimierung zielführend. In der Praxis müssen jedoch auch die Übergänge zwischen verschiedenen Planungsperioden (z.B. Sommer- zu Winterfahrplan und umgekehrt), Feiertage, Ferien, Baustellen, usw. berücksichtigt werden. Deshalb ist das erste Ziel im BahnLab des Forschungscampus MODAL eine kalendertagsscharfe Planung herzuleiten. Dies ist eine sehr bedeutende und schwierige Aufgabe, die in der Industrie bisher nicht mit Methoden der mathematischen Optimierung gelöst wird.

Der entscheidende Unterschied der kalendertagsscharfen Umlaufplanung zur bereits untersuchten, auf Musterwochen basierenden Umlaufplanung ist der Planungshorizont, welcher sich nun über einen Kalenderzeitraum (z.B. drei Wochen) erstreckt und nicht mehr zyklisch ist.
Zur Vorbereitung des Forschungscampus wurden diesbezüglich bereits die bestehenden Daten so aufbereitet, dass ein Testszenario für einen Übergang zwischen verschiedenen Fahrplanperioden entstand. Das Szenario soll für Testzwecke zunächst so weit wie möglich mit Hilfe der bereits bestehenden Methodik zur Anpassungsoptimierung auf bereits bestehende Umlaufpläne für einen entsprechenden Übergang angepasst werden. Das Optimierungsproblem besteht dabei in der Berechnung zweier nicht-zyklischer Umlaufpläne, die möglichst ähnlich zu den bestehenden Umlaufplänen sind, sodass eine aus taktischer Sicht maximal reibungsfreie Überleitung der Fahrplanperioden gewährleistet werden kann. Diesbezüglich mussten einige Softwareerweiterungen vorgenommen werden, um von einer zyklischen zu einer nicht-zyklischen Planung zu gelangen und die Schnittstelle anzupassen. Im ersten Ansatz wurden dabei nur die grundlegenden Umlauf-Anforderungen berücksichtigt. Erst im nächsten Schritt soll auf weitere Anforderungen, wie Wartungsregeln und Gleichförmigkeit, eingegangen werden.
 

Robuste Umlaufplanung

Ziel der robusten Umlaufplanung ist es, Verspätungen im Betriebsablauf entgegenzuwirken. Während man bei der Umlaufplanung auf direkte Verspätungen im Betriebsablauf keinen Einfluss nehmen kann, kann man jedoch die Folgeverspätungen minimieren. Eine mathematische Optimierung ist zunächst jedoch darauf ausgelegt, durch eher knappe Übergänge zwischen den Zugfahrten, Einspareffekte in Bezug auf die Fahrzeuganzahl zu erzielen, was die Propagierung von Zugfolgeverspätungen allerdings verstärkt. Unter Berücksichtigung des Aspekts der Folgeverspätungen können diese zum Beispiel durch gezielt eingesetzte Puffer-Zeiten verringert werden, dessen Allokation und Dimensionierung optimal bestimmt werden muss.
Erste Erfolge sind im Luftverkehr sichtbar. Bei der Eisenbahn besteht im Unterschied zur Luftfahrt allerdings das zusätzliche Problem, dass sich die Züge sehr stark gegenseitig beeinflussen.

Die bestehenden Software ROTOR wurde bereits in Bezug auf potentielle Robustheit der Umlaufpläne untersucht, indem die sogenannten Wendezeiten gezielt variiert wurden. Wendezeiten geben an, wie lange ein Fahrzeug zwischen zwei Fahrgastfahrten mindestens stehen muss, und stellen eine wichtige und sehr sensible Stellschraube in der Umlaufoptimierung dar. Die Erhöhung einer Wendezeit kann mit einer Pufferzeit zwischen zwei Zugfahrten verglichen werden und damit die Robustheit eines Umlaufplans erhöhen, während bei geringen Wendezeiten Zugverspätungen viel leichter von einem Zug auf einen anderen propagiert werden und somit die Robustheit verringert wird. Im Gegenzug hat die Erhöhung von Wendezeiten jedoch auch direkten Einfluss auf den Fahrzeugbedarf für einen Umlaufplan. Da die Fahrzeuge den wichtigsten
Kostenanteil darstellen, darf die Minimierung der Anzahl der Fahrzeuge keineswegs vernachlässigt werden. Durch eine multikriterielle Optimierung kann ein geeigneter Kompromiss gefunden werden, bei dem die Wendezeiten bei minimaler Fahrzeuganzahl gezielt maximiert werden.
Bisherige Tests haben gezeigt, dass die bestehende Software auch mit erheblichen Variationen in den Wendezeiten umgehen kann und sinnvolle Lösungen produziert. Im nächsten Schritt muss ein stochastisches Modell erstellt werden, das Verspätungen simuliert, um insbesondere ein Maß für die Robustheit eines Umlaufplanes definieren und berechnen zu können.
 

Angebotsorientierte Umlaufplanung

In der angebotsorientierten Umlaufplanung geht es um die Frage der Fahrzeugwahl für die im Fahrplan angebotenen Zugfahrten. Diesbezüglich sollen Nachfrageprognosen aus dem Marketing mit einbezogen werden. Das heißt, es wird mit statischen oder idealerweise mit elastischen Nachfragemodellen gearbeitet. Zudem soll die Umlaufplanung auch im Zusammenhang der Fahrplanung betrachtet werden, welche den direkten Vorgänger der Umlaufplanung im Planungsprozess darstellt. In diesem Bereich ist das Weglassen und Hinzufügen sowie das Einkürzen und Verlängern von Zugfahrten von Interesse.

In der Vorbereitungsphase für den Forschungscampus MODAL wurde die bestehende Software dahingehend getestet und analysiert, ob die Verwendung von alternativen Zugkonfigurationen (z.B. Einfachtraktion, Doppeltraktion, 5-Wagen-Zug, 11-Wagen-Zug, usw.) als Variation der Passagierkapazität für Zugfahrten möglich ist. Des Weiteren wurde getestet, ob das Weglassen und Hinzufügen von Zugfahrten oder Teilen davon möglich ist und die Ergebnisse sinnvoll bleiben. Im Ergebnis können diese Fragestellungen im Wesentlichen mit der bestehenden Umlaufplanungssoftware bearbeitet werden. Weitere wichtige und offene Fragestellungen in der angebotsorientierten Umlaufplanung sind: Gibt es einen Kostenvorteil bei Veränderung von Abfahrts- und Ankunftszeiten? Gibt es einen Kostenvorteil durch Rekombination von ganzen oder Teilen von Zugfahrten?


Weitere Themen im Umfeld der Umlaufplanung, wie zum Beispiel die Disposition, bei der im laufenden Betrieb zusätzlich unvorhergesehene Störungen in Echtzeit zu bewältigen sind, oder die Integration mit vor- oder nachgelagerten Schritten der Fahrplanung oder Personaleinsatzplanung, werden diskutiert und bei gegebenen Erfolgsaussichten in die Forschung des BahnLabs einbezogen.

 

Leitung: Prof. Dr. Ralf Borndörfer

Read more...
Subscribe to this RSS feed

Login