Flexible Transportplanung. Ein neuer praxisorientierter Ansatz?

Inhalt

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung

2 Transportplanung und Tourenplanung
2.1 Definitionen
2.2 Tourenplanungsprobleme
2.3 Savings-Algorithmus - Ein klassisches Problemslösungsverfahren .

3 Gegenwärtige Praxis in der Tourenplanung

4 Flexible Tourenplanung
4.1 Konzept der Ressourcenorientierten Planung
4.2 Generisches ressourcenorientiertes Modell
4.3 Generische Algorithmen
4.3.1 Virtuelle Funktionen
4.3.2 Parallele Einfügeheuristik
4.3.3 Heuristik Löschen und Einfügen
4.4 Anwendung in der Praxis

5 Vergleich der Ansätze

6 Zusammenfassung und Ausblick

Literaturverzeichnis III

Abbildungsverzeichnis

Abbildung 1: Ressourcenorientierte Planung

Tabellenverzeichnis

Tabelle 1: Beispiele für Ressourcen, Parameter und Übergangsfunktionen

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Im Bereich der Transportplanung müssen eine Vielzahl von Ressourcen simultan geplant, gesteuert und kontrolliert werden. Die Prozesse der Güterverteilung sind in den letzten Jahrzehnten stark gestiegen, so dass, bedingt durch den zunehmenden Wettbewerbsdruck zwischen den Unternehmen, ein sparsamer Umgang mit Ressourcen erforderlich ist. Des weiteren sind durch das Zusammenwachsen von Wirtschaftsräumen im Zuge der Globalisierung, speziell in der Tourenplanung immer größere Distanzen einzubeziehen. Just- in-Time Konzepte sind die Ursache dafür, dass nur relativ kleine Sendungsgrößen nachgefragt werden, so dass sich eine starke Zunahme der Transaktionen ergibt. Wachsende Ansprüche an Flexibilität, Lieferservice und Qualität erhöhen außerdem den Konkurrenzdruck. (vgl. Vogt, 1998)

Die zunehmende Komplexität der Tourenplanung setzt den Einsatz computergestützter Planungssysteme voraus. In der Praxis werden dazu eine Reihe von EDV-Systemen angeboten. Zur Lösung der Probleme ist den Systemen ein mathematisches Modell und Optimierungsalgorithmen, meistens Heuristiken, zugrunde gelegt.

Problematisch ist jedoch, dass der Einsatz theoretischer Modelle des Operations Research in der Praxis nicht immer erfolgreich verläuft. Tourenplanungsprobleme sind durch eine Vielzahl von komplexen Restriktionen gekennzeichnet, die in diesen abstrakten Modellen nicht berücksichtigt werden. Außerdem können nach der Systementwicklung weitere Restriktionen auftreten, die vorher jedoch nicht bekannt waren. Das Modell und die Optimierungsalgorithmen müssen dementsprechend angepasst werden. Dies ist jedoch nur bis zu einem bestimmten Punkt möglich, ab dem eigentlich eine Neuentwicklung notwendig wäre. Ein Verfehlen der optimalen Lösung des Tourenplanungsproblems ist somit zu erwarten. Die daraus resultierende Ablehnung durch die Anwender trägt zum Misserfolg des Tourenplanungssystems bei. (vgl. Grünert, 2003a) Ein neuer Ansatz zur Flexibilisierung der Tourenplanung kann zur Lösung dieser Problematik eingesetzt werden. Um komplexe und nicht vorhersehbare Restriktionen zu modellieren, wird das Konzept des generischen Modells und darauf basierender generischer Algorithmen verwendet. Der Ansatz beruht darauf, dass das Modell sowie die Zielfunktion und Algorithmen erst zu dem Zeitpunkt initiiert werden, zu dem das reale Tourenplanungsproblem vorliegt. (vgl. Grünert, 2003a) Ziel dieser Arbeit ist es, die gegenwärtige Problematik der computergestützten Tourenplanung in der Praxis zu verdeutlichen und daraus ableitend die flexible Tourenplanung als eine neue Vorgehensweise vorzustellen. Des weiteren soll die praktische Anwendbarkeit dieses Ansatzes eruiert werden. Bei der Auseinandersetzung mit dieser Flexible Transportplanung - ein neuer praxisorientierter Ansatz?

Problematik wurde deutlich, dass es kaum Forschungsansätze und damit verbunden auch wenig Literatur zu diesem Themengebiet gibt. Die Arbeit stützt sich deswegen überwiegend auf Arbeiten von Dr. Tore Grünert, wissenschaftlicher Assistent am Deutsche-Post-Lehrstuhl für Optimierung von Distributionsnetzwerken der RWTH Aachen.

Die vorliegende Arbeit gliedert sich in 6 Kapitel. Im folgenden Kapitel 2 wird eine kurze Einführung in das Gebiet der Tourenplanung im Rahmen der Transportplanung gegeben. Zu diesem Zweck werden nach einer Begriffsdefinition das Standardtourenproblem sowie weitere wichtige Tourenplanungsprobleme vorgestellt. Weiterhin erfolgt eine Beschreibung eines klassischen Algorithmus für die computergestützte Problemlösung. Kapitel 3 verdeutlicht die gegenwärtige Praxis der Entwicklung und Anwendung eines Tourenplanungssystems. Ein neuer Ansatz zur flexiblen Tourenplanung wird in Kapitel 4 vorgestellt. Hierbei wird vor allem auf das zugrundliegende neue ressourcenorientierte Modell der Tourenplanung und die darauf angewendeten generischen Algorithmen eingegangen. Außerdem wird die Anwendbarkeit des Ansatzes in der Praxis diskutiert. Kapitel 5 stellt anschließend den alten und den neuen flexiblen Ansatz vergleichend gegenüber. Abschließend erfolgt in Kapitel 6 eine Zusammenfassung der gewonnenen Erkenntnisse und ein Ausblick auf die zukünftige Entwicklung der flexiblen Tourenplanung.

2 Transportplanung und Tourenplanung

2.1 Definitionen

Transportplanung

Ziel der Transportplanung ist die Aggregation einzelner Lieferorte zu Abnehmerzentren und einzelner Liefervorgänge zu Transportströmen. Im Mittelpunkt der Transportplanung steht dabei die Wahl der Transportwege (von welchem Lager zu welchem Abnehmer) und die Bestimmung der Transportmengen. Die Koordination der einzelnen Transportvorgänge erfolgt durch die Tourenplanung. (vgl. Tempelmeier, 2003, S. 274) Flexible Transportplanung - ein neuer praxisorientierter Ansatz?

Tourenplanung

Die Tourenplanung wird von Kabath als eine aus der Distributionslogistik einer Unternehmung heraus resultierende Aufgabenstellung der termingerechten Verfügbarkeit von Produkten beim Kunden und der Rentabilität, das heißt von Kunden bestellte Ware mit einer vorhandenen Menge an Transportmitteln von bestehenden Lagerorten aus zu liefern, beschrieben. (vgl. Kabath, 1997)

Die Tourenplanung ist ein Teilaspekt der Transportplanung und betrachtet nicht mehr nur eine einzelne Transportaufgabe, sondern legt mehrere Transportaufgaben zu einer Tour zusammen. Existieren zudem eine große Anzahl von Kundenaufträgen sowie ein hohes Transportvolumen, müssen mehrere Auslieferungstouren geplant werden. Die Aufgabe der Tourenplanung besteht somit in der Zuordnung einzelner Kundenaufträge zu Touren und in der Festlegung einer Reihenfolge, in der die Kunden beliefert werden. (vgl. Fleischmann, 1994 und Diruf, 1996)

Die Aufgabenstellung der Tourenoptimierung lässt sich wie folgt definieren:

„ Eine Menge von Auftr Ägen ist einer Menge von Transportmitteln unter Berücksichtigung der Distanzen und Restriktionen so zuzuordnen, dass die gesamten Transportkosten, die durch den Einsatz der Transportmittel und die zurückgelegten Distanzen verursacht werden, minimiert werden. “ (vgl. Ziegler, 1988, S. 11 )

2.2 Tourenplanungsprobleme

In der Literatur existieren eine ganze Reihe mathematischer Formulierungen für das Standardtourenproblem. Das nachfolgende mathematische gemischt-ganzahlige Modell entspricht der Formulierung nach Stolze.

Abbildung in dieser Leseprobe nicht enthalten

Die Lösung des TTP erfolgt unter Einbeziehung des Fahrzeugparks, der Transportkapazität der Fahrzeuge, des Transportbedarfs jedes Bedarfsträgers (Liefermengen) und der Aufteilung des Gesamtterritoriums in Teilgebiete. Unter Nutzung der Bedingung (1) kann ein Auslieferungsproblem - Lieferbeziehungen zwischen einem Depot P und einer bestimmten Anzahl von Bedarfsträgern (Kunden) - formuliert werden. Dabei gilt, dass der Gesamtbedarf Flexible Transportplanung - ein neuer praxisorientierter Ansatz? aller Bedarfsträger p größer sein muss, als die Kapazität K des größten Fahrzeuges des

Abbildung in dieser Leseprobe nicht enthalten

Weitere Einzelziele der TTP sind die volle Bedarfsdeckung, die Auslastung und Minimierung der eingesetzten Fahrzeuge oder das Erreichen eines hohen Kundenservices. (vgl. Stolze, 2003)

Das Standardproblem der Tourenplanung umfasst lediglich die zwei Restriktionen Ladekapazität der Fahrzeuge und zeitliche Begrenzung der Touren. Die in der Praxis zu lösenden Tourenplanungsprobleme sind jedoch viel komplexer. Hier müssen zusätzliche Restriktionen wie Kunden-, Auftrags-, Fuhrpark-, Touren-, Personal- und Depotrestriktionen

Abbildung in dieser Leseprobe nicht enthalten

Flexible Transportplanung - ein neuer praxisorientierter Ansatz?

berücksichtigt werden, so dass sich daraus verschiedene weitere Tourenplanungsprobleme ergeben. (vgl. Vogt, 1998)

Assad und Golden klassifizieren die Probleme in Sammelprobleme, kombinierte Sammel- und Verteilprobleme, Mehrdepot-Auslieferungsprobleme, dynamische Tourenplanungs- probleme, depotfreie Auslieferung (Pick up and Delivery), Tourenprobleme mit Zeitfenstern, Tourenprobleme mit tageszeitabhängigen Fahrzeiten, Travelling-Salesman-Probleme, Chinese-Postman-Probleme, Zuordnungsoptimierung, Mehrfacher Einsatz der Fahrzeuge pro Tag, Ein- oder Mehrperiodenprobleme, Tourenplanungsprobleme mit heterogenem Fuhrpark und Transport von Personen (Schulbus-Probleme).¹ Kritisch ist hier jedoch anzumerken, dass es kaum möglich ist, a priori festzulegen, welche Ziele und Restriktionen für ein konkretes Tourenplanungssystem einzuhalten sind. Dies zeigt sich erst in der späteren praktischen Anwendung. Viele der in der Praxis auftauchenden Restriktionen werden von diesem Klassifikationsschema nicht berücksichtigt. (vgl. Grünert, 2003a)

2.3 Savings-Algorithmus - Ein klassisches Problemlösungsverfahren

Das Savings-Verfahren von Clarke und Wright (1964) ist ein heuristisches Verfahren, welches am häufigsten in Softwaresystemen zur Problemlösung eingesetzt wird. Heuristische Verfahren berechnen im Gegensatz zu den exakten Verfahren nur eine näherungsweise optimale Lösung (suboptimal), bieten jedoch den Vorteil, dass der Programmier- und Rechenaufwand sowie der Speicherbedarf viel geringer ist. Tourenplanungsprobleme gehören zu der Klasse der NP-schweren Probleme, so dass die Rechenzeit zur Lösung der Probleme exponentiell mit der Problemgröße wachsen kann. Ein exaktes Lösungsverfahren würde hier einen zu hohen Rechenaufwand verursachen.

Heuristische Verfahren werden in Tour-Konstruktionsverfahren und Tour- Verbesserungsverfahren unterschieden. Das Tour-Konstruktionsverfahren ermittelt zuerst eine zulässige Anfangslösung für das Problem, welche dann anschließend mit einem TourVerbesserungsverfahren verbessert wird. Beide Verfahren müssen dabei zwei Teilprobleme lösen: die Zuordnung der Kunden zu den Touren und die Festlegung der Reihenfolge einer Tour. Das Savings-Verfahren ist ein Tour-Konstruktionsverfahren und versucht die beiden Teilprobleme simultan (parallel) zu lösen. (vgl. Vahrenkamp, 1998) Durch sogenannte „Savings“ Abbildung in dieser Leseprobe nicht enthalten 0,...,n oder Koordinaten für das Depot und die Kunden. Die Anfangslösung besteht daraus, Flexible Transportplanung - ein neuer praxisorientierter Ansatz? dass jeder Kunde i in einer eigenen Tour i (Pendeltour) von dem Depot 0 angefahren wird, wobei die Anzahl der Touren n gleich der Anzahl der Kunden q entspricht. Um diese ungünstige Anfangslösung zu verbessern werden sukzessiv jeweils zwei Touren zu einer neuen Tour zusammengefasst. Dazu wird zwischen allen möglichen Kundenpaaren ein

Abbildung in dieser Leseprobe nicht enthalten

Zeitrestriktionen werden die Touren zusammengelegt, deren Savingswert (Fahrstreckenersparnis) am größten ist. Die Vereinigung wird iterativ weitergeführt bis das erste Null-Saving erreicht ist. Die Anzahl der entstandenen Touren hängt dabei von der Anzahl der zur Verfügung stehenden Fahrzeuge und deren Kapazitäten ab. (vgl. Vogt, 1998 und Diruf, 1996)

3 Gegenwärtige Praxis der Tourenplanungssysteme

Ein Tourenplanungssystem besteht aus einem mathematischen Grundmodell, welches das Tourenplanungsproblem, die relevanten Restriktionen und die Zielfunktion beschreibt. Die Wahl des Grundmodells ist dabei wichtig für die Anwendbarkeit und die Flexibilität des zu entwickelnden Tourenplanungssystems. (vgl. Grünert, 2003a) Nur wenn die Zielfunktion und die Restriktionen bestmöglich und vollständig beschrieben sind, können auftretende Probleme flexibel behandelt werden. Aufbauend auf dem speziellen Grundmodell, werden ein oder mehrere Optimierungsalgorithmen zur Problemlösung eingesetzt, wobei häufig das Savings-Verfahren verwendet wird. (vgl. Fleischmann, 1994) Im Verlauf der Entwicklung und Anwendung des Systems können jedoch zusätzliche Restriktionen hinzukommen oder die Zielfunktion ändert sich, so dass das Grundmodell und die Algorithmen angepasst werden müssen. In der gegenwärtigen Praxis wird folglich ein System ohne exakte Kenntnis des zukünftigen eigentlichen Problems entwickelt und für jede dazukommende Änderung lediglich im Programmcode angepasst. (vgl. Grünert, 2003a) Um die neuen, zusätzlichen Restriktionen zu berücksichtigen wird das Prinzip des „Customizing“ angewendet. Hierbei werden das spezielle Grundmodell und die Algorithmen so erweitert, dass bestimmte Schritte der Algorithmen nur dann ausgeführt werden, wenn auch die zusätzlichen, neuen Restriktionen eingehalten werden. Jedoch ist die Erweiterung des Grundmodells und der Algorithmen nur bis zu einem gewissen Grad möglich, da diese Vorgehensweise dazu führt, dass das eigentliche Problem und das verwendete Modell nur noch wenig Gemeinsamkeiten aufweisen. Die Qualität der Lösung ist somit nicht mehr gegeben und führt zu einer Ablehnung durch die Anwender. Darüber hinaus wird die Software unübersichtlich und schwer wartbar.

[...]

¹ Ausführliche Beschreibung in Vogt, 1998