Deklarative Problemmodellierung
Constraint Programming (CP) unterscheidet sich fundamental von klassischen Optimierungsansätzen: Statt einen Lösungsalgorithmus zu implementieren, beschreibt der Modellierer das Problem durch seine Struktur – Variablen, deren mögliche Wertebereiche (Domänen) und die Beziehungen zwischen ihnen (Constraints). Der CP-Solver übernimmt dann die Aufgabe, eine oder alle Lösungen zu finden, die sämtliche Constraints gleichzeitig erfüllen.
Dieser deklarative Ansatz bietet im Verkehrsbereich erhebliche Vorteile: Komplexe betriebliche Regeln – wie Pausenvorschriften, Qualifikationsanforderungen oder Fahrzeugtyp-Restriktionen – lassen sich direkt und intuitiv als Constraints formulieren, ohne sie in lineare Ungleichungen umwandeln zu müssen. Dies macht CP-Modelle leichter verständlich, wartbar und erweiterbar als äquivalente MILP-Formulierungen.
Die Kernstärke von CP liegt in der Constraint Propagation: Sobald eine Variable einen Wert zugewiesen bekommt, werden die Domänen aller verbundenen Variablen automatisch eingeschränkt. Dieser Prozess erkennt Inkonsistenzen frühzeitig und reduziert den Suchraum drastisch. In Kombination mit intelligenten Suchstrategien ermöglicht dies die effiziente Lösung auch sehr großer Scheduling-Probleme im öffentlichen Verkehr.
variables
start[i] ∈ [6:00, 22:00] ∀ i ∈ Dienste
end[i] ∈ [6:00, 22:00] ∀ i ∈ Dienste
assign[i,j] ∈ {0,1}
constraints
NoOverlap(intervals) // Keine Überlappung
Cumulative(res, cap) // Kapazität
end[i] - start[i] ≤ 9h // ArbZG
AllDifferent(assign[*,j])
CP-Anwendungen im Verkehrswesen
Constraint Programming entfaltet seine Stärken überall dort, wo komplexe logische Bedingungen und Scheduling-Anforderungen aufeinandertreffen.
Dienstplanung
NoOverlap-Constraints garantieren, dass kein Fahrer gleichzeitig zwei Dienste ausführt. Cumulative-Constraints stellen sicher, dass die Personalkapazität an jedem Standort eingehalten wird. ArbZG-Regeln werden als direkte Constraints modelliert, nicht als lineare Approximationen.
Fahrzeug-Scheduling
Interval-Variablen modellieren Fahrten als zeitliche Intervalle mit Start, Ende und Dauer. Sequenz-Constraints definieren die Reihenfolge der Fahrten pro Fahrzeug. Optional-Intervals ermöglichen die flexible Zuordnung von Reservefahrzeugen bei Bedarf.
Werkstattplanung
Cumulative-Constraints modellieren die begrenzte Anzahl von Hebebühnen und Werkstattplätzen. Precedence-Constraints definieren die Reihenfolge von Arbeitsschritten. Die CP-Modellierung ermöglicht eine realitätsnahe Abbildung komplexer Werkstattprozesse.
Fahrplankoordination
Synchronisations-Constraints stellen Anschlussgarantien zwischen verschiedenen Verkehrsmitteln sicher. Minimale und maximale Umsteigezeiten werden als Distanz-Constraints zwischen Ankunfts- und Abfahrtsintervallen modelliert.
Ressourcenzuordnung
AllDifferent-Constraints verhindern Doppelzuweisungen. Table-Constraints definieren erlaubte Kombinationen von Fahrzeugtyp, Strecke und Fahrerprofil. Element-Constraints verknüpfen Zuordnungsentscheidungen mit kostenrelevanten Parametern.
Echtzeit-Disposition
CP-SAT ermöglicht schnelle Re-Optimierung bei Störungen. Warm-Start mit der aktuellen Lösung und inkrementelle Constraint-Änderungen erlauben Reaktionszeiten im Sekundenbereich für die Echtzeit-Disposition im Schienenverkehr.
Google OR-Tools CP-SAT
Google OR-Tools CP-SAT ist einer der leistungsfähigsten Constraint-Programming-Solver der Welt und bildet das Rückgrat unserer CP-basierten Optimierungslösungen. Der Solver kombiniert Constraint Propagation mit SAT-Solving-Techniken (Boolean Satisfiability) und erzielt dadurch beeindruckende Performance auf einer breiten Klasse von Scheduling- und Zuordnungsproblemen.
CP-SAT unterstützt nativ Interval-Variablen, NoOverlap-Constraints und Cumulative-Constraints – genau die Bausteine, die für die Modellierung von Verkehrsplanungsproblemen benötigt werden. Durch die Integration von Linear-Relaxation-Techniken kann CP-SAT auch Optimierungsprobleme mit linearen Zielfunktionen effizient lösen und liefert dabei Optimalitätsbeweise ähnlich wie MILP-Solver.
Die enge Integration mit Python und C++ ermöglicht eine nahtlose Einbettung in unsere Optimierungsplattform. Durch die Open-Source-Lizenz von OR-Tools entstehen keine zusätzlichen Lizenzkosten für unsere Kunden, was CP-SAT zu einer besonders kosteneffizienten Alternative zu kommerziellen Solvern macht.
"Die CP-basierte Dienstplanung hat uns ermöglicht, komplexe Arbeitszeitregeln direkt zu modellieren, ohne Kompromisse bei der Lösungsqualität einzugehen. Die Ergebnisse sind nicht nur zulässig, sondern auch für unsere Betriebsräte transparent nachvollziehbar."
CP + MILP: Das Beste aus beiden Welten
In der Praxis kombinieren wir häufig Constraint Programming mit MILP-Modellierung, um die jeweiligen Stärken beider Paradigmen zu nutzen. CP eignet sich hervorragend für die Generierung zulässiger Lösungen und die Modellierung komplexer logischer Bedingungen, während MILP bei der Kostenoptimierung und der Berechnung von Optimalitätsschranken überlegen ist.
Ein typisches Beispiel ist die integrierte Fahrzeug- und Dienstplanung: Das Fahrzeugumlaufproblem wird als MILP formuliert, während die darauf aufbauende Dienstplanung als CP-Modell modelliert wird. Die Kopplung erfolgt über Lagrange-Relaxation oder iterative Verfahren, bei denen die Lösungen beider Modelle schrittweise aufeinander abgestimmt werden.
Diese hybriden Ansätze ermöglichen es uns, Probleme zu lösen, die weder mit reinem CP noch mit reinem MILP effizient lösbar wären. Die Kombination beider Paradigmen ist ein aktives Forschungsfeld, in dem wir durch unsere Zusammenarbeit mit Universitäten und FFG-Forschungsprojekten stets am Puls der neuesten Entwicklungen sind.
Scheduling
Kostenoptimierung
Nachbarschaftssuche
Integrierte Lösung