Divide et Impera: Große Probleme zerlegen
Viele praxisrelevante Verkehrsplanungsprobleme sind schlicht zu groß, um sie als monolithisches MILP-Modell zu lösen. Die integrierte Fahrzeug- und Dienstplanung eines großen Verkehrsunternehmens kann Millionen von Variablen und Nebenbedingungen umfassen – weit jenseits der Kapazität selbst modernster Solver. Dekompositionsverfahren lösen dieses Problem durch intelligente Zerlegung.
Das Grundprinzip ist elegant: Das Gesamtproblem wird in ein Masterproblem und mehrere Subprobleme zerlegt, die iterativ gelöst werden. Das Masterproblem koordiniert die Gesamtlösung, während die Subprobleme die detaillierte Optimierung der Teilbereiche übernehmen. Durch den systematischen Austausch von Dualwerten und Lösungsinformationen konvergiert das Verfahren gegen die optimale Gesamtlösung.
Im Verkehrsbereich nutzen wir Dekompositionsverfahren insbesondere für die integrierte Planung: Fahrzeugumläufe und Dienstpläne werden nicht sequentiell, sondern simultan optimiert. Die Zerlegung erfolgt typischerweise entlang der natürlichen Problemstruktur – beispielsweise nach Depots, Linien oder Planungstagen. Dies ermöglicht die Lösung von Problemen, die monolithisch nicht handhabbar wären.
Master Problem (Restricted):
min ∑ crλr
s.t. ∑ airλr = 1 ∀ i
Pricing Subproblem:
min c̄r = cr - ∑ πiair
// Finde Spalte mit negativen reduzierten Kosten
repeat until c̄r ≥ 0 ∀ r
Dekompositionstechniken im Überblick
Jedes Verfahren nutzt eine spezifische Problemstruktur aus – die Wahl der richtigen Dekomposition ist entscheidend für die Performance.
Column Generation
Iterative Erzeugung von Variablen (Spalten) für das Masterproblem. Das Pricing-Subproblem identifiziert neue vielversprechende Umläufe oder Dienste. Standard-Verfahren für Vehicle und Crew Scheduling im ÖPNV.
Benders Decomposition
Zerlegung in ein ganzzahliges Masterproblem und ein kontinuierliches Subproblem. Optimality und Feasibility Cuts schärfen das Masterproblem iterativ. Ideal für Netzwerkdesign und Schienenverkehrsplanung.
Lagrange-Relaxation
Relaxation koppelnder Nebenbedingungen durch Einführung von Lagrange-Multiplikatoren. Liefert untere Schranken für das Originalproblem und ermöglicht die unabhängige Lösung der resultierenden Teilprobleme.
Dantzig-Wolfe-Dekomposition
Reformulierung des Originalproblems durch Darstellung der zulässigen Menge als konvexe Kombination von Extrempunkten. Bildet die theoretische Grundlage für Column-Generation-Verfahren in der ÖPNV-Disposition.
Branch-and-Price
Kombination von Column Generation mit Branch-and-Bound für ganzzahlige Optimalität. An jedem Knoten des Branch-and-Bound-Baums wird ein Column-Generation-Verfahren ausgeführt. State-of-the-Art für Dienstplanung.
Cross-Decomposition
Kombination von Benders- und Lagrange-Dekomposition für Probleme mit gemischter Struktur. Primal- und Dual-Informationen werden zwischen den Verfahren ausgetauscht, was die Konvergenz beschleunigt.
Column Generation für die Dienstplanung
Die Dienstplanung im ÖPNV ist ein Paradebeispiel für den erfolgreichen Einsatz von Column Generation. Das Problem besteht darin, aus einer Menge von Fahrplanfahrten eine minimale Anzahl von Diensten zu bilden, die alle Fahrten abdecken und sämtliche arbeitsrechtlichen und tarifvertraglichen Vorgaben einhalten.
Die Anzahl möglicher Dienste ist astronomisch groß – bei einem mittelgroßen Verkehrsunternehmen können es Milliarden sein. Column Generation löst dieses Problem elegant: Das Masterproblem (Set Covering) wählt die kostenoptimale Teilmenge der Dienste aus, während das Pricing-Subproblem (Shortest Path mit Ressourcen-Constraints) neue vielversprechende Dienste generiert.
Durch die Kombination mit Branch-and-Bound (Branch-and-Price) garantieren wir ganzzahlige Optimalität. Unsere Implementierung nutzt fortgeschrittene Techniken wie Stabilisierung, Dual-Variable-Fixing und paralleles Pricing, um die Konvergenz zu beschleunigen und auch große Instanzen in akzeptabler Zeit zu lösen.
"Durch Column Generation konnten wir die integrierte Fahrzeug- und Dienstplanung erstmals simultan optimieren. Die Ergebnisse zeigen signifikante Einsparungen gegenüber der bisherigen sequentiellen Planung."
Skalierung durch parallele Dekomposition
Ein entscheidender Vorteil von Dekompositionsverfahren ist ihre natürliche Eignung für Parallelisierung. Die Subprobleme sind oft unabhängig voneinander lösbar und können daher auf mehrere Prozessorkerne oder sogar verteilte Rechnercluster aufgeteilt werden.
Bei der Column Generation können mehrere Pricing-Subprobleme gleichzeitig gelöst werden, was die Rechenzeit pro Iteration drastisch reduziert. Bei der Lagrange-Relaxation können die entkoppelten Teilprobleme vollständig parallel bearbeitet werden. Diese Parallelisierung ermöglicht die Lösung von Probleminstanzen, die auf einem einzelnen Prozessor Stunden oder Tage benötigen würden.
Unsere Cloud-basierte Optimierungsplattform nutzt diese Parallelisierungsmöglichkeiten voll aus: Je nach Problemgröße werden automatisch zusätzliche Rechenressourcen allokiert, um die gewünschte Lösungszeit einzuhalten. Dies ermöglicht eine flexible Skalierung von der Tagesplanung bis zur strategischen Jahresplanung.
Pricing
Skalierung
Architektur
Ressourcen