Ein Projekt innerhalb des HPCN TTNs CAPRICE, Industriesektorgruppe Scheduling and Logistics, gefördert durch das Informationstechnologie-Programm ESPRIT der EU This page in English

Ziele

Die Anwendung

Die folgende Abbildung zeigt das Netz der Straßenbahn- und Buslinien, das dem Fahrplan der Bremer Straßenbahn AG (BSAG) zugrundeliegt. Insgesamt sind hier täglich mehr als 800 Schichten und 1300 FahrerInnen zu planen.

Ein Dienstplan definiert für jeden Tag des Planungshorizonts die Dienste (Schichten), die von einer Gruppe von FahrerInnen zu fahren sind. Der zugrundeliegende Turnus gibt das Dienst-Frei-Schema an. Das Problem Dienstreihenfolgeplanung besteht darin,

• die Menge aller zu bedienenden Dienste auf die Gruppen von FahrerInnen gemäß ihrer Qualifikation und Präferenzen zu verteilen und dabei
• die Dienste innerhalb eines Dienstplans so in Reihenfolge zu bringen, daß
• gesetzliche, tarifvertragliche Regelungen und Betriebsvereinbarungen, insbesondere zu Ruhezeiten und maximalen Arbeitszeiten in bestimmten Zeiträumen,
• arbeitswissenschaftliche Kriterien sowie
• sozialverträgliche Kriterien (d.h. individuelle Präferenzen der Gruppen)
berücksichtigt werden.

Veränderungen in Randbedingungen, wie z.B.

• die Einführung neuer Linien oder neue Taktzeiten mit den dadurch bedingten Veränderungen in der Dienstmasse,
• Veränderungen des Mitarbeiterstamms, wie z.B. eine Fahrergruppe mit neuen Arbeitszeitregelungen,
• ein verändertes Profil einer Fahrergruppe hinsichtlich Qualifikation und Präferenzen,
• neue gesetzliche oder tarifvertragliche Regelungen oder Betriebsvereinbarungen, die neue Arten von Turnussen oder Dienstreihenfolgen gestatten,
• neue arbeitsmedizinische Erkenntnisse bezüglich der Reihenfolgebildung, die die Krankenquote oder die langfristige Arbeitsfähigkeit zu verbessern versprechen,

Vorteile

Was bietet ein solches System für Vorteile?

• höhere Produktivität der Planer.
• wirtschaftlicherer Personaleinsatz durch
• eine geringere Krankenrate,
• Verbesserung der langfristigen Arbeitsfähigkeit der Mitarbeiter,
• neue Flexibilität bei der Mittelfristplanung der Personalressourcen,
• verbesserte Personalauslastung,
• Minimierung von Überstunden,
• höhere Transparenz der Dienstpläne für das Management wie für die FahrerInnen,

gerechtere Dienstpläne
• Erhöhung der Mitarbeiterzufriedenheit durch Berücksichtigung ihrer Präferenzen. In der Personaldisposition sind dadurch weniger Planänderungen nötig, die Disponenten werden entlastet.

• Der Planer spezifiziert und modifiziert die Fahrerprofile (Qualifikationen und Präferenzen) der Fahrergruppen, die zeitraubende Dienstzuweisung auf deren Dienstpläne übernimmt die automatische Optimierung, deren Vorschläge der Planer ggf. nachbearbeitet. Die Arbeit der Planer kann sich darauf konzentrieren, in einem interaktiven Prozeß mit dem System Planungsalternativen zu erarbeiten und zu bewerten. Er erhält so den Freiraum, auf die individuellen Bedürfnisse der FahrerInnen einzugehen und die Dienstplanung als Ganzes zu verbessern, um die Belastung der Schichtarbeit zu mildern. Mitarbeiter, die ernstgenommen werden und am Planungsprozeß partizipieren können, sind motivierter und zufriedener.
• Die Planungsqualität wird gesichert durch die Abbildung einer großen Zahl von Zielkriterien, die es erlauben, wirtschaftliche, arbeitsmedizinische sowie sozialverträgliche Aspekte der Lösung zu beeinflussen und zu kontrollieren.
• Automatische Turnus-Optimierung. Das System schlägt Turnusse vor, die die zu bedienende Dienstmasse optimal mit den Fahrerprofilen abgleicht.
• Optimierung der Planungsstellgrößen durch Parameterstudien. Viele der Planungsziele widerstreben einander, so wie beispielsweise lange nächtliche Ruhezeiten vs. lange Wochenruhezeiten oder die Empfehlungen der Arbeitswissenschaft vs. der Wunsch nach besonders langen Freiblöcken. In diesen Fällen kann durch Parameterstudien ein akzeptabler Kompromiß gefunden werden.
• Unterstützung bei der Einrichtung und bei der Auswertung einer Simulation durch eine Benutzungsoberfläche, die Randbedingungen, Kenngrößen und Eigenschaften der Lösungen graphisch visualisiert. Die MDI-Technologie und der objektorientierte Ansatz erlauben es, Lösungen zu allen Zeiten komfortabel zu bewerten, zu vergleichen und zu manipulieren.

Das Konzept

Im Projekt DISSY wird eine Methodik, die vom Partner HUB im vom BMBF geförderten Projekt PARALOR für die Dienstplanung bei Fluggesellschaften entwickelt wurde, auf die Lösung des Dienstreihenfolgeproblems im ÖPNV übertragen. Um die Vergleichbarkeit von Lösungen aus Parameterstudien zu gewährleisten, ist eine hohe Qualität der Lösungen Voraussetzung. Die Komplexität des Optimierungsproblems (die Anzahl der Variablen wie die der beteiligten Optimierungskriterien) erfordert leistungsfähige Techniken des Operations Research wie die sogenannten Metaheuristiken, die jedoch hohe Laufzeiten (je nach Einstellung bis zu mehreren Stunden) aufweisen. Um trotzdem vernünftige Antwortzeiten garantieren zu können, wird HPCN-Technologie verwendet. Die Parallelisierung der Optimierungsverfahren für die Flugdienstplanung wies je nach Parallelisierungstechnik eine Effizienz von 60% bis nahezu 100% auf bis zu 16 Prozessoren auf einem Parsytec GigaCluster PowerPlus Parallelrechner auf. Vergleichbare Resultate können für ein PC-Cluster erwartet werden, eine Architektur, die ebenso kostengünstig wie leicht skalierbar ist, um für den Einsatz eben z.B. in ÖPNV-Unternehmen geeignet zu sein. Das System wird durch eine Test-Installation beim Partner BSAG evaluiert und optimiert; es beruht auf dem VDV-Datenmodell und ist somit genauso bei anderen ÖPNV-Unternehmen einsetzbar.
 

Weitere Informationen
 

Download	DISSY Whitepaper, präsentiert auf der CASPT 2000, Berlin [PDF, ca. 268 kB]
Download	DISSY-Demonstrator [Microsoft Powerpoint Präsentation, ca. 390 kB]
Links	Crew Scheduling, Staff Rostering, and Transportation Local Search Algorithms and Metaheuristics Parallele und verteilte Algorithmen

 

Projektpartner

Kontakt