>
') ;?>
') ;?>
'); ?>
Next: Ergebnisse
Up: Fahrereinsatzplanung im ÖPNV
Previous: Problemstellung
Als Modell für dieses Problem kommt ein Lineares Programm als
Set-Partitioning-Formulierung mit Nebenbedingungen zum Einsatz.
Hierbei wird aus der Menge aller möglichen
Dienste für die Fahrer die Kombination gewählt, die zum einen alle
Dienstelemente überdeckt und zum anderen alle Nebenbedingungen
einhält, wobei möglichst geringe Kosten verursacht werden.
Problematisch hierbei ist jedoch die schon bei einer geringen Anzahl an
Dienstelementen sehr große Anzahl an möglichen Diensten. Daher wird zur
Lösung ein Branch and Price Ansatz verwendet, wobei als Subproblem zur
Erzeugung der benötigten Dienste ein Kürzeste-Wege-Problem gelöst wird.
Einige Heuristiken zur Beschleunigung dieser Suche wurden bereits erprobt und
erfolgreich implementiert. Allein durch den Einsatz alternativer
Labeleliminationsverfahren konnte ein Geschwindigkeitszuwachs von bis zu 30%
erzielt werden.
') ;?>
') ;?>
'); ?>