Das Beste aus beiden Welten
In der Praxis der Verkehrsoptimierung stehen Planer oft vor einem Dilemma: Exakte Verfahren wie MILP liefern beweisbar optimale Lösungen, benötigen aber für große Instanzen inakzeptable Rechenzeiten. Metaheuristiken sind schnell, bieten aber keine Qualitätsgarantie. Hybride Ansätze – auch Matheuristiken genannt – lösen dieses Dilemma, indem sie die Stärken beider Paradigmen vereinen.
Das Grundprinzip ist einfach: Ein heuristischer Rahmen steuert den Gesamtprozess und definiert, welche Teilprobleme wann und wie gelöst werden. Die eigentliche Optimierung der Teilprobleme übernimmt ein exakter Solver (MILP oder CP), der innerhalb des definierten Teilraums beweisbar optimale Lösungen findet. Durch die geschickte Wahl der Teilprobleme und die iterative Verbesserung der Gesamtlösung erreichen Matheuristiken eine Lösungsqualität, die nahe am globalen Optimum liegt.
Für die Verkehrsplanung sind hybride Ansätze besonders wertvoll, da sie die Skalierbarkeit von Heuristiken mit der Präzision exakter Verfahren verbinden. Dies ermöglicht die Optimierung großer Verkehrsnetze mit hunderten Linien und tausenden Fahrten – bei einer Lösungsqualität, die manuelle Planung und reine Heuristiken deutlich übertrifft.
function fixAndOptimize(x0):
x = x0
for partition Pk ∈ Partitions:
// Fixiere Variablen außerhalb P_k
fix(x[i] = x0[i]) ∀ i ∉ Pk
// Optimiere Teilproblem exakt
x[Pk] = MILP_solve(subproblem)
if improved: update x0
return xbest
Hybride Optimierungsmethoden
Unsere hybriden Ansätze kombinieren verschiedene Optimierungsparadigmen für maximale Effektivität in der Verkehrsplanung.
Fix-and-Optimize
Iterative Verbesserung durch abwechselndes Fixieren und Optimieren von Variablengruppen. Partitionierung nach Depots, Linien oder Zeitfenstern. Besonders effektiv für die ÖPNV-Umlaufplanung.
Local Branching
Einschränkung des Suchraums durch Hamming-Distanz-Constraints zur aktuellen Lösung. Der MILP-Solver sucht innerhalb einer definierten Nachbarschaft nach Verbesserungen. Kontrollierte Exploration des Lösungsraums.
MILP-basierte LNS
Large Neighborhood Search mit MILP-Solver als Repair-Operator. Destroy-Operatoren entfernen Teile der Lösung, der MILP-Solver rekonstruiert sie optimal. Kombination der Flexibilität von LNS mit der Präzision exakter Verfahren.
Kernel Search
Identifikation eines Kerns vielversprechender Variablen durch LP-Relaxation. Iterative Erweiterung des Kerns und exakte Optimierung. Besonders effektiv für Set-Covering-Probleme in der Dienstplanung.
Proximity Search
Suche nach Lösungen in der Nähe der aktuellen besten Lösung durch zusätzliche Cutoff-Constraints. Der MILP-Solver wird gezwungen, eine bessere Lösung zu finden oder zu beweisen, dass keine existiert.
Relaxation-Induced Cuts
Nutzung von LP-Relaxationslösungen zur Generierung von Schnittebenen, die den Suchraum einschränken. Kombination mit Dekompositionsverfahren für skalierbare Lösungen.
Integrierte Fahrzeug- und Dienstplanung
Die simultane Optimierung von Fahrzeugumläufen und Dienstplänen ist eines der anspruchsvollsten Probleme der Verkehrsplanung. Traditionell werden beide Planungsschritte sequentiell durchgeführt – erst die Umlaufplanung, dann die Dienstplanung. Diese Vorgehensweise führt jedoch zu suboptimalen Gesamtlösungen, da die Wechselwirkungen zwischen beiden Planungsebenen nicht berücksichtigt werden.
Unsere hybriden Ansätze lösen dieses Problem durch iterative Integration: Fix-and-Optimize alterniert zwischen der Optimierung der Fahrzeugumläufe (bei fixierten Diensten) und der Optimierung der Dienste (bei fixierten Umläufen). In jedem Schritt wird ein MILP-Solver eingesetzt, der das jeweilige Teilproblem exakt löst. Die Konvergenz wird durch die systematische Rotation der Partitionen sichergestellt.
Die Ergebnisse zeigen konsistent signifikante Verbesserungen gegenüber der sequentiellen Planung: weniger Fahrzeuge, weniger Leerkilometer und bessere Dienstqualität. Diese Einsparungen rechtfertigen den höheren Rechenaufwand und die komplexere Implementierung der integrierten Planung.
"Der hybride Ansatz hat uns ermöglicht, Fahrzeugumläufe und Dienstpläne erstmals integriert zu optimieren. Die Einsparungen gegenüber der bisherigen sequentiellen Planung sind beachtlich."