Bei der Umlaufbildung werden die Fahrplanfahrtabschnitte des Modells verplant, die entstehenden Umläufe fahren also nacheinander Fahrplanfahrtabschnitte ab. Zu verplanen sind entweder alle oder alle aktiven oder orthogonal dazu alle oder alle noch nicht in der Zielumlaufversion in Umläufen gebundenen Fahrplanfahrtabschnitte (Anwendung: Parameter der Umlaufbildung). Vor Aufbau des Graphen wird das Problem in unabhängig zu bearbeitende Teilprobleme, sogenannte Partitionen, zerlegt. Eine Partition besteht aus allen Fahrplanfahrtabschnitten, denen dieselbe Fahrzeugkombination zugeordnet ist. Die Zerlegung in diese Teilprobleme ist möglich, da ein Umlauf immer von genau einer Fahrzeugkombination absolviert wird, also innerhalb des Umlaufs kein Wechsel des Fahrzeugs stattfindet. Auch die Fahrplanfahrtabschnitte, die keine Fahrzeugkombination besitzen, bilden zusammen eine Partition. Für jede Partition werden alle weiteren Verfahrensschritte getrennt durchgeführt. Es wird also jeweils ein eigener Graph aufgebaut, gelöst und das Ergebnis in Umläufe dekomponiert.
Optional kann die Umlaufbildung noch weiter partitioniert werden nach Betreiber, Verkehrssystem und Linie (Anwendung: Parameter der Umlaufbildung). Wird beispielsweise ein gleicher Betreiber für die Folgefahrt gefordert, wird zusätzlich nach Betreibern partitioniert. In diesem Fall enthält jedes Teilproblem und somit jeder resultierende Umlauf nur Fahrplanfahrtabschnitte einer Fahrzeugkombination und eines Betreibers, es kann also kein Betreiberwechsel innerhalb eines Umlaufs stattfinden. Innerhalb des Verfahrens wird ein eigener Graph für jede Kombination aus Fahrzeugkombination und Betreiber aufgebaut und die weiteren Verfahrensschritte separat für jeden einzelnen dieser Graphen durchgeführt. Abbildung 195 zeigt die Partitionierung an einem Beispiel. Hier gibt es Fahrplanfahrtabschnitte mit den Fahrzeugkombinationen Gelenkbus, Standardbus und Tram. Fahrplanfahrtabschnitte mit Gelenkbus werden von den Betreibern 1 und 2 gefahren, Fahrplanfahrtabschnitte mit der Tram nur vom Betreiber 1. Wird die Umlaufbildung zusätzlich nach Betreibern partitioniert, so werden insgesamt also fünf Graphen aufgebaut, für die jeweils getrennt das Flussproblem und die Dekomposition zu Umläufen durchgeführt wird.
Abbildung 195: Beispiel für Partitionierung nach Fahrzeugkombination und Betreiber
|
Hinweis: Kapazitätsrestriktionen in Depots können nur dann berücksichtigt werden, wenn der Graph nicht weiter als nach der Fahrzeugkombination partitioniert wird, wenn also keine der Optionen Gleicher Betreiber für Folgefahrt, Gleiches Verkehrssystem für Folgefahrt oder Gleiche Linie für Folgefahrt gewählt ist. Der Grund hierfür ist, dass Kapazitäten in Depots jeweils pro Fahrzeugkombination definiert werden. Erfolgt eine noch detailliertere Partitionierung zum Beispiel nach Betreibern, so hat das Verfahren keine Möglichkeit, die Kapazität noch weiter bis auf die Ebene Fahrzeugkombination x Betreiber aufzuteilen. |
