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
Zielsetzung & Themen
Das Hauptziel dieser Diplomarbeit besteht in der Entwicklung und Implementierung eines auf evolutionären Algorithmen basierenden Verfahrens zur Optimierung von Tourenplänen für den technischen Kundendienst der Miele & Cie. KG. Die Forschungsfrage untersucht, inwieweit dieses metaheuristische Verfahren geeignet ist, die Effizienz bei der Zuweisung und Routenplanung von Technikern im Vergleich zu den bestehenden Systemen zu steigern, unter Berücksichtigung komplexer Nebenbedingungen wie Qualifikationsprofilen und zeitlicher Vorgaben.
- Optimierung komplexer Tourenplanungsprobleme mittels evolutionärer Algorithmen.
- Berücksichtigung von spezifischen Nebenbedingungen (Mehrdepot-Problem, Qualifikationen, Zeitfenster).
- Konzeption einer flexiblen Softwarearchitektur zur Lösungsfindung.
- Empirische Evaluation des entwickelten Algorithmus anhand realer Testinstanzen.
- Vergleich der Ergebnisse mit existierenden Verfahren wie der VNS-Heuristik.
Auszug aus dem Buch
5.1 Lösungsrepräsentation und Kodierung
Die Lösungsrepräsentation orientiert sich an der Genetic Vehicle Representation (kurz GVR). GVR wird zur Darstellung der mehrschichtigen Informationen von Lösungen des klassischen Tourenplanungsproblems oder seiner Variante mit Zeitfenstern eingesetzt und wurde erstmals in [Pereira u. a. 2002] beschrieben.
Wie Abb. 5.1 zeigt, wird eine Route in GVR durch eine geordnete Untermenge der Knoten des zugrundeliegenden Problems repräsentiert. Zur Darstellung eines kompletten Tourenplans werden alle dazugehörenden Routen in einer GVR-Struktur zusammengefasst.
Der Evolutionäre Algorithmus, welcher im Rahmen der vorliegenden Arbeit für die Optimierung der Tourenpläne der Miele & Cie. KG entwickelt wird, arbeitet mit einer leicht abgewandelten Form von GVR. Zu beachten ist dabei, dass die Optimierung mehrere Depots berücksichtigen muss, da für jeden Techniker sein jeweiliger Wohnort als Depot gilt. Zudem ist bekannt, dass jeder Techniker die Orte der ihm für einen bestimmten Arbeitstag zugeordneten Aufträge in einer einzigen Route besucht, vgl. Abschnitt 3.2. Das bedeutet also, dass in einer zulässigen Lösung der gegebenen Aufgabe zu jedem Depot bzw. Techniker höchstens eine Route gehört.
Zusammenfassung der Kapitel
1 Einleitung: Die Arbeit führt in die Relevanz einer effizienten Kundendienstplanung bei der Miele & Cie. KG ein und skizziert die methodische Zielsetzung der Diplomarbeit.
2 Technischer Kundendienst der Miele & Cie. KG: Es werden die organisatorischen Rahmenbedingungen und die bestehende IT-gestützte Disposition erläutert sowie spezifische Schwachstellen und Verbesserungspotenziale identifiziert.
3 Grundlagen der Tourenplanung: Dieses Kapitel definiert das klassische Tourenplanungsproblem (VRP), überführt die spezifische Aufgabenstellung der Miele & Cie. KG in ein mathematisches Modell und gibt einen Überblick über gängige Lösungsmethoden.
4 Evolutionäre Algorithmen: Hier werden die theoretischen Grundlagen evolutionärer Algorithmen, ihr genereller Ablauf sowie zentrale Komponenten und Steuerungsparameter detailliert beschrieben.
5 Lösungsentwurf und Implementierung: Dieser Abschnitt erläutert die konkrete Anwendung der evolutionären Methodik, inklusive Kodierung der Tourenpläne, Bewertungsfunktionen und genetischer Operatoren, die im Rahmen der Arbeit entwickelt wurden.
6 Evaluation: Die Leistungsfähigkeit des entwickelten Algorithmus wird anhand realer Testinstanzen empirisch überprüft und mit den Ergebnissen bestehender Verfahren (CPLEX, VNS) verglichen.
7 Zusammenfassung und Ausblick: Die Arbeit schließt mit einer Bilanz der Ergebnisse und Vorschlägen für zukünftige Erweiterungen und Verbesserungen des Algorithmus.
Schlüsselwörter
Tourenplanung, Evolutionäre Algorithmen, Techniker-Einsatzplanung, Miele & Cie. KG, Metaheuristiken, Q-MDVRPTW, Kundenaufträge, Routenoptimierung, Genetische Operatoren, Fitnessfunktion, Kundendienst, Logistik, Softwareimplementierung, Heuristiken, Nebenbedingungen.
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit grundsätzlich?
Die Arbeit befasst sich mit der Optimierung des Technikereinsatzes bei der Miele & Cie. KG unter Verwendung metaheuristischer Verfahren, um die Effizienz der täglichen Tourenplanung zu steigern.
Was sind die zentralen Themenfelder der Arbeit?
Die Arbeit verbindet die praktische Logistik und Tourenplanung des technischen Kundendienstes mit der theoretischen Informatik, speziell dem Gebiet der evolutionären Algorithmen.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist die Konzeption und Implementierung eines evolutionären Algorithmus, der in der Lage ist, die bestehenden Tourenpläne der Miele & Cie. KG effizienter zu gestalten und dabei komplexe betriebliche Restriktionen einzuhalten.
Welche wissenschaftliche Methode wird verwendet?
Der Autor verwendet evolutionäre Algorithmen, eine Klasse von metaheuristischen Optimierungsverfahren, die Prinzipien der biologischen Evolution auf technische Problemlösungen übertragen.
Was wird im Hauptteil behandelt?
Im Hauptteil liegt der Fokus auf der Modellierung der Tourenplanung, der detaillierten Beschreibung des evolutionären Ansatzes sowie der praktischen Implementierung der Algorithmen-Komponenten.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind unter anderem Tourenplanung, evolutionäre Algorithmen, Routenoptimierung, Kundenaufträge und die spezifische Modellierung als Q-MDVRPTW.
Wie unterscheidet sich die entwickelte Methode von der bestehenden AMS-Planung?
Während das bestehende System (AMS) schrittweise und online disponiert, erlaubt der entwickelte evolutionäre Ansatz eine nachgelagerte Optimierung, die den Tourenplan als Ganzes betrachtet und Anpassungen vornimmt, um Distanzen zu minimieren.
Welche Rolle spielt die Programmdokumentation im Anhang?
Der Anhang enthält die technische Beschreibung der im Rahmen der Diplomarbeit implementierten C#-Klassen und Schnittstellen, die für die modulare Architektur des Algorithmus entscheidend sind.
- Quote paper
- Sabina El Haoum (geb. Puk) (Author), 2006, Evolutionärer Algorithmus zur Optimierung des Technikereinsatzes der Firma Miele und Cie. KG, Munich, GRIN Verlag, https://www.grin.com/document/70147
