Die vorliegende Arbeit ist so konzipiert, dass praktische Aspekte von Tourenplanungsproblemen in den Vordergrund gestellt werden. Anhand eines realitätsnahen Beispiels werden ausgewählte Verfahren vorgestellt und auch angewendet. Das theoretische Hintergrundwissen wird natürlich auch entsprechend behandelt und vorgestellt. Ohne eine fundierte theoretische Basis ist die systematische Lösung von komplexen Problemstellungen, zu denen Tourenplanungprobleme zweifelsohne gehören, nahezu unmöglich. Bei der Vorstellung der einzelnen Verfahren wird der theoretische Aspekt jedoch zugunsten einer umfangreicheren Darstellung praktischer Anwendungsmöglichkeiten so weit wie möglich reduziert. Daher war es auch nie mein Ziel, so viele Verfahren wie möglich in dieser Arbeit vorzustellen. Es wurden solche Verfahren ausgewählt, anhand derer besonders wichtige Aspekte hinsichtlich einer Umsetzung auf in der Realität vorkommende Probleme aufgezeigt werden konnten. Hauptsächlich ging es mir bei dieser Arbeit darum, zu verdeutlichen, dass es bei konkret vorliegenden Problemen nicht darum gehen kann, ein einzelnes Verfahren auszuwählen und anzuwenden. Vielmehr geht es darum, durch geeignete Modifikationen bestehender Verfahren eine zum konkreten Problem passende Optimierungsroutine zu entwickeln. Gerade bei sehr realitätsnahen Problemstellungen, zu denen auch die dynamische Tourenplanung mit Zeitfenstern zählt, können einzelne Standardverfahren nur den Ausgangspunkt der Problembewältigung darstellen. [...]
Inhaltsverzeichnis
1. Grundlagen zur Tourenplanung
1.1 Die Tourenplanung im betriebswirtschaftlichen Kontext
1.2 Tourenplanung als Disziplin des Operations Research
1.3 Gang der Problemanalyse und der Problemlösung
2. Zur Vielfältigkeit von Tourenplanungsproblemen
2.1 Kriterienkatalog zur Problemidentifizierung
2.1.1 Die Ausgestaltung des Netzwerks
2.1.2 Die Beschaffenheit des Fuhrparks
2.1.3 Die Zeit als wichtiger Einflussfaktor
2.1.4 Verschiedene Zielsetzungen
2.2 Grundmodelle der Tourenplanung
2.2.1 Das Handlungsreisendenproblem
2.2.2 Das Standardproblem der Tourenplanung
2.2.3 Kombinations- und Erweiterungsmöglichkeiten der Modelle
2.3 Berücksichtigung dynamischer Aspekte
2.4 Zusammenfassung und Problempräzisierung
3. Lösungsmöglichkeiten und Szenariokonstruktion
3.1 Konzepte zur Lösung des DTRP
3.1.1 Heuristische Verfahren für Tourenplanungsprobleme
3.1.2 Spezielle Lösungsansätze für dynamische Problemstellungen
3.1.3 Tourenoptimierung mit Hilfe von Metaheuristiken
3.2 Konstruktion eines DTRP - Szenarios
4. Konstruktions- und Verbesserungsverfahren
4.1 Konstruktionsverfahren
4.1.1 Das Savingsverfahren
4.1.2 Anwendungsmöglichkeiten von Einfügeheuristiken
4.1.3 Anwendung einer „nächster Nachbar“ Heuristik
4.1.4 Anwendungsmöglichkeiten zweistufiger Verfahren
4.2 Verbesserungsverfahren
4.2.1 Intraroutenverbesserung
4.2.2 Interroutenverbesserung
4.2.2.1 Das 2-opt* Kantentauschverfahren
4.2.2.2 Verbesserung anhand multipler Kriterien
4.2.3 Verfahrensvergleich und Ergebnisdetails
4.3 Anmerkungen zur Optimalität
5. Einbeziehung veränderlicher Informationen
5.1 Klassifizierung von Änderungsmöglichkeiten
5.2 Update eines bestehenden Tourenplans
5.3 Integration statischer Algorithmen in die Updateroutine
5.4 Betrachtung von Änderungen im Beispielproblem
6. Vorstellung weiterer Lösungsmöglichkeiten
7. Eine kritische Rekapitulation mit Ausblick
Zielsetzung und Themen
Die Arbeit untersucht die Herausforderungen und Lösungsstrategien für die dynamische Tourenplanung in Reparaturdienstleistungsunternehmen, bei denen Kundenbesuche unter strikten Zeitfensterrestriktionen erfolgen müssen. Das primäre Ziel besteht darin, ein mathematisches Modell zu entwickeln und praxisnahe heuristische Verfahren zu evaluieren, die in der Lage sind, bei neu eintretenden Informationen oder Änderungen der Rahmenbedingungen den Tourenplan zeitnah und effizient anzupassen.
- Modellierung von m-TSPTW (Multi-Travelling Salesman Problem with Time Windows) Szenarien
- Entwicklung und Vergleich von Konstruktions- und Verbesserungsheuristiken
- Methoden zur Integration dynamischer Informationen und Updates in bestehende Pläne
- Analyse der Kostenstrukturen und Servicequalität im Reparaturdienst
- Kritische Bewertung der Anwendbarkeit theoretischer Modelle in realitätsnahen, ländlichen Netzwerken
Auszug aus dem Buch
4.1.1 Das Savingsverfahren
Das Savingsverfahren gehört zur Klasse der parallelen Konstruktionsverfahren. Es werden mehrere Touren simultan entwickelt, wobei durch Modifikationen auch eine sequentielle Vorgehensweise möglich wird.
Die Grundidee des Savingsverfahrens besteht darin, durch Verknüpfen von einzelnen Touren eine Reduzierung der insgesamt zurückgelegten Distanzen zu erreichen. Den Ausgangspunkt bilden Pendeltouren der Art [0, i, 0] für i = 1,…,n. Die einzelnen Touren werden nun an den jeweiligen Endpunkten miteinander verbunden und es entstehen umfangreichere Touren. Die Verknüpfung zweier Touren liefert eine Ersparnis (Saving) der Form:
Solange savij positiv ist lohnt sich eine Verknüpfung der Touren, da eine Distanzersparnis erreicht wird. Um adäquatere Tourenpläne zu erhalten kann die Funktion (17) modifiziert werden. Insbesondere verspricht die Erweiterung der Funktion um einen Parameter, der die Bedeutung der Distanz zwischen Kunden i und Kunden j hervorhebt, anders lautende Lösungen. Die Savingswerte können dann durch die nachfolgende Funktion bestimmt werden:
Für wachsende γ wird die Fahrtzeit zwischen den Kunden immer stärker berücksichtigt. Bei einem niedrigen Wert des Parameters werden vorzugsweise weit vom Depot entfernte Kunden zusammengefasst, da die Entfernung zwischen den Anfangs- und Endkunden einer Tour zum Depot stärker berücksichtigt wird.
Zusammenfassung der Kapitel
1. Grundlagen zur Tourenplanung: Einführung in die allgemeinen Probleme der Fahrzeugtourenplanung, definitorische Abgrenzung statischer und dynamischer Szenarien sowie Einordnung in den Kontext der Logistik und des Operations Research.
2. Zur Vielfältigkeit von Tourenplanungsproblemen: Detaillierte Darstellung eines Kriterienkatalogs zur Kategorisierung von Tourenplanungsproblemen sowie Vorstellung der grundlegenden mathematischen Modelle wie TSP und VRP.
3. Lösungsmöglichkeiten und Szenariokonstruktion: Überblick über existierende Lösungsansätze, Einordnung der Heuristiken und Aufbau eines realitätsnahen Szenarios als Basis für die weiteren Untersuchungen.
4. Konstruktions- und Verbesserungsverfahren: Vorstellung von Algorithmen zur Erstellung einer initialen zulässigen Lösung und deren nachfolgende Optimierung durch lokale Suchverfahren.
5. Einbeziehung veränderlicher Informationen: Erörterung der dynamischen Aspekte, Entwicklung einer Updateroutine zur Anpassung bestehender Pläne und exemplarische Betrachtung von Änderungsfällen.
6. Vorstellung weiterer Lösungsmöglichkeiten: Kurze Skizzierung ergänzender Verfahren wie BARTOC und DRIVE sowie Einführung in die Nutzung von Metaheuristiken zur Problemlösung.
7. Eine kritische Rekapitulation mit Ausblick: Kritische Reflexion der in der Arbeit behandelten Aspekte, insbesondere hinsichtlich der Übertragbarkeit auf reale betriebswirtschaftliche Gegebenheiten.
Schlüsselwörter
Dynamische Tourenplanung, Zeitfensterrestriktionen, m-TSPTW, Operations Research, Heuristische Verfahren, Savingsalgorithmus, Lokale Suche, Kantentausch, 2-opt Verfahren, Dynamische Problemanalyse, Routenplanung, Logistik, Reparaturdienst, Kostenoptimierung, Metaheuristiken
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der optimalen Planung von Fahrzeugtouren für einen Reparaturdienst, bei dem dynamische Einflüsse wie neue Kundenanfragen oder kurzfristige Änderungen in einem realitätsnahen Straßennetz berücksichtigt werden müssen.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die mathematische Modellierung von Tourenplanungsproblemen mit Zeitfenstern (m-TSPTW), der Einsatz von Konstruktions- und Verbesserungsheuristiken sowie die Entwicklung von Strategien zur dynamischen Anpassung dieser Pläne.
Was ist das primäre Ziel der Arbeit?
Ziel ist es, Methoden aufzuzeigen, wie ein Reparaturdienstleister trotz unvollständiger Informationslage zu Beginn eines Arbeitstages einen kostenminimalen und serviceorientierten Tourenplan erstellen und bei Änderungen flexibel aktualisieren kann.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt Methoden der Graphentheorie und der kombinatorischen Optimierung. Zur Problemlösung werden diverse heuristische Verfahren, wie das Savingsverfahren, Einfügeheuristiken und verschiedene Kantentauschverfahren (2-opt), angewendet.
Was wird im Hauptteil behandelt?
Der Hauptteil analysiert verschiedene Kriterien zur Problemklassifizierung, stellt mathematische Modelle auf und führt spezifische Algorithmen an, um initial Touren zu konstruieren und diese iterativ durch lokale Suche zu optimieren.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Schlüsselbegriffe sind Dynamische Tourenplanung, Zeitfenster, m-TSPTW, Heuristische Verfahren, Savingsalgorithmus und lokale Optimierung (z.B. 2-opt).
Wie unterscheidet sich das DTRP von den untersuchten Szenarien des Reparaturdienstes?
Das Dynamic Travelling Repairman Problem (DTRP) bezieht sich meist auf Notdienste, die nach jedem Auftrag zum Depot zurückkehren. Das in der Arbeit betrachtete Modell hingegen plant Touren für Mitarbeiter, bei denen die Kundenaufträge weniger dringlich sind und bereits im Voraus in den Tagesplan integriert werden können.
Warum wird im Beispiel ein 2-opt Verfahren angewendet?
Da in dem betrachteten Beispiel nur eine kleine Anzahl von Kunden pro Tour bedient wird, ist das 2-opt Verfahren effizient geeignet, um die Reihenfolge innerhalb einer Tour so zu optimieren, dass Zeitfensterrestriktionen eingehalten und Fahrtkosten minimiert werden.
- Quote paper
- Lars Laboch (Author), 2005, Dynamische Tourenplanung mit Zeitfenstern, Munich, GRIN Verlag, https://www.grin.com/document/49534
