Transport- und Tourenplanung: Verfahren und Software zur Lösung komplexer Tourenplanungsprobleme

Masterarbeit , 2011 , 99 Seiten , Note: 1,0

BWL - Beschaffung, Produktion, Logistik

Gegenstand dieser Arbeit ist eine umfangreiche Betrachtung der Tourenplanungsproblematik. Es wird die Entwicklung und die Vielfalt des Tourenplanungsproblems dargestellt und erläutert. Hierzu werden das Standardproblem der Tourenplanung, die Mehrdepot-Tourenplanung, die Tourenplanung mit Zeitfensterrestriktionen und die dynamische Tourenplanung näher betrachtet.

Ein Schwerpunkt der Arbeit befasst sich mit Lösungsverfahren für die erwähnten Ausprägungen der Tourenplanungsproblematik. Dabei werden ausgewählte Verfahren vorgestellt und deren Funktionsweise erläutert. Hierbei erfolgt eine kritische Betrachtung der Verfahren. Des Weiteren wird deren Lösungsqualität untersucht und mit anderen Verfahren verglichen, sowie mögliche Vor- und Nachteile aufgezeigt.
Der zweite Schwerpunkt bezieht sich auf eine Marktrecherche nach Softwarelösungen für Tourenplanungsprobleme. Es werden geeignete Softwarelösungen für die Tourenplanungsproblematik zusammengefasst und nach bestimmten Kriterien untersucht. Ein wichtiger Bestandteil dieser Marktrecherche ist eine Studie, in welcher Unternehmen zu Tourenplanungssoftware befragt wurden. Ein Teil der Untersuchungskriterien leitet sich aus wichtigen Erkenntnissen dieser Studie ab und stellt somit einen praktischen Bezug dar.

Inhaltsverzeichnis

1 Einleitung
1.1 Ziele der Arbeit
1.2 Aufbau der Arbeit

2 Grundlagen
2.1 Beschreibung des Tourenplanungsproblems
2.2 Begriffe und Definitionen in der Tourenplanung
2.3 Standardproblem der Tourenplanung
2.4 Restriktionen in der Tourenplanung und daraus abgeleitete Ausprägungen der Tourenplanungsproblematik
2.5 Kombinatorische Optimierungsproblematik in der Tourenplanung
2.5.1 Exakte Verfahren
2.5.2 Problemspezifische Heuristiken und dazugehörige Operatoren
2.5.3 Metaheuristiken
2.5.3.1 Tabu Search
2.5.3.2 Genetische Algorithmen und Evolutionsstrategien
2.5.3.3 Simulated Annealing und Threshold Accepting
2.5.3.4 Guided Local Search

3 Verfahren zur Lösung von Tourenplanungsproblemen
3.1 Standardproblem der Tourenplanung
3.1.1 Sweep Verfahren
3.1.2 Savings Verfahren
3.1.3 Sonstige Verfahren
3.2 Mehrdepot-Tourenplanung
3.2.1 Mehrdepot Sweep Verfahren
3.2.2 Mehrdepot Savings Verfahren
3.2.3 Tabu Search Heuristik von Renaud, Laporte und Boctor
3.2.4 Sonstige Verfahren
3.3 Tourenplanung mit Zeitfensterrestriktionen
3.3.1 Kooperativ-parallele Metaheuristik von Homberger
3.3.2 Adaptive Suchheuristiken von Pisinger und Ropke
3.3.3 Aktiv gesteuerte Evolutionsstrategien von Mester und Bräysy
3.3.4 Sonstige Verfahren
3.4 Dynamische Tourenplanung
3.4.1 Simulator zur dynamischen Tourenplanung von Lund, Madsen und Rygaard
3.4.2 Zweistufige-parallele Tabu Search Heuristik von Gendreau, Guertin, Potvin und Taillard
3.4.3 Parallele Tabu Search Heuristik von Ichoua, Gendreau und Potvin
3.4.4 Sonstige Verfahren

4 Softwarelösungen für Tourenplanungsprobleme
4.1 Funktionen rechnergestützter Tourenplanungssysteme und deren Vor- und Nachteile
4.2 Wirtschaftliche Bedeutung
4.3 Kundenwünsche und -anforderungen an Tourenplanungssysteme
4.4 Tourenplanungssysteme auf dem Markt

5 Zusammenfassung und Ausblick

Abbildungsverzeichnis

Abbildung 1: Entwicklung des Welthandels im Zeitraum von 1980 bis

Abbildung 2: Veranschaulichung des Unterschieds zwischen dem knotenorientierten TSP und dem kantenorientierten CPP

Abbildung 3: Auslieferungsproblem in der Tourenplanung mit fünf Kunden und einem Depot

Abbildung 4: Beispiel für das Standardproblem der Tourenplanung mit fünf Kunden und zwei Touren

Abbildung 5: Beispiel einer Mehrdept-Tourenplanung

Abbildung 6: Zeitliche Darstellung einer Tour und der Problematik im VRPTW

Abbildung 7: Entwicklung des Auftragsbestandes über der Zeit im CVRP und DVRP

Abbildung 8: Ausprägungen der Tourenplanungsproblematik im Rahmen dieser Arbeit mit dem dazugehörigen Restriktionsbereich

Abbildung 9: Beispiel eines Klassifizierungsschemas nach Stumpf

Abbildung 10: Klassifizierung der Lösungsverfahren nach Streim

Abbildung 11: Vergleich zwischen heuristischen und exakten Tourenplanungsverfahren am Beispiel des technischen Kundendienstes des Unternehmens .. Miele & Cie. KG

Abbildung 12: Exemplarische Darstellung des Cluster First - Route Second Verfahrens in der Tourenplanung

Abbildung 13: Unterschied zwischen lokalen und globalen Optima

Abbildung 14: Beispielfall eines 2-opt Verfahrens

Abbildung 15: Tauschvarianten bei Inter-Tour Verfahren

Abbildung 16: Schematischer Ablauf evolutionärer Strategien nach Weicker

Abbildung 17: Verlauf der Akzeptanzwahrscheinlichkeit bei linearer Kühlfunktion am Beispiel von 5- und 10 prozentigen Verschlechterungen

Abbildung 18: Erstellung der Ausgangslage für das Sweep Verfahren durch Sortierung der Kunden mittels steigendem Polarwinkel φ

Abbildung 19: Prozess beim Savings Verfahren

Abbildung 20: Berechnung der Umwege für Grenzkunden i

Abbildung 21: Ermittlung der Savingswerte in der Mehrdepot- Tourenplanungsproblematik

Abbildung 22: Kombination zweier Touren entsprechend der Savingsfunktion nach Matthäus

Abbildung 23: Beispiel für eine zulässige und nicht zulässige Einfügung im Zusammenhang mit der erforderlichen Gesamtverspätung

Abbildung 24: Dispositionssystem auf Basis von GPS und GSM

Abbildung 25: Unterschiedlicher Status von Fahrzeugzügen

Abbildung 26: Simulator zur dynamischen Tourenplanung nach Lund, Madsen ... und Rygaard

Abbildung 27: Zweistufige-parallele Tabu Search Heuristik nach Gendreau, Guertin, Potvin und Taillard

Abbildung 28: Zeitdauer zwischen Auftragseingang und Auslieferung

Abbildung 29: Einsatz von Tourenplanungssoftware

Abbildung 30: Hinderungsgründe für den Einsatz von Tourenplanungssoftware

Abbildung 31: Wichtigkeit der Berücksichtigung individueller Kriterien

Abbildung 32: Notwendigkeit manueller Nacharbeit

Tabellenverzeichnis

Tabelle 1: Symmetrische Entfernungsmatrix D für das Beispiel des Standardproblems der Tourenplanung mit fünf Kunden

Tabelle 2: Restriktionen in der Tourenplanung

Tabelle 3: Laufzeitverhalten von Algorithmen in Abhängigkeit vom Rechenaufwand . und von der Größe des Problems n

Tabelle 4: Eingliederung heuristischer Verfahren für Tourenplanungsprobleme ... nach Domschke

Tabelle 5: Restriktionen ausgewählter dynamischer Tourenplanungsverfahren

Tabelle 6: Funktionen softwaregestützter Tourenplanungssysteme nach Schulte

Tabelle 7: Kosten ausgewählter softwaregestützter Tourenplanungssysteme nach ... einer Studie aus dem Jahr

Tabelle 8: Tourenplanungssoftware auf dem Markt mit Angabe des Herstellers .. und der untersuchten Kriterien

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Der Begriff „Logistik“, der ursprünglich aus dem Militärwesen stammt und Mitte der fünfziger Jahre in den zivilen Bereich überführt wurde, untersteht einer stetigen Neuorientierung und Weiterentwicklung. Während in den 80er Jahren der Lean-Gedanke in der Produktion immer mehr an Bedeutung gewann und das Outsourcing und die Suche nach immer günstigeren Produktionsmöglichkeiten förderte, konzentriert sich die Logistik des jungen 21. Jahrhunderts auf einen kostengünstigen Güter- und Informationstransport basierend auf Schnelligkeit und Flexibilität und ist zusätzlich durch ein erhöhtes Umwelt- und Qualitätsbewusstsein geprägt. Diese Entwicklung ist vor allem auf die zunehmende Globalisierung, aber auch auf die starke Verbreitung des Internets zurückzuführen,^[1] wodurch weltweite Informationsflüsse binnen weniger Sekunden möglich sind und schnelle Reaktionen fordern. Baumgarten spricht im Zusammenhang der neuen Logistikanforderungen auch von der Optimierung globaler Netzwerke,^[2] betont also den wachsenden Einfluss global abgestimmter Logistikprozesse.

Nicht nur die Anforderungen an die Logistik ändern sich, sondern auch die Bedeutung der Logistik wird zunehmend größer. Dies zeigt unter anderem die Entwicklung der Weltwirtschaft im Bezug auf den Welthandel, also den weltweiten Gütertransport in Abbildung 1.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Entwicklung des Welthandels im Zeitraum von 1980 bis 2008^[3]

Vor allem seit Beginn des neuen Jahrtausends ist ein starker Anstieg der Importe und Exporte zu verzeichnen. Das Welthandelsvolumen ist vom Jahr 2000 bis 2008 um fast das Zweieinhalbfache gestiegen. Es liegt also nahe, dass auch die Transportvolumina weltweit rasant zugenommen haben und die Notwendigkeit gut geplanter logistischer Prozesse und Strukturen immer wichtiger geworden ist.

Aber auch im gesellschaftlichen Bereich verändern sich stetig Strukturen, die eine Anpassung der Logistik fordern, wie der Demographiewandel^[4] in vielen Industrieländern und die voranschreitende Urbanisierung weltweit.^[5] Das führt dazu, dass bestehende Supply Chains neu strukturiert und angepasst werden müssen, um weiterhin effizient bleiben zu können.

Als klassisches Ziel der Logistik wird von vielen Autoren die Optimierung des Logistikerfolgs angegeben, der aus den zwei Komponenten Logistikleistung und Logistikkosten besteht.^[6] Dazu gehören unter anderem Elemente wie Lieferzeit, Lieferzuverlässigkeit, Lieferqualität, Lagerkosten, Transportkosten usw. In den letzen Jahren ist aber noch ein weiteres Element hinzugekommen, das einen immer größeren Einfluss auf den Logistikerfolg hat, nämlich die Verantwortung der Logistik für die Umwelt. Grund hierfür ist, dass durch den weltweit zunehmenden Güterverkehr die Emissionen rapide angestiegen sind. Laut einer Studie beträgt dieser Anstieg allein in den Jahren von 1990 bis 2005 bereits 224 %.^[7] Um diesen Trend entgegenzuwirken hat sich das Themengebiet „Green Logistics“ entwickelt, welches für viele Unternehmen bereits einen sehr hohen Stellenwert hat und laut Umfragen in Zukunft noch weiter steigen wird.^[8] Unternehmensbeispiele für „grüne“ Logistikkonzepte, -produkte, -instrumente usw. sind der Vito E-CELL des KEP-Dienstleisters Hermes,^[9] die Deutsche Post DHL GoGreen Strategie^[10] und das DB ECO Programm^[11] .

Ein wichtiges Aufgabengebiet der Logistik, welches zugleich Anforderungen und Ziele der Logistik gut vereint, ist die Routen- bzw. Tourenplanung. "Die Tourenplanung umfasst die kostenoptimale ‑ EDV-gestützte ‑ operative Planung und Durchführung inner- und außerbetrieblicher Transportaufgaben unter Berücksichtigung der verfügbaren personellen und sachlichen Kapazitäten, Strategien und Restriktionen mit Hilfe mathematischer Algorithmen".^[12] Dieser kostenoptimale Zustand wird in der Regel durch Weg- und Zeitoptimierungen, also kürzere Strecken und Transportzeiten, erreicht. Die Tourenplanung beinhaltet demnach Elemente der Logistikleistung und Logistikkosten, kann einen maßgeblichen Beitrag zur Senkung der Emissionen leisten und bietet die Möglichkeit Transporte schneller und flexibler durchzuführen, also effektiver zu gestalten. Sie erfüllt somit die aktuell an die Logistik gestellten Anforderungen und kann zur Maximierung des Logistikerfolgs beitragen.

In der Regel erfolgt die Tourenplanung rechnergestützt mit Verwendung von spezieller Software. Diese Softwarelösungen arbeiten nach unterschiedlichen mathematischen Algorithmen, die im Kapitel 3 näher erläutert werden. Die Anwendung geeigneter Tourenplanung ist sehr weitreichend und wird nicht nur von Unternehmen eingesetzt, um Kostensenkungspotenziale zu erzielen. Überall, wo es darum geht Transportaufgaben umzusetzen, bietet sich eine Tourenplanung an, um möglichst optimale Strecken zu benutzen. Ein Beispiel aus dem nichtwirtschaftlichen Bereich sind Hilfsorganisationen, die im Jahr 2007 nach Unruhen in Kenia Tourenplanungsverfahren zur Verteilung von Hilfsgütern nutzten und dadurch die Gesamtentfernung der zu fahrenden Touren um fast die Hälfte reduzierten.^[13] Hier lag der Schwerpunkt in einer schnellen und flexiblen Hilfe für die Betroffenen. Zusätzlich konnte ein wesentlicher Anteil der Transportkosten eingespart werden.

Folglich besteht großes Potenzial in der Tourenplanung, wenn es darum geht Transporte kosten- und zeitoptimal zu planen und durchzuführen und dabei die Umweltbelastung möglichst minimal zu halten. Da die Weltbevölkerung und die weltweiten Gütertransporte laut Prognosen in Zukunft weiter zunehmen werden, wird auch das Potenzial und die Bedeutung einer systematisch durchgeführten Tourenplanung weiter ansteigen.

1.1 Ziele der Arbeit

Die vorliegende Arbeit befasst sich mit der Thematik der Tourenplanung. Hierzu wird die Problematik der Tourenplanung näher erläutert und die zur Berechnung der Touren verwendeten Tourenplanungsverfahren vorgestellt. Des Weiteren wird eine Marktrecherche nach Softwarelösungen für Tourenplanungsprobleme durchgeführt. Anschließend werden diese nach bestimmten Kriterien untersucht.

Das Ziel der Arbeit ist eine kritische Darstellung und Zusammenfassung ausgewählter mathematischer Algorithmen für Tourenplanungsprobleme. Dabei soll vor allem auf die Funktionsweise und nach Möglichkeit die Eignung der Verfahren für Tourenplanungsprobleme eingegangen werden, also auf deren Ergebnisqualität. Ein Schwerpunkt wird hierbei auf die unterschiedlichen Ausprägungen von Tourenplanungsproblemen gesetzt, die vom Standardproblem der Tourenplanung abweichen. Dazu gehört die Mehrdepot-Tourenplanung, die Tourenplanung mit Zeitfensterrestriktionen und die dynamische Tourenplanung. Es wird geprüft, wie stark sich die einzelnen Ausprägungen vom Standardproblem unterscheiden, welche zusätzlichen relevanten Kriterien berücksichtigt werden müssen und welche Verfahren es für die Lösung dieser speziellen Tourenplanungsprobleme gibt.

Der zweite Schwerpunkt der Arbeit ist eine Marktrecherche nach zurzeit auf dem Markt befindlichen Softwarelösungen für Tourenplanungsprobleme. Hierzu werden im Laufe der Arbeit zunächst wichtige Kriterien gefiltert, nach welchen die Softwarelösungen untersucht werden. Bereits definierte Untersuchungskriterien sind die Möglichkeit Mehrdepotprobleme zu lösen, Zeitfensterrestriktionen zu beachten und eine dynamische Tourenplanung zu implementieren. Außerdem soll überprüft werden, ob und wie das neue wichtige Themengebiet „Grüne Logistik“ implementiert ist. Nach Möglichkeit soll darauf eingegangen werden mit welchen Algorithmen die Softwarelösungen arbeiten.

1.2 Aufbau der Arbeit

Nach der Einleitung und Zieldefinition im Kapitel Fehler! Verweisquelle konnte nicht gefunden werden. werden im Kapitel 2 die Grundlagen erläutert. Dazu wird näher auf die Entstehung und Problematik des Tourenplanungsproblems eingegangen und das Auslieferungsproblem dargestellt, aus welchem sich das Standardproblem der Tourenplanung ableitet. Des Weiteren werden Begriffe und Definitionen erläutert, um eine Verständnisbasis für die Thematik zu schaffen, sowie mögliche Restriktionen aus der Literatur zusammengefasst und in den Kontext der Arbeit eingebettet. Dadurch wird die Vielfalt und die zu beachtenden Kriterien in der Tourenplanungsproblematik deutlich. Abschließend erfolgt eine Beschreibung des kombinatorischen Optimierungsproblems in der Tourenplanung, sowie eine allgemeine Vorstellung bekannter Lösungsverfahren aufgegliedert in exakte Verfahren, problemspezifische Heuristiken und Metaheuristiken.

Im Kapitel 3 liegt der Schwerpunkt auf der Darstellung der verschiedenen Verfahren zur Lösung des Tourenplanungsproblems. Hier erfolgt zunächst eine Eingrenzung der jeweiligen Problematik. Danach werden ausgewählte Verfahren zum Standardproblem der Tourenplanung und zu den speziellen Ausprägungen des Tourenplanungsproblems detailliert betrachtet und deren Funktionsweise erläutert. Die Auswahl wird auf die bekanntesten, erfolgreichsten oder neuesten Verfahren beschränkt. Am Ende jeder einzelnen Ausprägung des Tourenplanungsproblems werden kurze Literaturverweise zu weiteren Werken gegeben, die sich mit anderen in dieser Arbeit nicht vorgestellten Verfahren befassen.

Kapitel 4 befasst sich mit den Softwarelösungen für Tourenplanungsprobleme. Hier wird zunächst ein Überblick über den Funktionsumfang einer geeigneten Tourenplanungssoftware gegeben, die Vorteile und Nachteile der Nutzung solcher Software aufgelistet und die wirtschaftliche Bedeutung für ein Unternehmen dargestellt. Anschließend werden die wichtigsten Ergebnisse und Kernaussagen aus einer im Jahr 2005 durchgeführten Studie zu Kundenwünschen und -anforderungen an Tourenplanungssysteme zusammengefasst und daraus Kriterien für die Marktrecherche abgeleitet. Am Ende des Kapitels werden die Ergebnisse der Marktrecherche vorgestellt und diskutiert.

Das abschließende Kapitel 5 fasst die wichtigsten Erkenntnisse noch einmal zusammen und gibt einen kurzen Ausblick für zukünftige Arbeiten im Bereich der Tourenplanung.

2 Grundlagen

Im Kapitel Grundlagen wird zunächst die Entstehung und der Kerngedanke der Tourenplanung näher erläutert und dessen Bedeutung aus wirtschaftlicher Sicht aufgeführt. Das Standardproblem der Tourenplanung wird dargestellt und die dazu notwendigen Begriffe und Definitionen als Verständnisbasis eingeführt. Des Weiteren wird eine Liste mit zu beachtenden Restriktionen vorgestellt und dessen Bedeutung aus Sicht der Tourenplanungsproblematik erläutert. Dazu erfolgt eine Abgrenzung zwischen dem allgemeinen Tourenplanungsproblem und diversen Ausprägungen dieser Problematik, sowie eine Einbettung dieser in den Rahmen dieser Arbeit. Abschließend wird die kombinatorische Optimierungsproblematik erläutert und die möglichen Lösungsverfahren bzw. Lösungsansätze dargestellt, die in exakte Verfahren, problemspezifische Heuristiken und Metaheuristiken eingeteilt sind.

2.1 Beschreibung des Tourenplanungsproblems

Die Tourenplanung kann auf das Travelling Salesman Problem (TSP), sowie das Chinese Postman Problem (CPP) zurückgeführt werden.^[14] Beides sind Reihenfolgeprobleme, bei denen es darum geht definierte Gebiete in einem kürzest möglichen Weg zu durchqueren und wieder zum Anfangsort zu gelangen. D.h. es soll ein möglichst optimaler Weg gefunden werden, der den geringsten Aufwand aufweist, dabei handelt es sich in der Regel um Kosten- oder Zeitaufwand, aber dennoch die Zielvorgaben erfüllt und dabei bestimmte Bedingungen einhält. Wirtschaftlich gesehen soll das Problem nach dem Minimalprinzip gelöst werden.

Obwohl beide Problemstellungen dasselbe Ziel verfolgen, unterscheiden sie sich durch zwei für die Tourenplanung wesentliche Merkmale. Das TSP ist ein knotenorientiertes Problem, bei welchem die Knoten genau ein Mal besucht werden müssen. Die Knoten können als Kunden oder Kundenorte interpretiert werden und mögliche Wege bzw. Verbindungen zwischen den Knoten werden als Kanten dargestellt. Das CPP dagegen ist ein kantenorientiertes Problem, bei welchem die Kanten mindestens ein Mal auf dem Weg durchquert werden müssen, d.h. sie können auch mehrmals benutzt werden. Hier sind die Kanten das entscheidende Element und können stellvertretend als Straßen oder mögliche Wege angesehen werden. Die Knoten bilden lediglich Verbindungselemente zwischen den Kanten ab.^[15] Dieser Unterschied zwischen Knoten- und Kantenorientierung wird in Abbildung 2 veranschaulicht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Veranschaulichung des Unterschieds zwischen dem knotenorientierten TSP und dem kantenorientierten CPP

Klassische Beispiele für das TSP sind die Zustellung von Paketen oder das Setzen von Bohrungen auf einer Leiterplatte und für das CPP die Briefzustellung oder die Müllabfuhr.^[16] In der Praxis treten knotenorientierte Fragestellungen weitaus häufiger auf, wodurch die im Kapitel 3 dargestellten Verfahren ausschließlich Lösungsansätze für knotenorientierte Tourenplanungsprobleme sind.

Da die Tourenplanung ein Teilgebiet der Distributions- und Entsorgungslogistik ist, hat sich aus Analogien zum TSP das sogenannte Auslieferungsproblem entwickelt, welches Vahrenkamp wie folgt formuliert hat:

"Eine Anzahl von Kunden einer Region, deren Bedarfe und Standorte bekannt sind, soll mit einer Anzahl von Fahrzeugen mit bestimmten Kapazitäten von einem Depot (z.B. Lager) aus mit einem bestimmten Gut beliefert werden. Es gilt (...) die Kunden so zu beliefern, dass unter Einhaltung aller Restriktionen (z.B. Kapazitäts- und Zeitrestriktionen) die Gesamttransportkosten minimiert werden".^[17] Die Abbildung 3 stellt die Problematik grafisch dar.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Auslieferungsproblem in der Tourenplanung mit fünf Kunden und einem Depot^[18]

Zur Lösung der Problematik sind die Distanzen zwischen den einzelnen Kundenorten und dem Depot zu beachten, sowie eine Vielzahl von Restriktionen, auf die im Kapitel 2.4 näher eingegangen wird. Die Ziele einer Tourenplanung können unterschiedlich sein und verschiedene wirtschaftliche Auswirkungen mit sich bringen. Grundsätzlich geht es darum, wie im Auslieferungsproblem erwähnt, die Gesamttransportkosten zu minimieren und somit einen höheren Logistikerfolg zu erzielen. Dies kann durch mehrere unterschiedliche Vorgehensweisen erzielt werden, wie durch Minimierung der Gesamtentfernung, der eingesetzten Fahrzeuge oder der Fahrzeit. Es kann jedoch auch eine Erhöhung des Lieferservicegrades oder eine gleichmäßige Auslastung der Fahrzeuge als Ziel angegeben werden.^[19] In diesem Fall bedarf es spezieller bzw. modifizierter Verfahren oder gar manueller Nachabreit im Planungsprozess und kann zu einer Erhöhung der Gesamttransportkosten kommen. Aus diesem Grund sind das eher seltene Zielvorgaben einer Tourenplanung.

2.2 Begriffe und Definitionen in der Tourenplanung

Die Kenntnis über folgende Begriffe und Definitionen ist für den weiteren Verlauf der Arbeit nützlich und dient zum besseren Verständnis der Tourenplanungsproblematik:^[20]

- Das Tourenplanungsproblem wird auf einem bewerteten Graphen G abgebildet, der die Knotenmenge V und die Kantenmenge E besitzt.
- Das Depot ist der Ort, an welchem Auslieferungs-, Sammel-, Ver- oder Entsorgungsfahrten beginnen und enden. Es wird gekennzeichnet durch den Knoten 0. Jedes weitere Depot wird mit 0', 0'', 0''' usw. benannt.
- Die Kunden werden ebenfalls als Knoten dargestellt und von 1...n nummeriert.
- Jedem Kunden i wird ein Bedarf bi des zu liefernden oder abzuholenden Gutes zugewiesen. Dieser Bedarf wird in Mengeneinheiten (ME) angegeben. Diese Zuweisung wird in der Literatur auch Knotengewicht bzw. Knotenbewertung genannt.

Zusätzlich ist es möglich Servicezeiten szi als Knotengewicht zu definieren, falls nicht nur etwas geliefert werden soll, sondern auch beispielsweise eine Montage des gelieferten Gutes Bestandteil der Tour ist.

- Die Entfernung dij von Kunde i zu Kunde j wird als Kante zum Ausdruck gebracht und in km angegeben. Analog gilt die Entfernung d0j vom Depot 0 zum Kunden j, sowie di0 vom Kunden i zu Depot 0. Hierzu wird in der Regel eine symmetrische Distanzmatrix D = (dij) verwendet. Es handelt sich hierbei um das sogenannte Kantengewicht bzw. die Kantenbewertung.

Da es allerdings einen Unterschied macht, ob beispielsweise 100 km auf der Autobahn oder 100 km in der Innenstadt zurückgelegt werden müssen, wird oftmals die Fahrzeit tij vom Kunden i zu Kunden j als Kantengewicht genutzt. Diese Fahrzeit tij wird aus dem Produkt der Entfernung dij und der reziproken Durchschnittsgeschwindigkeit auf der Strecke αij gebildet. Die Standzeit ti beim Kunden i ist ebenfalls Bestandteil der Fahrzeit und wird dazugerechnet.

Weitere mögliche Kantengewichte sind beispielsweise Kosten kij, die bei Nutzung der Strecke anfallen.

- Die Anzahl der Fahrzeuge k, die an einem Depot stationiert sind, haben die Kapazität c zur Verfügung, um die jeweiligen Knotengewichte abzudecken.
- Eine Tour wird beschrieben durch die Angabe der Menge der Kunden, die auf einer in einem Depot beginnenden und in einem Depot endenden Fahrt bedient werden. Dabei darf die maximal zulässige Tourdauer TD nicht überschritten werden.
- Die Route zeigt an, in welcher Reihenfolge die Kunden in einer Tour bedient werden.
- Damit eine Tourenplanung erfolgreich durchgeführt werden kann, müssen unter Umständen mehrere Restriktionen beachtet werden. Restriktionen bedeuten, dass bestimmte Einschränkungen bei der Planung beachtet werden müssen. Dazu gehören beispielsweise Kapazitätsrestriktionen der Fahrzeuge, also die maximal mögliche Ladungsmenge oder Zeitrestriktionen, wie gesetzliche Beschränkungen der Lenk- und Ruhezeiten. Diese Restriktionen sorgen für eine Vielfalt an unterschiedlichen Ausprägungen des Tourenplanungsproblems und werden deshalb im Kapitel 2.4 ausführlich behandelt.
- Das Ergebnis der Tourenplanung ist der Tourenplan. Dieser ist eine zulässige Lösung eines Tourenplanungsproblems und definiert eine Menge von Touren mit der Eigenschaft, dass jeder Kunde auf genau einer Tour bedient wird und keine Restriktionen verletzt werden.

2.3 Standardproblem der Tourenplanung

Das Standardproblem der Tourenplanung ist eine Grundform des Vehicle Routing Problems (VRP) und unterscheidet sich in seiner Definition nur geringfügig vom bereits erwähnten Auslieferungsproblem im Kapitel 2.1.^[21] Mithilfe der im Kapitel 2.2 eingeführten Begriffe und Definitionen, lässt sich dieses wie folgt beschreiben:^[22]

Innerhalb einer Periode sind n Kunden von einem Depot aus zu bedienen. Der Standort des Depots, sowie die Anzahl, Nachfragemenge und Standorte der Kunden sind bekannt. Die kürzesten Entfernungen zwischen den Kunden sowie zwischen dem Depot und den Kunden sind ebenfalls bekannt und durch die symmetrische Distanzmatrix D = (dij) mit i, j = 0, 1, ..., n gegeben. Zur Bedienung der Kunden steht eine beliebig große, homogene Flotte an Fahrzeugen k mit der Ladekapazität c zur Verfügung. Die Fahrzeuge sind alle an einem Depot stationiert, an welchem jede Tour beginnt und endet. Für die Kunden i =1, ..., 0 gilt:

- Der Bedarf des Kunden i beträgt in der Periode bi Mengeneinheiten.
- Der Bedarf bi jedes Kunden ist durch eine Bedienung komplett zu decken, d.h. Teillieferungen werden ausgeschlossen.
- Die Fahrzeuge unterliegen Kapazitätsrestriktionen, nach welchen sie die maximale Fahrzeugkapazität c nicht überschreiten dürfen.
- Die erforderliche Fahrzeit für eine Route darf die maximal zulässige Tourdauer TD nicht überschreiten. Als Vereinfachung wird die Fahrzeit proportional zur zurückgelegten Entfernung angenommen.

Auf der nächsten Seite zeigt die Abbildung 4 ein Beispiel des Standardproblems der Tourenplanung. In blau sind die Knotengewichte, also die Bedarfe bi der Kunden gekennzeichnet und in grün werden die Kantengewichte, d.h. die Entfernungen dij dargestellt. Die dazugehörige Distanzmatrix D = (dij) ist in der Tabelle 1 abgebildet.

Tabelle 1: Symmetrische Entfernungsmatrix D für das Beispiel des Standardproblems der Tourenplanung mit fünf Kunden

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Beispiel für das Standardproblem der Tourenplanung mit fünf Kunden und zwei Touren

Da bei dieser Grundform des VRPs ein homogener Fuhrpark als Vereinfachung angenommen wird, wird das Problem auch als Capacitated Vehicle Routing Problem bezeichnet (CVRP).^[23] Im Folgenden wird das CVRP synonym für das Standardproblem der Tourenplanung verwendet.

2.4 Restriktionen in der Tourenplanung und daraus abgeleitete Ausprägungen der Tourenplanungsproblematik

Die Tourenplanungsproblematik unterscheidet sich durch eine Vielzahl an unterschiedlichen in der Praxis auftretenden Restriktionen. Dadurch wird die optimale Lösung des Problems zusätzlich erschwert. Vor allem wenn es darum geht all diese Einschränkungen und Ausnahmen mathematisch in einem Algorithmus zu erfassen, werden schnell Grenzen erreicht. Eine starke Vereinfachung des Problems wiederum führt zu einem stark von der Praxis abweichenden Modell, welches im Zweifelsfall nicht zufriedenstellende Ergebnisse liefert. Aus diesem Grund werden im Kapitel 3 unterschiedliche Verfahren vorgestellt, die auf die Lösung eines Tourenplanungsproblems mit bestimmten Restriktionen spezialisiert sind, also auf unterschiedliche Ausprägungen des Problems.

Eine Vielzahl möglicher Restriktionen in der Tourenplanung ist in der Tabelle 2 zusammengefasst und unterstreicht nochmal die Komplexität dieser Problematik. In der Tabelle werden die am häufigsten in der Literatur auftretenden Restriktionen genannt. Eine vollständige Erfassung bei den vielen in der Praxis auftretenden und sich wandelnden Problemstellungen ist kaum möglich und für diese Arbeit auch nicht erforderlich. Die Restriktionen, zu welchen die speziellen Verfahren im Kapitel 3 erläutert werden, sind farblich gekennzeichnet.

Tabelle 2: Restriktionen in der Tourenplanung^[24]

Abbildung in dieser Leseprobe nicht enthalten

Im Folgenden werden die farblich hervorgehobenen Restriktionen näher erläutert und in den Kontext der Arbeit eingebettet:

- Depotrestriktionen

Depotrestriktionen befassen sich mit Möglichkeiten und Gegebenheiten des Depots. Hierzu zählt unter anderem die Möglichkeit Waren für Transporte zu lagern oder umzuschlagen. Je nach Warenart müssen hierzu gegebenenfalls spezielle Läger oder Be- und Entlademittel vorhanden sein. Beispielsweise ein Kühllager für gefrorene Lebensmittel oder Kräne zum Bewegen schwerer Lasten. Ebenso ist die Kapazität der Läger ein wichtiges Kriterium, da hierdurch ein gewisser Planungsspielraum für zukünftige Aufträge geschaffen werden kann.

Diese Arbeit befasst sich mit dem Kriterium Anzahl der Depots. In den meisten Fällen wird von einem Depot ausgegangen. Am Beispiel der Warendistribution würde das einem Lager entsprechen, das für ein bestimmtes Gebiet zuständig ist und die darin befindlichen Kunden beliefert. Die Eindepot-Tourenplanung ist ein in der Praxis häufig auftretender Fall und wird auch im Standardproblem der Tourenplanung, dem CVRP, so angenommen. Wird jedoch die Lösung eines Tourenplanungsproblems in einem vielgliedrigen Logistiksystem angestrebt, also mit mehreren Depots, die eine gleiche oder ähnliche Warenstruktur enthalten und für dieselben Gebiete zuständig sind, so sollten alle Möglichkeiten bezüglich der Belieferung in Betracht gezogen werden, um einen möglichst optimalen Tourenplan zu erstellen. In vielen Fällen wird jedoch aus Vereinfachungsgründen die Betrachtungsweise auf einzelne Depots reduziert. Das schränkt den vollen unternehmerischen Handlungsspielraum ein und entfernt die Lösung des Problems weiter vom Optimum,^[25] was unter Umständen großes Potenzial verschwendet. Daher erscheint die Betrachtung einer Mehrdepot-Tourenplanung oder des Multiple Depot Vehicle Routing Problem (MDVRP) als sinnvoll. Abbildung 5 veranschaulicht diese Problemstellung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Beispiel einer Mehrdept-Tourenplanung

- Zeit- bzw. Zeitfensterrestriktionen

Bei Zeit- bzw. Zeitfensterrestriktionen handelt es sich um Tätigkeiten, die innerhalb bestimmter Zeiten durchgeführt werden müssen. Dies können bestimmte Lieferzeiten sein, in denen der Kunde beliefert werden kann, Zeiten zu welchen einige Zonen oder Gebiete befahren werden dürfen oder Zeitfenster zu welchen bestimmte Güter Be- oder Entladen werden müssen, um den weiteren Zeitplan einzuhalten. Grundsätzlich geht es hierbei um das Zeitfenster als entscheidende Komponente und nicht um die Tätigkeit, die innerhalb dieser Zeit ausgeführt werden soll.

Hauptsächlich wird die Problematik in der Tourenplanung aber damit in Verbindung gebracht, dass Kunden in einem vorgegebenen Zeitfenster zu beliefern sind.^[26] Diese Arbeit befasst sich mit eben diesem Problem. Im vereinfachten Standardproblem der Tourenplanung werden solche Zeitfenster im Planungsprozess nicht eingebunden. Dort ist der Belieferungszeitpunkt frei, so dass die Kundenreihenfolge strikt nach der kürzesten Gesamtentfernung oder geringsten Fahrzeuganzahl festgelegt werden kann. Anders im Vehicle Routing Problem with Time Windows (VRPTW). Hier werden Zeitfenster für Kunden vorgegeben, wodurch selbst ein für die Gesamtentfernung ungünstiger Kunde zunächst beliefert werden muss, wenn es keine andere Möglichkeit aufgrund seines Zeitfensters gibt. Die Verletzung bzw. nicht Einhaltung eines Zeitfensters führt unmittelbar zu einer nicht zulässigen Lösung eines Tourenplans, weshalb in der Literatur auch oft von harten Zeitfenstern gesprochen wird. Abbildung 6 veranschaulicht die Problematik des VRPTW.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: Zeitliche Darstellung einer Tour und der Problematik im VRPTW^[27]

Anhand der Abbildung wird ersichtlich, dass eine Tour nicht immer so geplant werden kann, dass das Fahrzeug bzw. der Fahrer durchgängig effektiv im Einsatz ist. Beim Kunden 2 ist eine Wartezeit bis zum Beginn des Zeitfensters notwendig, da anderenfalls Kunde 3 aus Zeitgründen nicht mehr in der Tour beliefert werden kann. Andererseits soll die zurückgelegte Gesamtentfernung möglichst minimal gehalten werden und die Fahrzeugauslastung möglichst maximal sein. Beides sind Gründe, warum spezielle Algorithmen für diese Problematik benötigt werden.

- Auftragsrestriktionen

Bei den Auftragsrestriktionen handelt es sich um mögliche Einschränkungen oder Kundenwünsche bezogen auf den Auftrag bzw. die Bestellung des Kunden. Wichtig ist hierbei, dass die Kapazitätsgrenzen beachtet werden, d.h. ob der Auftrag mit den zur Verfügung stehenden Mitteln und Personal überhaupt angenommen werden kann und ob er aus zeitlicher Sicht nicht bereits mit anderen Aufträgen kollidiert. Des Weiteren ist die Warenart zu beachten und zu überprüfen, ob sich z.B. qualifiziertes Personal im Unternehmen befindet, um Gefahrgüter zu transportieren und ob diese Güter mit anderen Gütern in einer Tour zusammen transportiert werden dürfen.

Entscheidend für diese Arbeit ist die Fragestellung, ob es sich um deterministische oder stochastische Aufträge handelt. Bei deterministischen Aufträgen ist der Auftrag zum Zeitpunkt der Planung in allen seinen Ausprägungen bekannt.^[28] Das bedeutet Lieferorte und Liefermengen stehen bereits vor Planungsbeginn fest und ein Tourenplan kann fertiggestellt werden. Ist ein Tourenplan für eine Periode erstellt, so können neue Informationen oder Änderungen nicht mehr berücksichtigt werden. Diese Vereinfachung wird im CVRP angenommen und als statisch bezeichnet. Das CVRP beschäftigt sich demnach nur mit statischen Kunden. In der Praxis treten jedoch nicht selten Auftragsänderungen, also Änderungen der Liefermenge, des gewünschten Belieferungszeitpunktes, Stornierungen der Bestellung usw. auf. Noch häufiger kommt es zu kurzfristigen Auftragseingängen, die eine schnelle und flexible Anpassung des bereits erstellten Tourenplans benötigen. In diesem Fall handelt es sich um stochastische Aufträge bzw. Kunden. Das bedeutet zum Zeitpunkt der Planung liegen keine oder nur ein Teil der benötigten Informationen über Lieferorte, Liefermengen usw. vor, um eine Tour zu planen. In diesem Fall wird nur ein vorläufiger Plan aus den bekannten Informationen erstellt, der bei Bekanntwerden neuer Informationen aktualisiert wird. Diese Aktualisierung wird auch Planungslauf oder rollierende Planung genannt, so dass der gesamte Planungszeitraum aus einer Folge von Planungsläufen besteht. Somit wird nicht notwendigerweise gleich eine gesamte Tour für jedes Fahrzeug geplant, sondern unter Umständen einzelne Auftrag-Fahrzeug-Zuordnungen.^[29] Auftragseingang und Auftragsabarbeitung findet simultan statt, wobei unter Auftrag auch Kunde verstanden werden kann. Die in dieser Arbeit später vorgestellten Verfahren behandeln genau diesen Fall des zufälligen sukzessiven Auftragseingangs, da dieser in der Praxis die höchste Relevanz besitzt.^[30] Abbildung 7 veranschaulicht den Auftragsbestand im statischen und dynamischen Fall über der Zeit.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Entwicklung des Auftragsbestandes über der Zeit im CVRP und DVRP^[31]

Bei solch einer Problemstellung handelt es sich um eine dynamische Tourenplanung, auch Dynamic Vehicle Routing Problem (DVRP) genannt. Einer der ersten Autoren, der sich mit der dynamischen Tourenplanung beschäftigt hat und weitere Unterschiede zum statischen Fall erläutert, ist Psaraftis.^[32] Weitere Unterschiede formuliert Richter in seiner Dissertation.^[33] Ein Tourenplanungsproblem wird bereits als dynamisches Problem angesehen, sobald es sowohl statische als auch stochastische Kunden enthält. Zur Lösung derartiger Problemstellungen können prinzipiell die Verfahren aus dem statischen Problemfeld genutzt werden. Sie müssen lediglich um Verfahren bzw. Strategien erweitert werden, wie mit stochastischen Kunden umzugehen ist.

Da die dynamische Tourenplanung ein sehr breit gefächertes Themengebiet ist, erfolgt im Kapitel 3.4 eine genauere Beschreibung und vor allem engere Eingrenzung der Problematik in den Rahmen dieser Arbeit.

Abbildung 8 zeigt zusammenfassend die im Rahmen dieser Arbeit relevanten Merkmale, in welchen sich das Standardproblem der Tourenplanung von anderen Ausprägungen unterscheidet und zu welchem Restriktionsbereich diese gehören. Im weiteren Verlauf der Arbeit werden Verfahren für das Standardproblem der Tourenplanung, das CVRP vorgestellt, sowie für das DVRP, MDVRP und das VRPTW.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Ausprägungen der Tourenplanungsproblematik im Rahmen dieser Arbeit mit dem dazugehörigen Restriktionsbereich

Aufgrund der Vielzahl an zu beachtenden Restriktionen und Ausprägungen werden häufig zur besseren Einordnung von Tourenplanungsproblemen Klassifizierungsschemata verwendet. Diese liefern keine detaillierten Information über das jeweilige Problem, stellen aber einen groben Rahmen auf, in welchem sich das Problem bewegt. Diese Schemata sind beliebig erweiterbar und anpassbar. Abbildung 9 zeigt ein solches Schema nach Stumpf am Beispiel des Standardproblems der Tourenplanung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 9: Beispiel eines Klassifizierungsschemas nach Stumpf^[34]

2.5 Kombinatorische Optimierungsproblematik in der Tourenplanung

Tourenplanungsprobleme gehören zur Klasse der NP-schweren Probleme in der Komplexitätstheorie. Anders als bei P-Problemen, die mit polynomial ansteigender Zeit lösbar sind, nimmt der Rechenaufwand der NP-schweren Probleme bei steigender Problemgröße, z.B. steigender Kundenanzahl, im ungünstigsten Fall exponentiell zu.^[35] Unter der Annahme, dass die Ausführung eines Rechenschrittes eine Mikrosekunde benötigt, haben die Autoren Gary und Johnson den Zeitaufwand angegeben, den Algorithmen für polynomiale und exponentielle Probleme mit unterschiedlichen Problemgrößen n benötigen, um eine optimale Lösung zu berechnen. Die Rechenzeiten sind in Tabelle 3 zusammengefasst.

Tabelle 3: Laufzeitverhalten von Algorithmen in Abhängigkeit vom Rechenaufwand und von der Größe des Problems n^[36]

Abbildung in dieser Leseprobe nicht enthalten

Anhand der Tabelle wird ersichtlich, dass bei NP-schweren Tourenplanungsproblemen, aufgrund des exponentiell wachsenden Rechenaufwandes, die Berechnung einer exakten Lösung innerhalb eines vertretbaren Zeitrahmens nicht realisierbar ist. Zumal die Problemgröße n in der dargestellten Tabelle maximal 100 beträgt, wohingegen in der Praxis durchaus Fälle mit mehreren Hundert Kunden auftreten können. Aus diesem Grund werden für derartige Problemstellungen sogenannte heuristische Verfahren eingesetzt.^[37]

Eine Klassifizierung möglicher Verfahren und Einordnung der heuristischen Verfahren nach Streim ist in Abbildung 10 dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 10: Klassifizierung der Lösungsverfahren nach Streim^[38]

Nach dieser Klassifizierung ist zu erkennen, dass die heuristischen Verfahren zwar potenzielle Lösungen vernachlässigen, dies aber nicht willkürlich machen. Sie gehen dabei nach bestimmten Regeln vor. Dennoch bieten sie keine Garantie dafür, dass eine optimale Lösung für das Problem gefunden wird. Anders die Verfahren der vollständigen Enumeration, die nachweisbar die optimale Lösung berechnen können.

Im Folgenden werden die exakten und heuristischen Verfahren detaillierter betrachtet. Zusätzlich werden einige Metaheuristiken vorgestellt, die in der Tourenplanung immer mehr an Bedeutung gewinnen und in den später betrachteten Verfahren Anwendung finden.

2.5.1 Exakte Verfahren

Unter exakten Verfahren werden diejenigen Verfahren verstanden, die keine potenziellen Lösungen vernachlässigen und nachweislich die optimale Lösung berechnen. Nach der Klassifizierung von Streim sind das Verfahren der vollständigen Enumeration.

Den einfachsten Ansatz für ein exaktes Verfahren stellt die vollständige Enumeration dar. Dieses Verfahren löst das Optimierungsproblem, indem es den gesamten Lösungsraum durchsucht, alle möglichen Lösungen erzeugt und diese bewertet. Anhand der Bewertungen wird anschließend die beste Lösung ausgewählt.^[39]

Ein weiteres häufig eingesetztes Verfahren ist das Branch and Bound Verfahren. Dieses hat gegenüber dem einfachen Ansatz der vollständigen Enumeration den Vorteil, dass es nicht den gesamten Lösungsraum durchsucht, sondern systematisch Teile eines Lösungsraumes ausschließt, in denen das Optimum mit Sicherheit nicht gefunden werden kann.^[40] Hierzu wird der Lösungsraum in Form eines Entscheidungsbaumes, oder auch Enumerationsbaumes, organisiert. Begonnen wird mit der Zerlegung des gesamtem Problems in Teilprobleme, also des gesamten Lösungsraumes in Teillösungsräume. Die Bedingungen hierfür sind, dass jeder Teillösungsraum kleiner als der ursprüngliche Lösungsraum ist, dass möglichst wenig Überschneidungen zwischen den neu erzeugten Teillösungsräumen entstehen und dass die Vereinigung aller Teillösungsräume den ursprünglichen Lösungsraum des zerlegten Problems ergibt. Zu den Teillösungsräumen werden zwei Schranken berechnet und miteinander verglichen. Als untere Schranke (Lower Bound) wird der Weg von der Wurzel des Baumes zu einem Teillösungsraum genannt. Die obere Schranke (Upper Bound) dient als eine vorerst optimale zulässige Lösung des gesamten Lösungsraumes. Übersteigt nun die untere Schranke die obere Schranke, so kann dieser aktuell betrachtete Teillösungsraum ausgeschlossen werden, da es bereits mindestens eine bessere Lösung gibt. Wird allerdings eine Lösung des Problems gefunden, die unterhalb der oberen Schranke liegt, dann wird diese zur neuen oberen Schranke und gilt als Referenz für weitere Berechnungen.^[41]

Die exakten Verfahren führen zwar immer zu einer optimalen Lösung des Problems, finden aber aufgrund der langen Rechenzeiten in der Praxis kaum Anwendung. Der rapide ansteigende Zeitbedarf zur Berechnung optimaler Lösungen bei komplexen Optimierungsproblemen wurde bereits in Kapitel 2.5 erläutert. In Abbildung 11 wird der direkte Vergleich zwischen exakten Verfahren und problemspezifischen Heuristiken anhand eines praktischen Falls dargestellt. Die Ergebnisse beruhen auf der Analyse des technischen Kundendienstes des Unternehmens Miele & Cie. KG. Näheres zu der Problemstellung und den einzelnen Daten kann bei Lasch und Janker nachgelesen werden.^[42]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 11: Vergleich zwischen heuristischen und exakten Tourenplanungsverfahren am Beispiel des technischen Kundendienstes des Unternehmens Miele & Cie. KG^[43]

Dargestellt werden die Einsparungen in km, die aufgrund der Berechnungen für das Unternehmen realisierbar wären. Das exakte Verfahren weist nur eine um 2,4 % bessere Lösung als die problemspezifische Heuristik auf. Allerdings wird dafür eine Rechenzeit von über 18 Stunden benötigt, während die Heuristik bereits nach einer Sekunde eine Lösung anbietet. Aber die Heuristik bietet selbst nach einer Laufzeit von 1,4 Minuten keine signifikant bessere Lösung an, als nach einer Sekunde. Das Potenzial dieser verwendeten Heuristik ist somit nahezu ausgeschöpft. Es müsste demnach getestet werden, ob andere Heuristiken bessere Ergebnisse erzielen können. Dennoch wird anhand dieses praktischen Beispiels der deutlich geringere Zeitbedarf von Heuristiken bei nahezu gleichbleibendem Ergebnis nochmals bestätigt, was vor allem in der Praxis besonders wichtig ist.^[44]

2.5.2 Problemspezifische Heuristiken und dazugehörige Operatoren

Problemspezifische Heuristiken sind Verfahren, die ein Optimierungsproblem mithilfe problemspezifischer Regeln innerhalb kurzer Rechenzeiten suboptimal lösen. Das bedeutet sie bieten selbst bei langen Laufzeiten keine Garantie dafür, dass eine optimale Lösung gefunden wird, kommen aber in die Nähe des Optimums.^[45] Diese Aussage wurde bereits in Abbildung 11 bestätigt.

Die problemspezifischen Heuristiken lassen sich in Eröffnungs- bzw. Konstruktionsverfahren und Verbesserungsverfahren einteilen. Die Verfahren müssen sich mit zwei Teilproblemen auseinandersetzen:^[46]

- Dem Zuordnungs- oder Gruppierungsproblem: Jeder Kunde ist genau einer Tour zuzuordnen (Clustering) und
- dem Routing- oder Reihenfolgeproblem: Für jeden Kunden ist die Bedienreihenfolge innerhalb jeder Tour festzulegen (Routing).

Je nachdem, ob diese Teilprobleme sequentiell oder simultan gelöst werden, unterteilt Domschke die Verfahren weiterhin nach Sukzessiv- oder Parallelverfahren, wie in Tabelle 4 dargestellt.

Tabelle 4: Eingliederung heuristischer Verfahren für Tourenplanungsprobleme nach Domschke ^[47]

Abbildung in dieser Leseprobe nicht enthalten

Da in dieser Arbeit nur Verfahren für knotenorientierte Problemstellungen vorgestellt werden, ist in der Tabelle 4 gekennzeichnet, welche Kombinationen aus Konstruktions- und Verbesserungsverfahren sich besonders für derartige Problemstellungen eignen.

Im Folgenden werden die Konstruktions- und Verbesserungsverfahren näher erläutert. Konstruktions- bzw. Eröffnungsverfahren dienen zur Erstellung einer ersten zulässigen Lösung eines Optimierungsproblems.^[48] Sie folgen in jedem Konstruktionsschritt einer definierten Regel bzw. einem Verfahren. Ein typisches Beispiel für solch ein Verfahren ist der Greedy Algorithmus. Dieser wählt als Auswahlkriterium für jeden Konstruktionsschritt die Änderungsalternative aus, die die größte Vorteilhaftigkeit bezüglich des Optimierungsziels aufweist. Das bedeutet, es wird aus mehreren potenziellen Fahrzielen jenes ausgewählt, welches die geringste Entfernung aufweist. In der Regel führen solche Greedy Verfahren allerdings zu relativ schlechten Lösungen.^[49]

Weitere bekannte und stark verbreitete Konstruktionsheuristiken sind die nach Domschke eingeteilten Sukzessivverfahren, die nach dem Cluster First - Route Second oder Route First - Cluster Second Verfahren arbeiten. Die Vorgehensweise des ersten Verfahrens ist zur Veranschaulichung in Abbildung 12 skizziert. Die Vorgehensweise beim zweiten Verfahren ist analog und unterscheidet sich nur in der Reihenfolge.

[...]

---

^[1] vgl. [Gün10 S. 9]

^[2] vgl. [Bau01 S. 10 f.]

^[3] vgl. [Sta10 S. 712]

^[4] vgl. [Sta10 S. 37]

^[5] vgl. [Dep10 S. 3 ff.]

^[6] vgl. [Sch09 S. 7 ff.], [Arn08 S. 122] und [Ste09 S. 4]

^[7] vgl. [Log10 S. 8]

^[8] vgl. [Sch10 S. 683]

^[9] vgl. [Log10 S. 44]

^[10] vgl. [Dhl10]

^[11] vgl. [Dbe10]

^[12] [Hei02 S. 292]

^[13] vgl. [Log10 S. 26 f.]

^[14] vgl. [Afi08 S. 519]

^[15] vgl. [Dom10 S. 197 ff.] und [Vah05 S. 450]

^[16] vgl. [Vah05 S. 450]

^[17] [Vah05 S. 448]

^[18] in Anlehnung an [Vah05 S. 448]

^[19] vgl. [Vah05 S. 451]

^[20] vgl. [Dom10 S. 198 ff.], [Ebe87 S. 19 ff.], [Hei02 S. 293], [Vah05 S. 451 ff.] und [Vah07 S. 275 ff.]

^[21] vgl. [Ohr07 S. 14]

^[22] vgl. [Vah05 S. 452 f.], [Vah07 S. 275 ff.] und [Wen10 S. 41 ff.]

^[23] vgl. [Ohr07 S. 14] und [Wen10 S. 41]

^[24] vgl. [Sch09 S. 217 f.], [Ebe87 S. 6 ff.] und [Hei02 S. 294 f.]

^[25] vgl. [Ebe87 S. 2]

^[26] vgl. [Ohr07 S. 16 f.]

^[27] in Anlehnung an [Bay08 S. 47]

^[28] vgl. [Ebe87 S. 9]

^[29] vgl. [San04 S. 9] und [Ric05 S. 65]

^[30] vgl. [Kry09 S. 31]

^[31] vgl. [San04 S. 11]

^[32] vgl. [Psa88 S. 233 ff.]

^[33] vgl. [Ric05 S. 55 ff.]

^[34] vgl. [Stu98]

^[35] vgl. [Ric05 S. 88 ff.], [Vah05 S. 453] und [Med00 S. 40 ff.]

^[36] vgl. [Vog98]

^[37] vgl. [Ric05 S. 30] und [Vah05 S. 453]

^[38] vgl. [Str75 S. 143 ff.]

^[39] vgl. [Str07 S. 23]

^[40] vgl. [Kat08 S. 152 f.]

^[41] vgl. [Str07 S. 23 f.] und [Afi08 S. 50 ff.]

^[42] vgl. [Las05 S. 321 ff.]

^[43] vgl. [Las05 S. 330]

^[44] vgl. [Vah05 S. 453] und [Dom10 S. 226]

^[45] vgl. [Str07 S. 24] und [Vog98]

^[46] vgl. [Vah05 S. 453] und

^[47] in Anlehnung an [Dom10 S. 226 ff.]

^[48] vgl. [Bay08 S. 23]

^[49] vgl. [Str07 S. 24]

• Hochschule: Beuth Hochschule für Technik Berlin
• Note: 1,0
• Autor: David Schipior (Autor:in)
• Erscheinungsjahr: 2011
• Seiten: 99
• Katalognummer: V202277
• ISBN (eBook): 9783656308546
• ISBN (Buch): 9783656309598
• Sprache: Deutsch
• Schlagworte: Tourenplanung, Heuristik, dynamische Tourenplanung, Tabu Search, Sweep, Savings, Metaheuristik