Was ist MILP-Modellierung?
Die gemischt-ganzzahlige lineare Programmierung (Mixed-Integer Linear Programming, MILP) ist eines der leistungsfähigsten Werkzeuge des Operations Research. Sie ermöglicht es, komplexe Entscheidungsprobleme mathematisch exakt zu formulieren und mit Hilfe spezialisierter Solver-Software beweisbar optimale Lösungen zu berechnen. Im Kern besteht ein MILP-Modell aus einer linearen Zielfunktion, die unter einer Menge linearer Nebenbedingungen optimiert wird, wobei einige oder alle Entscheidungsvariablen ganzzahlige Werte annehmen müssen.
Im Kontext der Verkehrsplanung und Disposition bedeutet dies: Jede Entscheidung – ob ein bestimmter Bus eine bestimmte Fahrt übernimmt, ob ein Fahrer einem bestimmten Dienst zugewiesen wird, ob ein Zug an einem bestimmten Bahnhof hält – wird als binäre Variable modelliert. Die Zielfunktion minimiert typischerweise die Gesamtkosten, maximiert die Servicequalität oder optimiert eine Kombination beider Kriterien. Die Nebenbedingungen stellen sicher, dass alle betrieblichen, gesetzlichen und tarifvertraglichen Vorgaben eingehalten werden.
Der entscheidende Vorteil gegenüber heuristischen Verfahren liegt in der Optimalitätsgarantie: Ein MILP-Solver liefert nicht nur eine gute Lösung, sondern beweist mathematisch, wie nah diese am theoretischen Optimum liegt. Diese Transparenz ist besonders in regulierten Branchen wie dem öffentlichen Personennahverkehr von unschätzbarem Wert, da Planungsentscheidungen gegenüber Aufsichtsbehörden und Aufgabenträgern nachvollziehbar begründet werden müssen.
minimize cTx + dTy
subject to
Ax + By ≤ b
x ≥ 0 // Kontinuierliche Variablen
y ∈ ℤn // Ganzzahlige Variablen
// Verkehrsanwendung: Fahrzeugzuordnung
minimize ∑ cij · xij
∑j xij = 1 ∀ i ∈ Fahrten
xij ∈ {0,1}
MILP im Verkehrs- und Transportwesen
Unsere MILP-Modelle adressieren die gesamte Bandbreite der Verkehrsplanung – von der strategischen Netzplanung bis zur operativen Echtzeitdisposition.
Fahrzeugumlaufplanung
Optimale Zuordnung von Fahrzeugen zu Fahrplanfahrten unter Minimierung von Leerfahrten und Fahrzeugbedarf. Berücksichtigung von Depotkapazitäten, Fahrzeugtyp-Kompatibilitäten und E-Bus-Ladeanforderungen. Das resultierende Vehicle Scheduling Problem (VSP) wird als Set-Partitioning-Modell formuliert.
Dienstplanung
Erstellung ArbZG-konformer Fahrerdienste durch Column-Generation-basierte MILP-Modelle. Berücksichtigung von Pausenregelungen, Schichtlängen, Qualifikationsanforderungen und Tarifverträgen. Integration mit der Dienst- und Personalplanung für ganzheitliche Optimierung.
Netzplanung
Strategische Optimierung von Liniennetzen, Haltestellenstandorten und Taktfrequenzen. Multi-Objective-Modelle balancieren Betriebskosten, Fahrgastabdeckung und Umsteigehaeufigkeit. Szenarioanalysen ermöglichen fundierte Investitionsentscheidungen für Verkehrsverbünde.
Schienenersatzverkehr
Automatisierte Planung von SEV-Bussen bei Streckensperrungen. MILP-Modelle optimieren Fahrzeugeinsatz, Routenführung und Fahrpläne unter Berücksichtigung der verbleibenden Schienenkapazitäten und der erwarteten Fahrgastnachfrage.
Werkstattplanung
Optimale Terminierung von Wartungsarbeiten und Zuordnung zu Werkstattkapazitäten. MILP-Modelle berücksichtigen Hebebühnen-Verfügbarkeit, Personalqualifikationen und Ersatzteillogistik.
Triebfahrzeugplanung
Rolling-Stock-Assignment für Schienenverkehrsunternehmen. MILP-Modelle weisen Triebfahrzeuge und Wagengarnituren unter Berücksichtigung von Kapazitätsanforderungen, Werkstattintervallen und Kupplungskompatibilitäten optimal zu.
Fortgeschrittene MILP-Formulierungen
Die Qualität einer MILP-Lösung hängt maßgeblich von der Modellformulierung ab. Wir setzen auf bewährte Techniken aus der akademischen Forschung und jahrelanger Praxiserfahrung, um Modelle zu entwickeln, die sowohl mathematisch elegant als auch computertechnisch effizient lösbar sind.
Tight Formulations: Durch die Wahl geeigneter Formulierungen minimieren wir den Integrality Gap – die Differenz zwischen LP-Relaxation und ganzzahliger Optimallösung. Dies beschleunigt den Branch-and-Bound-Prozess erheblich und ermöglicht die Lösung größerer Instanzen in kürzerer Zeit.
Valid Inequalities: Zusätzliche Schnittebenen (Cutting Planes) verschärfen die LP-Relaxation und reduzieren den Suchraum. Wir entwickeln problemspezifische Cuts, die die Struktur des Verkehrsplanungsproblems ausnutzen, beispielsweise Subtour-Elimination-Constraints oder Clique-Inequalities.
Symmetry Breaking: Viele Verkehrsplanungsprobleme weisen Symmetrien auf – beispielsweise sind identische Fahrzeuge austauschbar. Durch gezielte Symmetriebrechung reduzieren wir den Suchraum und vermeiden redundante Berechnungen, was die Lösungszeit um Größenordnungen verkürzen kann.
minimize ∑r∈R cr · λr
subject to
∑r∈R air · λr = 1 ∀ i ∈ T
λr ∈ {0,1} ∀ r ∈ R
// Symmetry Breaking
yk ≥ yk+1 ∀ k ∈ K
Industrielle MILP-Solver im Einsatz
Die Leistungsfähigkeit moderner MILP-Solver hat sich in den letzten zwei Jahrzehnten um den Faktor 10.000 verbessert – eine Kombination aus algorithmischen Fortschritten und Hardware-Entwicklung. Wir nutzen diese Technologie, um Verkehrsplanungsprobleme zu lösen, die noch vor wenigen Jahren als praktisch unlösbar galten.
Unsere Solver-Integration umfasst die automatische Parametrierung, Warm-Start-Strategien mit Lösungen aus vorherigen Planungsläufen, Callback-Funktionen für die Integration problemspezifischer Heuristiken und die parallele Nutzung mehrerer Solver-Kerne. Durch die enge Verzahnung von Modellierung und Solver-Konfiguration erreichen wir Lösungszeiten, die eine Echtzeit-Disposition ermöglichen.
Für Kunden, die keine kommerziellen Solver-Lizenzen erwerben möchten, bieten wir Lösungen auf Basis von Open-Source-Solvern wie HiGHS und SCIP an. Diese erreichen für viele praxisrelevante Problemgrößen vergleichbare Ergebnisse und ermöglichen eine kosteneffiziente Implementierung unserer mathematischen Optimierung.
Kommerzieller Solver
IBM Solver
Open Source
Akademischer Solver
MILP-basierte Busumlaufplanung
Ein konkretes Anwendungsbeispiel verdeutlicht die Leistungsfähigkeit unserer MILP-Modellierung: Ein Verkehrsunternehmen mit einer umfangreichen Busflotte und hunderten täglichen Fahrplanfahrten suchte nach einer Möglichkeit, die manuelle Umlaufplanung zu automatisieren und gleichzeitig die Betriebskosten zu senken.
Unser MILP-Modell formuliert das Problem als Multi-Depot Vehicle Scheduling Problem (MDVSP) mit zusätzlichen Nebenbedingungen für E-Bus-Ladung, Fahrzeugtyp-Kompatibilität und Werkstattintervalle. Die Zielfunktion minimiert eine gewichtete Kombination aus Fahrzeugbedarf, Leerkilometern und Energiekosten. Das resultierende Modell umfasst tausende binäre Variablen und wird durch unseren optimierten Solver-Stack in wenigen Minuten gelöst.
Die Ergebnisse sprechen für sich: signifikante Reduktion des Fahrzeugbedarfs, deutliche Senkung der Leerkilometer und eine vollständige Automatisierung des Planungsprozesses. Die Planer können sich nun auf die Qualitätssicherung und Szenarioanalyse konzentrieren, statt Stunden mit manueller Zuordnung zu verbringen. Weitere Erfolgsgeschichten finden Sie in unseren Case Studies.
"Die MILP-basierte Umlaufplanung hat unsere Erwartungen übertroffen. Die mathematische Nachvollziehbarkeit der Ergebnisse gibt uns die Sicherheit, dass wir tatsächlich das Optimum erreichen."