Integrative Umlauf- und Dienstplanbildung


Bei der operativen Planung von Verkehrsbetrieben spielen die Umlauf­planung und Dienstplanung eine wichtige Rolle. In der Regel wird als erstes ein Umlauf­plan gebildet, der dann als Grundlage für die nachfol­gende Dienstplanung dient. Dieses Vorgehen hat den Vorteil, dass die Optimierungsaufgabe für die Um­laufplanbildung sich gut formalisieren lässt und in den meisten Fällen mit ma­thematischen Algorithmen exakt lösbar ist. Dadurch ist eine rein automatische Umlaufplanbildung mög­lich, die einen optimalen Umlaufplan liefert.
 
Optimaler Umlaufplan bedeutet in diesem Kontext, dass mit dem Um­laufplan das Minimum an Fahrzeugen, oder, allgemeiner, das Minimum  an Kosten, er­reicht wird, mit denen ein bestehender Fahrplan bedient werden kann. Diese Kosten schließen aber noch keine Personalkosten ein, die erst bei der Dienst­planbildung berücksichtigt werden können.
 
Die Dienstplanbildung ist um einiges komplizierter als die Umlaufplan­bildung. Die zu bildenden Dienste müssen einer ganzen Reihe der ge­setzlichen und be­trieblichen Anforderungen, wie etwa Pausenregelun­gen, genügen, was die ent­sprechende mathematische Aufgabe so kom­pliziert macht, dass eine exakte Aufgabelösung bei akzeptablen Lö­sungszeiten unmöglich wird. Deswegen wer­den hier unterschiedliche heuristische Techniken angewendet, aber auch heu­ristische Verfahren sind schwierig. Die fest vorgegebenen Rahmen von dem optimalen Um­laufplan lassen nicht nur einen optimalen, sondern oft auch einen ak­zeptablen Dienstplan nicht zu. Die Ursache ist offensichtlich: Die Opti­mie­rungsziele der Dienstplanbildung stehen in Widerspruch mit den Optimierungs­zielen der Umlaufplanbildung. Gerade die einzuhaltenden Pausenregelungen wären ein deutliches Beispiel dafür.
 
Um dieser Situation vorzubeugen, wird versucht schon bei der Umlauf­planbil­dung die Interessen der Dienstplanung mit zu berücksichti­gen, damit die gebildeten Umläufe besser für die Dienstplanung geeig­net sind. Dabei wird entweder  die Kostenmatrix manipuliert, um z.B. die Bildung von pausenreichen Umläufen zu begünstigen, oder, wie es in Praxis oft gemacht wird, ein Zwischen­schritt eingeschaltet, bei dem die gebildeten Umläufe mit Pausen bereichert werden. Diese Maßnahmen, oft mit einem großen manuellen und kosteninten­siven Aufwand ver­bunden, schaffen zwar Abhilfe, lösen das Problem aber nicht. Der grundsätzliche Umstand, dass bei der Umlaufplanbildung die vielfälti­gen und komplizierten Anforderungen der nachfolgenden Dienstplanbil­dung nur be­dingt berücksichtigt werden können, führt dazu, dass der optimierte Umlaufplan zum Hindernis für die Dienstplanbildung und –optimierung wird. Als Folge sind die gebildeten Dienste von einer schlechten Qualität, das Optimierungspotential der gesamten Planung bleibt unerschöpft und es wird eine aufwendige manu­elle Anpassung des Dienstplans benötigt.
 
Einen Ausweg aus dieser Situation bietet  eine integrative Umlauf- und Dienst­planbildung, bei der die beiden Planungsaufgaben gleichzeitig gelöst werden.
 
Das Dienstplanbildungs- und -optimierungssystem  MACSSY (Multiobjective Automatic Crew Scheduling System) bzw. Archeops realisiert das Prinzip einer integrativen Umlauf- und Dienstplanbildung und erlaubt nicht nur die Anzahl der Dienste im Vergleich zur manuellen Bildung wesentlich zu reduzieren, sondern auch die Dienstplanqualität sowie -effizienz entscheidend zu verbessern. Aufgrund der Integrativität sind die vorangehende Umlaufplanbildung mit anschließender Umlaufplananpassung nicht mehr notwendig.
 

Optimierungsprozess

Der Optimierungsprozessablauf wird vom Anwender aus mehreren Teiloptimierungen zusammen gestellt, die während des Optimierungsprozesses ausgeführt werden soll. In einer Teiloptimierung wird definiert, welche Zielfunktion für die Dienstplanoptimierung und welche Qualitätsauswertungsfunktionen benutzt werden sollen, wie aufwendig die Berechnungen durchgeführt werden sollen und bei Bedarf auch zusätzliche vom Anwender definierte Einschränkungen auf Fahrtenverknüpfungen, die während der Teiloptimierung gelten sollen.
 
Jede Teiloptimierung hat einen Optimierungsgegenstand, der bestimmt, worauf sich die Teiloptimierung bezieht. Es gibt folgende Optimierungsgegenstände:
 
-   Umlaufplan

Es wird ein optimaler Umlaufplan gebildet. Normalerweise ist diese Optimierung nicht notwendig, wird aber manchmal benutzt mit dem Zweck, anschließend die gesamte Fahrtenmasse umlaufweise zwischen verschiedenen Betriebshöfen zu verteilen und dann den Optimierungsprozess für jeden einzelnen Betriebshof zu starten. Sinngemäß sollte so eine Teiloptimierung nicht mit anderen kombiniert werden.

-   Dienstplan

Es wird ein Dienstplan gebildet bzw. optimiert.  Wenn eine Teiloptimierung mit diesem Optimierungsgegenstand auf einem vorhandenen Dienstplan aufgesetzt wird, dann wird in der Regel der entsprechende Umlaufplan im Laufe der Optimierung geändert, wenn das dem Dienstplan zugute kommt.

Das oberste Optimierungsziel bei einer solchen Teiloptimierung ist die Anzahl der Dienste. Die Qualität der Dienste spielt dabei keine Rolle. Diese Teiloptimierung sollte die erste in der Teiloptimierungsfolge des Prozesses sein gefolgt von Qualität- und Effizienzteiloptimierungen.

-   Qualität

Es wird die Qualität des Dienstplans optimiert. Es ist dabei keine Erhöhung der Anzahl der Dienste möglich, es sei denn, solche Erhöhung wurde extra bei der Teiloptimierungsdefinition zugelassen . Was als Qualität des Dienstplans gilt, wird mittels Überwachungswerte bei der Teiloptimierungsdefinition beschrieben. Es können mehrere unterschiedliche Qualitäts-Teiloptimierungen hintereinander folgen, um sukzessiv die Qualitätsverbesserung  zu erreichen.

-   Effizienz

Es wird die Effizienz gesteigert durch eine Minimierung der unproduktiven Zeit, wo der Bus ohne Fahrgäste ist, also entweder gerade eine Leerfahrt macht oder parkt. Eine Teiloptimierung mit diesem Optimierungsgegenstand sollte die letzte in der Teiloptimierungsfolge sein. Die in den vorangehenden Teiloptimierungen erreichte Dienstplanqualität bleibt bei dieser Teiloptimierung erhalten.

Qualität und Überwachungswerte 


Im MICSS-Konzept wird die Qualität eines Umlauf- und Dienst­plans als eine Menge von hierarchisch geordneten Werten, genannt Überwachungs­werte, verstanden, wo jeder Wert eine Charakteristik des Umlauf- und Dienstplans aus einer bestimmten Sicht darstellt. Diese Überwachungswerte können ver­schiedenste Aspekte sowohl des Um­lauf- als auch Dienstplans in Betracht nehmen. Mit dieser Definition von Qualität des Umlauf- und Dienstplans wird es möglich, zwei ver­schiedene Umlauf- und Dienstpläne zu vergleichen: besser ist der Plan, dessen Überwachungswert auf irgendeiner Ebene besser ist, voraus­ge­setzt, dass auf höheren Hierarchieebenen die Werte gleich sind.
 
Hier sind nur einige Beispiele für mögliche Überwachungswerte:
 
- Anzahl der Dienste mit einer Dienstqualität kleiner als ein Grenzwert 

- Anzahl der Dienste mit einer Längenabweichung von einem Idealwert größer als ein Grenzwert

- Anzahl der geteilten Dienste

- Bezahlte Arbeitszeit 
 
Die meisten während des Optimierungsprozesses geltenden Überwachungswerte werden vom Anwender in der Teiloptimierungsdefinition vorgegeben. Es gibt aber auch systeminterne Überwachungs­werte, die von außen nicht oder nur bedingt beeinfluss­bar sind. Der Überwa­chungswert mit dem höchsten Rang in der Hierar­chie ist die Anzahl der unzu­lässigen Dienste. Das bedeutet, dass keine Änderung des Umlauf- und Dienst­plans akzeptiert wird, wenn sie die Anzahl der unzulässigen Dienste erhöht. Umgekehrt wird der Umlauf- und Dienstplan im Laufe des Optimierungsprozes­ses geändert, wenn dabei die Anzahl der unzulässigen Dienste reduziert wird. Diese Eigen­schaft ermöglicht die Fähigkeit von MACSSY bzw. Archeops die un­zuläs­sigen Ausgangspläne zu korrigieren.
 
Der zweite Überwachungswert in der Hierarchie ist die Anzahl der Dienste. Auf diesen Überwachungswert kann der Anwender einen ge­wissen Einfluss neh­men, und zwar kann er bestimmen, dass die Anzahl der Dienste bis zu einem bestimmten Grad erhöht werden kann, wenn das einen anderen anwenderspe­zifischen Überwachungswert positiv beein­flusst. Vor allem findet diese Möglich­keit eine  Anwendung in den Fäl­len, wo sich die Qualität eines oder mehrerer Dienste bei der erreichten Anzahl der Dienste nicht verbessern lässt. Eine andere Möglichkeit ist die zu erreichende Anzahl der Dienste vorzugeben, wenn der Anwender genau weiß, wie viele Dienste er braucht.

 

Startdialog

Der Optimierungsprozess wird mittels eines Startdialogs gestartet, wo der Anwender eine Möglichkeit hat, die Parameter und Einstellungen des Optimierungsprozesses zu ändern.