Logistische Tourenplanung. Lösungsansätzte für effiziente Rundreisen mithilfe von gerichteten Graphen


Seminararbeit, 2015

24 Seiten, Note: 1,3


Leseprobe

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung

2 Tourenplanungsprobleme
2.1 Einordnung der Tourenplanung in die Logistik
2.2 Problem der Tourenplannung
2.3 Lösung des Tourenplanungsproblem
2.3.1 Grundlegende Begriffe
2.3.2 Sweep-Algorithmus zur Lösung des Tourenplanungsproblem

3 Traveling-Salesman-Problem
3.1 Grundlagen und Problem des Traveling-Salesman
3.2 Lösungsverfahren

4 Briefträgerproblem
4.1 Grundlagen und Problem des Briefträgerproblems
4.2 Weitere Briefträgerprobleme
4.3 Euler-Kreise und Euler-Wege

5 Briefträgerproblem in gerichteten Graphen
5.1 Kostenminimale Erweiterung eines gerichteten Graphen
5.2 Formale Problembeschreibung

6 Zusammenfassung und Ausblick in die Zukunft

Literaturverzeichnis

Abbildungsverzeichnis

2.1 Tourenplan

2.2 Sweep-Algorithmus

3.1 Verfahren des besten Nachfolgers

3.2 Grafische Ermittlung nach dem Verfahren des besten Nachfolgers

5.1 Kostenminimale Erweiterung eines gerichteten Graphen

Tabellenverzeichnis

3.1 Kostenmatrix

1 Einleitung

Die Problematik der Tourenplanung ist in Grundzügen seit langem bekannt und gewinnt in der heutigen Zeit immer mehr an Bedeutung. Eine effizente Tourenplanung kann zur Verringerung der Distributionskosten führen. Für einzelne Industriezweige können bereits geringe Kostensenkungen von entscheidenter Bedeutung sein.1 Dasselbe Optimierungs- problem tritt bei der Rundreise auf. Der Briefträger interessiert sich für eine möglichst kurze und effektive Tour durch sein Verteilungsnetz, bei der jede Straße mindestens ein- mal durchlaufen werde. Dieses Problem findet analoge Anwendung bei der Durchführung der Müllabfuhr oder Straßenreinigung unter Minimierung der unproduktiven Strecken. Der ökonomische Nutzen beziehungsweise das Kostensenkungspotenzial bei verbesserten Rundreisen ist beachtlich.2

Vor diesem Hintergrund befasst sich die vorliegende Seminararbeit mit den Problemen der Rundreise und Tourenplanung. Ziel ist es die Grundlagen der Graphentheorie und ausgewählte Praxisthemen zu vermitteln und mit dieser Art Mathematik die wirtschaft- lich relevanten Probleme zu lösen. Kapitel zwei behandelt die Grundlagen der Touren- planung. Darüber hinaus werden die Begriffe ”Problem des Handlungsreisendenünd das ”Briefträgerproblemërklärt sowie eine Reihe weiterer spezieller Briefträgerprobleme auf- gezeigt. Insbesonders setzt sich die Arbeit näher mit dem Briefträgerproblem in gerich- teten Graphen auseinander und wird ein zugrundeliegendes mathematisches Model und das Lösungsverfahren vorstellen. Abschliessend werden die wessentlichen Erkenntnisse und der Inhalt der Arbeit zusammengefasst. Ferner wird weiterer Forschungsbedarf dar- gestellt.

2 Tourenplanungsprobleme

Die allgemeine Aufgabe der Tourenplanung ist, kleinere Transportaufträge, zu einer Tour zusammenzufassen. Dabei wird ein Zielkriterium zum Beispiel die zurückzulegende Stre- cke zu minimieren verfolgt. Die Belieferung der Kunden ist sicherzustellen, wobei diese Sicherstellung kostenoptimal erfolgen sollte. Ziel ist die Transportkostenminimierung.1

2.1 Einordnung der Tourenplanung in die Logistik

Logistik ist die ganzheitliche, marktgerechte, nachhaltige Planung, Steuerung, Abwicklung und Kontrolle aller Material-, Waren- und Informationsflüsse von Lieferanten in das Unternehmen und innerhalb des Unternehmen sowie vom Unternehmen zum Kunden. In einem Unternehmen wird dir Logistik in Beschaffungs-, Produktions- und Distributionslogistik gegliedert, die der Versorgungslogistik zugeordnet sind. Entsorungungslogistik und die Versorgungslogistik schliessen den logistischen Kreislauf.2

Die Tourenplanung wird der Distributionslogistik zugeordnet. Die Distributionslogistik umfasst alle Aktivitäten, die den Abnehmern die physische Verfügbarkeit der Produk- te sowie die damit verbundenen Informationen ermöglichen. Sie befasst sich mit der Planung, Steuerung und Kontrolle des physischen Warenflusses einschließlich der dazu- gehörigen Information zwischen Unternehmen und den jeweiligen Kunden. Die Aufgaben der Distributionslogistik sind in strategische und operative Aufgaben unterteilt.3

Strategische Aufgaben:4

- Standortplanung
- Gestaltung der Distributionsstruktur
- Entscheidung über Eigentransport oder Fremdtransport
- Bestimmung der Vertriebswege und Transportwege

Operative Aufgaben:5

- Auftragsabwicklung
- Warenverteilung
- Kommissionierung
- Rundreis-/Tourenplanung

Die Aufgabe der strategischen Planung ist die Betrachtung der allgemeinen Unterneh- mensziele und die zu verfolgenden Strategien. Dabei wird die zukünftige Entwicklung des Unternehmens betrachtet. Bei der strategischen Planung ist die Datenunsicherheit sehr groß und die Problemstellung unstrukturiert. Die operative Planung weist einen kurzfristigen Zeithorizont auf, bei der ein einzelner Teilbereich mit zuverlässigen Daten im Vordergrund steht. Demnach ist die Tourenplanung eine Teilaufgabe der operativen Distribution.6

2.2 Problem der Tourenplannung

Das Gebiet der Tourenplanung hat in den letzten Jahren immer mehr an Aufmerksam- keit gewonnen. 1959 führten schon Dantzig und Ramser das Tourenplanungsproblem ein. In den folgenden Jahren wurden eine Vielzahl von Modellen und Algorithmen für die Lösung von verschiedenen Varianten des Tourenplanungsproblems entwickelt. Untersu- chungen zeigen das durch Einsatz von Softwareanwendungen 5% bis 20% Einsparungen bei den Transportkosten erreicht werden können.7 Daher ist eine Zusammenfassung von Touren unter ökonomischen und ökologischen Gesichtspunkten sehr ratsam.8

Ein Tourenplan ist dadurch gekennzeichnet, dass eine Anzahl von Kunden einer Regi- on, mit einer Anzahl von Fahrzeugen mit bestimmter Kapazität von einem Depot aus beliefert werden. Dabei sind Bedarf und Standort der Kunden bekannt.9 Alle Kunden sind genau einmal zu beliefern und die Nachfrage der Kunden muss befriedigt werden.10 Ziel ist es die Kunden unter Einhaltung von Kapazitätsrestriktion und Zeitrestriktion zu beliefern und die Gesamtkosten zu minimieren.11 Die Abbildung 2.1 veranschaulicht das Tourenplanungsproblem.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Tourenplanungsproblem mit einem Depot und 9 Kunden12

Die Tourenplanungsprobleme unterscheiden sich in zahlreichen Details. Zu nennen sind bespielsweise:13

- Pick-up & Delivery-Porblem: Während einer Tour werden Waren ausgeliefert und abgholt. Wenn Volumen und Gewicht der Rückladung eines Kunden dem geliefer- ten Gewicht entsprechen, kann das Problem wie ein Auslieferungsproblem gelöst werden
- Transport von Personen: Es handelt sich um den Transport von Personen. So muss in einer Region eine Flotte von Schulbussen Schüler von Bushaltestellen abholen und zur Schule und zurück befördern. Ziel ist es die Fahrzeuge und sie Fahrleistung zu minimieren
- Travelling-Salesman-Problem: Ist ein Reihenfolgeproblem, bei dem die kürzeste Rundreise durch eine vorgegebene Menge von Orten gesucht ist. Es sind keine Fahrzeugkapazitäten zu beachten
- Briefträgerproblem: Ist ebenfalls ein Reihemfolgeproblem, bei dem der Briefträger alle Straßen in seinem Gebiet mindestens einmal durchläuft. Ziel ist es die Wegstrecke zu minimieren

Die grundlegendste Unterscheidung bei Tourenplanungsproblemen ist die Unterschei- dung in kantenorientierte und knotenorientierte Problemstellung. Bei kantenorientierten Tourenproblemen sind die Kunden gleichmäßig über die versorgenden beziehungswei- se entsorgenden Straßen verteilt, während bei knotenorientierten Tourenproblemen die Kunden diskrete Punkte in einer Ebene darstellen. Bei kantenorientierten Problemen wird auch von verallgemeinerten Briefträgerproblem gesprochen und bei knotenorien- tierten Problemen von verallgemeinerten Travelling-Salesman-Problem.14

2.3 Lösung des Tourenplanungsproblem

Durch die schnelle Entwicklung auf dem Gebiet der Tourenplanung finden immer mehr Methoden des Operations Research Anwendung bei der Lösung von Tourenplanungsproblemen. Es wurden immer mehr Softwarepackete entwickelt.15 In der Praxis gibt es kein einheitliches Problem, sondern ist von Branche zu Branche unterschiedlich und von Fall zu Fall können sich die zu lösenden Probleme hinsichtlich zahlreicher Kriterien unterscheiden. Die jeweils zu empfehlenden Lösungsverfahren unterscheiden sich daher entsprechend.16 Im Folgende werden mathematische Modelle als auch Verfahren zur Lösung von Tourenplanungsproblem vorgestellt.

2.3.1 Grundlegende Begriffe

In der nachfolgenden Ausführung werden einige Begriffe erklärt:17

- Depot: An diesem Ort werden Sammelfahrten und Auslieferungsfahrten beginnen und enden. Hier ist das Sammellager, der Fuhrpark oder das Auslieferungslager
- Tour: Eine Tour beinhaltet die Menge aller Kunden, die durch ein Fahrzeug auf der ein und derselben, in einem Depot beginnenden und endenden Fahrt beliefert werden
- Route: Ist die Reihenfolge, in der die Kunden innerhalb einer Tour bedient werden
- Tourenplan: Fasst alle Touren zusammen, die zur Erfüllung der gegebenen Aufträge notwendig sind

2.3.2 Sweep-Algorithmus zur Lösung des Tourenplanungsproblem

Es findet eine Unterscheidung bei den Lösungsverfahren für das Tourenplanungspro- blem statt. Heuristische Lösungsverfahren bestimmen für ein gegebenes Problem in begrenzter Zeit eine zulässige Lösung. Exakte Verfahren hingegen lösen eine gegebe- ne Problemstellung optimal. Heuristische Lösungen versprechen jedoch nicht das Auf- finden von Optimallösungen und verfehlen bei zunehmender Problemstellung die Op- timallösung. Dafür benötigen sie einen geringern Rechenaufwand als exakte Verfahren. Exakte Lösungsverfahren haben aufgrund des hohen Rechenaufwandes Probleme mit be- schränkter Größe in kurzer Zeit. In der Praxis werden aus diesen Gründen kaum exakte Verfahren verwendet.18

Das wohl bekannteste Verfahren ist der Sweep-Algorithmus, der zu den heuristischen Lösungsverfahren gehört und bereits 1974 von Gillet und Miller entwickelt wurde.19 Der Algorithmus ist stark an der geographischen Anordnung der Kunden orientiert. Von ei- nem Koodinatensystem ausgehend, stimmt der Standort des Depot mit dem Ursprung überein. Es erfolgt die Sortierung der Kunden nach aufsteigendem Polarwinkel, zu dessen Bestimmung die Standortkoordinaten der Kunden verwendet werden. Im ersten Schritt findet die Zusammenfassung der Kunden zu Clustern statt, dies findet anhand der Rei- henfolge der sortierten Liste statt. Ein Cluster ist abgeschlossen, wenn durch die Kapa- zitätsrestriktion oder Zeitrestriktion keine Aufnahme eines weiteren Kunden möglich ist. Im zweiten Schritt erfolgt die Bestimmung der Reihenfolge innerhalb der Tour für die Kunden je Cluster. Der geschilderte Schritt wiederholt sich n-mal um ein Tourenplan zu generieren, da jeder Knoten einmal Startknoten für die Sortierung nach aufsteigenden Polarwinkel ist. Es werden n Tourenpläne bestimmt und derjenige mit der geringsten Gesamtdistanz ausgewählt.20

Der Sweep-Algorithmus liefert vergleichsweise gute Ergebnisse, wenn das Depot zentral liegt und die Kundenstandorte gleichmäßig über die Regionen verteilt sind. Ausserdem das Verhältnis der Anzahl der Touren zur Anzahl der durchschnittlichen Kundenzahl pro Tour kleiner 2 ist.21 Die Abbildung 2.2 veranschaulicht den Sweep-Algorithmus mit der Kapazitätsrestriktion von 150 Mengeneinheiten pro Tour. Es ergibt sich ein Tourenplan mit vier Touren.

[...]


1 Vgl. Richter (2005): Dynamische Tourenplanung, S. 2.

2 Vgl. Krischke / Röpke (2014): Graphen und Netzwerktheorie, S. 90.

1 Vgl. Führer (2011): Standortplanung, S. 5f.

2 Vgl. Lasch (2012): Strategisches und operatives Logistikmanagement, S. 5f.

3 Vgl. Huber / Laverentz (2012): Logistik, S. 121f.

4 Vgl. Richter (2005): Dynamische Tourenplanung, S. 15f.

5 Vgl. Richter (2005): Dynamische Tourenplanung, S. 16.

6 Vgl. Huber / Laverentz (2012): Logistik, S. 125-130.

7 Vgl. Wiedey (1982): Tourenplanung, S. 5f.

8 Vgl. Dethloff (1994): Verallgemeinerte Tourenplanungsproblem, S. 18.

9 Vgl. Mayer (1977): Das Tourenplanungsproblem, S. 7f.

10 Vgl. Vahrenkamp / Kotzab (2012): Management und Strategien, S. 454.

11 Vgl. Engele (1980): Rundreisen und Touren, S. 5-8.

12 Eigene Abbildung.

13 Vgl. Vahrenkamp / Kotzab (2012): Management und Strategien, S. 455f.

14 Vgl. Domschke (1997): Rundreisen und Touren, S. 205.

15 Vgl. Lasch (2012): Strategisches und operatives Logistikmanagement, S. 177f.

16 Vgl. Richter (2005): Dynamische Tourenplanung, S. 42f.

17 Vgl. Domschke / Scholl (2010): Rundreisen und Touren, S. 198.

18 Vgl. Richter (2005): Dynamische Tourenplanung, S. 33.

19 Vgl. Wiedey (1982): Tourenplanung, S. 55.

20 Vgl. Engele (1980): Rundreisen und Touren, S. 60f.

21 Vgl. Lasch (2012): Strategisches und operatives Logistikmanagement, S. 167f.

Ende der Leseprobe aus 24 Seiten

Details

Titel
Logistische Tourenplanung. Lösungsansätzte für effiziente Rundreisen mithilfe von gerichteten Graphen
Hochschule
Technische Universität Dresden
Note
1,3
Autor
Jahr
2015
Seiten
24
Katalognummer
V306974
ISBN (eBook)
9783668058866
ISBN (Buch)
9783668058873
Dateigröße
548 KB
Sprache
Deutsch
Schlagworte
BWL, Logistik, Produktion, Beschaffung, Briefträgerproblem, Gerichtete Graphen, Tourenplanungsprobleme, Traveling-Salesman-Problem, Sweep-Algorithmus, Euler-Kreise, Euler-Wege, Handlungsreisende, Briefträger, Rundreise, Lösungsansätze
Arbeit zitieren
Felix Ritter (Autor), 2015, Logistische Tourenplanung. Lösungsansätzte für effiziente Rundreisen mithilfe von gerichteten Graphen, München, GRIN Verlag, https://www.grin.com/document/306974

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Logistische Tourenplanung. Lösungsansätzte für effiziente Rundreisen mithilfe von gerichteten Graphen



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden