Algorithmen und Komplexität

ESPRIT-Projekt DISSY

Ein Projekt innerhalb des HPCN TTNs CAPRICE, gefördert durch das Informationstechnologie-Programm ESPRIT der EU

ESPRIT-Projekt

DISSY

Dienstreihenfolgeplanung im öffentlichen Nahverkehr

Dauer	1998/1/1 - 1999/2/28
Schlüsselwörter	Öffentlicher Personennahverkehr (ÖPNV), Dienstplanung, Turnus, Schichtarbeit, kombinatorische Optimierung, Personaleinsatzplanung, Simulation, Decision Support, verteiltes Rechnen
Technische Daten	Client/Server, MPI, MS Windows NT, Visual C++, ActiveX

Ziele

Im Projekt DISSY wird ein HPCN-basiertes Decision-Support-System für die Dienstreihenfolgeplanung im öffentlichen Personennahverkehr (ÖPNV) entwickelt und evaluiert. Das System erlaubt es, verschiedene Planungsszenarien zu simulieren und zu studieren, um die Personaleinsatzplanung besser auf neue Rahmenbedingungen anzupassen. Es vervielfacht die Produktivität der Planer in der Planungsabteilung und schafft Transparenz für das Management wie für die Bus- und StraßenbahnfahrerInnen. Die neue Planungsflexibilität wird öffentlichen Nahverkehrsunternehmen wie auch Industriebetrieben mit Schichtarbeit neue Impulse geben, ihre Personalplanungsprozesse zu verbessern.

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.

In herkömmlichen Systemen muß der Turnus manuell vorgegeben werden, insbesondere muß für jeden Tag, der kein freier Tag ist, in einem Dienstplan genau spezifiziert werden, welche Art von Dienst die Zuweisungsautomatik hier zuweisen soll. Dadurch wird das von der Zuweisungsautomatik zu lösende Optimierungsproblem einfach, aber für den Nutzer entsteht ein unverhältnismäßig hoher Aufwand beim Anpassen an neue Randbedingungen. Auch der Grad, bis zu dem die Dienstpläne optimiert werden können, ist hierdurch eingeschränkt.
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,

erfordern ein Werkzeug zur Entscheidungsunterstützung bei der Anpassung des Geschäftsprozesses an die neue Situation. Was-wäre-wenn-Studien und Simulationen sind nötig, um verschiedene Szenarien evaluieren und vergleichen und um den Einfluß von Stellgrößen und Abhängigkeiten zwischen verschiedenen Optimierungszielen untersuchen zu können. Kurzfristig verfügbare Planungsvarianten geben neue Ideen, den Betriebsablauf - in wirtschaftlicher Hinsicht wie in Hinblick auf die Mitarbeiterzufriedenheit - zu optimieren. Konkrete Planalternativen, neue Dienstplan- und Turnusarten können zwischen Planungsabteilung, Betriebsrat und Management auf der Basis gesicherter Information diskutiert werden.

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.

Wodurch werden diese Vorzüge erreicht?

• 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

Die Lösung kombinatorischer Optimierungsprobleme ist in Bereichen wie Logistik, Transport und Produktion der Schlüssel zu einem ökonomischen Einsatz der Ressourcen, zu einer Verbesserung der Effizienz von Prozessen oder zu einer Verbesserung der Produktqualität. Aufgrund der geforderten kurzen Antwortzeiten und der komplexen Gestalt von Werkzeugen zur Entscheidungsunterstützung, die eine automatische Optimierung von großen Problemeninstanzen erlauben, ist die Verwendbarkeit herkömmlicher sequentieller Rechnerarchitekturen stark eingeschränkt. Parallele und verteilte Systeme bieten die Möglichkeit,  auch große und komplexe Probleme mit der vereinten Leistung mehrerer Prozessoren, die durch ein schnelles Netzwerk verbunden sind, ökonomisch zu lösen.

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 technische Informationen:

• Crew Scheduling, Staff Rostering, and Transportation
• Local Search Algorithms and Metaheuristics
• Parallel and Distributed Algorithms

Projektpartner

Kontakt

Thomas Emden-Weinert  VSS Gesellschaft für Beratung, Projektmanagement, Informationstechnologien mbH  Am Fallturm 9  28359 Bremen  Tel.: [+49] (+421) 22003-803  Fax: [+49] (+421) 22003-50  E-mail: temdenwe@vss.com

Thomas Langhammer  Bremer Straßenbahn AG  Fachbereich B2: Fahr-, Umlauf-, Dienstplanung  Flughafendamm 12  28199 Bremen  Tel.: [+49] (+421) 5596-289  Fax: [+49] (+421) 5596-135  E-mail: bsag-b2@t-online.de

---

zuletzt geändert am 21.03.2006 (alkox-www)