Mathematische Modellierung im Crew Scheduling. Wie gelingt eine gerechte Schichtverteilung?


Bachelorarbeit, 2018
44 Seiten, Note: 1,3

Leseprobe

Inhaltsverzeichnis

Tabellenverzeichnis

Abbildungsverzeichnis

Symbolverzeichnis

1. Einleitung

2. Grundlagen des Crew Scheduling Problems
2.1. Wirtschaftlicher Hintergrund des Schienengüterverkehrs
2.2. Begriffe und Definitionen

3. Lösungsverfahren des Crew Scheduling Problems
3.1. Das Column Generation Verfahren
3.1.1. Masterproblem
3.1.2. Subproblem
3.2. Die Variable-Fixing Phase

4. Erweiterung des Crew Scheduling Problems
4.1. Vorteile der Erweiterung
4.2. Mathematische Modellierung der Erweiterung
4.2.1. Option 1: weiche Nebenbedingung
4.2.2. Option 2: Minimierung der Streuung
4.3. Auswirkungen der Erweiterung

5. Fazit

Literaturverzeichnis

Anhang

Tabellenverzeichnis

Tabelle 1: Beispielwerte fUr Schichtdauer, Losungsund Distrikzugehorigkeit

Tabelle 2: Berechnete Werte fUr die Hilfsvariable

Abbildungsverzeichnis

Abbildung 1: Beispielhafter Ablauf einer Schicht

Abbildung 2: Column Generation Verfahren mit Variable-Fixing Phase

Abbildung 3: Ein beispielhaftes Netzwerkmodell

Abbildung 4: Ablauf der Variable-Fixing Phase

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1. Einleitung

Die Erzeugung von Schichtplänen zur Planung des Personaleinsatzes, welche als Crew Scheduling bezeichnet wird, ist in vielen unterschiedlichen Branchen von Bedeutung. Um zulässige Schichtpläne kosteneffizient und schnell zu erzeugen, wird an der Entwicklung und Verbesserung softwarebasierter Lösungen gearbeitet. Dabei besteht die Herausforderung darin, einen optimalen Schichtplan unter Berücksichtigung aller Nebenbedingungen und Anforderungen zu generieren (Ernst et al., 2004). Der Fokus dieser Arbeit liegt ausschließlich auf dem Crew Scheduling Problem des Schienengüterverkehrs der Deutschen Bahn AG. Die Deutsche Bahn AG gilt als einer der größten Logistikund Transportdienstleister Europas (Deutsche Bahn, 2017a). Innerhalb des Konzerns ist das Unternehmen DB Cargo (bis 2016 war es DB Schenker) für den Schienengüterverkehr verantwortlich (DB Cargo, 2016). Im Jahr 2016 transportierte DB Cargo 277,4 Mio. Tonnen Güter, pro Tag wurden durchschnittlich 4.362 Züge eingesetzt. Das Schienennetz umfasst dabei mehr als 30.000 km (Deutsche Bahn, 2017b). Aufgrund dieser Größen ergibt sich ein komplexes und umfangreiches Crew Scheduling Problem, bei dem Schichten für mehrere tausend Besatzungsmitglieder generiert werden müssen (Jütte et al., 2011). Da der Schienengüterverkehr in Deutschland und Europa unter starkem Wettbewerbsdruck steht, ist es dort besonders wichtig, mögliches Optimierungspotenzial auszuschöpfen und die Kosten zu minimieren (Albers, 2009, S.1). Gleichzeitig gewinnen soziale Faktoren wie Mitarbeiterzufriedenheit und faire Arbeitsbedingungen innerhalb der Unternehmen immer mehr an Bedeutung (Malcherek, 2010, S.1). Das Ziel dieser Arbeit ist deshalb, das rein kostenorientierte Crew Scheduling Problem um einen sozialen Faktor zu erweitern. Bei diesem Faktor handelt es sich um die gerechte Verteilung der Schichtdauern, sodass ein möglichst fairer Schichtplan erzeugt wird. Alle Schichten sollen dabei ungefähr gleich lang sein und sehr kurze wie auch sehr lange Schichten vermieden werden. Bisher werden die Schichtdauern nur durch tarifliche und arbeitsrechtliche Vereinbarungen begrenzt und können dadurch bis zu 14 Stunden dauern (Jütte et al., 2011). Da sich insbesondere zu lange Schichten negativ auf das Wohlbefinden der Mitarbeiter auswirken können, werden zwei Erweiterungen zur Beeinflussung der Schichtdauern vorgeschlagen (Spurgeon, Harrington und Cooper, 1997): In der ersten Erweiterung wird eine Nebenbedingung eingeführt, die Minimalund Maximaldauern festlegt. Abweichungen von diesen nach unten oder oben werden in der Zielfunktion bestraft. Die zweite Erweiterung misst die Streuung der Schichtdauern und minimiert diese durch die Einführung von Straffaktoren. Grundlage für die Erweiterungen des Problems bildet eine von Jütte et al. (2011) entwickelte Software zur Lösung des Crew Scheduling Problems im Güterverkehr der Deutschen Bahn. Die im Rahmen dieser Arbeit getroffenen Aussagen beziehen sich auf das der Software zugrundeliegende Modell und Lösungsverfahren.

In Kapitel 2 werden weiterführende Informationen, Begriffe und Definitionen zum Verständnis des Crew Scheduling Problems dargelegt. Anschließend wird das erarbeitete Verfahren zur Lösung des Problems genauer erklärt. In Kapitel 4 werden mögliche Erweiterungen des Modells, deren Nutzen und Auswirkungen behandelt. Abschließend folgt im letzten Kapitel das Fazit mit einer Zusammenfassung der Ergebnisse, deren kritischer Betrachtung, sowie ein Ausblick.

2. Grundlagen des Crew Scheduling Problems

Zum besseren Verständnis der Problemstellung liefern die folgenden Abschnitte Informationen zur Einordnung des Problems und erläutern wichtige Begriffe und Definitionen.

2.1.Wirtschaftlicher Hintergrund des Schienengüterverkehrs

Der Schienengüterverkehr erbringt in Deutschland nach dem Straßengüterverkehr die zweitgrößte Transportleistung und macht damit dennoch nur 17% der gesamten Transportleistung aus (Statistisches Bundesamt Deutschland, 2017). Dabei baut der Straßenverkehr seinen Anteil an der Transportleistung kontinuierlich weiter aus, während der Anteil des Schienengüterverkehrs weitestgehend konstant bleibt. Für den Schienengüterverkehr entsteht dadurch ein hoher Wettbewerbsdruck. Zusätzlich zu dem Wettbewerbsdruck durch andere Formen des Güterverkehrs hat die Deutsche Bahn 2016 Marktanteile an andere Güterbahnen von Privatanbietern oder an Tochtergesellschaften ausländischer Staatsbahnen verloren (Deutsche Bahn, 2016a; Handelsblatt, 2017). Für die Deutsche Bahn ist es daher besonders relevant kosteneffizient zu wirtschaften, um sich gegenüber allen Konkurrenten behaupten zu können. Da Lohnkosten einen bedeutenden Anteil der Gesamtkosten ausmachen, kann Crew Scheduling durch effizient eingesetzte Mitarbeiter zu deutlichen Kostenreduktionen führen und zum wirtschaftlichen Erfolg des Unternehmens beitragen (Albers, 2009, S.1-2). Da DB Schenker bis 2006 das Crew Scheduling Problem noch manuell gelöst hat, sollte mit der Einführung einer softwarebasierten Lösung noch vorhandenes Optimierungspotential ausschöpft werden (Jütte et al., 2011). Dazu wurde die von Jütte et al. (2011) entwickelte Software (Triebfahrzeugführer-Einsatz-Optimierung – TEO) zur Lösung des Crew Scheduling Problems bei DB Schenker implementiert. Im Zuge dessen mussten über 100 gesetzliche und vertragliche Anforderungen eingehalten werden (Jütte et al., 2011). Eine beispielhafte Übersicht davon ist im Anhang zu sehen. Die einzuhaltenden Anforderungen sind unternehmens-, länderund tarifabhängig. Im Rahmen dieser Arbeit beziehen sich Aussagen bezüglich der arbeitsrechtlichen und vertraglichen Vereinbarungen auf das Verkehrsunternehmen Deutsche Bahn AG.

2.2. Begriffe und Definitionen

Im Folgenden werden einige Begrifflichkeiten und Definitionen eingeführt und erläutert.

Ein Fahrblock sind einzelne Zugbewegungen zwischen Stationen, die von einem Fahrer ausgeübt werden. Eine Schicht ist eine Abfolge von Fahrblöcken, die von einem Fahrer ausgeübt wird. Zwischen den Fahrblöcken einer Schicht können z.B. Pausenzeiten oder andere Aktivitäten liegen, die im Folgenden noch genauer beleuchtet werden. Ein Schienennetzwerk besteht aus verschiedenen Stationen, die gruppenweise einem Crew Distrikt zugeordnet sind. Einige dieser Stationen fungieren als Depot, das heißt sie stellen Startund Endpunkte von Schichten dar. Schichten müssen an einem Depot des gleichen Distrikts beginnen, an dem sie enden (Jütte et al., 2011; Albers, 2009, S.37). Schichtwechsel an Depots anderer Distrikte sind nicht möglich. Demnach sind Lösungen, die Schichten enthalten, die diese Bedingung nicht erfüllen, unzulässig. Ein vereinfachter Ablauf einer Schicht ist in Abbildung 1 zu sehen.

Die Schichtdauer ist die Zeit von Beginn bis Ende einer Schicht. Arbeitszeit bezeichnet die Zeit, in der Aktivitäten ausgeübt werden, die gesetzlich als Arbeit eingeordnet werden. Diese Zeit wird immer bezahlt. Zusätzlich jedoch werden auch Aktivitäten bezahlt, die nicht zur Arbeitszeit zählen, wie z.B. Leerlaufzeiten (Bengtsson et al., 2007, S.134).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Beispielhafter Ablauf einer Schicht

Eine Schicht umfasst eine Reihe von Tätigkeiten, die ein Fahrer ausüben muss. Die Haupttätigkeit besteht dabei aus dem Fahren der Züge. Darüber hinaus müssen jedoch folgende weitere Tätigkeiten ausgeführt werden:

An-und Abmeldung: Eine Schicht beginnt damit, dass sich der Fahrer in einem Depot anmeldet und endet sobald er sich dort wieder abmeldet. Diese Aktivität nimmt sehr wenig Zeit in Anspruch.

Zugbezogene Aufgaben: Unter zugbezogenen Aufgaben werden sowohl technische Anforderungen, wie z.B. das Ankoppeln der Züge und Rangieraufgaben, als auch die Übergaben des Zuges an den nächsten Fahrer zusammengefasst. Diese Aufgaben werden vor oder nach dem Fahren ausgeübt.

Laufen: Es ist möglich, dass am Ende eines Fahrblocks der Zug an einem Gleis abgestellt wird, welches sich nicht in unmittelbarer Nähe des Gleises befindet, an dem der nächste Fahrblock der gleichen Schicht startet. In einem solchen Fall muss der Fahrer die Strecke dazwischen zu Fuß gehen. Je nach Größe der Station kann die Laufdistanz bis zu 2 km betragen und dementsprechend viel Zeit in Anspruch nehmen.

Deadheads (Leerfahrten): Wenn der nächste Fahrblock eines Fahrers an einer anderen Station beginnt, als sein letzter geendet hat, muss dieser ein Transportmittel nutzen, um seinen nächsten Fahrblock ausüben zu können. Dazu kann er z.B. Taxi fahren, einen Bus nehmen oder als Passagier in einem Güterzug mitfahren; dies wird als Gastfahrten bezeichnet.

Leerlaufzeit: Leerlaufzeit ist unproduktive Zeit des Fahrers, z.B. wenn er auf den nächsten Zug warten muss. Hierzu werden auch Pufferzeiten gezählt, die eingeplant werden, um Unsicherheiten wie Verspätungen etc. abzufangen.

Pausenzeiten: Pausenzeiten sind gesetzlich und tariflich vorgeschrieben. Der Fahrer erhält keinen Lohn für seine Pausenzeiten (Jütte et al., 2011; Albers, 2009, S.38-41).

Zielsetzung des Crew Scheduling Problems ist es, einen kostenminimalen Schichtplan zu erzeugen. Der Schichtplan enthält eine Kombination der optimalen Schichten, Informationen darüber, welchem Distrikt diese zugeordnet sind, welche Fahrblöcke sie abdecken und wie viel Personal benötigt wird. Den Schichten wird noch kein konkretes Personal zugeordnet, dies geschieht erst im Rahmen des Crew Rostering, welches im Anschluss an das Crew Scheduling ausgeführt wird. Vor Beginn des Crew Scheduling müssen einige vorangelagerte Prozessschritte abgeschlossen sein. Der Gesamtprozess beginnt mit der Tourenplanung und der Fahrzeugblockierung. Darauf folgen die Fahrplanerstellung, die Fahrzeugzuordnung und anschließend die Fahrzeugumlaufbestimmung. Erst nach Beendigung dieser Prozesse beginnt das Crew Scheduling (Jütte et al., 2011).

3. Lösungsverfahren des Crew Scheduling Problems

Bei der Entwicklung von Lösungsverfahren des Crew Scheduling Problems lag der Fokus lange Zeit auf der Flugverkehrsindustrie. Eine direkte Übertragung der Lösungsverfahren auf den Schienenverkehr war nicht möglich, da sich die Problemgrößen zwischen dem Crew Scheduling des Flugund Schienenverkehrs deutlich unterscheiden. Das Crew Scheduling Problem des Schienenverkehrs ist weitaus umfangreicher und komplexer als das des Flugverkehrs (Bengtsson, 2007, S.129). Dies liegt unter anderem daran, dass die Menge an Fahrblöcken 1-2 Mal größer als die des Flugverkehrs (Albers, 2009, S.49). Außerdem ist keine Unterteilung in Subprobleme je nach Fahrzeugtyp, wie es im Flugverkehr üblich ist, möglich, da ein Fahrer mehrere Fahrzeugtypen bedienen kann (Jütte et al., 2011). Durch stark weiterentwickelte Softund Hardware konnten schließlich einige Ansätze auf den Schienenverkehr übertragen werden (Abbink et al., 2005). Im Rahmen dieser Arbeit wird ausschließlich das Column Generation Verfahren zur Lösung des Crew Scheduling Problems im Schienengüterverkehr betrachtet. Dieses bildet die Grundlage der von Jütte et al. (2011) für die Deutsche Bahn entwickelten Software TEO. Es ist ein geeignetes Lösungsverfahren, da es insbesondere zur Lösung linearer Programme mit einer großen Anzahl an Variablen eingesetzt wird (Malcherek, 2010, S.21; Abbink et al., 2005). Da die Lösung Aufschluss darüber gibt, welche Schichten im Schichtplan enthalten sind, ist es notwendig, dass die Entscheidungsvariablen ganzzahlige Werte annehmen. Daher folgt im Anschluss an das Column Generation Verfahren die Variable-Fixing Phase, welche die Variablen zur Ganzzahligkeit zwingt. Der gesamte Ablauf ist in Abbildung 2 zu sehen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Column Generation Verfahren mit Variable-Fixing Phase (Jütte et al., 2011)

3.1. Das Column Generation Verfahren

Im Column Generation Verfahren wird das zu lösende Problem in Masterund Subproblem unterteilt (Desrosiers und Lübbecke, 2005, S.3-4). Ziel des Masterproblems ist es, aus einer gegebenen Menge an zulässigen Schichten diejenigen auszuwählen, die eine optimale Lösung erzeugen. Die Generierung dieser Menge an Schichten erfolgt im Rahmen des Subproblems (Malcherek, 2010, S.11; Albers, 2009, S.13).

Voraussetzung zur Anwendung des Column Generation Verfahrens ist, dass alle notwendigen Inputdaten vorhanden sind. Die wichtigste Information stellt hierbei der Fahrplan dar, der unter anderem Informationen über Ankunftsund Abfahrtszeiten und Ankunftsund Abfahrtsorte enthält (Janacek et al., 2017). Auf Grundlage der Inputdaten kann das Problem als Netzwerkmodell dargestellt werden, welches die Basis zur Lösung des Subproblems bildet (siehe Abschnitt 3.1.2.) (Malcherek, 2010, S.49).

Wie im Netzwerkmodell aus Abbildung 3 zu erkennen ist, besteht ein Netzwerk aus einer Menge an Knoten und Bögen. Ein Bogen ist eine gerichtete Verbindung zwischen zwei Knoten. Die Menge an Knoten setzt sich zusammen aus Ursprungsknoten, Fahrblockknoten und Zielknoten. Für jedes Depot existiert genau ein Ursprungsund ein Zielknoten und für jeden Fahrblock ein Fahrblockknoten. Jedem Bogen sind Kosten, reduzierte Kosten und Ressourcenverbräuche zugeordnet. Die Kosten enthalten dabei Lohnkosten, Kosten für Gastfahrten und Strafkosten. Die Aussage der reduzierten Kosten wird in Abschnitt 3.1.2. genauer erklärt. Jedem Bogen wird eine Variable zugeordnet, die den Ressourcenverbrauch des Bogens einer bestimmten Ressource angibt. An jedem Knoten wird der kumulierte Ressourcenverbrauch bestimmt. Mögliche Ressourcen sind z.B. Schichtdauer, Arbeitszeit und Fahrzeit (Albers, 2009, S.86-92). Die Ressourcen garantieren dabei die Einhaltung aller arbeitsrechtlichen Anforderungen. Nur Pfade, die die Ressourcenkapazitäten nicht überschreiten, sind zulässig und stellen damit zulässige Schichten dar.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Ein beispielhaftes Netzwerkmodell

3.1.1. Masterproblem

Das Masterproblem kann als lineares Programm formuliert werden (Jütte et al., 2011). Lineare Programme sind häufig verwendete Verfahren des Operations Research (Suhl und Mellouli, 2009, S.8). Sie bestehen immer aus einer linearen Zielfunktion und einer oder mehrerer linearer Nebenbedingungen. Die Zielfunktion wird abhängig von der Problemstellung entweder maximiert (Maximierungsproblem) oder minimiert (Minimierungsproblem). Die Nebenbedingungen schränken den Lösungsraum ein, indem sie festlegen, welche Lösungen zulässig und welche unzulässig sind. Den Variablen (Entscheidungsvariablen) wird bei der Generierung der Lösung ein (optimaler) Wert zugewiesen, der sich in einem vorher festgelegten Wertebereich bewegt (Suhl und Mellouli, 2009, S.32-35).

Das lineare Programm der Personaleinsatzplanung stellt ein Minimierungsproblem dar. Ziel ist es, die Kosten des gesamten Schichtplans unter Berücksichtigung der Nebenbedingungen zu minimieren (Jütte et al., 2011).

Zum Verständnis der mathematischen Formulierung von Jütte et al. (2011) müssen einige Variablen und Parameter beschrieben werden: Das betrachtete Netzwerk des Güterverkehrs besteht aus verschiedenen Crew Distrikten j E J, die Gruppen von Stationen darstellen. Die Fahrblöcke, welche Zugbewegungen zwischen Stationen sind, werden mit tET bezeichnet. Ob eine Schicht dED einen Fahrblock enthält, wird durch atd ausgedrückt. atd ist gleich 1, wenn Schicht d Fahrblock t abdeckt und gleich 0, wenn nicht. Die Kosten für eine Schicht werden durch cd ausgedrückt. Diese setzen sich aus Lohnkosten, Kosten für Hotelaufenthalte und Bezahlungen für Gastfahrten zusammen (Albers, 2009, S.46-47). Wenn eine Schicht d an einem Depot von Distrikt j beginnt, wird bjd = 1 und gleich 0, wenn nicht. Für jeden Distrikt j Ej steht eine bestimmte Kapazität zur Verfügung. Die Kapazität eines Distrikts wird durch die Anzahl verfügbarer Fahrer kj für diesen Distrikt ausgedrückt. Jeder Fahrer ist einem bestimmten Distrikt zugeteilt. Das Modell lässt Kapazitätsüberschreitungen in Form einer weichen Nebenbedingung zu.Um Kapazitätsüberschreitungen jedoch mit zusätzlichen Kosten zu bestrafen, wird der Straffaktor <x.j eingeführt. Die Entscheidungsvariablen des Modells sind xd und yj. xd ist eine Binärvariable, die den Wert 1 annimmt, wenn Schicht d in dem Lösungsschichtplan vorkommt und den Wert 0, wenn nicht. yj misst die Kapazitätsüberschreitungen von Distrikt j. Wenn die Kapazität des Distrikts j nicht überschritten wird, ist yj = 0. Es ergibt sich folgendes Masterproblem:

Abbildung in dieser Leseprobe nicht enthalten

[...]

Ende der Leseprobe aus 44 Seiten

Details

Titel
Mathematische Modellierung im Crew Scheduling. Wie gelingt eine gerechte Schichtverteilung?
Hochschule
Universität zu Köln
Note
1,3
Autor
Jahr
2018
Seiten
44
Katalognummer
V513697
ISBN (eBook)
9783346111715
Sprache
Deutsch
Schlagworte
mathematische, modellierung, crew, scheduling, schichtverteilung
Arbeit zitieren
Isabelle Huber (Autor), 2018, Mathematische Modellierung im Crew Scheduling. Wie gelingt eine gerechte Schichtverteilung?, München, GRIN Verlag, https://www.grin.com/document/513697

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Mathematische Modellierung im Crew Scheduling. Wie gelingt eine gerechte Schichtverteilung?


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden