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ür jeden Arbeitstag eine Planungsaufgabe, deren Ziel es ist, die Durchführung
aller Reparaturaufträge möglichst effizient zu organisieren. Gleichzeitig muss ein
Plan bestimmte zeitliche Anforderungen erfüllen, die aus tariflichen Arbeitszeit- und
Pausenbestimmungen auf der einen, und aus Terminwünschen 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äne generiert, die
erhebliches Potenzial für eine nachgelagerte Optimierung bieten. Im Rahmen der
vorliegenden Arbeit wurde zu diesem Zweck ein Evolutionärer Algorithmus implementiert.
Die Implementierung erfüllt alle Vorgaben der Planungsaufgabe und ist in
der Lage, die Ergebnisse von AMS zu verbessern.
Inhaltsverzeichnis
1 Einleitung
1.1 Vorausgegangene Arbeiten
1.2 Ziel und Aufbau der Diplomarbeit
2 Technischer Kundendienst der Miele & Cie. KG
2.1 Rahmenbedingungen und Organisation
2.1.1 Disposition der Kundenaufträge
2.1.2 Auftragsdurchführung
2.2 Verbesserungspotenziale in der Planung des Technikereinsatzes
2.2.1 Realitätsnahe Schätzung der Fahrzeiten
2.2.2 Nachgelagerte Optimierung
2.2.3 Einplanung der Pausen und der Fahrt zum ersten Kunden
3 Grundlagen der Tourenplanung
3.1 Probleme der Tourenplanung
3.1.1 Modellierung und Problemvarianten
3.1.2 Komplexität
3.2 Tourenplanung beim technischen Kundendienst der Miele & Cie. KG
3.3 Lösungsmethoden
3.3.1 Exakte Verfahren
3.3.2 Heuristiken
4 Evolutionäre Algorithmen
4.1 Ursprung
4.2 Genereller Ablauf und zentrale Begriffe
4.3 Komponenten evolutionärer Verfahren
4.3.1 Lösungsrepräsentation und Kodierung
4.3.2 Bewertungs-/Fitnessfunktion
4.3.3 Elternselektion
4.3.4 Genetische Operatoren
4.3.5 Selektion der Nachfolgegeneration
4.3.6 Populationsgröße
4.3.7 Initialisierung der Startpopulation
4.4 Berücksichtigung von Nebenbedingungen
5 Lösungsentwurf und Implementierung
5.1 Lösungsrepräsentation und Kodierung
5.2 Bewertungsfunktion
5.3 Elternselektion
5.4 Genetische Operatoren
5.4.1 Rekombinationsoperator
5.4.2 Mutationsoperator
5.5 Selektion der Nachfolgegeneration
5.6 Populationsgröße
5.7 Initialisierung der Startpopulation
6 Evaluation
6.1 Vergleich mit den Ergebnissen des Decision Support Project
6.1.1 Ergebnisse der exakten Optimierung
6.1.2 Ergebnisse der Heuristik VNS
6.2 Vergleich mit der VNS-Implementierung von Szczepanski und Graute
7 Zusammenfassung und Ausblick
A Programmdokumentation
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 custo- mers’ 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 consi- derable 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ür jeden Arbeitstag eine Planungsaufgabe, deren Ziel es ist, die Durchführung aller Reparaturaufträge möglichst effizient zu organisieren. Gleichzeitig muss ein Plan bestimmte zeitliche Anforderungen erfüllen, die aus tariflichen Arbeitszeitund Pausenbestimmungen auf der einen, und aus Terminwünschen 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äne generiert, die erhebliches Potenzial für eine nachgelagerte Optimierung bieten. Im Rahmen der vorliegenden Arbeit wurde zu diesem Zweck ein Evolutionärer Algorithmus implementiert. Die Implementierung erfüllt alle Vorgaben der Planungsaufgabe und ist in der Lage, die Ergebnisse von AMS zu verbessern.
Abkürzungsverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
Abbildungsverzeichnis
2.1 Vertriebsregionen und Technikerstandorte der Miele & Cie. KG in Deutschland
2.2 Darstellung unterschiedlicher Dispositionsalternativen in AMS
2.3 Potenzialanalyse für die Planung des Technikereinsatzes
2.4 Erweiterung eines Tourenplans bei Disposition eines Auftrages im Online-Optimierungsverfahren
2.5 Optimaler Tourenplan
3.1 Graphdarstellung eines Tourenplans für ein klassisches VRP
4.1 Verletzung des Prinzips der strengen Kausalität bei der Binärkodierung
4.2 Beispiel eines einfachen Crossover
4.3 Beispiel einer einfachen Mutation
4.4 Nachbarschaft einer unzulässigen Lösung x zum globalen Optimum x*
5.1 Lösung eines CVRP und ihre GVR-Darstellung
5.2 Beispiel eines einfachen Tourenplans der Miele & Cie. KG und seine GVR-basierte Darstellung
5.3 Beispiel eines Genotyps und seiner Interpretation auf der Phänotyp- Ebene
5.4 Beziehungen zwischen den Klassen Individuum, Tourenplan und Rou- tenplan
5.5 Rouletterad und Implementierungsmodell am Beispiel einer Popula- tion mit sechs Individuen
5.6 Beispiel zweier Elternindividuen p1 und p2
5.7 Rekombination der Individuen p1 und p2
5.8 Elitäres Ersetzungsschema zur Selektion der Nachfolgegeneration
Tabellenverzeichnis
2.1 Einflussfaktoren bei der Disposition von Aufträgen
4.1 Zentrale Begriffe Evolutionärer Algorithmen und ihre Analogien zur Biologie
5.1 Berechnung der Strafe für Restriktionsverletzungen in einer Route Ri
6.1 Ergebnisse des Evolutionären Algorithmus für 13 Referenztourenpläne
6.2 Ergebnisse des Evolutionären Algorithmus im Vergleich mit CPLEX- Lösungen
6.3 Im DSP verwendete Testinstanzen
6.4 DSP-Testinstanzen nach dem Löschen der unzulässigen Routen . . .
6.5 Durchschnittliche Ergebnisse des Evolutionären Algorithmus für über- arbeitete Testinstanzen des DSP
6.6 Ergebnisse des Evolutionären Algorithmus für überarbeitete Testin- stanzen des DSP nach 250 Generationen
6.7 Gegenüberstellung der Ergebnisse der VNS-Heuristik und der Ergeb- nisse des Evolutionären Algorithmus (EA)
6.8 In der Seminararbeit von Szczepanski und Graute verwendete Testin- stanzen
6.9 Ergebnisse des Evolutionären Algorithmus für die Testinstanzen aus [Szczepanski u. Graute 2005]
1 Einleitung
In den heutigen, hart umkämpften Märkten ist hohe Kundenzufriedenheit entschei- dend für den Erfolg eines Unternehmens. Vor diesem Hintergrund bietet die Miele & Cie. KG den Abnehmern ihrer Erzeugnisse nicht nur qualitativ hochwertige Produk- te sondern auch einen zuverlässigen technischen Kundendienst an. Dafür unterhält das Unternehmen ein flächendeckendes Netz von bundesweit stationierten mobilen Technikern, welche die anfallenden Reparaturaufträge direkt am Standort des be- troffenen Gerätes ausführen.
Die Ergebnisse der täglichen Planung des Technikereinsatzes werden in so genannten Tourenplänen erfasst. Diese legen fest:
1. Welche Aufträge die einzelnen Techniker am gegebenen Arbeitstag überneh- men sollen.
2. In welcher Reihenfolge und nach welchem Zeitplan die Techniker die ihnen jeweils zugeordneten Aufträge bearbeiten sollen.
Aus Kostengründen ist es wünschenswert, Tourenpläne zu generieren, welche für die Techniker möglichst kurze Fahrten vorsehen. Gleichzeitig muss ein Plan bestimmte zeitliche Anforderungen erfüllen, die aus tariflichen Arbeitszeit- und Pausenbestim- mungen auf der einen, und aus Terminwünschen der Kunden auf der anderen Seite resultieren. Ein weiterer zu beachtender Faktor sind die unterschiedlichen Qualifi- kationsprofile der Techniker.
Insgesamt stellt sich die Planung des Technikereinsatzes als eine komplexe Aufgabe dar, welche aus theoretischer Sicht als ein qualifikationsbezogenes Mehrdepottouren- planungsproblem mit Zeitfenstern1 (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 Lehr- stuhl Decision Support & OR Lab. Zum einen wurden in der Diplomarbeit von Gerke die für die Planung des Kundendienstes relevanten Prozesse eingehend analysiert. Darüber hinaus wurden verschiedene Verfahren zur Distanz- und Fahrzeitschätzung für die Fahrten der Techniker untersucht, vgl. [Gerke 2005].
Im Rahmen der Veranstaltung Decision Support Project (DSP), welche im Winterse- mester 2004/2005 stattgefunden hat, wurde mit der Variable-Neighborhood-Search- Methode aus [Polacek u. a. 2004] eine Heuristik für die nachgelagerte Optimierung der AMS-Tourenpläne verwendet. Unter der Annahme einer leicht vereinfachten Problemformulierung konnte bei den bisherigen Tourenplänen ein Verbesserungspo- tenzial 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ässigte Aspekte der Aufgabenstellung ergänzt. Insgesamt konnte immer noch ein interessantes Op- timierungspotenzial der AMS-Tourenpläne nachgewiesen werden, vgl. [Szczepanski u. Graute 2005].
1.2 Ziel und Aufbau der Diplomarbeit
Ziel der vorliegenden Diplomarbeit ist es, eine auf dem Prinzip Evolutionärer Algorithmen basierende Methode zu konzipieren und zu implementieren. Anschließend soll untersucht werden, ob diese Methode für eine nachgelagerte Optimierung der Tourenpläne der Miele & Cie. KG genutzt werden kann. Evolutionäre Algorithmen setzen bestimmte Prinzipien biologischer Evolution und Genetik zur Lösung von Optimierungsproblemen ein und sind bereits erfolgreich zur Bewältigung anderer komplexer Tourenplanungsaufgaben eingesetzt worden.
Die Arbeit geht zunächst in Kapitel 2 auf die Rahmenbedingungen und die Or- ganisation des Kundendienstes der Miele & Cie. KG ein und zeigt mögliche Ver- besserungspotenziale in der Planung des Technikereinsatzes auf. In Kapitel 3 wird die Aufgabe als ein Tourenplanungsproblem formuliert und ein Überblick über die grundsätzlich dafür in Frage kommenden Lösungsmethoden gegeben. Die zur Klas- se der metaheuristischen Lösungsverfahren zählenden Evolutionären Algorithmen werden in Kapitel 4 eingehend beschrieben. Kapitel 5 enthält Erläuterungen zu den Komponenten des Evolutionären Algorithmus, welcher im Rahmen dieser Arbeit für 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 Technischer Kundendienst der Miele & Cie. KG
Die Miele & Cie. KG ist ein bekannter Anbieter von Elektrogeräten und stellt den Abnehmern ihrer Produkte einen mobilen Kundendienst zur Verfügung. Die effiziente Organisation des Einsatzes der Techniker, welche in diesem Kundendienst beschäftigt sind, muss sowohl räumliche als auch zeitliche Aspekte berücksichtigen und stellt eine komplexe Aufgabe dar.
Die folgenden Ausführungen beschreiben, wie diese Aufgabe in der Miele & Cie. KG derzeit gelöst wird. Dazu werden zunächst in Abschnitt 2.1 die Rahmenbedingun- gen und die Organisation der in diesem Zusammenhang relevanten Arbeitsabläufe 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äten versorgt die Miele & Cie. KG mit Hauptsitz in Gütersloh sowohl private Haushalte als auch gewerbliche Abnehmer. Das Pro- duktportofolio umfasst unter anderem Staubsauger, Geschirrspüler, Kühlschränke, Waschautomaten sowie Maschinen für Geschirrreinigung und Aufbereitung von La- borinstrumenten. Für die Reparatur und Wartung der Geräte stellt das Unterneh- men einen Kundendienst bereit, in welchem ca. 600 Techniker beschäftigt sind. Die Techniker sind an verschiedenen Standorten in ganz Deutschland stationiert (siehe Abb. 2.1) und erledigen den überwiegenden Teil der Reparatur- und Wartungsar- beiten direkt beim Kunden.
Die Planung und Organisation des Technikereinsatzes in Deutschland übernehmen die Servicezentren der sechs Vertriebsregionen Hamburg, Berlin, Frankfurt, Karls- ruhe, Bochum und München. 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 wei- tere für die Einsatzplanung der Techniker relevanten Daten (Kunden-, Techniker- und Produktstammdaten) verwaltet. Welche Daten das im Einzelnen sind, wird nachfolgend erläutert.
Abbildung in dieser Leseprobe nicht enthalten
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ächst 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. Eben- falls festgehalten werden Informationen über den Grund des Reparaturauftrages und die Produktnummer des betroffenen Gerätes. Darüber hinaus werden zeitliche Vor- gaben des Kunden bezüglich des Technikerbesuches vermerkt: zum einen die in Ka- lendertagen ausgedrückten möglichen 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öglich, weil der Auftrag zu einem bestimmten Termin stattfinden muss, wird als Terminart “Fixtermin” festgehalten. Fixtermine kommen in der Regel nur in dringenden Fällen vor, z.B. beim Auftreten eines Defektes wich- tiger Geräte in Krankenhäusern, vgl. [Gerke 2005, S. 6 f].
Technikerdaten
Für jeden Techniker ist ein Arbeitszeitmodell hinterlegt. Es enthält Vorgaben zum Beginn und Ende seiner Arbeitszeit sowie zu der von ihm einzuhaltenden Pausendauer. In der Regel beträgt die Pausendauer 45 Minuten pro Arbeitstag.
Darüber hinaus ist jedem Techniker ein Qualifikationsprofil zugeordnet. Es gibt Aufschluss darüber, 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ück. Jedem Techniker ist anhand von Postleitzahlen ein bestimmtes Stammgebiet zugeordnet, in welchem er vornehmlich zum Einsatz kommt. Weiteren Gebieten, in denen er aushilfsweise tätig sein kann, wird in der Gebietszuordnung eine niedrigere Priorität zugewiesen.
Produktdaten
Jedes Gerät besitzt eine Produktnummer. Über diese Nummer kann die Produktgruppe identifiziert werden, zu welcher es gehört. Für jede Produktgruppe wiederum ist festgelegt, welche Qualifikationen sie im Reparaturfall erfordert. Somit kann über die Zuordnung eines Gerätes zu einer Produktgruppe auf die für seine Reparatur in Frage kommenden Techniker geschlossen werden.
Die Produktgruppenzuordnung fließt auch in die Veranschlagung voraussichtlicher Arbeitszeiten für die Reparatur eines Gerätes ein. So ist beispielsweise die Arbeitszeit bei der Gruppe “Waschmaschinen” geringer als bei “professionellen Desinfektionsgeräten”, vgl. [Gerke 2005, S. 12].
2.1.1 Disposition der Kundenaufträge
Die automatische Disposition von Kundenaufträgen wird von AMS unterstützt. 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.
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 2.1: Einflussfaktoren bei der Disposition von Aufträgen
Auf der Grundlage dieser Angaben ermittelt AMS diejenigen Techniker1, welche für die Erledigung des Auftrages in Frage kommen. Für diese Techniker wiederum werden - unter Berücksichtigung ihrer Arbeitszeitmodelle und ggf. zuvor eingeplanter Termine - alle im Rahmen der Terminart des Auftrages zulässigen Bearbeitungszeitpunkte untersucht und bewertet. Dem Disponenten werden die daraus resultierenden Dispositionsalternativen zur Auswahl vorgeschlagen, siehe Abb. 2.2.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2.2: Darstellung unterschiedlicher Dispositionsalternativen in AMS, Quelle: [Szczepanski u. a. 2005, S. 20]
Die Bewertung der unterschiedlichen Dispositionsalternativen wird in AMS von meh- reren Faktoren bestimmt. Der in die Bewertung am stärksten einfließende Faktor bezieht sich auf die so genannte Tourenverlängerung, also die Frage: Um wie vie- le Kilometer verlängert sich die von einem Techniker am gewählten Arbeitstag zu fahrende Strecke, wenn der Auftrag ihm zugeordnet wird? Zur Beantwortung dieser Frage berechnet AMS die euklidischen Luftliniendistanzen als Näherungswerte für die tatsächlichen Längen der Fahrstrecken zwischen den jeweiligen geographischen Orten.
Ein weiterer in der Bewertungszahl berücksichtigter Aspekt betrifft die Einhaltung der Vorgaben, welche der Kunde bezüglich des Zeitpunktes des Technikerbesuches gemacht hat (Stichwort Terminart ). Für die dazu erforderliche Angabe, wann der Techniker am Auftragsort eintrifft, erfolgt in AMS eine Schätzung der Bearbeitungs- und der Fahrzeiten. Die voraussichtliche Bearbeitungszeit eines Auftrages wird nach Erfahrungswerten ähnlicher Aufträge aus der Vergangenheit geschätzt. Bei Fahrzeitberechnungen geht AMS von einer Durchschnittsgeschwindigkeit von 30 km/h und einer Rüstzeit von sieben Minuten pro Fahrt aus, vgl. [Gerke 2005, S. 9].
Die Bewertungszahl unterstützt den Disponenten bei der Auswahl der Dispositionsalternative. Dabei gilt: je größer der Wert der Bewertungszahl, desto besser erfüllt diese Alternative die unterschiedlichen Bewertungskriterien. Hat der Disponent die Auswahl getroffen, wird der Auftrag dem gewählten Techniker zugeordnet und erscheint in seinem Arbeitsplan.
AMS unterstützt nicht nur die automatische Disposition von Aufträgen. Es erlaubt darüber hinaus manuelle Veränderungen an den Touren bzw. Routen der Techniker. Solche Veränderungen werden beispielsweise dann vorgenommen, wenn ein Kunde seinen Auftrag storniert. Sie können aber auch der Optimierung von Plänen dienen, in welchen die Disponenten offensichtliche Umwege erkennen konnten.
2.1.2 Auftragsdurchführung
Alle Techniker sind mit einem Notebook ausgestattet. Am Vorabend eines Arbeits- tages stellen sie eine Verbindung zum Servicezentrum ihrer jeweiligen Region her und erhalten von AMS ihren individuellen Einsatzplan für den nächsten Tag.
Jeder Techniker besitzt ein Einsatzfahrzeug, welches mit den am häufigsten benötigten Ersatzteilen und Werkzeugen ausgestattet ist. Mit diesem Fahrzeug besucht der Techniker die Kunden entsprechend des Tourenplans und erfasst dabei seine tatsächlichen Fahr- und Arbeitszeiten sowie den Materialverbrauch. Den Kunden wird vor Ort eine Rechnung erstellt und ausgehändigt.
Bei Aufträgen, die nicht an einem Tag abschließend bearbeitet werden können - z.B. weil das dazu benötigte Ersatzteil nicht vom Techniker mitgeführt wurde und erst bestellt werden muss - werden so genannte Folgeaufträge erzeugt. Der Techniker muss in einem solchen Fall den Kunden an einem anderen Tag zum zweiten Mal besuchen.
Die Techniker können nach eigenem Ermessen entscheiden, wann sie während des Arbeitstages ihre Pausenzeiten nehmen. Sie planen dazu ihre Pausen zwischen jeweils zwei Aufträgen 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ägen kann somit in AMS nicht von der zwischen ihnen liegenden Fahrzeit unterschieden werden.
Nach der Erledigung aller Aufträge ihrer Touren kehren die Techniker zu ihren Depots zurück. Sie melden die während des Tages erfassten Daten an AMS zurück und erhalten wiederum die Plandaten für ihren nächsten Arbeitstag.
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ührt. Nachfolgend werden die aufgedeckten Zusammenhänge und abgeleiteten Verbesserungspotenziale im Einzelnen erläutert.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2.3: Potenzialanalyse für die Planung des Technikereinsatzes
2.2.1 Realitätsnahe Schätzung der Fahrzeiten
Eine Schwachstelle besteht darin, dass bei der Planung des Technikereinsatzes re- gelmäßig manuelle Eingriffe seitens der Disponenten erfolgen. Das Eingreifen der Disponenten in den komplexen Planungsprozess ist nicht wünschenswert, es ist je- doch notwendig, weil die vollständig automatische Disposition in AMS erfahrungs- gemäß zur Überlastung bzw. mangelnder Auslastung einzelner Techniker führt.
Die Unzulänglichkeit der automatischen Disposition resultiert aus der unrealisti- schen Schätzung der Fahrzeiten der Techniker. In manchen Gebieten (z.B. in Bal- lungszentren) ergeben sich für die Techniker erfahrungsgemäß längere Fahrzeiten als von AMS geschätzt. Das hat zur Folge, dass die dort im Einsatz befindlichen Techni- ker tendenziell mehr Aufträge vom System zugewiesen bekommen als sie tatsächlich in ihrer Arbeitszeit schaffen können. Die Disponenten versuchen das Problem zu umgehen, indem sie fiktive Aufträge (so genannte “künstliche Aufträge”) erzeugen und den betroffenen Technikern manuell zuordnen.
Die Einplanung eines “künstlichen Auftrages” am Ende der Route eines Technikers reduziert seine noch verfügbare Arbeitszeit und verhindert so die Zuweisung zu vieler Kundenaufträge. Wird dem “künstlichen Auftrag” aber zu viel Zeit zugemessen, führt seine Einplanung zu einer zu geringen tatsächlichen Auslastung des Technikers, also einem unerwünschten Effekt. An dieser Stelle wird deutlich, dass dieser Kunstgriff problematisch ist und - selbst von erfahrenen Disponenten eingesetzt - unbeabsichtigte Folgen haben kann.
In Gebieten, in welchen sich die Techniker schneller als von AMS geschätzt bewegen können (z.B. in ländlichen Gegenden), führt die automatische Disposition in der Regel zu einer unzureichenden Auslastung der Techniker. Der Disponent versucht in einem solchen Fall, die noch vorhandene Kapazität durch die manuelle Zuwei- sung eines zusätzlichen Kundenauftrages zu nutzen. Dazu ändert er den geplanten Bearbeitungsbeginn der automatisch disponierten Aufträge des Technikers so, dass sich für den zusätzlichen Auftrag ein zeitliches Fenster eröffnet. Bei diesem Vorgang sieht der Disponent auf seiner Plantafel aber nur die zeitlichen Auswirkungen sei- nes manuellen Eingriffes. Er hat keinen Überblick darüber, inwiefern der Einschub des zusätzlichen Auftrages an einer bestimmten Stelle der Route zur Entstehung unnötiger Umwege führen kann.
Die Analyse zeigt also, dass manuelle Eingriffe seitens der Disponenten notwen- dig sind, weil die auf unrealistischen Fahrzeitschätzungen basierende automatische Disposition regelmäßig beeinflusst bzw. korrigiert werden muss. Warum aber sind die in AMS gemachten Fahrzeitschätzungen unrealistisch? Die wesentliche Ursache dafür 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ährend einer Fahrt tatsächlich erreichte Durch- schnittsgeschwindigkeit mit der Luftlinienentfernung ihrer Start- und Zieladresse korreliert, vgl. [Gerke 2005, S. 43]. Auch zwischen der Bevölkerungsdichte2 der Start- und Zieladresse einer Fahrt und ihrer Durchschnittsgeschwindigkeit ist ein signifi- kanter Zusammenhang nachweisbar, vgl. [Gerke 2005, S. 55]. Die Arbeit von Gerke hat gezeigt, dass die Einbeziehung der Entfernung und Bevölkerungsdichte in die Schätzfunktion der Durchschnittsgeschwindigkeit zur Verbesserung der Planungsge- nauigkeit von AMS beitragen kann und somit ein wichtiges Verbesserungspotenzial darstellt.
Als eine weitere Ursache für die unrealistischen Fahrzeitschätzungen ist die Ap- proximation der zu fahrenden Strecken mittels euklidischer Luftliniendistanzen zu nennen. Das Problematische an dieser Vorgehensweise ist, dass die zwischen zwei Auftragsorten zurückzulegende Strecke in Wirklichkeit deutlich von ihrer Luftli- niendistanz abweichen kann. Also liegt auch hier ein Verbesserungspotenzial vor, welches ausgeschöpft werden kann, wenn für die jeweiligen Fahrten der Techniker die tatsächlich zu wählenden 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äglich zu fahrende Gesamtstrecke zu minimieren. Die Tatsache, dass die bei der derzeitigen Vorgehensweise entstehenden Tourenpläne bezüglich dieses Kriteri- ums suboptimal sind, stellt eine wichtige Schwachstelle des untersuchten Systems dar, siehe Abb. 2.3.
Eine Ursache dieser Suboptimalität wurde schon erwähnt: Es ist die manuelle Dispo- sition zusätzlicher Aufträge zu Technikern, bei welchen die Disponenten sonst eine mangelnde Auslastung erwarten, vgl. S. 9 der vorliegenden Arbeit. Diese manuelle Disposition kann für einzelne Techniker zu Routen führen, die vermeidbare Umwege enthalten.
Ein weiterer Grund der Suboptimalität der Tourenpläne ist die Art und Weise, mit welcher die automatische Disposition die Aufträge erfolgt. Neue Kundenauf- träge werden nicht gesammelt, um aus ihrer Gesamtheit einen optimalen Touren- plan zu erstellen. Vielmehr werden sie im Moment ihrer Erfassung sofort disponiert. Der Tourenplan wird also schrittweise aufgebaut, wobei bei jeder Erweiterung ver- sucht wird, die mit ihr verbundene Verlängerung der zu fahrenden Strecke (genannt Tourenverlängerung, vgl. Abschnitt 2.1.1) so klein wie möglich zu halten. Bereits getroffene Dispositionsentscheidungen werden im Nachhinein nicht mehr revidiert. Diese Vorgehensweise entspricht dem so genannten Sequenzparadigma der Online- Optimierung3.
Gerke zeigt in seiner Arbeit an einem anschaulichen Beispiel, wie dieses Vorgehen zu einem suboptimalen Tourenplan führen 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ätzte Länge der jeweiligen Fahrt in km.
Abb. 2.4(b) veranschaulicht, wie für einen weiteren zu disponierenden Kunden- auftrag (schwarzer Knoten) die Tourenverlängerung zweier Dispositionsalternativen verglichen wird. Wird der Auftrag in die links im Bild erscheinenden Route einge- ordnet, ergibt sich eine Tourenverlängerung von 21 km (11 + 18 - 8). Die Zuordnung dieses Auftrages zur Route des zweiten Technikers bedeutet dagegen eine Touren-
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2.4: Erweiterung eines Tourenplans bei Disposition eines Auftrages im Online- Optimierungsverfahren, Quelle: [Gerke 2005, S. 71], leicht verändert
verlängerung von 17 km (30 + 11 - 24). Folglich wird die zweite Alternative gewählt und es ergibt sich der in Abb. 2.4(c) dargestellte suboptimale Tourenplan.
Der optimale Tourenplan, welcher das wünschens- werte Ergebnis der Disposition darstellt, ist in Abb. 2.5 sichtbar. In ihm wurde eine zuvor - unter Unkenntnis des jetzt zu disponierenden Auftrages - getroffene Dispositionsentscheidung revidiert. Eine solche Modifikation des Touren- plans entspricht der veränderten Gesamtsituati- on, die sich durch einen weiteren zu disponieren- den Auftrag (schwarzer Knoten) ergibt.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2.5: Optimaler Tourenplan
AMS verfährt aber bei der automatischen Disposition nach einem Online-Optimierungs- algorithmus, der den Tourenplan schrittweise um einzelne Aufträge erweitert und nachträgliche Modifikationen bereits getroffener Entscheidun- gen nicht in Betracht zieht. Dementsprechend bietet der am Vorabend eines Arbeits- tages feststehende, von AMS erstellte Tourenplan noch Potenzial für eine nachgela- gerte Optimierung. Diese kann eine Reduzierung der für die Techniker entstehenden Fahrstrecken erreichen: einerseits - wie in dem zuvor vorgestellten Beispiel - durch alternative Aufteilung der Aufträge auf die in Frage kommenden Techniker und an- dererseits durch die Änderung 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ücksichtigt wer- den. Zum einen gibt es Regelungen, die besagen, dass die Techniker nach spätestens sechs Stunden Arbeit die Möglichkeit für eine Pause bekommen müssen. In AMS werden die Pausen jedoch nicht im Voraus fest eingeplant. Vielmehr liegt es an den Technikern, selbst für die Einhaltung ihrer Pausen zu sorgen.
Zum anderen gibt es tarifliche Bestimmungen bezüglich der Anfahrt zur Arbeit: nur die ersten 30 Minuten der Anfahrt sollen nicht als Arbeitszeit betrachtet werden. Da- gegen ist bei Fahrten, welche mehr als eine halbe Stunde dauern, eine entsprechende arbeitszeitliche Anrechnung vorzunehmen. Diese Regelung wird von AMS nicht be- achtet, weil darin die Fahrt zum ersten Kunden grundsätzlich 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önnen in gleicher Weise wie Kundenaufträge feste Zeiten im ge- planten 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.
3 Grundlagen der Tourenplanung
Bei Problemen der Tourenplanung geht es im Allgemeinen um die Planung opti- maler Routen für 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ät 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änken [Golden u. Wasil 1987] oder des Schulbuseinsatzes [Li u. Fu 2002].
Im Folgenden werden die wichtigsten Grundlagen der Tourenplanung beschrieben. Dazu wird zunächst in Abschnitt 3.1 das klassische Problem der Tourenplanung (engl. Vehicle Routing Problem, kurz VRP) vorgestellt. Anschließend wird die in Kapitel 2 eingeführte Tourenplanungsaufgabe der Miele & Cie. KG als eine verall- gemeinerte Variante des VRP modelliert. In Abschnitt 3.3 folgt eine Übersicht über die grundsätzlichen Möglichkeiten zur Lösung von Tourenplanungsproblemen.
3.1 Probleme der Tourenplanung
Das klassische Problem der Tourenplanung (VRP) wurde in [Dantzig u. Ramser 1959] eingeführt und lässt sich wie folgt beschreiben:
Gegeben ist eine Menge von n Kunden, deren Standorte bekannt sind. Für jeden Kunden i ist ferner sein Bedarf qi an dem auszuliefernden Produkt bekannt. Für die Versorgung der Kunden in einer Planungsperiode steht eine Flotte von m gleichen Fahrzeugen mit der Kapazität Q bereit1. 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 = (dij ) verzeichnet.
Gesucht wird eine Menge von m (oder maximal m) Fahrzeugtouren und den dazu gehörigen Routen, welche:
- im Depot beginnen und enden,
- gewährleisten, dass jeder Kunde i genau einmal von genau einem Fahrzeug entsprechend seines Bedarfes qi beliefert wird,
- die Kapazitätsbeschränkung 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örigen Routen, welche die Belieferung aller Kunden gewährleisten und die Kapazitätsbeschränkung 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 = {n0, n1, n2, . . . , nn} des Graphen repräsentiert der Knoten n0 das Depot und die Knoten n1, n2, . . . , nn die Kunden bzw. deren Standorte. Jedem “Kundenknoten” (also jedem ni ∈ N \{n0}) wird ein Gewicht qi zugeordnet, welches den Bedarf des Kunden an dem auszuliefernden Produkt darstellt. Jede Kante (i, j) aus der Kantenmenge E ist mit einem Gewicht dij belegt. Dieses Gewicht stellt die Entfernung zwischen Knoten ni und nj dar und entspricht dem Wert in der Distanzmatrix D.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 3.1: Graphdarstellung eines Tourenplans für ein klassisches VRP
Eine zulässige Lösung des Problems (siehe Abb. 3.1) ist gegeben durch:
- eine Zuordnung der Kunden zu Fahrzeugen in Form einer Partition [Abbildung in dieser Leseprobe nicht enthalten] der Menge N\{n0}, wobei für jedes Ti gilt:[Abbildung in dieser Leseprobe nicht enthalten]
- die Festlegung der Reihenfolge der Kundenbesuche für jede Route durch[Abbildung in dieser Leseprobe nicht enthalten], wobei jedes Ri eine Permutation von Ti ∪ n0 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üter 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ür einen längeren 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ügung stehenden Fahrzeuge in mehreren, dezentralen Depots stationiert, vgl. [Cordeau u. a. 1997].
Wenn bei der Tourenplanung auch zeitliche Aspekte wie Zeitfenster (time win- dows) oder eine begrenzte Dauer der Arbeitseinsätze der Fahrzeuge beachtet werden müssen, spricht man von einem kombinierten Touren- und Zeitplanungsproblem (Ve- hicle Routing and Scheduling Problem, kurz VRSP). Mögliche Klassifikationen für die zahlreichen Varianten der VRSP werden in [Bodin u. Golden 1981] und [Desro- chers u. a. 1990] vorgestellt.
3.1.2 Komplexität
Beim klassischen VRP handelt es sich um ein NP-hartes Problem, vgl. [Lenstra u. Rinnooy Kan 1981]. Dabei bedeutet NP-hart, dass nicht zu erwarten ist, dass ein Algorithmus gefunden wird, welcher für das VRP eine Lösung mit polynomialen Rechenaufwand2 ermitteln kann.
Die Identifizierung des klassischen VRP als NP-hart gibt auch Aufschluss über die Komplexität der unterschiedlichen Varianten des Problems. Dabei wird auf die Er- kenntnis zurückgegriffen, dass ein Spezialfall eines Problems nie schwieriger zu lösen sein kann als das Problem selbst. So gilt z.B. für das MDVRP, dass es als ver- allgemeinerte Form des VRP ebenso NP-hart ist. Für die Zeitfenstervariante des Problems der Tourenplanung (Vehicle Routing Problem with Time Windows, kurz VRPTW) stellt alleine das Auffinden einer zulässigen Lösung ein NP-vollständiges Problem dar, vgl. [Savelsbergh 1985].
3.2 Tourenplanung beim technischen Kundendienst der Miele & Cie. KG
Die in Kapitel 2 beschriebene Aufgabe der Planung des Technikereinsatzes der Miele & Cie. KG kann als eine Tourenplanungsaufgabe modelliert werden. Als Planungshorizont wird ein Arbeitstag betrachtet. Da der tägliche Einsatz der Techniker an ihrem jeweiligen Wohnort startet und dort endet, wird die Aufgabe als ein Mehrdepotproblem formuliert. Die in AMS Terminart genannte Angabe eines Zeitintervalls, in welchem die Durchführung der Arbeiten beim Kunden möglich ist, kann mit Hilfe von Zeitfenstern abgebildet werden.
In der Literatur sind derartige Probleme als Mehrdepottourenplanungsprobleme mit Zeitfenstern (Multi-Depot Vehicle Routing Problem with Time Windows, kurz MD- VRPTW) bekannt, vgl. [Desaulniers u. a. 1998]. Bei den zusätzlichen Aspekten, wel- che im vorliegenden praktischen Fall zu berücksichtigen sind, handelt es sich um die Arbeitszeitmodelle und Qualifikationen der Techniker. Im Folgenden wird das Op- timierungsmodell als ein qualifikationsbezogenes Mehrdepottourenplanungsproblem mit Zeitfenstern (Qualification based MDVRPTW, kurz Q-MDVRPTW) formuliert, vgl. [Kliewer u. a. 2005].
Qualifikationsbezogene Mehrdepottourenplanung mit Zeitfenstern
Für die Modellierung der Tourenplanungsaufgabe der Miele und Cie. KG werden zunächst folgende Parameter eingeführt:
Sei V die Menge der am betrachteten Arbeitstag verfügbaren Techniker. Für jeden Techniker v ∈ V sei der Beginn Sv und das Ende Tv seiner Arbeitszeit definiert. Ferner sei N die Menge aller Knoten des Problems. Es gelte:
Abbildung in dieser Leseprobe nicht enthalten
wobei Nv die Menge der Knoten des Technikers v notiert. Die Knotenmenge Nv des Technikers v umfasse seinen Depotknoten dv , einen zur Abbildung seiner Pause eingeführten Pausenknoten pv und die Menge NAv aller Auftragsknoten, für deren Bearbeitung er aufgrund seiner Qualifikation in Frage kommt, also:
Abbildung in dieser Leseprobe nicht enthalten
Für jeden Auftragsknoten i ∈ NAv seien eine Bearbeitungsdauer ti und ein Zeitfens- ter [ai, bi] gegeben. Dabei gebe ai den frühest- und bi den spätestmöglichen Bear- beitungsbeginn des Auftrags i an. Auch für jeden Pausenknoten pv seien eine Dauer tpv und ein Zeitfenster [apv ,bpv ] definiert. An dieser Stelle erlaubt die Definition von Zeitfenstern die Abbildung tariflicher Bestimmungen, welche im Zusammenhang mit Pausen gelten.
Die Menge der Kanten des Problems sei A. Es gelte:
Abbildung in dieser Leseprobe nicht enthalten
wobei Av die Menge der Kanten des Technikers v notiert. Diese Menge umfasse Kanten zwischen dem Depotknoten dv des Technikers und jedem Auftragsknoten aus der Menge NAv , Kanten zwischen je zwei Auftragsknoten aus NAv sowie Kanten zwischen dem Pausenknoten pv des Technikers und den einzelnen Auftragsknoten aus NAv :
Abbildung in dieser Leseprobe nicht enthalten
Jeder Kante (i, j) sei ein Gewicht tij zugeordnet, welches der Fahrtdauer zwischen den Knoten i und j entspricht. Es wird angenommen, dass jeder Techniker seine Pause direkt am Ort des Kundenauftrages absolviert, welcher der Pause unmittelbar vorhergeht. Demnach unternimmt der Techniker keine Fahrt zu einem gesonderten Pausenort, sondern befindet sich vor und nach der Pause am Ort des vorhergehenden Kundenauftrages. Aus diesem Grund haben alle Kanten, die in einem Pausenknoten münden oder von ihm abgehen, ein Gewicht von null Zeiteinheiten.
Als Entscheidungsvariablen des mathematischen Modells werden definiert:
xvij : binäre Variablen (für alle v ∈ V und alle (i, j) ∈ Av ) mit:
Abbildung in dieser Leseprobe nicht enthalten
Dvi: kontinuierliche Variablen (für alle v ∈ V und alle i ∈ Nv ), welche die Uhrzeit speichern, zu welcher Techniker v Knoten i verlässt.
Das mathematische Modell lautet dann, vgl. [Kliewer u. a. 2005]:
Abbildung in dieser Leseprobe nicht enthalten
unter den Nebenbedingungen:
Abbildung in dieser Leseprobe nicht enthalten
In der Zielfunktion (3.1) wird die Gesamtdauer aller Fahrten im Tourenplan minimiert. Bei Unterstellung einer konstanten Durchschnittsgeschwindigkeit für alle Fahrten des Tourenplans ist dies gleichbedeutend mit einer Minimierung der insgesamt zu fahrenden Strecke.
Nebenbedingung (3.2) stellt sicher, dass jeder Auftrag genau einem Techniker zu- geordnet wird. Gleichung (3.3) erreicht, dass jeder Techniker alle Knoten, welche er besucht, auch wieder verlässt. Der Ausdruck in (3.4) bewirkt, dass jeder Techniker sein Depot höchstens einmal verlässt. Gleichung (3.5) sagt aus, dass der Techniker nach einer Pause sich am selben Ort befindet wie davor. Gemäß (3.6) hat jeder Techniker genau eine Pause während seines Arbeitstages zu machen. Ungleichung (3.7) betrifft die Bestimmung des Zeitpunktes Dvj, zu welchem der Techniker v den Knoten j verlässt. Die Restriktionen (3.8) und (3.9) stellen sicher, dass der Beginn und das Ende der Arbeitszeit eines Technikers die in seinem Arbeitszeitmodell ver- einbarten Zeiten nicht verletzt. Die Einhaltung der Zeitfenster der Kundenaufträge und Pausenknoten wird durch Nebenbedingung (3.10) erzwungen. In (3.11) folgt die Definition der binären Entscheidungsvariablen xv ij .
3.3 Lösungsmethoden
Für die Lösung von Tourenplanungsproblemen kommen grundsätzlich exakte Verfahren oder Näherungsverfahren (so genannte Heuristiken) in Frage. Im Folgenden werden die Kennzeichen dieser Klassen von Methoden skizziert und ein Überblick über ihre Implementierungen insbesondere für (Mehrdepot)-Tourenplanungs- aufgaben mit Zeitfenstern gegeben.
3.3.1 Exakte Verfahren
Bei exakten Verfahren handelt es sich um Lösungsmethoden, welche in endlich vielen Schritten das mathematische Optimum eines lösbaren Optimierungsmodells finden, vgl. [Domschke 1997, S. 20]. Sie ermöglichen zudem den Nachweis der Optimalitätseigenschaft der ermittelten Lösungen.
Die zahlreichen in der Literatur beschriebenen exakten Optimierungsverfahren für verschiedene Varianten des Tourenplanungsproblems lassen sich den folgenden wesentlichen Klassen zuordnen:
- Branch-and-Bound
- Branch-and-Cut
- Set Partitioning-basierte Ansätze
- Dynamische Programmierung
Einen Überblick über die wichtigsten exakten Algorithmen für das VRP gibt [Laporte 1992]. Darüber hinaus findet der interessierte Leser in [Toth u. Vigo 2002] ausführliche Untersuchungen der Branch-and-Bound, Branch-and-Cut und Set-Partitioning- basierten Ansätze für das CVRP.
Für Mehrdepotprobleme der Tourenplanung wurden aufgrund ihrer Komplexität nur wenige exakte Lösungsverfahren entwickelt, vgl. [Domschke 1997, S. 255]. Auch für größere Tourenplanungsprobleme mit Zeitfenstern (VRPTW) sind die Möglichkeiten der exakten Optimierungsverfahren begrenzt, vgl. [Cordeau u. a. 2002, S. 157].
3.3.2 Heuristiken
Jenseits der exakten Verfahren gibt es Methoden, die mit vertretbarem Rechenauf- wand das Auffinden guter Lösungen für Optimierungsprobleme ermöglichen. Diese Verfahren werden als Heuristiken oder heuristische Verfahren bezeichnet. Im Ge- gensatz zu exakten Verfahren können Heuristiken ”keineGarantiedafürbieten,daß [durch ihren Einsatz] eine optimale Lösung des betrachteten Problems gefunden bzw. eine gefundene optimale Lösung als solche erkannt wird“ [Domschke 1997, S. 21].
Heuristische Verfahren lassen sich weiter in klassische Heuristiken und Metaheuristi- ken unterteilen. Dabei ist das Kennzeichen klassischer Heuristiken, dass sie problem- basiert arbeiten, d.h. sie nutzen bekannte Eigenschaften des zu lösenden Problems, um schneller gute Lösungen zu erhalten, vgl. [Suhl u. Mellouli 2005, S. 12]. Bei Me- taheuristiken handelt es sich dagegen um problemunabhängige Suchstrategien, die als übergeordnetes Prinzip den Suchvorgang einer klassischen Heuristik steuern, vgl. [Gendreau u. a. 2002, S. 129].
Klassische Heuristiken
Alle Probleme der Tourenplanung umfassen zwei grundsätzliche Teilprobleme, vgl. [Domschke 1997, S. 234], und zwar:
- ein Zuordnungsproblem (Clustering): Insgesamt stellt sich die Frage: Welche Kunden werden welcher Tour zugeordnet?
- ein Reihenfolgeproblem (Routing): Für jede einzelne Tour ist die Frage zu be- antworten: In welcher Reihenfolge sollen die Kunden der Tour besucht werden?
Bei Heuristiken, welche die beiden Teilprobleme nacheinander bearbeiten, spricht man von Sukzessiv- oder Zwei-Phasen-Verfahren. Wird zunächst das Zuordnungs- und anschließend das Reihenfolgeproblem gelöst, handelt es sich um eine Cluster- First-Route-Second-Methode. Entsprechend wird eine Methode, welche zuerst das Reihenfolgeproblem und dann das Zuordnungsproblem löst Route-First-Cluster- Second-Methode genannt.
Zu der Gruppe der Sukzessivverfahren zählt die Sweep-Heuristik, welche vor allem durch die Veröffentlichung von Gillett und Miller [Gillett u. Miller 1974] bekannt wurde. Auch bei den weit verbreiteten Heuristiken von Fisher und Jaikumar [Fisher u. Jaikumar 1981] und von Bramel und Simchi-Levi [Bramel u. Simchi-Levi 1995] handelt es sich um Sukzessivverfahren.
Ein anderes Vorgehen bestimmt den Ablauf so genannter Simultanverfahren: sie bau- en die zulässige Lösung eines Tourenplanungsproblems schrittweise auf und betrach- ten dabei das Zuordnungs- und das Reihenfolgeproblem gemeinsam. Als wichtigste Heuristik kann hier der in kommerzieller Tourenplanungssoftware häufig benutzte Savings-Algorithmus von Clarke und Wright [Clarke u. Wright 1964] genannt wer- den.
Man unterscheidet bei den Simultanverfahren zwei Klassen: zum einen Eröffnungs- und zum anderen Verbesserungsverfahren, vgl. [Domschke 1997, S. 235]. Eröffnungs- verfahren bilden Touren und die zugehörigen Routen für ein gegebenes Problem, wohingegen Verbesserungsverfahren von einem bereits gebildeten Tourenplan aus- gehend durch Modifikationen der Lösung versuchen, sie bezüglich der definierten Zielsetzung zu verbessern. Vielfach ist jedoch eine klare Unterscheidung zwischen Eröffnungs- und Verbesserungsverfahren nicht möglich, da zahlreiche Eröffnungsver- fahren sich bereits während der Konstruktion eines Tourenplans bestimmter Verbes- serungstechniken bedienen, vgl. [Laporte u. Semet 2002, S. 110].
Einige Verbesserungsverfahren beschränken sich auf die Optimierung der Routen ohne die Zuordnung der Kunden zu Fahrzeugen (Touren) zu modifizieren. Zu die- sen Methoden zählt z.B. der in [Lin 1965] eingeführte r-opt-Algorithmus. Andere Verfahren versuchen, eine Verbesserung der Lösung durch Veränderung der Touren zu erreichen. Mögliche tourenverändernde Operationen sind z.B. der Tausch von Kunden verschiedener Touren gegeneinander. In der Literatur ist eine Reihe tou- renverändernder Verbesserungsverfahren für das VRP bekannt, von denen einige in [Laporte u. Semet 2002, S. 122 f] beschrieben werden. Eine gute Übersicht über die neueren Entwicklungen in diesem Bereich bietet [Cordeau u. a. 2004a].
Verallgemeinerte Versionen der klassischen Heuristiken erlauben es, auch Touren- planungsprobleme mit Zeitfenstern und/oder mit mehreren Depots zu betrachten, vgl. [Domschke 1997, S. 254 f]. So beschreibt z.B. [Solomon 1987] für das VRPTW entwickelte Versionen der bekannten Sweep- und der Savings-Heuristik. In [Tansi- ni u. Viera 2005] wird eine Cluster-First-Route-Second-Heuristik für das mit der Tourenplanungsaufgabe der Miele & Cie. KG verwandte MDVRPTW vorgestellt. Insgesamt lässt sich jedoch sagen, dass die Zahl der Veröffentlichungen, welche sich mit der Lösung des MDVRPTW mittels klassischer Heuristiken befassen, begrenzt ist.
Metaheuristiken
Etwa seit Beginn der 1990er Jahre hat die Entwicklung von Metaheuristiken für Tourenplanungsprobleme große Aufmerksamkeit bekommen. Diese übergeordneten Strategien der heuristischen Suche unterscheiden sich von klassischen Heuristiken vor allem dadurch, dass sie während des Suchprozesses eine zwischenzeitliche Ver- schlechterung oder sogar Unzulässigkeit der potenziellen Lösung zulassen. Die daraus folgende breitere Untersuchung des Lösungsraumes führt dazu, dass Metaheuristi- ken in der Regel - wenn auch unter Beanspruchung von mehr Rechenkapazität - bessere Lösungen als die klassischen Verfahren finden, vgl. [Gendreau u. a. 2002].
Zu den im Bereich der Tourenplanung bedeutendsten Metaheuristiken zählen:
- Simuliertes Abkühlen (Simulated Annealing)
- Tabu-Suche (Tabu Search)
- Evolutionäre Algorithmen (Evolutionary Algorithms)
Simuliertes Abkühlen ist von dem unter der Bezeichnung Annealing bekann- ten Verfahren zur langsamen Abkühlung von Metallen inspiriert. Die langsame Ab- kühlung unterstützt die Bildung stabiler Kristallstrukturen und führt somit zur Erreichung eines energetisch (nahezu) optimalen Zustandes. Die Idee, dieses Prin- zip zur Lösung mathematischer Optimierungsprobleme anzuwenden, entwickelten [Kirkpatrick u. a. 1983] und [Cerny 1985] unabhängig voneinander. Demnach wird beim Simulierten Abkühlen eine lokale Suche3 durchgeführt, bei welcher mit einer bestimmten Wahrscheinlichkeit eine Verschlechterung der Lösung in der nächsten Iteration akzeptiert wird. Diese Wahrscheinlichkeit nimmt jedoch mit einer während des Optimierungslaufs sinkenden Steuerungsgröße (der so genannten Temperatur ) nach und nach ab.
Eine ausführliche Beschreibung der Prinzipien des Simulierten Abkühlens ist unter anderem in [Reeves 1995, S. 20 ff] zu finden. Bekannte Beispiele der Anwendung dieser Metaheuristik im Bereich der Tourenplanung sind unter anderem [Osman 1993] und [Van Breedam 1995].
Die so genannte Tabu-Suche wurde durch [Glover 1986] eingeführt. Tabu-Such- verfahren liegt eine lokale Suche zugrunde, bei welcher in jeder Iteration die beste Lösung der (nicht tabu gesetzten) Nachbarschaft übernommen wird. Dabei wird eine eventuelle Verschlechterung des Zielfunktionswertes in Kauf genommen. Um Zyklen im Suchverlauf zu verhindern, werden kürzlich untersuchte Lösungen (bzw. ihre Attribute) in die so genannte Tabu-Liste aufgenommen. Die in der Tabu-Liste enthaltenen Lösungen werden für eine bestimmte Anzahl von Iterationen als tabu betrachtet, d.h. als Lösungskandidaten ausgeschlossen.
Eine umfassende Beschreibung der Tabu-Suche und ihrer Abwandlungen findet man unter anderem in [Reeves 1995, S. 70 ff]. Es gibt zahlreiche Veröffentlichungen über die Anwendung von Tabu-Suchverfahren im Bereich der Tourenplanung. Speziell für das MDVRPTW ist hier der Algorithmus von Cordeau, Laporte und Mercier zu nennen, vgl. [Cordeau u. a. 2001] und [Cordeau u. a. 2004b].
Im Gegensatz zum Simulierten Abkühlen und zur Tabu-Suche operieren Evoluti- onäre Algorithmen in einer Iteration nicht auf einer einzigen sondern auf einer Menge von Lösungen. Eine solche Menge gleichzeitig betrachteter Lösungen wird in Analogie zur Biologie Population genannt. In jeder Iteration werden aktuelle Lösungen mittels Mutation und/oder Kreuzung manipuliert und so neue Lösungen erzeugt. Selektionsmechanismen entscheiden, welche Lösungen in die Nachfolgepo- pulation eingehen und Nachkommen erzeugen, d.h. zur Generierung neuer Lösungen herangezogen werden. Stochastische Elemente spielen bei Evolutionären Algorith- men ebenfalls eine Rolle. Eine detaillierte Erklärung dieser Klasse von Verfahren folgt in Kapitel 4.
Evolutionäre Algorithmen haben sich bei der Optimierung komplexer Probleme der realen Welt bewährt und eignen sich mit entsprechend angepassten Datenstruktu- ren und Operatoren auch zur Lösung von Tourenplanungsproblemen. Insbesonde- re für die praxisrelevante Problemvariante mit Zeitfenstern (VRPTW) existieren bereits erfolgreiche Implementierungen Evolutionärer Algorithmen. Eine sehr gute Übersicht darüber ist in [Bräsy u.a. 2004] zu finden.
Der Autorin ist jedoch kein evolutionäres Verfahren bekannt, welches zur Lösung einer Aufgabe angewendet wurde, die ähnliche Anforderungen wie die Tourenpla- nung der Miele & Cie. KG (mehrere Depots, Qualifikationsprofile der Techniker oder arbeitszeitliche Bestimmungen) erfüllen muss. Vor diesem Hintergrund soll im Rahmen dieser Arbeit ein solcher Evolutionärer Algorithmus entwickelt werden.
4 Evolutionäre Algorithmen
Unter dem Oberbegriff Evolutionäre Algorithmen werden Verfahren zusammengefasst, welche bestimmte Prinzipien biologischer Evolution und Genetik zur Lösung von Optimierungsproblemen einsetzen. Die Grundidee ist, eine Population von Punkten im Lösungsraum gleichzeitig zu betrachten und die - bezüglich der Zielfunktion der Optimierung - besten Punkte im nächsten Schritt der Suche bei der Erzeugung neuer Lösungen zu bevorzugen.
Während der letzten 30 Jahre wurden unzählige Algorithmen entwickelt, welche in ihrem Namen den Zusatz genetisch oder evolutionär führen. Abschnitt 4.1 skiz- ziert kurz die Entwicklungen und unterschiedlichen Richtungen, die am Anfang der Forschungen standen. Auch wenn die einzelnen Ausprägungen Evolutionärer Algo- rithmen teilweise unterschiedlich sind, liegt ihnen allen ein gemeinsamer prinzipieller Ablauf zugrunde. In Abschnitt 4.2 wird dieser Ablauf erläutert. Dabei wird auch die stark an der Biologie orientierte Terminologie erklärt. Darüber hinaus werden in Abschnitt 4.3 die einzelnen Komponenten und Steuerungsparameter Evolutionärer Algorithmen vorgestellt. In Abschnitt 4.4 werden schließlich Strategien präsentiert, welche zum Einsatz kommen, wenn evolutionäre Verfahren der Optimierung von Problemen mit Nebenbedingungen dienen.
4.1 Ursprung
Die Evolutionstheorie hat schon vor rund 50 Jahren Forscher bei der Entwicklung von Optimierungssystemen in unterschiedlichen Kontexten inspiriert, vgl. z.B. [Box 1957], [Bremermann 1962]. Wie [Gerdes u. a. 2004, S. 2] beschreibt, haben sich später im Wesentlichen drei Hauptrichtungen entwickelt, und zwar:
- Evolutionsstrategien (ES): Rechenberg und Schwefel entwickelten die Evolutionsstrategien in den 1960er Jahren in Berlin. Die Forscher arbeiteten im physikalisch-technischen Bereich und setzten in ihren ersten Experimenten die vereinfachte Nachahmung evolutionärer Prinzipien bei der Entwicklung optimaler Körperformen in der Strömungstechnik ein. Die Ergebnisse wurden erstmals in [Rechenberg 1973] und [Schwefel 1975] veröffentlicht. Charakteristisch für evolutionsstrategische Ansätze sind vor allem die Selbstadaptation der Steuerungsparameter des Algorithmus und die Ausrichtung auf Optimierungsprobleme mit kontinuierlichen Parametern.
- Genetische Algorithmen (GA): Ebenfalls in den 1960er Jahren entwickelte Holland die genetischen Algorithmen als verallgemeinerte Modelle adaptiver Systeme, vgl. [Holland 1975]. De Jong hat die Ideen der Genetischen Algorith- men zur Lösung komplexer Optimierungsprobleme eingesetzt [De Jong 1975] und damit den Grundstein für ihre Anwendung in diesem Bereich gelegt. Zur besonderen Popularität dieses Ansatzes ist es nach der Veröffentlichung des Buches von Goldberg [Goldberg 1989] gekommen. Genetische Algorithmen verwenden in ihrer ursprünglichen Form eine binäre Kodierung zur Problem- repräsentation.
- Genetische Programmierung (GP): Diese Methode wurde vor allem durch Koza geprägt und durch seine Bücher [Koza 1992] und [Koza 1994] bekannt. Genetische Programmierung optimiert Computerprogramme, indem sie ihre Struktur mit evolutionären Mitteln verändert. Die Kernidee Genetischer Pro- grammierung ist es also, nicht die Lösung des eigentlichen Problems zu opti- mieren, sondern die Lösungsstrategie in den Mittelpunkt der Betrachtung zu stellen.
Die am Anfang noch konkurrierenden Richtungen haben im Laufe der Jahre zunehmend Elemente anderer Ansätze integriert. Aus diesem Grund ist es schwierig, einen heute entwickelten Algorithmus eindeutig einer der klassischen Formen zuzuordnen. Da aber alle Richtungen einige grundlegende Gemeinsamkeiten aufweisen, kann man sie unter dem Begriff Evolutionäre Algorithmen zusammenfassen.
4.2 Genereller Ablauf und zentrale Begriffe
Der algorithmische Kern ist bei allen evolutionären Ansätzen gleich. Sie sind alle in irgendeiner Form Abwandlungen des folgenden generellen Ablaufs, vgl. [Gottlieb 2000, S. 46]:
1: t ← 0
2: initialisiere P (0) 3: bewerte P (0)
4: while (not Abbruchbedingung) do
5: wähle eine Elternpopulation Pp(t) aus P (t)
6: generiere eine Nachkommenpopulation Pc(t) aus Pp(t)
7: bewerte Pc(t)
8: wähle P (t + 1) aus P (t) und Pc(t)
9: t←t+1
10: end while
Demnach arbeitet ein Evolutionärer Algorithmus auf einer Menge bzw. Population P von kodierten Lösungen (Individuen), wobei P (t) die Population in der Iteration bzw. Generation t notiert. Zunächst muss also die Kodierung festgelegt d.h. eine Beschreibungsform gefunden werden, welche entsprechend der Struktur des gegebe- nen Problems eine Lösung repräsentieren kann. Darüber hinaus muss eine Funktion definiert werden, welche für jede Lösung ihre Güte (Fitness genannt) bewerten kann.
Der Evolutionäre Algorithmus erzeugt dann eine meist zufällige Startpopulation P (0) und errechnet die Fitness jedes darin enthaltenen Individuums. In jeder Ite- ration t erfolgt dann nach einem definierten Selektionsmechanismus die Auswahl der so genannten Elternpopulation Pp(t), also derjenigen Individuen, welche für die Generierung neuer Lösungen (Nachkommen) herangezogen werden. Bei der Gene- rierung der Nachkommenpopulation Pc(t) kommen genetische Operatoren, wie Mu- tation und/oder Rekombination, zum Einsatz. Anschließend wird die Fitness der Nachkommen errechnet (vgl. Zeile 7 im generellen Ablauf) und die Entscheidung getroffen, welche Individuen in die Nachfolgegeneration P (t + 1) eingehen sollen (vgl. Zeile 8 ebenda). Dieser Ablauf wird wiederholt, bis ein Abbruchkriterium, z.B. eine bestimmte Anzahl von Iterationen, erreicht ist.
Die Beschreibung zeigt, dass Evolutionäre Algorithmen durch eine stark an der Biologie orientierte Terminologie gekennzeichnet sind. Tabelle 4.1 beschreibt die in diesem Kontext zentralen Begriffe und zeigt ihre Bezüge zur Biologie auf.
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 4.1: Zentrale Begriffe Evolutionärer Algorithmen und ihre Analogien zur Biologie, vgl. [Gerdes u. a. 2004, S. 34] und [Nissen 1997, S. 15]
Diese Terminologie soll jedoch nicht darüber hinwegtäuschen, dass das Ziel evoluti- onärer Verfahren in erster Linie in der Optimierung künstlicher Systeme und nicht in einer möglichst genauen Simulation biologischer Anpassungsprozesse besteht. Folg- lich verwenden sie auch Konzepte, die in der belebten Welt unbekannt sind, wie beispielsweise die Erzeugung von Nachkommen aus mehr als zwei Eltern. Auf der anderen Seite verzichten viele der Evolutionären Algorithmen auf die Nachahmung wesentlicher biologischen Phänomene (z.B. das altersbedingte Sterben von Lebewe- sen).
4.3 Komponenten evolutionärer Verfahren
Der im vorhergehenden Abschnitt vorgestellte generelle Ablauf eines Evolutionären Algorithmus beschreibt nur das grundlegende Gerüst. Bei einer konkreten Implementierung eines solchen Verfahrens sind Entscheidungen in Bezug auf
- die Repräsentation und Kodierung von Lösungen,
- die Bewertungs-/Fitnessfunktion,
- den Mechanismus der Elternselektion,
- die genetischen Operatoren (Mutation, Rekombination) und
- die Selektion der Nachfolgegeneration (Ersetzungsstrategie)
- die Populationsgröße
- die Initialisierung der Startpopulation zu treffen, vgl. [Eiben u. Smith 2003, S. 18].
Beim Entwurf eines Evolutionären Algorithmus sind die gegenseitigen Wechselwirkungen der Entscheidungen zu berücksichtigen. Hier sollen jedoch aus Gründen der Übersichtlichkeit die einzelnen Komponenten getrennt behandelt werden.
4.3.1 Lösungsrepräsentation und Kodierung
Eine fundamentale Entscheidung beim Entwurf Evolutionärer Algorithmen betrifft die Wahl einer geeigneten Form der Repräsentation und Kodierung2 der Lösungen des gegebenen Optimierungsproblems. Es geht dabei um die Fragen:
1. Repräsentation: Welche Daten sind für die Beschreibung einer Lösung notwen- dig bzw., wie sieht der Phänotyp einer Lösung aus?
2. Kodierung: In welcher Form sollen diese Daten in einem Individuum gespei- chert werden bzw., wie sieht der entsprechende Genotyp einer Lösung aus?
Für die Repräsentation kommen je nach Struktur des Optimierungsproblems unterschiedliche Darstellungsformen in Frage. Bei der Parameteroptimierung reichen Vektoren mit Zahlenwerten als Repräsentation einer Lösung, während bei kombinatorischen Problemen eher Permutationen verwendet werden.
Die Kodierung kann mittels sehr einfacher Zeichen- bzw. Zahlenketten oder mit Hilfe spezieller Datenstrukturen erfolgen. Sie sollte in jedem Fall aber das Prinzip der strengen Kausalität erfüllen. Dieses Prinzip besagt, dass kleine Veränderungen im Genotyp ebenfalls nur kleine Veränderungen im Phänotyp bewirken, vgl. [Gen u. Cheng 2000, S. 7].
Ist die strenge Kausalität in der gewählten Form der Kodierung verletzt, können bereits kleine Veränderungen des Genotyps unverhältnismäßig große Änderungen des Phänotyps bedeuten. Eine solche Kodierung würde aber einer Grundidee der Evolutionären Algorithmen zuwiderlaufen, nämlich der Idee, durch die Anwendung genetischer Operatoren auf besonders vielversprechende Elternindividuen ähnliche Kinderindividuen zu erhalten, um bei ihnen die Suche fortzusetzen.
An einem einfachen Beispiel lässt sich veranschaulichen, wie z.B. die binäre Kodie- rung einer ganzzahligen Variable das Prinzip der strengen Kausalität verletzt. Abb. 4.1 zeigt, wie bereits eine kleine Änderung des Genotyps (nur ein Bit wird umgekehrt) eine Veränderung des dekodierten Variablenwertes von 0 auf 4 bewirkt. Auf der anderen Seite ist eine komplette Umkehrung der kodierten Information mit einer relativ kleinen Änderung des Phänotyps von 3 auf 4 verbunden.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.1: Verletzung des Prinzips der strengen Kausalität bei der Binärkodierung
Die Wahl der Kodierung hängt eng mit der Wahl der genetischen Operatoren zusammen. Während die binäre Kodierung recht einfache Formen der Mutation und Rekombination zulässt, erfordern komplexere Datenstrukturen spezielle Mutationsund Rekombinationsmechanismen.
4.3.2 Bewertungs-/Fitnessfunktion
Die Bewertungsfunktion weist jedem Individuum einen Wert zu, welcher dessen Güte bezüglich der Zielfunktion der Optimierung widerspiegelt. Ausgehend von der Be- wertung eines Individuums wird seine Fitness, also die Chance zur Reproduktion in der nächsten Generation, errechnet. Da in vielen Evolutionären Algorithmen die Bewertungsfunktion und die Fitnessfunktion identisch sind, wird in der Literatur häufig nicht zwischen Bewertung und Fitness eines Individuums unterschieden.
Entsprechend dem Prinzip Survival of the Fittest gilt: Je besser der Fitnesswert eines Individuums, desto größer auch seine Chance, Nachkommen für die nächste Generation zu erzeugen. Aufgrund dieser elementaren Rolle bei der Elternselektion lässt sich sagen, dass die Fitnesswerte die Grundlage der evolutionären Suche bilden.
4.3.3 Elternselektion
Die Elternselektion ist für die Auswahl derjenigen Individuen zuständig, welche für die Reproduktion, d.h. die Erzeugung neuer Individuen, herangezogen werden. Die Elternselektion und die Selektion der Nachfolgegeneration bewirken zusammen, dass der Suchprozess auf die Merkmale guter Individuen fokussiert wird.
Die Selektion der Eltern wird in der Regel von stochastischen Elementen mitbe- stimmt. Auf diese Weise bekommen auch Individuen mit schlechterer Fitness eine bestimmte Chance zur Reproduktion, und der Evolutionäre Algorithmus einen Me- chanismus, welcher dem Verlassen eines lokalen Optimums dienen kann, vgl. [Eiben u. Smith 2003, S. 20 f].
[Nissen 1997, S. 46] zählt als besonders bekannte Arten der Elternselektion folgende auf:
- fitnessproportionale Selektion,
- rangbasierte Selektion (ranking),
- Wettkampf-Selektion (tournament selection).
Fitnessproportionale Selektion bedeutet, dass die Wahrscheinlichkeit eines Individuums j, für die Reproduktion ausgewählt zu werden, proportional zu seiner Fitness fj ist. Bei einer Populationsgröße n und einer zu maximierenden Zielfunktion wird diese Wahrscheinlichkeit berechnet als:
Abbildung in dieser Leseprobe nicht enthalten
So ermittelte Wahrscheinlichkeitswerte bilden die Grundlage für die tatsächliche Auswahl (Sampling) der Individuen für die Reproduktion, welche z.B. nach dem von [Goldberg 1989] eingeführten Rouletterad-Verfahren erfolgen kann. Dieses Ver- fahren heißt so, weil es mit Hilfe eines Rouletterades veranschaulicht werden kann: Man stelle sich vor, dass jedem Individuum j ein Bereich des Rouletterades zu- geordnet wird, welcher dem Wert von λj entspricht. Sollen aus einer Population k Individuen für die Reproduktion ausgewählt werden, wird das Rouletterad k mal ge- dreht. Ausgewählt wird jeweils das Individuum, in dessen Bereich das Rouletterad anhält. Dies entspricht einem k-maligen Erzeugen einer Zufallszahl zwischen 1 und 100 und Ziehen mit Zurücklegen.
Ein alternatives Sampling-Verfahren wurde in [Baker 1987] vorgestellt und heißt Stochastic Universal Sampling. Wie das Rouletterad-Verfahren lässt es sich mit der Metapher eines Rouletterades veranschaulichen, jedoch mit dem Unterschied, dass hier für die Auswahl von k Individuen das Rad nur einmal gedreht wird. Um das Rad herum sind in gleichen Abständen k Zeiger angebracht. Für die Reproduktion werden diejenigen Individuen gewählt, in deren Bereich die Zeiger nach dem Anhalten des Rouletterades zeigen. Der Vorteil dieser Vorgehensweise (Ziehen ohne Zurücklegen) gegenüber dem Rouletterad-Verfahren (Ziehen mit Zurücklegen) ist die geringere Varianz zwischen der erwarteten und tatsächlichen Häufigkeit der Zulassung eines Individuums zur Reproduktion.
Bei der rangbasierten Selektion wird zunächst eine Rangliste aller Populations- mitglieder erstellt, in welcher das Individuum mit der besten Fitness Rang 1, das Individuum mit der zweitbesten Fitness Rang 2 usw. bekommt. Bei der Berechnung der Wahrscheinlichkeit eines Individuums, für die Reproduktion ausgewählt zu wer- den, wird dann anstatt des absoluten Fitnesswertes nur noch der Rang aus dieser “Fitness-Rangliste” berücksichtigt. Auf diese Weise kann die Dominanz so genann- ter Superindividuen (d.h. Individuen, mit einem deutlich besseren Fitnesswert als der Rest der Population) beim Selektionsvorgang verhindert werden, vgl. [Gerdes u. a. 2004, S. 83].
Wettkampf-Selektion ist die Bezeichnung für Auswahlverfahren, bei welchen zunächst n Individuen zufällig aus der Population gezogen werden. Anschließend wird das Individuum mit der besten Fitness unter den n Kandidaten entweder de- terministisch oder mit einer bestimmten Wahrscheinlichkeit für die Reproduktion ausgewählt. Der Vorgang wird so oft wiederholt, bis die benötigte Anzahl an Eltern- individuen vorliegt. Mit dem Parameter n lässt sich der Selektionsdruck bei dieser Art der Elternauswahl leicht steuern, denn es gilt: Bei konstanter Populationsgröße bedeutet ein steigendes n einen stärkeren Selektionsdruck, vgl. [Gerdes u. a. 2004, S. 84].
4.3.4 Genetische Operatoren
In Evolutionären Algorithmen kommen zwei Arten von genetischen Operatoren zum Einsatz:
- Rekombination: Hierbei werden aus einem oder mehreren (in der Regel zwei) Elternindividuen neue Individuen (“Kinder”) erzeugt. Im Idealfall führt die Rekombination bei den Kindern zu neuen, günstigeren Kombinationen der guten Eigenschaften der Eltern und somit zu besseren Lösungen.
- Mutation: Diese Operation bewirkt eine (kleine) Veränderung eines Individuums. Mutation sorgt für ein Mindestmaß an Diversität innerhalb einer Population und wirkt somit einer vorzeitigen Konvergenz3 des Algorithmus entgegen, vgl. [Gerdes u. a. 2004, S. 42].
Richtig konzipiert und eingesetzt sorgen die genetischen Operatoren zum einen für die Ausbeutung vielversprechender Individuen (Exploitation) und zum anderen für eine ausreichende Durchforstung des gesamten Suchraumes (Exploration), vgl. [Dréo u. a. 2006, S. 94].
Die Definition konkreter genetischer Operatoren ist von der Art der Lösungskodierung des jeweiligen Optimierungsproblems abhängig. Bei einfach strukturierten Problemen, für welche eine binäre Darstellung in Frage kommt, kann z.B. das so genannte Crossover verwendet werden, siehe Abb. 4.2. Dabei handelt es sich um einen einfachen Rekombinationsoperator, welcher aus zwei Eltern (P1, P2) durch einen Über-Kreuz-Tausch der kodierten Informationen an einer zufälligen Schnittstelle zwei Kinderindividuen (C1, C2) erzeugt, vgl. [Holland 1975].
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.2: Beispiel eines einfachen Crossover
Anders als die Rekombination führt Mutation meist nur eine geringe stochastische Änderung eines Individuums herbei. Insofern kann der Mutationsoperator als eine Art zufallsbasierte lokale Suche gesehen werden, vgl. [Dréo u. a. 2006, S. 97]. Wie viele Individuen einer Population mutieren, hängt von der Wahl der so genannten Mutationsrate ab.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.3: Beispiel einer einfachen Mutation
Abb. 4.3 zeigt eine einfache Art der Mutation für binäre Probleme, welche in der Umkehrung zufällig ausgesuchter Werte eines Individuums I besteht. Das Ergebnis dieser Operation ist dar Mutant I′.
Für andere Arten der Lösungsrepräsentation und -kodierung gibt es spezielle gene- tische Operatoren. Die wichtigsten davon beschreibt z.B. [Dréo u. a. 2006, S. 98 ff]. Die problemspezifische Anpassung genetischer Operatoren ist erforderlich, weil ein- fache Crossover- und Mutationsvarianten bei komplexeren Formen der Darstellung zur Zerstörung günstiger Strukturen oder sogar zur Unzulässigkeit der Nachkommen führen kann.
4.3.5 Selektion der Nachfolgegeneration
Die Selektion der Nachfolgegeneration (auch Ersetzungsstrategie oder Ersetzungs- schema genannt) entscheidet nach einer Reproduktion darüber, welche Individuen aus der Gesamtheit der Eltern und der Kinder die nächste Generation bilden sollen.
Die einfachste Form der Selektion der Nachfolgegeneration findet beim so genannten Generationenmodell statt. Bei Anwendung dieses Modells wird in jedem Schritt des Evolutionären Algorithmus die ganze Population durch die aus ihr im Reproduktionsprozess gewonnenen Kinder ersetzt, vgl. [Dréo u. a. 2006, S. 90]. Auf diese Weise entsteht eine Abfolge immer neuer Populationen bzw. Generationen.
Eine andere Vorgehensweise kennzeichnet das Steady State-Modell. Hierbei werden in jeder Generation nur wenige Individuen erzeugt. Anschließend wird überprüft, ob die neu erzeugten Individuen Lösungen darstellen, welche bereits in der Population vertreten sind. Wenn dies nicht der Fall ist, gehen sie in die Population ein und ersetzen die schlechtesten Individuen darin, vgl. [Nissen 1997, S. 39].
Ein weiteres Prinzip, welches bei der Selektion der Nachfolgegeneration eine Rolle spielen kann, bildet die Grundlage des Elitemodells. Eine diesem Modell entsprechende Ersetzungsstrategie stellt sicher, dass die besten Individuen einer Population als eine Art Elite den Generationenwechsel “überleben”, vgl. [Dréo u. a. 2006, S. 91]. Dies kann z.B. dadurch erfolgen, dass die n besten Individuen automatisch in die nächste Generation übernommen werden.
In der Praxis kommen die hier genannten Modelle selten in ihrer Reinform zur Anwendung. In konkreten Implementierungen werden sie zumeist um weitere Aspekte ergänzt, wodurch eine Fülle unterschiedlicher Vorgehensweisen entsteht, siehe z.B. [Schöneburg u. a. 1994, S. 205 ff].
4.3.6 Populationsgröße
Die Größe der Population ist ein wichtiger Steuerungsparameter der evolutionären Suche. Generell gilt: Je größer die Population desto rechenintensiver die Ausführung des Algorithmus. Auf der anderen Seite ermöglicht eine größere Population aber die Bewahrung der Diversität und wirkt tendenziell der vorzeitigen Konvergenz entgegen, vgl. [Nissen 1997, S. 38].
[...]
1 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 Hier wird die Mehrzahl verwendet, weil in der Regel mehrere Techniker für die Bearbeitung eines Auftrages zur Auswahl stehen.
2 Dabei wird die Bevölkerungsdichte für jedes Postleitzahlengebiet mit der durchschnittlichen Anzahl der Einwohner je Quadratmeter dieses Gebietes angegeben, vgl. [Gerke 2005, S. 54].
3 In der 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ötschel u. a. 2001].
1 Wegen der begrenzten Kapazität der Fahrzeuge ist das klassische VRP ebenfalls als Capacitated Vehicle Routing Problem (CVRP) bekannt.
2 Der Rechenaufwand eines Algorithmus ist polynomial, wenn die Anzahl der Rechenoperationen des Algorithmus proportional zu Nn ist, wobei N die Problemgröße repräsentiert (z.B. Anzahl der zu besuchenden Kunden beim VRP) und n eine positive ganzzahlige Konstante darstellt, vgl. [Dréo u. a. 2006, S. 2]
3 ”LokaleSucheisteineBezeichnungfürSuchmethoden,dieausgehendvoneinerAnfangslösung versuchen, in der nahen Umgebung (lokal) nach besseren Lösungen zu suchen. (. . . ) Zu jeder zulässigen Lösung L (Punkt im Suchraum) wird eine [Nachbarschaft von L genannte] Umgebung ω(L) definiert. Diese Umgebung beinhaltet alle zulässigen Lösungen, die durch genau eine (als atomar angesehene) Transformation der Lösung L gebildet werden können.“[Suhl u. Mellouli 2005, S. 138].
1 Vor allem GA-orientierte Verfahren verwenden als Synonym für Individuum den Begriff Chromosom. Dies kann zu Missverständnissen führen, weil diese beiden Begriffe in der Biologie mit unterschiedlichen Bedeutungen belegt sind, vgl. [Michalewicz 1996, S. 15].
2 Die Begriffe Repräsentation und Kodierung werden von manchen Autoren synonym verwendet. Andere Forscher weisen jedoch darauf hin, dass sie streng genommen zwei unterschiedliche Sachverhalte betreffen: Die Repräsentation behandelt die Frage, wie eine Lösung beschrieben werden soll. Beim Problem des Handelsreisenden (Traveling Salesman Problem) mit den Städten A,B,C und D kann die Repräsentation einer Lösung durch eine Permutation der Städte erfolgen. Mit Kodierung ist dagegen gemeint, wie diese Lösungsrepräsentation im Rechner dargestellt werden soll. Für die Permutation [A,D,B,C] z.B. kann die i-te Stelle der Kodierung beschreiben, welche Stadt in der i-ten Stelle der Sequenz besucht wird, also [1,4,2,3]. Alternativ kann die i-te Stelle der Kodierung aussagen, an welcher Stelle der Sequenz die i-te Stadt besucht wird, also [1,3,4,2], vgl. [Eiben u. Smith 2003, S. 40 ff].
3 Vorzeitige Konvergenz (engl. premature convergence) ist die Bezeichnung für das Stagnieren der Suche in einem lokalen Optimum.
- Arbeit zitieren
- Sabina El Haoum (geb. Puk) (Autor:in), 2006, Evolutionärer Algorithmus zur Optimierung des Technikereinsatzes der Firma Miele und Cie. KG, München, GRIN Verlag, https://www.grin.com/document/70147
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.