Dynamische Tourenplanung mit Zeitfenstern

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

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.