Abstract

As a service orientated company, the Miele & Cie. KG offers technical support to their customers. The field technicians carry out the repair jobs on-site at the customers’ facilities. Thus, on each working day, a special plan needs to be elaborated, which allows the company to execute the repair orders as efficiently as possible. At the same time, such a plan needs to fulfill certain time requirements resulting from the regulations on working times and rest breaks on the one hand, as well as the customers’ preferred time of day on the other hand. Moreover, the different qualification profiles of the technicians have to be taken into consideration. Previous student projects have shown that the Order Management System AMS, which is being deployed at the Miele & Cie. KG, generates plans which bear considerable potential for a subsequent optimization. Therefore, within the scope of this thesis an Evolutionary Algorithm was implemented. The implementation meets all requirements of the above mentioned planning task and is able to improve the AMS solutions.

Als serviceorientiertes Unternehmen bietet die Miele & Cie. KG den Abnehmern ihrer Produkte einen technischen Kundendienst an. Die mobilen Techniker des Kundendienstes erledigen die Reparaturarbeiten vor Ort beim Kunden. Somit ergibt sich f¨ ur jeden Arbeitstag eine Planungsaufgabe, deren Ziel es ist, die Durchf¨ uhrung aller Reparaturauftr¨ age m¨ oglichst effizient zu organisieren. Gleichzeitig muss ein Plan bestimmte zeitliche Anforderungen erf¨ ullen, die aus tariflichen Arbeitszeit-und Pausenbestimmungen auf der einen, und aus Terminw¨ unschen der Kunden auf der anderen Seite resultieren. Einen weiteren zu beachtenden Faktor stellen die unterschiedlichen Qualifikationsprofile der Techniker dar. Vorausgegangene studentische Arbeiten haben gezeigt, dass das derzeitig bei der Miele & Cie. KG genutzte Auftragsmanagementsystem AMS Pl¨ ane generiert, die erhebliches Potenzial f¨ ur eine nachgelagerte Optimierung bieten. Im Rahmen der vorliegenden Arbeit wurde zu diesem Zweck ein Evolution¨ arer Algorithmus implementiert. Die Implementierung erf¨ ullt alle Vorgaben der Planungsaufgabe und ist in der Lage, die Ergebnisse von AMS zu verbessern.

Inhaltsverzeichnis

1  Einleitung  1

1.1  Vorausgegangene Arbeiten  1

1.2  Ziel und Aufbau der Diplomarbeit  2

2  Technischer Kundendienst der Miele Cie. KG  3

2.1  Rahmenbedingungen und Organisation  3

2.1.1  Disposition der Kundenauftr age  5

2.1.2  Auftragsdurchf uhrung  7

2.2  Verbesserungspotenziale in der Planung des Technikereinsatzes  8

2.2.1  Realit atsnahe Sch atzung der Fahrzeiten  8

2.2.2  Nachgelagerte Optimierung  10

2.2.3  Einplanung der Pausen und der Fahrt zum ersten Kunden  11

3  Grundlagen der Tourenplanung  13

3.1  Probleme der Tourenplanung  13

3.1.1  Modellierung und Problemvarianten  14

3.1.2  Komplexit at  15

3.2  Tourenplanung beim technischen Kundendienst der Miele Cie. KG  16

3.3  L osungsmethoden  19

3.3.1  Exakte Verfahren  19

3.3.2  Heuristiken  19

4  Evolution are Algorithmen  24

4.1  Ursprung  24

4.2  Genereller Ablauf und zentrale Begriffe  25

4.3  Komponenten evolution arer Verfahren  27

4.3.1  L osungsrepr asentation und Kodierung  27

4.3.2  Bewertungs-/Fitnessfunktion  29

4.3.3  Elternselektion  29

4.3.4  Genetische Operatoren  30

4.3.5  Selektion der Nachfolgegeneration  32

4.3.6  Populationsgr oße  32

4.3.7  Initialisierung der Startpopulation  33

4.4  Ber ucksichtigung von Nebenbedingungen  33

5  L osungsentwurf und Implementierung  36

5.1  L osungsrepr asentation und Kodierung  36

5.2  Bewertungsfunktion  39

5.3  Elternselektion  41

i

Inhaltsverzeichnis

5.4  Genetische Operatoren  43

5.4.1  Rekombinationsoperator  43

5.4.2  Mutationsoperator  45

5.5  Selektion der Nachfolgegeneration  46

5.6  Populationsgr oße  48

5.7  Initialisierung der Startpopulation  48

6  Evaluation  49

6.1  Vergleich mit den Ergebnissen des Decision Support Project  49

6.1.1  Ergebnisse der exakten Optimierung  49

6.1.2  Ergebnisse der Heuristik VNS  52

6.2  Vergleich mit der VNS-Implementierung von Szczepanski und Graute  54

7  Zusammenfassung und Ausblick  57

A  Programmdokumentation  64

ii

Abk¨ urzungsverzeichnis

AMS bei der Miele & Cie. KG eingesetztes Auftragsmanagementsystem

CVRP Capacitated Vehicle Routing Problem, kapazitiertes Problem der Tourenplanung

DSP

ES Evolutionsstrategien

GA Genetische Algorithmen

GP Genetische Programmierung

GVR Genetic Vehicle Representation

MDVRP Multi-Depot Vehicle Routing Problem, Mehrdepotproblem der Tourenplanung

MDVRPTW Multi-Depot Vehicle Routing Problem with Time Windows, Mehrdepottourenplanungsproblem mit Zeitfenstern

PDP Pickup and Delivery Problem, Tourenplanungsproblem mit Einsammeln und Ausliefern

PVRP Periodic Vehicle Routing Problem, periodisches Problem der Tourenplanung

Q-MDVRPTW Qualification based Multi-Depot Vehicle Routing Problem with Time Windows, qualifikationsbezogenes Mehrdepottourenplanungsproblem mit Zeitfenstern

VNS Variable Neighborhood Search

VRP Vehicle Routing Problem, (klassisches) Problem der Tourenplanung

iii

VRPTW

VRSP

Abbildungsverzeichnis

2.1 Vertriebsregionen und Technikerstandorte der Miele & Cie. KG in Deutschland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3.1 Graphdarstellung eines Tourenplans f¨ ur ein klassisches VRP . . . . . 14

v

Tabellenverzeichnis

2.1 Einflussfaktoren bei der Disposition von Auftr¨ agen . . . . . . . . . . 5 4.1 Zentrale Begriffe Evolution¨ arer Algorithmen und ihre Analogien zur Biologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.1 Berechnung der Strafe f¨ ur Restriktionsverletzungen in einer Route R i 40

6.6 Ergebnisse des Evolution¨ aren Algorithmus f¨ ur ¨ uberarbeitete Testinstanzen des DSP nach 250 Generationen . . . . . . . . . . . . . . . . 54

6.9 Ergebnisse des Evolution¨ aren Algorithmus f¨ ur die Testinstanzen aus [Szczepanski u. Graute 2005] . . . . . . . . . . . . . . . . . . . . . . . 56

vi

1 Einleitung

In den heutigen, hart umk¨ ampften M¨ arkten ist hohe Kundenzufriedenheit entscheidend f¨ ur den Erfolg eines Unternehmens. Vor diesem Hintergrund bietet die Miele & Cie. KG den Abnehmern ihrer Erzeugnisse nicht nur qualitativ hochwertige Produkte sondern auch einen zuverl¨ assigen technischen Kundendienst an. Daf¨ ur unterh¨ alt das Unternehmen ein fl¨ achendeckendes Netz von bundesweit stationierten mobilen Technikern, welche die anfallenden Reparaturauftr¨ age direkt am Standort des betroffenen Ger¨ ates ausf¨ uhren.

Die Ergebnisse der t¨ aglichen Planung des Technikereinsatzes werden in so genannten Tourenpl¨ anen erfasst. Diese legen fest:

1. Welche Auftr¨ age die einzelnen Techniker am gegebenen Arbeitstag ¨ ubernehmen sollen.

2. In welcher Reihenfolge und nach welchem Zeitplan die Techniker die ihnen jeweils zugeordneten Auftr¨ age bearbeiten sollen.

Aus Kostengr¨ unden ist es w¨ unschenswert, Tourenpl¨ ane zu generieren, welche f¨ ur die Techniker m¨ oglichst kurze Fahrten vorsehen. Gleichzeitig muss ein Plan bestimmte zeitliche Anforderungen erf¨ ullen, die aus tariflichen Arbeitszeit- und Pausenbestimmungen auf der einen, und aus Terminw¨ unschen der Kunden auf der anderen Seite resultieren. Ein weiterer zu beachtender Faktor sind die unterschiedlichen Qualifikationsprofile der Techniker.

Insgesamt stellt sich die Planung des Technikereinsatzes als eine komplexe Aufgabe dar, welche aus theoretischer Sicht als ein qualifikationsbezogenes Mehrdepottourenplanungsproblem mit Zeitfenstern ¹ (Qualification based Multi-Depot Vehicle Routing Problem with Time Windows, kurz Q-MDVRPTW) modelliert werden kann, vgl. [Kliewer u. a. 2005].

1.1 Vorausgegangene Arbeiten

Verschiedene Aspekte der Tourenplanung des technischen Kundendienstes der Miele & Cie. KG waren Gegenstand vorausgegangener studentischer Arbeiten am Lehrstuhl Decision Support & OR Lab. Zum einen wurden in der Diplomarbeit von Gerke

¹ Das Q-MDVRPTW ist eine Verallgemeinerung des in der Transportlogistik bekannten Mehrdepottourenplanungsproblems mit Zeitfenstern (Multi-Depot Vehicle Routing Problem with Time Windows bzw. kurz MDVRPTW).

1

die f¨ ur die Planung des Kundendienstes relevanten Prozesse eingehend analysiert. Dar¨ uber hinaus wurden verschiedene Verfahren zur Distanz- und Fahrzeitsch¨ atzung f¨ ur die Fahrten der Techniker untersucht, vgl. [Gerke 2005]. Im Rahmen der Veranstaltung Decision Support Project (DSP), welche im Wintersemester 2004/2005 stattgefunden hat, wurde mit der Variable-Neighborhood-Search-

Methodeaus [Polacek u. a. 2004] eine Heuristik f¨ ur die nachgelagerte Optimierung der AMS-Tourenpl¨ ane verwendet. Unter der Annahme einer leicht vereinfachten Problemformulierung konnte bei den bisherigen Tourenpl¨ anen ein Verbesserungspotenzial von mehr als 10% aufgedeckt werden, vgl. [Szczepanski u. a. 2005]. In der Seminararbeit von Szczepanski und Graute wurde die Variable-Neighborhood-Search-Implementierung aus dem DSP um weitere, zuvor vernachl¨ assigte Aspekte der Aufgabenstellung erg¨ anzt. Insgesamt konnte immer noch ein interessantes Op-

1.2Ziel und Aufbau der Diplomarbeit

Ziel der vorliegenden Diplomarbeit ist es, eine auf dem Prinzip Evolution¨ arer Algorithmen basierende Methode zu konzipieren und zu implementieren. Anschließend soll untersucht werden, ob diese Methode f¨ ur eine nachgelagerte Optimierung der Tourenpl¨ ane der Miele & Cie. KG genutzt werden kann. Evolution¨ are Algorithmen setzen bestimmte Prinzipien biologischer Evolution und Genetik zur L¨ osung von Optimierungsproblemen ein und sind bereits erfolgreich zur Bew¨ altigung anderer komplexer Tourenplanungsaufgaben eingesetzt worden.

Die Arbeit geht zun¨ achst in Kapitel 2 auf die Rahmenbedingungen und die Organisation des Kundendienstes der Miele & Cie. KG ein und zeigt m¨ ogliche Ver-

besserungspotenziale in der Planung des Technikereinsatzes auf. In Kapitel 3 wird die Aufgabe als ein Tourenplanungsproblem formuliert und ein ¨ Uberblick ¨

grunds¨ atzlich daf¨ ur in Frage kommenden L¨ osungsmethoden gegeben. Die zur Klasse der metaheuristischen L¨ osungsverfahren z¨ ahlenden Evolution¨ aren Algorithmen werden in Kapitel 4 eingehend beschrieben. Kapitel 5 enth¨ alt Erl¨ auterungen zu den Komponenten des Evolution¨ aren Algorithmus, welcher im Rahmen dieser Arbeit f¨ ur die nachgelagerte Tourenplanoptimierung entworfen und implementiert wurde. Eine Auswertung der Ergebnisse der empirischen Untersuchung dieses Algorithmus folgt

in Kapitel 6. Die Arbeit schließt mit einer Zusammenfassung und einem Ausblick.

2

2 Technischer Kundendienst der

Miele & Cie. KG

Die Miele & Cie. KG ist ein bekannter Anbieter von Elektroger¨ aten und stellt den Abnehmern ihrer Produkte einen mobilen Kundendienst zur Verf¨ ugung. Die effiziente Organisation des Einsatzes der Techniker, welche in diesem Kundendienst besch¨ aftigt sind, muss sowohl r¨ aumliche als auch zeitliche Aspekte ber¨ ucksichtigen und stellt eine komplexe Aufgabe dar.

Die folgenden Ausf¨ uhrungen beschreiben, wie diese Aufgabe in der Miele & Cie. KG derzeit gel¨ ost wird. Dazu werden zun¨ achst in Abschnitt 2.1 die Rahmenbedingungen und die Organisation der in diesem Zusammenhang relevanten Arbeitsabl¨ aufe dargelegt. Anschließend werden in Abschnitt 2.2 die Verbesserungspotenziale der bisherigen Vorgehensweise zur Planung des Technikereinsatzes analysiert.

2.1 Rahmenbedingungen und Organisation

Als Hersteller von Elektroger¨ aten versorgt die Miele & Cie. KG mit Hauptsitz in G¨ utersloh sowohl private Haushalte als auch gewerbliche Abnehmer. Das Pro-duktportofolio umfasst unter anderem Staubsauger, Geschirrsp¨ uler, K¨ uhlschr¨ anke, Waschautomaten sowie Maschinen f¨ ur Geschirrreinigung und Aufbereitung von La-borinstrumenten. F¨ ur die Reparatur und Wartung der Ger¨ ate stellt das Unternehmen einen Kundendienst bereit, in welchem ca. 600 Techniker besch¨ aftigt sind. Die Techniker sind an verschiedenen Standorten in ganz Deutschland stationiert (siehe Abb. 2.1) und erledigen den ¨ uberwiegenden Teil der Reparatur- und Wartungsarbeiten direkt beim Kunden.

Die Planung und Organisation des Technikereinsatzes in Deutschland ¨ ubernehmen

die Servicezentren der sechs Vertriebsregionen Hamburg, Berlin, Frankfurt, Karlsruhe, Bochum und M¨ unchen. Ihre Aufgabe umfasst die telefonische Entgegennahme des Kundenauftrages und seine Disposition, also Zuordnung zu einem Techniker der jeweiligen Region. Die dabei zum Einsatz kommende Software ist AMS, ein von der GMS Development GmbH entwickeltes Service- und Auftragsmanagementsystem, vgl. [Szczepanski u. a. 2005, S. 2]. In AMS werden die Auftragsdaten erfasst und weitere f¨ ur die Einsatzplanung der Techniker relevanten Daten (Kunden-, Techniker-und Produktstammdaten) verwaltet. Welche Daten das im Einzelnen sind, wird nachfolgend erl¨ autert.

3

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

Abb. 2.1: Vertriebsregionen und Technikerstandorte der Miele & Cie. KG in Deutschland, Quelle: [Gerke 2005, S. 5]

Auftrags- und Kundendaten

Bei der Entgegennahme eines Reparaturauftrages werden zun¨ achst der Name und die Adresse des Kunden erfasst. Bei bereits bestehenden Kunden geschieht dies durch den Zugriff auf die Kundenstammdaten, bei Neukunden durch ihre Befragung. Ebenfalls festgehalten werden Informationen ¨ uber den Grund des Reparaturauftrages und

die Produktnummer des betroffenen Ger¨ ates. Dar¨ uber hinaus werden zeitliche Vorgaben des Kunden bez¨ uglich des Technikerbesuches vermerkt: zum einen die in Kalendertagen ausgedr¨ uckten m¨ oglichen Besuchstage und zum anderen die in AMS als Terminart bezeichnete Angabe des Zeitintervalls, in welchem der Termin stattfinden kann, beispielsweise “ganzer Tag” oder “14:00 - 17:00 Uhr”. Ist die Angabe eines solchen Zeitintervalls nicht m¨ oglich, weil der Auftrag zu einem bestimmten Termin stattfinden muss, wird als Terminart “Fixtermin” festgehalten. Fixtermine kommen in der Regel nur in dringenden F¨ allen vor, z.B. beim Auftreten eines Defektes wichtiger Ger¨ ate in Krankenh¨ ausern, vgl. [Gerke 2005, S. 6 f].

Technikerdaten

F¨ ur jeden Techniker ist ein Arbeitszeitmodell hinterlegt. Es enth¨ alt Vorgaben zum Beginn und Ende seiner Arbeitszeit sowie zu der von ihm einzuhaltenden Pausendauer. In der Regel betr¨ agt die Pausendauer 45 Minuten pro Arbeitstag.

4

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

Dar¨ uber hinaus ist jedem Techniker ein Qualifikationsprofil zugeordnet. Es gibt Aufschluss dar¨ uber, auf welche Produktgruppen der jeweilige Arbeiter aufgrund seiner Ausbildung spezialisiert ist.

Die Techniker sind an ihren Wohnorten stationiert. Von dort starten sie ihre Touren und dorthin kehren sie am Ende eines Arbeitstages zur¨ uck. Jedem Techniker ist anhand von Postleitzahlen ein bestimmtes Stammgebiet zugeordnet, in welchem er vornehmlich zum Einsatz kommt. Weiteren Gebieten, in denen er aushilfsweise t¨ atig sein kann, wird in der Gebietszuordnung eine niedrigere Priorit¨ at zugewiesen.

Produktdaten

Jedes Ger¨ at besitzt eine Produktnummer. ¨ Uber diese Nummer kann die Produktgruppe identifiziert werden, zu welcher es geh¨ ort. F¨ ur jede Produktgruppe wiederum ist festgelegt, welche Qualifikationen sie im Reparaturfall erfordert. Somit kann ¨ uber

die Zuordnung eines Ger¨ ates zu einer Produktgruppe auf die f¨ ur seine Reparatur in Frage kommenden Techniker geschlossen werden.

Die Produktgruppenzuordnung fließt auch in die Veranschlagung voraussichtlicher Arbeitszeiten f¨ ur die Reparatur eines Ger¨ ates ein. So ist beispielsweise die Arbeitszeit bei der Gruppe “Waschmaschinen” geringer als bei “professionellen Desinfektionsger¨ aten”, vgl. [Gerke 2005, S. 12].

2.1.1 Disposition der Kundenauftr¨ age

Die automatische Disposition von Kundenauftr¨ agen wird von AMS unterst¨ utzt. Das System vergleicht dabei die zeitlichen, geographischen und qualifikationsbezogenen Anforderungen eines eingehenden Auftrages mit den Eigenschaften der Techniker. Tabelle 2.1 zeigt, welche Daten dabei betrachten werden.

qualifikations- Anforderung der betroffenen Qualifikationsprofil bezogen Produktgruppe

Tabelle 2.1: Einflussfaktoren bei der Disposition von Auftr¨ agen

5

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

Auf der Grundlage dieser Angaben ermittelt AMS diejenigen Techniker ¹ , welche f¨ ur die Erledigung des Auftrages in Frage kommen. F¨ ur diese Techniker wiederum werden - unter Ber¨ ucksichtigung ihrer Arbeitszeitmodelle und ggf. zuvor eingeplanter Termine - alle im Rahmen der Terminart des Auftrages zul¨ assigen Bearbeitungszeitpunkte untersucht und bewertet. Dem Disponenten werden die daraus resultierenden Dispositionsalternativen zur Auswahl vorgeschlagen, siehe Abb. 2.2.

Abb. 2.2: Darstellung unterschiedlicher Dispositionsalternativen in AMS, Quelle: [Szczepanski u. a. 2005, S. 20]

Die Bewertung der unterschiedlichen Dispositionsalternativen wird in AMS von mehreren Faktoren bestimmt. Der in die Bewertung am st¨ arksten einfließende Faktor bezieht sich auf die so genannte Tourenverl¨ angerung, also die Frage: Um wie viele Kilometer verl¨ angert sich die von einem Techniker am gew¨ ahlten Arbeitstag zu fahrende Strecke, wenn der Auftrag ihm zugeordnet wird? Zur Beantwortung dieser Frage berechnet AMS die euklidischen Luftliniendistanzen als N¨ aherungswerte f¨ ur die tats¨ achlichen L¨ angen der Fahrstrecken zwischen den jeweiligen geographischen Orten.

Ein weiterer in der Bewertungszahl ber¨ ucksichtigter Aspekt betrifft die Einhaltung der Vorgaben, welche der Kunde bez¨ uglich des Zeitpunktes des Technikerbesuches gemacht hat (Stichwort Terminart). F¨ ur die dazu erforderliche Angabe, wann der Techniker am Auftragsort eintrifft, erfolgt in AMS eine Sch¨ atzung der Bearbeitungs-und der Fahrzeiten. Die voraussichtliche Bearbeitungszeit eines Auftrages wird nach

¹ Hier wird die Mehrzahl verwendet, weil in der Regel mehrere Techniker f¨ ur die Bearbeitung eines Auftrages zur Auswahl stehen.

6

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

Erfahrungswerten ¨ ahnlicher Auftr¨ age aus der Vergangenheit gesch¨ atzt. Bei Fahrzeitberechnungen geht AMS von einer Durchschnittsgeschwindigkeit von 30 km/h und einer R¨ ustzeit von sieben Minuten pro Fahrt aus, vgl. [Gerke 2005, S. 9]. Die Bewertungszahl unterst¨ utzt den Disponenten bei der Auswahl der Dispositionsalternative. Dabei gilt: je gr¨ oßer der Wert der Bewertungszahl, desto besser erf¨ ullt diese Alternative die unterschiedlichen Bewertungskriterien. Hat der Disponent die Auswahl getroffen, wird der Auftrag dem gew¨ ahlten Techniker zugeordnet und erscheint in seinem Arbeitsplan.

AMS unterst¨ utzt nicht nur die automatische Disposition von Auftr¨ agen. Es erlaubt dar¨ uber hinaus manuelle Ver¨ anderungen an den Touren bzw. Routen der Techniker. Solche Ver¨ anderungen werden beispielsweise dann vorgenommen, wenn ein Kunde seinen Auftrag storniert. Sie k¨ onnen aber auch der Optimierung von Pl¨ anen dienen, in welchen die Disponenten offensichtliche Umwege erkennen konnten.

2.1.2 Auftragsdurchf¨ uhrung

Alle Techniker sind mit einem Notebook ausgestattet. Am Vorabend eines Arbeitstages stellen sie eine Verbindung zum Servicezentrum ihrer jeweiligen Region her und erhalten von AMS ihren individuellen Einsatzplan f¨ ur den n¨ achsten Tag. Jeder Techniker besitzt ein Einsatzfahrzeug, welches mit den am h¨ aufigsten ben¨ otigten Ersatzteilen und Werkzeugen ausgestattet ist. Mit diesem Fahrzeug besucht der Techniker die Kunden entsprechend des Tourenplans und erfasst dabei seine tats¨ achlichen Fahr- und Arbeitszeiten sowie den Materialverbrauch. Den Kunden wird vor Ort eine Rechnung erstellt und ausgeh¨ andigt.

Bei Auftr¨ agen, die nicht an einem Tag abschließend bearbeitet werden k¨ onnen - z.B. weil das dazu ben¨ otigte Ersatzteil nicht vom Techniker mitgef¨ uhrt wurde und erst bestellt werden muss - werden so genannte Folgeauftr¨ age erzeugt. Der Techniker muss in einem solchen Fall den Kunden an einem anderen Tag zum zweiten Mal besuchen.

Die Techniker k¨ onnen nach eigenem Ermessen entscheiden, wann sie w¨ ahrend des Arbeitstages ihre Pausenzeiten nehmen. Sie planen dazu ihre Pausen zwischen jeweils zwei Auftr¨ agen ein. Im Rahmen der Erfassung der Fahr- und Arbeitszeiten der Techniker werden die von ihnen gemachten Pausen bzw. deren Zeiten nicht gesondert ausgewiesen. Eine Pausenzeit zwischen zwei Auftr¨ agen kann somit in AMS nicht von der zwischen ihnen liegenden Fahrzeit unterschieden werden. Nach der Erledigung aller Auftr¨ age ihrer Touren kehren die Techniker zu ihren Depots zur¨ uck. Sie melden die w¨ ahrend des Tages erfassten Daten an AMS zur¨ uck und erhalten wiederum die Plandaten f¨ ur ihren n¨ achsten Arbeitstag.

7

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

2.2 Verbesserungspotenziale in der Planung des

Technikereinsatzes

In der bisherigen Vorgehensweise bei der Planung des Technikereinsatzes gibt es erkennbare Schwachstellen. Abb. 2.3 verdeutlicht, wie die systematische Analyse ihrer Ursachen zur Identifizierung von Verbesserungspotenzialen f¨ uhrt. Nachfolgend werden die aufgedeckten Zusammenh¨ ange und abgeleiteten Verbesserungspotenziale im Einzelnen erl¨ autert.

Abb. 2.3: Potenzialanalyse f¨ ur die Planung des Technikereinsatzes

2.2.1 Realit¨ atsnahe Sch¨ atzung der Fahrzeiten

Eine Schwachstelle besteht darin, dass bei der Planung des Technikereinsatzes regelm¨ aßig manuelle Eingriffe seitens der Disponenten erfolgen. Das Eingreifen der Disponenten in den komplexen Planungsprozess ist nicht w¨ unschenswert, es ist jedoch notwendig, weil die vollst¨ andig automatische Disposition in AMS erfahrungsgem¨ aß zur ¨ Uberlastung bzw. mangelnder Auslastung einzelner Techniker f¨ uhrt. Die Unzul¨ anglichkeit der automatischen Disposition resultiert aus der unrealistischen Sch¨ atzung der Fahrzeiten der Techniker. In manchen Gebieten (z.B. in Ballungszentren) ergeben sich f¨ ur die Techniker erfahrungsgem¨ aß l¨ angere Fahrzeiten als von AMS gesch¨ atzt. Das hat zur Folge, dass die dort im Einsatz befindlichen Techniker tendenziell mehr Auftr¨ age vom System zugewiesen bekommen als sie tats¨ achlich

8

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

in ihrer Arbeitszeit schaffen k¨ onnen. Die Disponenten versuchen das Problem zu umgehen, indem sie fiktive Auftr¨ age (so genannte “k¨ unstliche Auftr¨ age”) erzeugen und den betroffenen Technikern manuell zuordnen.

Die Einplanung eines “k¨ unstlichen Auftrages” am Ende der Route eines Technikers reduziert seine noch verf¨ ugbare Arbeitszeit und verhindert so die Zuweisung zu vieler Kundenauftr¨ age. Wird dem “k¨ unstlichen Auftrag” aber zu viel Zeit zugemessen, f¨ uhrt seine Einplanung zu einer zu geringen tats¨ achlichen Auslastung des Technikers, also einem unerw¨ unschten Effekt. An dieser Stelle wird deutlich, dass dieser Kunstgriff problematisch ist und - selbst von erfahrenen Disponenten eingesetztunbeabsichtigte Folgen haben kann.

In Gebieten, in welchen sich die Techniker schneller als von AMS gesch¨ atzt bewegen k¨ onnen (z.B. in l¨ andlichen Gegenden), f¨ uhrt die automatische Disposition in der Regel zu einer unzureichenden Auslastung der Techniker. Der Disponent versucht in einem solchen Fall, die noch vorhandene Kapazit¨ at durch die manuelle Zuweisung eines zus¨ atzlichen Kundenauftrages zu nutzen. Dazu ¨ andert er den geplanten Bearbeitungsbeginn der automatisch disponierten Auftr¨ age des Technikers so, dass sich f¨ ur den zus¨ atzlichen Auftrag ein zeitliches Fenster er¨ offnet. Bei diesem Vorgang sieht der Disponent auf seiner Plantafel aber nur die zeitlichen Auswirkungen seines manuellen Eingriffes. Er hat keinen ¨ Uberblick dar¨ uber, inwiefern der Einschub

des zus¨ atzlichen Auftrages an einer bestimmten Stelle der Route zur Entstehung unn¨ otiger Umwege f¨ uhren kann.

Die Analyse zeigt also, dass manuelle Eingriffe seitens der Disponenten notwendig sind, weil die auf unrealistischen Fahrzeitsch¨ atzungen basierende automatische Disposition regelm¨ aßig beeinflusst bzw. korrigiert werden muss. Warum aber sind die in AMS gemachten Fahrzeitsch¨ atzungen unrealistisch? Die wesentliche Ursache daf¨ ur liegt in der Annahme einer Durchschnittsgeschwindigkeit von 30 km/h. Die Untersuchung von 162.807 Fahrten der Miele-Techniker im Zeitraum 05.04.2004 -03.12.2004 hat ergeben, dass die w¨ ahrend einer Fahrt tats¨ achlich erreichte Durchschnittsgeschwindigkeit mit der Luftlinienentfernung ihrer Start- und Zieladresse korreliert, vgl. [Gerke 2005, S. 43]. Auch zwischen der Bev¨ olkerungsdichte ² der Start-und Zieladresse einer Fahrt und ihrer Durchschnittsgeschwindigkeit ist ein signifikanter Zusammenhang nachweisbar, vgl. [Gerke 2005, S. 55]. Die Arbeit von Gerke hat gezeigt, dass die Einbeziehung der Entfernung und Bev¨ olkerungsdichte in die Sch¨ atzfunktion der Durchschnittsgeschwindigkeit zur Verbesserung der Planungsgenauigkeit von AMS beitragen kann und somit ein wichtiges Verbesserungspotenzial darstellt.

Als eine weitere Ursache f¨ ur die unrealistischen Fahrzeitsch¨ atzungen ist die Approximation der zu fahrenden Strecken mittels euklidischer Luftliniendistanzen zu nennen. Das Problematische an dieser Vorgehensweise ist, dass die zwischen zwei Auftragsorten zur¨ uckzulegende Strecke in Wirklichkeit deutlich von ihrer Luftliniendistanz abweichen kann. Also liegt auch hier ein Verbesserungspotenzial vor, welches ausgesch¨ opft werden kann, wenn f¨ ur die jeweiligen Fahrten der Techniker

² Dabei wird die Bev¨ olkerungsdichte f¨ ur jedes Postleitzahlengebiet mit der durchschnittlichen Anzahl der Einwohner je Quadratmeter dieses Gebietes angegeben, vgl. [Gerke 2005, S. 54].

9

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

die tats¨ achlich zu w¨ ahlenden Wege bestimmt werden. Dies kann mit Hilfe von Routenplanungssoftware erfolgen.

2.2.2 Nachgelagerte Optimierung

Die Planung des Technikereinsatzes der Miele & Cie KG zielt in erster Linie darauf ab, die t¨ aglich zu fahrende Gesamtstrecke zu minimieren. Die Tatsache, dass die bei der derzeitigen Vorgehensweise entstehenden Tourenpl¨ ane bez¨ uglich dieses Kriteriums suboptimal sind, stellt eine wichtige Schwachstelle des untersuchten Systems dar, siehe Abb. 2.3.

Eine Ursache dieser Suboptimalit¨ at wurde schon erw¨ ahnt: Es ist die manuelle Disposition zus¨ atzlicher Auftr¨ age zu Technikern, bei welchen die Disponenten sonst eine mangelnde Auslastung erwarten, vgl. S. 9 der vorliegenden Arbeit. Diese manuelle Disposition kann f¨ ur einzelne Techniker zu Routen f¨ uhren, die vermeidbare Umwege enthalten.

Ein weiterer Grund der Suboptimalit¨ at der Tourenpl¨ ane ist die Art und Weise, mit welcher die automatische Disposition die Auftr¨ age erfolgt. Neue Kundenauftr¨ age werden nicht gesammelt, um aus ihrer Gesamtheit einen optimalen Tourenplan zu erstellen. Vielmehr werden sie im Moment ihrer Erfassung sofort disponiert. Der Tourenplan wird also schrittweise aufgebaut, wobei bei jeder Erweiterung versucht wird, die mit ihr verbundene Verl¨ angerung der zu fahrenden Strecke (genannt Tourenverl¨ angerung, vgl. Abschnitt 2.1.1) so klein wie m¨ oglich zu halten. Bereits getroffene Dispositionsentscheidungen werden im Nachhinein nicht mehr revidiert. Diese Vorgehensweise entspricht dem so genannten Sequenzparadigma der Online-Optimierung ³ .

Gerke zeigt in seiner Arbeit an einem anschaulichen Beispiel, wie dieses Vorgehen zu einem suboptimalen Tourenplan f¨ uhren kann, vgl. [Gerke 2005, S. 71]. In der Ausgangssituation des Beispiels besteht der bisher aufgebaute Tourenplan aus zwei Routen. Der Graph in Abb. 2.4(a) zeigt diese Ausgangssituation. Dabei stellen die Knoten des Graphen die Auftragsorte (hellgraue Knoten) und Depots (dunkelgraue Knoten) der Techniker dar. Die Kanten symbolisieren die geplanten Fahrten der Techniker auf ihren Routen. Die Kantenbewertung notiert die gesch¨ atzte L¨ ange der jeweiligen Fahrt in km.

Abb. 2.4(b) veranschaulicht, wie f¨ ur einen weiteren zu disponierenden Kundenauftrag (schwarzer Knoten) die Tourenverl¨ angerung zweier Dispositionsalternativen verglichen wird. Wird der Auftrag in die links im Bild erscheinenden Route einge-ordnet, ergibt sich eine Tourenverl¨ angerung von 21 km (11 + 18 - 8). Die Zuordnung dieses Auftrages zur Route des zweiten Technikers bedeutet dagegen eine Touren- ³ Inder Online-Optimierung geht es um Probleme, deren Daten nicht alle auf einmal gegeben sind, sondern nach und nach bekannt werden. Ein Online-Algorithmus trifft dementsprechend Entscheidungen noch bevor ihm alle Eingabedaten bekannt sind. Folgt dieser Algorithmus dem Sequenzparadigma (engl. sequence model ), sind die Entscheidungen jeweils sofort beim Auftreten der einzelnen Eingaben zu treffen und unwiderruflich, vgl. [Gr¨ otschel u. a. 2001].

10

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

(a) Ausgangssituation

Abb. 2.4: Erweiterung eines Tourenplans bei Disposition eines Auftrages im Online-Optimierungsverfahren, Quelle: [Gerke 2005, S. 71], leicht ver¨ andert

verl¨ angerung von 17 km (30 + 11 - 24). Folglich wird die zweite Alternative gew¨ ahlt und es ergibt sich der in Abb. 2.4(c) dargestellte suboptimale Tourenplan. Der optimale Tourenplan, welcher das w¨ unschenswerte Ergebnis der Disposition darstellt, ist in

Abb. 2.5 sichtbar. In ihm wurde eine zuvorunter Unkenntnis des jetzt zu disponierenden Auftrages - getroffene Dispositionsentscheidung revidiert. Eine solche Modifikation des Tourenplans entspricht der ver¨ anderten Gesamtsituation, die sich durch einen weiteren zu disponierenden Auftrag (schwarzer Knoten) ergibt. AMS verf¨ ahrt aber bei der automatischen Disposition nach einem Online-Optimierungs-algorithmus, der den Tourenplan schrittweise um einzelne Auftr¨ age erweitert und nachtr¨ agliche Abb. 2.5: Optimaler Tourenplan Modifikationen bereits getroffener Entscheidungen nicht in Betracht zieht. Dementsprechend bietet der am Vorabend eines Arbeitstages feststehende, von AMS erstellte Tourenplan noch Potenzial f¨ ur eine nachgelagerte Optimierung. Diese kann eine Reduzierung der f¨ ur die Techniker entstehenden Fahrstrecken erreichen: einerseits - wie in dem zuvor vorgestellten Beispiel - durch alternative Aufteilung der Auftr¨ age auf die in Frage kommenden Techniker und andererseits durch die ¨ Anderung der Routen einzelner Techniker beim Besuch ihrer Kunden.

2.2.3 Einplanung der Pausen und der Fahrt zum ersten Kunden

Die letzte wichtige Schwachstelle der jetzigen Vorgehensweise besteht darin, dass bestimmte tarifliche Bestimmungen nicht in ausreichender Weise ber¨ ucksichtigt werden. Zum einen gibt es Regelungen, die besagen, dass die Techniker nach sp¨ atestens

11

KAPITEL 2. TECHNISCHER KUNDENDIENST DER MIELE & CIE. KG

sechs Stunden Arbeit die M¨ oglichkeit f¨ ur eine Pause bekommen m¨ ussen. In AMS werden die Pausen jedoch nicht im Voraus fest eingeplant. Vielmehr liegt es an den Technikern, selbst f¨ ur die Einhaltung ihrer Pausen zu sorgen. Zum anderen gibt es tarifliche Bestimmungen bez¨ uglich der Anfahrt zur Arbeit: nur die ersten 30 Minuten der Anfahrt sollen nicht als Arbeitszeit betrachtet werden. Dagegen ist bei Fahrten, welche mehr als eine halbe Stunde dauern, eine entsprechende arbeitszeitliche Anrechnung vorzunehmen. Diese Regelung wird von AMS nicht beachtet, weil darin die Fahrt zum ersten Kunden grunds¨ atzlich nicht als Arbeitszeit gilt. Deshalb legt AMS den Bearbeitungsbeginn des ersten Auftrages auf den im Arbeitszeitmodell vereinbarten Tagesbeginn eines Technikers, der in der Regel bei 8:00 Uhr liegt.

Die Verbesserungspotenziale liegen in der Einbeziehung der beiden Punkte in die Planung: Pausen k¨ onnen in gleicher Weise wie Kundenauftr¨ age feste Zeiten im geplanten Tagesablauf eines Technikers zugewiesen bekommen. Ebenso kann die Fahrt zum ersten Auftrag kalkuliert und ggf. als Arbeitszeit angerechnet werden. In Abb. 2.3 sind die letzten drei Verbesserungspotenziale farblich hervorgehoben, weil sie im Fokus der vorliegenden Arbeit liegen.

12

3 Grundlagen der Tourenplanung

Bei Problemen der Tourenplanung geht es im Allgemeinen um die Planung optimaler Routen f¨ ur Fahrzeuge, welche von einem oder mehreren Depots aus starten und die Bedienung von Kunden organisieren, deren Standorte und Bedarfe bekannt sind. Dabei sind je nach Aufgabenstellung unterschiedliche Nebenbedingungen (z.B. begrenzte Kapazit¨ at der Fahrzeuge oder zeitliche Aspekte) zu beachten. In der Praxis kommt Tourenplanung in den unterschiedlichsten Branchen zur Anwendung. Einige Beispiele sind die effiziente Organisation der Abfallbeseitigung

[Kim u. a. 2006], der Auslieferung von Getr¨ anken [Golden u. Wasil 1987] oder des Schulbuseinsatzes [Li u. Fu 2002].

Im Folgenden werden die wichtigsten Grundlagen der Tourenplanung beschrieben. Dazu wird zun¨ achst in Abschnitt 3.1 das klassische Problem der Tourenplanung (engl. Vehicle Routing Problem, kurz VRP) vorgestellt. Anschließend wird die in Kapitel 2 eingef¨ uhrte Tourenplanungsaufgabe der Miele & Cie. KG als eine verallgemeinerte Variante des VRP modelliert. In Abschnitt 3.3 folgt eine ¨ Ubersicht ¨ uber

die grunds¨ atzlichen M¨ oglichkeiten zur L¨ osung von Tourenplanungsproblemen.

3.1 Probleme der Tourenplanung

Gegeben ist eine Menge von n Kunden, deren Standorte bekannt sind. F¨ ur jeden Kunden i ist ferner sein Bedarf q i an dem auszuliefernden Produkt bekannt. F¨ ur die Versorgung der Kunden in einer Planungsperiode steht eine Flotte von m gleichen Fahrzeugen mit der Kapazit¨ at Q bereit ¹ . Die Fahrzeuge sind alle an einem bestimmten Ort (dem so genannten Depot) stationiert. Die Entfernungen zwischen den verschiedenen Kundenstandorten und ihre Entfernung zum Depot sind in der Distanzmatrix D = (d ij ) verzeichnet.

Gesucht wird eine Menge von m (oder maximal m) Fahrzeugtouren und den dazu geh¨ origen Routen, welche:

¹ Wegen der begrenzten Kapazit¨ at der Fahrzeuge ist das klassische VRP ebenfalls als Capacitated Vehicle Routing Problem (CVRP) bekannt.

13

• im Depot beginnen und enden,

• gew¨ ahrleisten, dass jeder Kunde i genau einmal von genau einem Fahrzeug entsprechend seines Bedarfes q i beliefert wird, • die Kapazit¨ atsbeschr¨ ankung Q der Fahrzeuge beachten und • die gesamte Fahrstrecke aller Fahrzeuge minimieren.

Dabei versteht man unter:

• Tour: Die Menge aller Kunden die auf einer vom Depot aus startenden und im Depot endenden Fahrt eines Fahrzeuges beliefert werden. • Route: Die genaue Reihenfolge, in der die Kunden einer Tour zu besuchen sind. • Tourenplan: Eine Menge von Touren und zugeh¨ origen Routen, welche die Belieferung aller Kunden gew¨ ahrleisten und die Kapazit¨ atsbeschr¨ ankung des Problems beachten.

3.1.1 Modellierung und Problemvarianten

Das klassische VRP kann mit Hilfe eines Graphen G = (N, E) modelliert werden, vgl. [Dorronsoro 2006]. In der Knotenmenge N = {n 0 , n 1 , n 2 , . . . , n n } des Graphen repr¨ asentiert der Knoten n 0 das Depot und die Knoten n 1 , n 2 , . . . , n n die Kunden bzw. deren Standorte. Jedem “Kundenknoten” (also jedem n i ∈ N \{n 0 }) wird ein Gewicht q i zugeordnet, welches den Bedarf des Kunden an dem auszuliefernden Produkt darstellt. Jede Kante (i, j) aus der Kantenmenge E ist mit einem Gewicht d ij belegt. Dieses Gewicht stellt die Entfernung zwischen Knoten n i und n j dar und entspricht dem Wert in der Distanzmatrix D.

Abb. 3.1: Graphdarstellung eines Tourenplans f¨ ur ein klassisches VRP

14

Eine zul¨ assige L¨ osung des Problems (siehe Abb. 3.1) ist gegeben durch: • eine Zuordnung der Kunden zu Fahrzeugen in Form einer Partition T 1 , T 2 , . . . , T m der Menge N \{n 0 }, wobei f¨ ur jedes T i gilt: q j ≤ Q

ⁿ j ^∈T i

• die Festlegung der Reihenfolge der Kundenbesuche f¨ ur jede Route durch R 1 , R 2 . . . , R m , wobei jedes R i eine Permutation von T i ∪ n 0 ist. Die Literatur zum Problem der Tourenplanung behandelt neben dem klassischen VRP zahlreiche Abwandlungen des Problems. Einige davon sind: • Pickup and Delivery Problem (PDP): Bei dieser Variante sind G¨ uter oder Personen von bestimmten Orten abzuholen (pickup) und an anderen Orten wieder abzuliefern (delivery), vgl. [Desaulniers u. a. 2002]. • Periodic Vehicle Routing Problem (PVRP): Die Planung erfolgt f¨ ur einen l¨ angeren Planungshorizont (z.B. eine Woche). Zu entscheiden ist, in welcher Planungsperiode (z.B. Wochentag) und welcher Tour die einzelnen Kunden zu beliefern sind, vgl. [Cordeau u. a. 1997]. • Multi-Depot Vehicle Routing Problem (MDVRP): Bei dieser Art der Tourenplanung - den so genannten Mehrdepotproblemen - sind die zur Verf¨ ugung stehenden Fahrzeuge in mehreren, dezentralen Depots stationiert, vgl. [Cordeau u. a. 1997].

Wenn bei der Tourenplanung auch zeitliche Aspekte wie Zeitfenster (time windows) oder eine begrenzte Dauer der Arbeitseins¨ atze der Fahrzeuge beachtet werden m¨ ussen, spricht man von einem kombinierten Touren- und Zeitplanungsproblem (Ve- hicleRouting and Scheduling Problem, kurz VRSP). M¨ ogliche Klassifikationen f¨ ur

3.1.2 Komplexit¨ at

Algorithmus gefunden wird, welcher f¨ ur das VRP eine L¨ osung mit polynomialen Rechenaufwand ² ermitteln kann.

Die Identifizierung des klassischen VRP als NP-hart gibt auch Aufschluss ¨ uber die

Komplexit¨ at der unterschiedlichen Varianten des Problems. Dabei wird auf die Erkenntnis zur¨ uckgegriffen, dass ein Spezialfall eines Problems nie schwieriger zu l¨ osen sein kann als das Problem selbst. So gilt z.B. f¨ ur das MDVRP, dass es als verallgemeinerte Form des VRP ebenso NP-hart ist. F¨ ur die Zeitfenstervariante des

² Der Rechenaufwand eines Algorithmus ist polynomial, wenn die Anzahl der Rechenoperationen des Algorithmus proportional zu N ⁿ ist, wobei N die Problemgr¨ oße repr¨ asentiert (z.B. Anzahl der zu besuchenden Kunden beim VRP) und n eine positive ganzzahlige Konstante darstellt, vgl. [Dr´ eo u. a. 2006, S. 2]

15