Tourenplanung und Stauraumoptimierung. Optimierungsansätze und Software zur Kostensenkung

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

1 Einleitung
1.1 Problemstellung
1.2 Zielsetzung der Arbeit
1.3 Aufbau der Arbeit

2 Grundlagen der Tourenplanung
2.1 Standardproblem
2.2 Restriktionen
2.2.1 Fahrzeugbedingte Restriktionen
2.2.2 Zeitrestriktionen
2.2.3 Liefergebietsindividuelle Restriktionen
2.2.4 Kundenrestriktionen
2.2.5 Auftragsbezogene Restriktionen
2.3 Lösung von Tourenplanungsproblemen
2.3.1 Exakte Verfahren
2.3.2 Heuristische Verfahren
2.3.3 Metaheuristiken

3 Grundlagen der Stauraumoptimierung
3.1 Das dreidimensionale Standardproblem
3.2 Restriktionen
3.3 Lösung von Stauraumoptimierungsproblemen
3.3.1 Exakte Verfahren
3.3.2 Heuristische Verfahren
3.3.3 Metaheuristiken

4 Computergestützte Lösungen der Tourenplanung und Stauraumoptimierung
4.1 Computergestützte Tourenplanungssysteme
4.1.1 Funktionen
4.1.2 Vor- und Nachteile des Einsatzes von Tourenplanungssystemen . .
4.1.3 Lösung praxisrelevanter Probleme
4.1.4 Aktuelle Marktübersicht
4.2 Computergestützte Stauraumoptimierung
4.2.1 Einsatzmöglichkeiten von Stauraumoptimierungssoftware
4.2.2 Lösung praxisrelevanter Probleme
4.3 Integrierte Systeme

5 Möglichkeiten zur Kostensenkung mittels Tourenplanung- und Stauraumop- timierung

6 Fazit

Literatur

Abbildungsverzeichnis

2.1 Veranschaulichung des Unterschieds zwischen dem TSP und dem CPP

2.2 Beispiel für eine Tour ohne (oben) und mit (unten) Zeitfenster

2.3 Branch-and-Bound-Baum

2.4 B&B-Baum mit Bounding

2.5 Anwendung des Sweep-Verfahrens auf ein einfaches Problem

2.6 Vereinigung zweier Touren

2.7 Kantenersetzung im 2-opt-Verfahren

2.8 Beispielhafte Ausführung eines 3-opt-Verfahrens

2.9 Nachbarschaftssuchmethode bei dem Tabu-Search-Verfahren

3.1 Schematische Darstellung des Wall-Building Approach

3.2 Schematische Darstellung des Column-Building Approach

3.3 Ablauf der Placement-Heuristik von Bischoff und Ratcliff (1995)

3.4 Mögliche Anordnungen der Packstü>2-Block-Anordnung (rechts)

3.5 Beispielhafte Packstückanordnung nach dem Algorithmus von Bischof- f/Janetz/Ratcliff

3.6 Stauplan mit einer Schichtstruktur (von oben betrachtet)

3.7 Erzeugung von Tochter-Resträumen

3.8 Mögliche Lagen zweier Kisten

4.1 Die Benutzeroberfläche einer Tourenplanungssoftware (PTV Smartour)

4.2 Komponenten eines Tourenplanungssystems

4.3 Behandelbare Problemgrößen

4.4 Unterstützte Fahrzeugtypen in einem heterogenen Fuhrpark

4.5 Behandlung relevanter Fahrzeugrestriktionen

4.6 Mögliche Kapazitätsrestriktionen

4.7 Zeitfensterrestriktionen

4.8 Kostenarten

4.9 Anwender von Tourenplanungssystemen nach Branche

4.10 Oberfläche der Stauraumoptimierungssoftware MultiMix

5.1 Anteil der Transportkosten an den gesamten Logistikkosten

5.2 Kosten von Tourenplanungssystemen

5.3 Angebotene Lizenzmodelle

Tabellenverzeichnis

2.1 Klassifizierung der Restriktionen und Beispiele

4.1 Die wesentlichen Funktionen von Tourenplanungssystemen

5.1 Beispiele für Kostenreduzierungsmöglichkeiten mittels Tourenplanungop- timierung

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Kurzfassung

Die vorliegende Bachelorarbeit behandelt die Möglichkeiten für Kostenoptimierung von Transportprozessen, die sich aus der Anwendung von Tourenplanung und Stau- raumoptimierung ergeben. Es wird zunächst ein Überblick über die Grundlagen dieser zwei Themengebiete gegeben. Es werden die allgemeinen Problemstellungen, die für die Praxis relevanten Restriktionen sowie einige wichtige Lösungsverfahren beschrie- ben. Im Anschluss wird der Einsatz softwarebasierter Lösungen erläutert und es wird ausgeführt, inwiefern diese eine Kostensenkung erwirken können.

Abstract

The following Bachelor’s thesis deals with option for cost optimisation in transportation processes that arise from the application of tour planning and storage optimisation. First, an overview over the basics of these two fields is given. The general formulations of the problems and relevant restrictions for practical applications as well as some important solutions are described. Subsequently, the use of software-based solutions are discussed and it is explained how these can lead to a reduction of transport related costs.

1. Einleitung

Die Aufgabe der Distributionslogistik besteht darin, bestimmte Arten und Mengen von Waren den Kunden zur Verfügung zu stellen. Ein wichtiger Bestandteil dieses Prozesses ist der Warentransport entweder zwischen Lagern oder direkt zum Kunden.¹ Dabei gewinnt der Straßengüterverkehr in der Bundesrepublik Deutschland immer mehr an Bedeutung, was zum einen an der zentralen Lage und zum anderen an dem auf Export ausgerichteten Wirtschaftssystem liegt.²

Dabei treten jedoch zwei wichtige Punkte auf, die in dem Kontext thematisiert werden müssen. Einerseits sollen die aus Transportprozessen resultierenden Abgasemissionen aufgrund der Gefahr des anthropogenen Klimawandels reduziert werden. Andererseits soll der Güterverkehr den gesteigerten Anforderungen, die sich aus der wirtschaftlichen Entwicklung und der Globalisierung ergeben, gerecht werden. Laut Prognosen können beide Probleme mit den aktuell verfügbaren Möglichkeiten nicht vollständig adressiert werden. Der emissionsärmere Schienenverkehr wird infolge begrenzter Optionen für den Infrastrukturausbau bis 2050 nicht zum Hauptträger des Güterverkehrs werden können. Demgegenüber bietet der Straßenverkehr mit Lkw zwar eine höhere Flexibilität und mehr Entwicklungspotenzial, er stellt sich jedoch für die steigenden Warenmengen und Transportweiten als nicht angemessen heraus.³

Es ist darüber hinaus mit einer Erhöhung straßenverkehrsbezogener Kosten zu rech- nen. Insbesondere die steigenden Energiepreise stellen für die Transportlogistik ein Problem dar, da der Warentransport mit einem hohen Energieverbrauch verbunden ist. Im Jahr 2015 hatte die BRD einen Gesamtverbrauch von ca. 9060PJ, an dem der Verkehr einen Anteil von 28 % hatte. Obwohl die technische Entwicklung des Straßen- güterverkehrs zu immer kleineren Verbrauchswerten führt, besteht hier weiterhin noch Optimierungsbedarf.⁴

Möglichkeiten, die Steigerung transportbezogener Kosten unter Kontrolle zu halten bzw. die weitere Erhöhung der Abgasemissionen zu vermeiden, bestehen dabei nicht nur in der weiteren technischen Entwicklung (Green Logistics, Elektrofahrzeuge), son- dern auch in der Optimierung der Transportprozesse. Zwei wichtige Methoden, die dabei behilflich sein können, sind die Tourenplanung und die Stauraumoptimierung.

1.1 Problemstellung

Das Ziel der Tourenplanung ist es, die verfügbaren Transportmittel (Lkw, Pkw, Schiffe, Züge usw.) derart auf die gegebenen Zielorte zu verteilen, dass der Transportprozess nicht nur effizienter, sondern auch kostengünstiger abläuft. Somit stellt sie ein wich- tiges Werkzeug zur Kostenoptimierung für Unternehmen dar, die im Bereich der Dis- tributionslogistik tätig sind. In der Theorie existiert für das Problem eine Vielzahl von Lösungsverfahren, die teilweise für die Lösung verwandter Probleme, wie beispielswei- se das Travelling Salesman-Problem (TSP) entwickelt wurden, sodass eine Erstellung kostenoptimierender Tourenpläne in der Regel in diesem Zusammenhang kein Pro- blem darstellt.

In der Praxis können jedoch zahlreiche Besonderheiten und Anforderungen auftreten, welche die Lösung des Problems erschweren. Darüber hinaus gibt es eine Reihe von Ein- flussgrößen, die dazu führen, dass die tatsächlich gefahrenen von den idealen Touren abweichen. Ein weiteres Problem resultiert oft aus der Unkenntnis relevanter Informa- tionen bzw. dem Auftreten unbekannter oder unveränderbarer Variablen. Oft sind auch aktualisierte Informationen erst während der Durchführung einer Tour bekannt, sodass diese in Echtzeit verarbeitet werden müssen. All diese Probleme, die aus praktischen Anwendungsfällen resultieren, lassen sich mithilfe von sog. Tourenplanungssystemen umgehen. So werden computergestützte Systeme bezeichnet, die in der Lage sind, pra- xisbezogen zu arbeiten.

Der Einsatz von Tourenplanung lässt sich weiterhin mit einer Optimierung der verfüg- baren Laderäume in Containern oder den verwendeten Transportmitteln verbinden. Oft können Transportprozesse weiter optimiert werden, indem nicht nur die Eintei- lung der Fahrzeuge in Touren, sondern auch die Art der Verteilung von Waren auf die Fahrzeuge berücksichtigt werden. Damit wird eine bessere Ausnutzung der Stauräume erreicht, woraus weitere Optimierungspotenziale resultieren. Beispielsweise lässt sich unter Umständen die Anzahl der benötigten Touren reduzieren, indem die Stauraum- optimierung so erfolgt, dass für die Warenauslieferung weniger Fahrzeuge erforderlich sind. Auch hierfür existieren zahlreiche Softwarelösungen, die in der Praxis zum Einsatz kommen.

Eine Hürde, besonders für kleine und mittelständische Unternehmen, stellt zumeist die Höhe der Anschaffungskosten einer entsprechenden Software dar. Daher muss vor der Umstellung auf eine softwarebasierte Lösung zuerst die Frage untersucht werden, unter welchen Umständen sich diese überhaupt rentiert. Dafür muss sich das Unternehmen einen Überblick über die aktuellen Angebote auf dem Markt verschaffen. Die Optimie- rungspotenziale hängen jedoch auch von der Art der Unternehmenstätigkeit ab, d. h. davon, wie viele Kunden mit welcher Art von Waren bzw. Dienstleistungen bedient werden. Diese Faktoren müssen daher auch in den Entscheidungsprozess einfließen.

1.2 Zielsetzung der Arbeit

Die vorliegende Arbeit setzt sich mit der Aufgabe der Tourenplanung und der Stau- raumoptimierung auseinander. Dazu werden zunächst die Fragestellungen dieser zwei Probleme explizit erklärt und die wichtigsten Lösungsverfahren zur Berechnung von Touren- bzw. Stauplänen dargestellt. Dabei werden insbesondere auch die relevanten Restriktionen behandelt, die aus den Anforderungen der Praxis resultieren.

Darauf aufbauend werden im Anschluss die computergestützte Tourenplanung sowie Stauraumoptimierung ausgeführt. Dabei liegt der Schwerpunkt nicht auf der Beschrei- bung einzelner Software, sondern das Ziel ist, einen allgemeinen Überblick über die wichtigen Funktionalitäten und die Behandlung praxisrelevanter Anforderungen zu verschaffen. Für Tourenplanungssysteme wird auch eine aktuelle Marktübersicht an- hand der Studie des Fraunhofer-Instituts für Materialfluss und Logistik (IML) erläutert.

Der dritte Abschnitt dieser Arbeit umfasst die Möglichkeiten zur Kostenoptimierung, die aus der Anwendung solcher computergestützten Systeme resultieren. Es wird unter- sucht, ob bzw. wie eine Kostenoptimierung mithilfe der eingesetzten Software möglich ist und welche Einsparungen erzielt werden können.

1.3 Aufbau der Arbeit

In Kapitel 1 erfolgt zunächst eine kurze Einführung in die Problematik und eine Dar- stellung der Zielsetzung der vorliegenden Arbeit.

Die darauf folgenden Kapitel 2 und Kapitel 3 stellen kurz die Tourenplanung und die Stauraumoptimierung als Optimierungsprobleme dar. Dabei werden die grundlegen- den Problemstellungen sowie die wichtigsten Lösungsverfahren und -algorithmen für die zwei Aufgaben vorgestellt.

Kapitel 4 stellt die wichtigsten computergestützten Lösungen auf dem Markt vor. Da- bei handelt es sich in erster Linie um allgemeine Aussagen und weniger um spezielle Beispiele. Es werden die Funktionen, die Vor- und Nachteile des Einsatzes sowie die Merkmale der Lösungen praxisrelevanter Probleme diskutiert.

Kapitel 5 ist der Kostenoptimierung mithilfe der zuvor beschriebenen softwarebasierten Lösungen gewidmet. Ausgehend von den gängigen Kosten, die beim Warentransport anfallen, wird hervorgehoben, in welchen Bereichen und unter welchen Umständen mithilfe von Optimierungsmaßnahmen eine Kostenreduzierung erzielt werden kann.

Das letzte Kapitel 6 beschließt die Arbeit mit einer Zusammenfassung und einem Aus- blick.

2. Grundlagen der Tourenplanung

Mit einem Tourenplanungsproblem (Vehicle Routing Problem - VRP) wird im Allgemei- nen das Problem bezeichnet, bei dem eine Menge von Aufträgen durch eine Menge von Transportmitteln ausgeführt werden soll. Das bedeutet, eine bestimmte Anzahl von Kunden soll mithilfe der verfügbaren Fahrzeuge von einem oder mehreren Depots aus mit einem oder mehreren festgelegten Gütern beliefert werden. Mit Depot ist dabei der Ort gemeint, an dem alle Fahrten starten und enden und an dem die Sammlung oder Auslieferung der Sendung bzw. die Stationierung der Transportmittel stattfindet. Ziel ist die Bestimmung eines Tourenplans. Als Tourenplan wird die Menge aller Touren - diese beinhalten die Kunden, die durch ein Fahrzeug auf einer Fahrt bedient werden - und der zugehörigen Routen, d. h. die Reihenfolge, in der die Belieferung der Kunden innerhalb einer Tour erfolgt, bezeichnet.⁵

Zusätzlich liegen im Allgemeinen gewisse Anforderungen und Einschränkungen vor, die im Bereich der Tourenplanung als Restriktionen bezeichnet werden und die weite- re Bedingungen an die Lösung des Problems stellen. Diese können beispielsweise die Kapazitäten der Transportmittel oder die zeitbezogenen Vorgaben (z. B. Belieferungszeitfenster) betreffen.⁶

Bei der Tourenoptimierung handelt es sich um ein kombinatorisches Optimierungs- problem. Ziel ist die Bestimmung einer Lösung im obigen Sinne unter Beachtung aller Restriktionen derart, dass eine vorgegebene Zielfunktion, bspw. die Kostenfunktion oder die gesamte Fahrstrecke, minimiert wird.⁷

Die räumliche Struktur eines Tourenplanungsproblems lässt sich mithilfe eines Gra- phen veranschaulichen. Dabei kann zwischen knotenorientierten und kantenorien- tierten Problemstellungen differenziert werden. Diese Unterteilung resultiert aus der Verteilung der Kunden. Knotenorientierte Tourenprobleme gehen davon aus, dass sich die Kunden an diskreten, festen Punkten befinden. Bei kantenorientierten Problemen sind sie demgegenüber gleichmäßig über die zu ver- bzw. entsorgende Straße verteilt, z. B. ist dies bei Postverteilung oder Müllabholung der Fall. Beide Problemklassen lassen sich auf jeweils ein typisches Beispiel bzw. ein Spezialfall zurückführen: dem Travelling- Salesman-Problem (TSP) und dem Chinese-Postman-Problem (CPP).⁸ Abb. 2.1 veranschaulicht die Unterschiede.

Abbildung in dieser Leseprobe nicht enthalten

(a) Travelling-Salesman-Problem (b) Chinese-Postman-Problem

Abbildung 2.1: Veranschaulichung des Unterschieds zwischen TSP und dem CPP (Quelle: Kissling und Ziegler 2008, S. 19)

Bei dem TSP handelt es sich um ein reines Reihenfolgeproblem. Es wird auch Rundrei- seproblem oder Handlungsreisendenproblem genannt. Ein praktisches Beispiel kann beispielsweise so lauten:

„Ein Handlungsreisender möchte eine Anzahl von Kunden in verschiedenen Orten besuchen. Nach Abschluss der Besuche möchte er in seinen Ausgangs- ort zurückkehren. Welchen Weg soll er wählen (in welcher Reihenfolge soll er die Kunden besuchen), damit die dabei insgesamt zurückzulegende Entfernung so gering wie möglich ist?“⁹

Das TSP entspricht demnach einem Tourenplanungsproblem mit einem Depot, einem Fahrzeug und mehreren Kunden, die einmal beliefert werden, ohne weitere Restriktio- nen.

Analog dazu ist das CPP ein pures Reihenfolgeproblem¹⁰ und kann wie folgt skizziert werden:

„Ein Briefträger hat die Häuser eines Stadtteils mit Post zu beliefern. Da- bei muss er, um die Post zu verteilen, jede Straße einmal oder (bei breiten Straßen) zweimal durchlaufen. Darüber hinaus ist es aber unter Umstän- den erforderlich, Straßen erneut — ohne gleichzeitiges Verteilen von Post — zu begehen, um andere Gebiete des Stadtteils zu erreichen. Der Briefträger interessiert sich für einen geschlossenen Weg mit minimaler Länge (minima- len Kosten oder minimaler Zeitdauer), der jede zu bedienende Straße oder Straßenseite mindestens einmal enthält.“¹¹

Auch hier handelt es sich um ein Äquivalent eines Tourenplanungsproblems mit einem Fahrzeug, einem Depot und mehreren Kunden. Der Unterschied besteht lediglich in der Art der Kundenverteilung.

In der Tourenplanung ist in der Regel die Minimierung der Gesamtkosten als Hauptziel festgesetzt. Diese lassen sich in variable und fixe Kosten unterteilen. Erstere werden durch die Bereitstellung und Instandhaltung der Fahrzeuge sowie die Gehälter vom Personal bestimmt, während variable Kosten durch die Wahl der gefahrenen Strecken bedingt sind. Da diese Kostenarten jedoch nicht eindeutig definier- bzw. erfassbar sind und somit nicht als geeignetes Kriterium dienen können, erfolgt die Kostenminimie- rung in der Regel über andere Variable, wie

- die Minimierung der Anzahl der verwendeten Fahrzeuge,
- die Minimierung der Dauer der Fahrzeit oder
- die Minimierung der Länge der Fahrtstrecke.¹²

2.1 Standardproblem

Tourenplanungsprobleme, die in der Fachliteratur oder in der Praxis behandelt werden, weisen im Allgemeinen aufgrund der hohen Anzahl an Problemgrößen (Fahrzeuge, De- pots, Kunden, usw.) und Restriktionen ein hohes Maß an Komplexität auf. Der Klarheit halber ist es zweckmäßig, zunächst ein sog. Standardproblem der Tourenplanung zu betrachten, das im Prinzip eine vereinfachte Problemstellung mit einer kleinen Anzahl an Problemgrößen und Restriktionen darstellt.¹³

Ein Standardproblem der Tourenplanung lässt sich folgendermaßen definieren:¹⁴ In- nerhalb einer Periode sollen Kunden von einem Depot aus mit Gütern beliefert werden, wobei die Touren für jedes Fahrzeug einer Flotte ermittelt werden sollen. Das bedeu- tet, pro Fahrzeug wird jeweils eine Route berechnet, deren Start- und Endpunkt beide im Depot liegen. Jeder Kunde wird genau einmal besucht und sein Bedarf wird dabei vollständig befriedigt. Das Ziel besteht in der Minimierung der Gesamtkosten, das in der Regel über die Minimierung der gesamten Fahrstrecke erfolgt. Wird zusätzlich eine feste Ladungskapazität für die Transportmittel vorgegeben, so ist auch von einem ka- pazitierten Tourenplanungsproblem (Capacitated Vehicle Routing Problem - CVRP) die Rede.¹⁵

Die Aufgabe der Tourenplanung kann demzufolge in zwei Teilaufgaben aufgeteilt wer- den:¹⁶

- in „Clustering“, d. h. die Verteilung der Kunden auf Touren derart, dass jede Tour am Depot beginnt und endet, jeder Kunde genau einmal beliefert wird und die Kapazität der Fahrzeuge nicht überschritten wird,
- und in „Routing“, d. h. die Festlegung der Reihenfolge, in der die Kunden innerhalb einer Tour bedient werden.

2.2 Restriktionen

Der obige Abschnitt 2.1 verweist darauf, dass das Standardproblem der Tourenplanung (CVRP) zwei Restriktionen unterliegt. Die Erste betrifft die Kapazität der Fahrzeuge und die Zweite die zeitliche Einschränkung (Planungsperiode). Diese Problemstellung ist für die Praxis jedoch nicht von Interesse, da in realen Situationen im Allgemeinen mehr als nur diese zwei Restriktionen auftreten. Bei der „realen“ Tourenplanung müssen daher weitere, praxisbezogene Bedingungen berücksichtigt werden.¹⁷

In der Tabelle 2.1 wird eine Klassifikation der Restriktionen und dazugehörige Beispiele aufgezeigt.

Im Folgenden werden die wichtigsten Restriktionsklassen - die Kapazitäts-, Kunden-, Auftrags- und Zeitrestriktionen - näher erläutert.

Tabelle 2.1: Klassifizierung der Restriktionen und Beispiele (in Anlehnung an Novak 1999, S. 101f.)

Abbildung in dieser Leseprobe nicht enthalten

2.2.1 Fahrzeugbedingte Restriktionen

Der Planungsprozess der Zuordnung von Fahrzeugen zu den einzelnen Touren wird eingeschränkt, wenn zusätzliche Anforderungen und Bedingungen an die Fahrzeuge gestellt werden.

Die wichtigste Art von Restriktionen dieser Klasse ist die Kapazitätsrestriktion. Sie stellt eine Grenze an die Ladungskapazität der Fahrzeuge, sodass die Gesamtmenge der ge- lieferten Güter diese Grenze nicht überschreiten darf. Dadurch kann sich beispielswei- se die Anzahl der nötigen Fahrzeuge für die Ausführung eines Tourenplans erhöhen oder die Liefergüter müssen mit der gleichen Anzahl an Transportmitteln auf mehrere Touren verteilt werden, die entweder nacheinander oder parallel ausgeführt werden können.¹⁸

Darüber hinaus beeinflusst die Homogenität des Fuhrparks die Lösung eines Touren- planungsproblems. Die Fahrzeuge können entweder alle dieselbe Kapazität haben - in dem Fall handelt es sich um ein homogenes Problem - oder die Kapazitäten können sich unterscheiden (heterogenes Problem).

Des Weiteren müssen etwa Güterverträglichkeit - nicht alle Fahrzeuge sind für den Transport beliebiger Güter geeignet -, die Verfügbarkeit der Fahrzeuge oder Reparatur- zeiten bei der Planung der Touren berücksichtigt werden.

2.2.2 Zeitrestriktionen

In der Praxis ist die Belieferung eines Kunden nicht zu jeder Zeit möglich. Grund dafür ist, dass der Kunde ein bestimmtes Zeitfenster für die Annahme der Ware bedingt durch die Öffnungszeiten vorgeben kann. Derartige zeitliche Restriktionen müssen ebenfalls in den Planungsprozess einfließen.

Weitere zeitliche Restriktionen ergeben sich z. B. aus den Öffnungszeiten des Depots. Darüber hinaus können bestimmte Waren ebenfalls Bedingungen an die Lieferzeit bzw. die Fahrzeit stellen, was beispielsweise bei schnell verderblichen Lebensmitteln der Fall ist. Insbesondere wenn die Lieferung nach dem vereinbarten Zeitpunkt erfolgt, besteht die Möglichkeit, dass die Ware ihren optimalen Zustand verliert. Ein Beispiel hierfür ist etwa die Auslieferung von Tiefkühl-Produkten. Die Berücksichtigung zeitlicher Re- striktionen ist auch für die Kundenzufriedenheit entscheidend, denn ein verspätetes Eintreffen einer Lieferung kann den Kunden dazu zwingen, nach einer Ersatzoption zu suchen.¹⁹

Diese realen Probleme werden in der Tourenplanung berücksichtigt, indem die Bedie- nung des Kunden in einem vorab definierten Zeitintervall - dem Zeitfenster - erfolgt. Hierbei wird zwischen harten und weichen Zeitfenstern unterschieden. Bei harten Zeit- fenstern ist es erlaubt, dass ein Fahrzeug zu früh an dem Zielort ankommt, es darf aber in keinem Fall zu spät eintreffen. Im Gegenteil dazu besteht bei einem weichen Zeitfens- ter die Möglichkeit, dass das Fahrzeug verspätet sein Ziel erreichen kann.²⁰ In Abb. 2.2 wird der Unterschied zwischen Touren mit und ohne Zeitfenster veranschaulicht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Beispiel für eine Tour ohne (oben) und mit (unten) Zeitfenster (Quelle: Prohn 2017)

2.2.3 Liefergebietsindividuelle Restriktionen

Oft muss bei der Belieferung von Kunden beachtet werden, wie der Ort, an dem sich diese befinden, beschaffen ist. Örtliche Verkehrsregeln - wie etwa eine Beschränkung des zulässigen Fahrzeuggewichts -, Straßenbauarbeiten oder das Wetter müssen bei der Planung der Routen in die Berechnung einfließen. Auch das Straßennetz muss im All- gemeinen berücksichtigt werden. Beispielsweise hat das Vorhandensein von Einbahn- oder Messestraßen eine Relevanz. Jegliche Information über das Straßennetz kann in ein zentrales Datenbanksystem eingetragen werden, das stets auf dem aktuellen Stand gehalten werden muss.²¹

2.2.4 Kundenrestriktionen

Darüber hinaus muss auch beachtet werden, welche Möglichkeit zur Entladung der Transportgüter bei dem Kunden vorhanden ist. Im Idealfall steht eine Entladerampe und die entsprechenden Werkzeuge und Geräte (z. B. Gabelstapler) zur Verfügung, so- dass der Entladevorgang deutlich schneller ablaufen kann. Ist dies jedoch nicht der Fall, so ist es vorteilhaft, die Fahrzeuge selbst mit den nötigen Hilfsmitteln (Hebebühne) auszustatten oder eigene Geräte zu besitzen (z. B. Hub-Ameise).²²

Weitere wichtige, zu berücksichtigende Faktoren ergeben sich aus den Kundenwün- schen oder dem Kundenzeitfenster. Es gibt häufig Kunden, die regelmäßig beliefert und somit bei der Tourenplanung bevorzugt behandelt werden. Auch die Größe des Auf- tragsvolumens spielt bei der Planung eine Rolle. So kann etwa der Bedarf eines Kunden derart hoch sein, dass die Belieferung aufgrund mangelnder Ressourcen eine besonde- re Planung benötigt. Für gewisse Kunden muss des Weiteren die Bedienung innerhalb eines festen Zeitfensters erfolgen. Dieses ergibt sich aus den Kundengeschäftszeiten oder den befristeten Durchfahrverboten.²³

2.2.5 Auftragsbezogene Restriktionen

Die Durchführung der Tourenplanung besteht in der Ausführung von Aufträgen, die sich aus deren Abhol- und Auslieferungsort, der Menge der transportierten Waren sowie dem Lieferzeitrahmen zusammensetzen. In der Praxis können Aufträge

- die Belieferung bzw. Abholung einer Ware zu bzw. von einem Kunden,
- die Erbringung einer Dienstleistung oder
- eine Personenbeförderung

betreffen.²⁴

Aufträge werden durch die Kunden freigegeben. Dabei werden jeweils gewisse Vorga- ben wie etwa die Kapazitätsbelastung (Menge, Gewicht und die Größe der Güter) oder die zeitlichen Rahmenbedingungen (Be- und Entladezeiten, Liefertermin) vorgegeben. Aufträge lassen sich diesbezüglich in zwei Klassen einteilen: Bei deterministischen Auf- trägen sind alle Informationen bereits vor Beginn der Planung bekannt, bei stochasti- schen Aufträgen werden hingegen einige der Angaben erst bei Lieferung, d. h. nach der Planungsphase, von dem Auftraggeber vorgelegt.²⁵

Aufträge lassen sich ebenfalls bezüglich ihrer Teilbarkeit unterscheiden. Manche Auf- träge lassen sich in Teilaufgaben aufteilen. Somit wird die Belieferung nicht durch eine einzige Tour verwirklicht, sondern jedem Teilauftrag kommt eine separate Tour zu.²⁶

2.3 Lösung von Tourenplanungsproblemen

Generell sind die Lösungsverfahren für Optimierungsprobleme in zwei Ebenen aufge- teilt: exakte Verfahren und heuristische Verfahren.

Zu den exakten Verfahren gehören beispielsweise endliche Verfahren, bei denen in endlich vielen Schritten eine optimale Lösung für das Optimierungsproblem gefun- den wird, d. h. sie kann mithilfe endlich vieler mathematischer Berechnungsschritte ermittelt werden. Es kann jedoch vor allem bei Problemen mit einer hohen Anzahl an Variablen nicht garantiert werden, dass die gesuchte optimale Lösung in endlich vie- len Iterationen ermittelt werden kann. In solchen Fällen werden Näherungsverfahren eingesetzt, welche die Berechnung nach einer beliebigen Zeit abbrechen und dadurch eine angenäherte Lösung liefern. Bei dem Verfahren der vollständigen Enumeration wird das Optimum durch Beurteilung und Vergleich aller Lösungsmöglichkeiten bestimmt.²⁷ Abschnitt 2.3.1 gibt einen Überblick über die wichtigsten exakten Verfahren im Tourenplanungsbereich.

Bei Tourenplanungsproblemen handelt es sich um NP-schwere Probleme, d. h. es exis- tiert vermutlich²⁸ kein exakter Lösungsalgorithmus mit polynomialer Laufzeit. Die Er- mittlung exakter Lösungen ist daher mit einem hohen Rechenaufwand verbunden, so- dass der Einsatz exakter Verfahren mit steigender Anzahl an Problemgrößen immer unpraktikabler wird. Aus diesem Grund wurden sog. heuristische Verfahren entwickelt. Hier existiert im Gegensatz zu exakten Verfahren kein fester Lösungsweg, sondern es wird vielmehr versucht, eine Lösung anhand von auf Sachkenntnissen beruhenden Vermutungen zu erraten. Derartige Verfahren haben i. d. R. das Ziel, eine zufrieden- stellende Kombination zwischen Lösungsqualität und Rechenaufwand zu erreichen. Die ermittelten Ergebnisse sind oft suboptimal, d. h. es besteht keine Garantie, dass eine optimale Lösung tatsächlich gefunden werden kann. In vielen Fällen lässt sich dar- über hinaus keine Aussage darüber treffen, inwieweit die ermittelte Lösung von dem Optimum abweicht.²⁹

Die exakten Verfahren sind im Allgemeinen nicht auf praktische Problemstellungen anwendbar, da diese eine hohe Anzahl an Kunden beinhalten und komplexe Nebenbe- dingungen mit sich führen können. In solchen Fällen haben die Berechnungen eine für praktische Zwecke ungeeignete Laufzeit und erfordern eine hohe Rechenleistung. Statt- dessen empfiehlt sich in der Praxis der Einsatz heuristischer Verfahren. Diese werden in Abschnitt 2.3.2 näher ausgeführt.³⁰

2.3.1 Exakte Verfahren

Für die Anwendung exakter Verfahren muss in erster Linie eine hohe Rechenleistung vorausgesetzt werden. Grund dafür ist, dass die Rechenzeit für das Auffinden optima- ler Lösungen eines Tourenplanungsproblems im ungünstigsten Fall exponentiell mit der Anzahl der Variablen ansteigt, d. h. es handelt sich dabei um sog. NP-vollständige Probleme.³¹

Infolgedessen lässt sich der Anwendungsbereich exakter Verfahren vorwiegend auf ei- ne bestimmte Klasse von Problemen beschränken, insbesondere auf solche, bei denen aufgrund der begrenzten Anzahl der Problemgrößen eine angemessene Rechenzeit ge- währleistet werden kann. Das heißt, exakte Verfahren werden nur für die Behandlung eines kleinen Teils möglicher Problemstellungen herangezogen. Beispiele dafür sind et- wa die standardisierten TSP und CVRP. Darüber hinaus ist für praktische Anwendungen ein gewisses Maß an Flexibilität erforderlich, die von exakten Verfahren in der Regel nicht geleistet werden kann.³²

Trotz dieser Einschränkungen können über exakte Verfahren ermittelte optimale Lösungen als ein Vergleichsmaßstab bei bestimmten Problemstellungen dienen.³³ Im Folgenden werden zwei wichtige Algorithmen genauer untersucht.

2.3.1.1 Branch-and-Bound-Verfahren

Das Branch-and-Bound-Verfahren ist einer der am häufigsten verwendeten Ansätze zur exakten Lösung kombinatorischer Probleme.³⁴ Das Verfahren besteht aus zwei Tei- len, dem „Branching“ (Verzweigung) und dem „Bounding“ (Abgrenzung).³⁵ Branching bezeichnet die Zerlegung des Ausgangsproblems P0 in zwei oder mehrere Teilprobleme P1,...,Pk derart, dass jede einzelne zulässige Lösung von P0 in mindestens einem der Teilprobleme enthalten ist. Durch die< analoge Zerlegung der so entstandenen Teilpro-

bleme lässt sich ein Entscheidungsbaum (auch Branch-and-Bound-Baum oder B&B- Baum genannt) mit dem ursprünglichen Problem P0 als Wurzelknoten (siehe Abb. 2.3) konstruieren. Als nächstes wird versucht, diejenigen Zweige des Baumes „abzuschnei- den“, die nicht zu einer optimalen Lösung führen können. Dieses Vorgehen wird als Bounding bezeichnet.³⁶

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Branch-and-Bound-Baum (Quelle: Scholl 2008, S. 51)

Zu Beginn der Berechnung wird das Ausgangsproblem linear relaxiert, d. h. die Bedin- gung der Ganzzahligkeit der Variablen wird ignoriert, um eine einfache und schnelle Lösung zu ermöglichen. Diese Lösung wird dementsprechend i. d. R. keine ganzzahlige Lösung und somit nicht zulässig sein. An dieser Stelle kann das Problem verzweigt wer- den. Hierzu wird der Lösungsraum des relaxierten Problems derart in zwei Teilräume zerlegt, dass unzulässige Lösungen ausgeschlossen werden. Dies erfolgt durch Hinzu- nahme zusätzlicher Nebenbedingungen, welche die neuen Teilräume festlegen. Durch wiederholte Anwendung dieses Prinzips entsteht in jedem Knoten des B&B-Baums ein relaxiertes Teilproblem, das gelöst werden kann.³⁷

Für Problemstellungen mit einer großen Anzahl an Variablen führt die obige Metho- de zu einer langen Rechenzeit. Der Aufwand kann reduziert werden, wenn bestimmte Zweige des Lösungsbaums - d. h. bestimmte Teilprobleme - ausgeschlossen werden können. Da gewisse Nebenbedingungen bei der Relaxation vernachlässigt werden, ist die Lösung relaxierter Probleme stets besser als die des Ausgangsproblems und stellt somit eine untere Schranke dar, d. h. sie gilt als die bestmögliche Lösung. Wird während der Verzweigung eine zulässige Lösung gefunden, d. h. eine Lösung, die alle ursprüngli- chen Nebenbedingungen erfüllt, so kann diese als obere Schranke dienen. Ist in einem Knoten die untere größer als die obere Schranke, so müssen dieser Knoten sowie alle daraus abgeleiteten Zweige nicht weiter betrachtet werden, da deren Lösungen nicht besser sein können als die Lösungen der übergeordneten Knoten, welche die unteren Schranken liefern.³⁸

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: B&B-Baum mit Bounding. z∗ steht für die beste bislang ermittelte Lösung, z für eine beliebige zulässige Lösung (Quelle: Baudach u. a. 2013, S. 355)

Abb. 2.4 stellt diesen Sachverhalt schematisch dar. z* bezeichnet die aktuell beste zu- lässige Lösung. Sie dient als obere Schranke. Überschreitet der Wert einer Lösung - der jeweils eine untere Schranke darstellt - in einem anderen Knoten diesen Grenzwert, so kann der entsprechende Zweig nicht zu einer optimalen Lösung führen.

2.3.1.2 Branch-and-Cut-Verfahren

Das Branch-and-Cut-Verfahren ist eine Kombination aus dem Schnittebenen- und dem Branch-and-Bound-Verfahren. Es kann somit als eine erweiterte Form des B&B-Verfahr- ens angesehen werden. Es zählt zu den leistungsfähigsten exakten Lösungstechniken für Tourenplanungsprobleme.³⁹

Das Verfahren beginnt - wie es auch bei dem B&B-Verfahren der Fall war - mit der LP- Relaxation des Ausgangsproblems, d. h. gewisse Nebenbedingungen werden ignoriert. Ist die Lösung des relaxierten Problems nicht zulässig, d. h. nicht ganzzahlig, so lässt sie sich durch ein sog. Separationsverfahren von dem Lösungsraum abtrennen. Dies erfolgt durch Angabe zusätzlicher Nebenbedingungen in Form von Ungleichungen. Diese definieren Hyperebenen, die den ursprünglichen Lösungsraum eingrenzen.⁴⁰

Anschließend wird das relaxierte Problem mit den neu dazugewonnenen Nebenbedin- gungen gelöst. Nach jedem Schritt wird dabei der Lösungsraum mittels Hyperebenen weiter verkleinert, bis eine zulässige Lösung gefunden wurde oder bis keine weiteren Nebenbedingungen mehr erzeugt werden können. In diesem Fall lässt sich das Problem mittels eines Branching-Schritts in zwei Teilprobleme aufteilen, wobei die ermittelte Lösung eine untere Schranke für die gesuchte Zielfunktion darstellt. Der Rechenprozess wird anschließend für jeden Knoten durchgeführt, bis eine optimale Lösung gefunden wurde.⁴¹

In der Praxis werden Branch-and-Cut-Verfahren den anderen Alternativen vorgezogen. Viele kommerzielle Software benutzen dieses Verfahren, um die Lösung von sog. Mixed Integer Problems (MIP) zu ermitteln.⁴²

2.3.2 Heuristische Verfahren

Heuristische Verfahren, auch Heuristiken genannt, werden in der Regel bei Problemen mit einer hohen Anzahl an Problemgrößen herangezogen. Diese setzen bestimmte Vor- gehensregeln ein, die der Konstruktion oder Verbesserung von Lösungen dienen und im Bezug auf die verfolgten Ziele sowie unter Beachtung der Problemstruktur „sinnhaft, zweckmäßig und Erfolg versprechend“⁴³ erscheinen.

Der niedrigere Rechenaufwand⁴⁴ von Heuristiken zieht jedoch den Nachteil nach sich, dass sie im Allgemeinen keine optimalen Lösungen, sondern nur sog. Suboptima lie- fern. Darüber hinaus lässt sich nicht ohne weiteres angeben, inwieweit eine solche suboptimale Lösung von dem tatsächlichen Optimum abweicht. In den meisten Fällen können nur Abschätzungen darüber ermittelt werden, beispielsweise durch Angabe von Schranken für das Optimum oder durch eine Performance-Garantie.⁴⁵

Das einfachste und bekannteste Beispiel für eine Heuristik stellen Greedy-Algorithmen dar. Diese versuchen, in jedem Rechenschritt diejenige Entscheidung zu wählen, die zu der größten Kostenreduktion oder der kleinsten Kostenerhöhung führt. In der Regel wird dabei jedoch kein Optimum erreicht.⁴⁶

Der Lösungsweg eines konkreten Problems kann im Allgemeinen in zwei Schritte einge- teilt werden. Zunächst werden im Regelfall eine oder mehrere Anfangslösungen ermit- telt. Hierzu dienen die sog. Eröffnungs- oder Konstruktionsheuristiken. Im Anschluss wird versucht, diese Anfangslösungen mithilfe von sog. Verbesserungsheuristiken zu verbessern.⁴⁷

2.3.2.1 Eröffnungsverfahren (Konstruktionsverfahren)

Eröffnungsverfahren beginnen in der Regel mit einem unzulässigen Tourenplan, der in vielen Fällen mit einem leeren Tourenplan übereinstimmt. Ziel ist es, aus dieser Anfangslösung einen Tourenplan zu konstruieren, der nicht nur zulässig ist, sondern gleichzeitig eine möglichst gute Qualität aufweist, d. h. möglichst nahe am Optimum liegt. Diese Lösung dient anschließend als Grundlage für modifizierende Verbesserungsverfahren, die sie verbessern.⁴⁸

Entsprechend den Teilschritten eines Tourenplanungsproblems aus Abschnitt 2.1 (Clus- tering und Routing) existieren sog. Sukzessiv- und Parallelverfahren. Sukzessivverfah- ren bearbeiten diese Teilaufgaben sequenziell, d. h. bei jeder Tour werden sie schritt- weise gelöst. Sie können je nach Reihenfolge der Bearbeitung wiederum in sog. Route- First-Cluster-Second- und Cluster-First-Route-Second-Algorithmen unterteilt werden. Parallele Verfahren erstellen hingegen den Tourenplan unter gleichzeitiger Beachtung beider Teilaufgaben.⁴⁹

Die zwei bekanntesten Beispiele für diese Verfahren sind der Sweep-Algorithmus von Gillet und Miller (ein Sukzessivverfahren) und das Savings-Verfahren von Clarke und Wright (ein Parallelverfahren), die im Folgenden näher behandelt werden. Die Bedeutung dieser Verfahren resultiert daraus, dass sie schnell umsetzbar sind und gute Lösungen von Grundproblemen der Tourenplanung liefern.⁵⁰

Viele der Lösungsalgorithmen, die ursprünglich für die Lösung des Travelling-Salesman- Problems entworfen worden sind, lassen sich ebenfalls mit entsprechenden Modifika- tionen (Beachtung der relevanten Restriktionen) auf Tourenplanungsprobleme über- tragen. Dazu gehören z. B. das Verfahren des besten (oder des nächsten) Nachfolgers oder die Einfüge-Heuristiken Nearest-Insertion, Cheapest-Insertion, Farther-Insertion oder Arbitary-Insertion.⁵¹

Allgemein sind Lösungen von Eröffnungsverfahren nicht als endgültige und beste Lösungen zu verstehen. Jedoch können sie mittels einer Verbesserungsheuristik verbessert werden oder als Ausgangslösungen für eine Metaheuristik dienen.⁵²

Das Sweep-Verfahren

Bei dem Sweep-Algorithmus von Gillett und Miller (1974) ist die Lage aller Knoten (Standorte des Depots und der Kunden) in Koordinatenform vorgegeben. Die Koordinaten (xi ,yi ) sowie die Entfernungen dij sollen dabei alle derart definiert sein, dass das Depot im Ursprung des Koordinatensystems liegt. Die Kunden und die Zielorte werden anfangs nach aufsteigenden Polarwinkeln ϕi⁵³, d. h. gegen den Uhrzeigersinn, von 1 bis n durchnummeriert.⁵⁴

Die Menge aller Kunden wird zu Beginn in eine variable Anzahl an Untermengen auf- geteilt und die Touren sukzessiv für diese Untermengen erstellt. Das heißt, die erste Tour des Plans geht die Kunden 1, 2, . . . , i1 (die ersten i1 Kunden mit den kleinsten Po- larwinkeln) durch, die zweite Tour enthält die Kunden i1 + 1, . . . , i1 + i2, usw. Die derart konstruierten Routen werden im Anschluss mithilfe eines Verbesserungsverfahrens un- ter Beachtung der vorgegebenen Restriktionen optimiert, d. h. die Reihenfolge der zu beliefernden Kunden in jeder Tour wird derart geändert, dass die Fahrstrecke dabei minimal wird.⁵⁵

Des Weiteren kann noch geprüft werden, inwieweit das Auswechseln des letzten Kun- den einer Tour gegen den ersten Kunden der darauffolgenden Tour eine Verbesserung erwirken kann. Dabei soll beachtet werden, dass keine Überschreitung der Kapazitäts- grenze Q des Fahrzeugs und die maximale Zeitdauer T der Tour stattfinden wird.⁵⁶

Das Verfahren wird anschließend wiederholt, wobei der Startpunkt auf den nächstgelegenen Kunden verschoben wird. Somit entstehen n unterschiedliche Lösungen, von denen die beste ausgewählt werden kann (vgl. Abb. 2.5).⁵⁷

Als Kritikpunkt kann die Sortierung nach den Polarwinkeln ϕi genannt werden, da dabei der Abstand der Kunden zum Depot nicht berücksichtigt wird. Dies führt dazu,

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Anwendung des Sweep-Verfahrens auf ein einfaches Problem (Quelle: Suhl und Mellouli 2013, S. 251)

dass aufeinander folgende Zielpunkte in großer Entfernung liegen können. Durch eine Unterscheidung zwischen Nah- und Fernzone kann dieses Problem aber vermieden werden.⁵⁸

Darüber hinaus kann angemerkt werden, dass es sich bei dem Sweep-Algorithmus um einen Route-First-Cluster-Second-Algorithmus handelt. Die Touren werden zunächst ohne Beachtung jeglicher Restriktionen festgelegt. Die darauffolgende Verbesserung kann je nach Art der vorgegebenen Anforderungen einen unverhältnismäßig großen Rechenaufwand erfordern. Dies ist insbesondere dann der Fall, wenn Restriktionen bezüglich der Belieferungszeiten gegeben sind.⁵⁹

Das Savings-Verfahren

In praktischen Logistikprozessen findet das Savings-Verfahren wesentlich häufiger Ein- satz als das zuvor vorgestellte Sweep-Verfahren. Dieses Verfahren wurde von Clarke und Wright (1964) erarbeitet und ist ein Beispiel für Parallelverfahren, da die Erstellung und die Veränderung von Touren parallel zueinander erfolgen.⁶⁰

Es wird vorausgesetzt, dass alle Entfernungen dij zwischen den Knoten bekannt sind. Alternativ reicht ebenfalls die Vorgabe der Koordinaten für das Depot und die Kunden, aus denen sich die Abstände berechnen lassen. Die zugrundeliegende Anfangslösung besteht aus einem Tourenplan, bei dem für jeden Kunden i eine Tour von dem Depot aus gebildet wird. Diese werden als Pendeltouren bezeichnet. Die Routen bestehen aus einer Fahrt vom Depot zum Kunden und wieder zurück. Daraus ergibt sich eine Gesamtlänge des Tourenplans von

Abbildung in dieser Leseprobe nicht enthalten

wobei d0i den Abstand zwischen dem Depot und dem Kunden i bezeichnet.⁶¹

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6: Vereinigung zweier Touren

Diese Anfangslösung wird anschließend durch die sukzessive Vereinigung zweier Tou- ren verbessert, wobei die Beschränkungen bezüglich der Kapazität und Fahrtdauer be- achtet werden. Dies kann auf vier verschiedenen Wegen erfolgen. Sind (0,i1,...,ik,0)

und (0,il ,...,im,0) zwei Touren, so können daraus die folgenden Kombinationen ent- stehen:

Abbildung in dieser Leseprobe nicht enthalten

Durch Verknüpfung der Endkunden i und j zweier Touren (vgl. Abb. 2.6) ergibt sich ein Saving - oder eine Fahrstreckenersparnis - von

Abbildung in dieser Leseprobe nicht enthalten

Diese Größe kann sowohl positiv als auch negativ sein. Sie dient als Zielfunktion, d. h. das Verfahren zielt darauf ab, jeweils diejenigen Vereinigungen zu realisieren, die den Saving maximieren.⁶²

Die ermittelte Lösung hängt von der Reihenfolge der Verknüpfung ab, d. h. es kann nicht garantiert werden, dass das Verfahren unmittelbar die optimale Lösung des vorgegebe- nen Problems liefert. Daher empfiehlt es sich, mehrere Lösungen zu bestimmen, indem die Verknüpfungsreihenfolge variiert wird.⁶³ Anschließend kann unter den Ergebnissen dasjenige ausgewählt werden, das die größte Kostenersparnis einbringt.

Lässt sich der ermittelte Tourenplan mithilfe der zur Verfügung stehenden Fahrzeuge bewerkstelligen, so ist dadurch eine zulässige Lösung definiert. Ansonsten ergibt der Algorithmus eine Lösung, deren Ausführung zusätzliche Fremdfahrzeuge erfordert.⁶⁴

2.3.2.2 Verbesserungsverfahren

Verbesserungsverfahren können im Wesentlichen zwei Zwecke erfüllen: die Verfeine- rung der Reihenfolge innerhalb einer Tour oder die Optimierung der Verteilung der Kun- den auf die Touren.⁶⁵ Die meisten Verbesserungsverfahren, die in der Tourenplanung Anwendung finden, wurden ursprünglich für das Travelling-Salesman-Problem entwi- ckelt. Dazu zählen das 2-opt- und das 3-opt-Verfahren sowie das Or-opt-Verfahren.

Die Übertragbarkeit dieser Verfahren auf Tourenplanungsprobleme ist möglich, wenn entsprechende Modifikationen vorgenommen werden.⁶⁶

Das 2-opt-Verfahren

Bei dem 2-opt-Verfahren wird versucht, die Länge einer Tour durch eine Vertauschung zweier Kanten zu verringern. Dabei werden jeweils zwei Kanten { j , j + 1} und {k, k + 1} gegen zwei andere Kanten {j,k} und {j +1,k +1} ausgetauscht (vgl. Abb. 2.7). Diese Vertauschung führt genau dann zu einer Verbesserung, wenn dj,k + dj+1,k+1 < dj,j+1 + dk,k+1 gilt. Der Prozess wird solange weitergeführt, bis keine weitere Verbesserung der Tourenlänge mehr möglich ist. Die daraus ermittelte Tour gilt dann als 2-optimal. Sind zwei oder mehrere Touren vorhanden, so besteht ebenfalls die Möglichkeit, die Knoten auch zwischen zwei Touren zu tauschen.⁶⁷

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.7: Kantenersetzung im 2-opt-Verfahren. Die Vertauschung ist sinnvoll, wenn die neue Fahrtstrecke kürzer ist als die alte (Quelle: M. Vogt 1998, S. 68)

Bei der Ausführung eines Kantenaustauschs müssen dabei die vorliegenden Restriktionen beachtet werden, d. h. die verbesserte Tour muss weiterhin zulässig sein.⁶⁸

Da die Qualität der Lösung von der Reihenfolge abhängig ist, in der die Vertauschungen erfolgen, kann es von Vorteil sein, zunächst alle möglichen Vertauschungskombinatio- nen zu untersuchen und im Anschluss die beste darunter auszuwählen, anstatt den ersten profitablen und zulässigen Austausch direkt zu übernehmen.⁶⁹ Dadurch erhöht sich jedoch der Rechenaufwand, d. h. es muss ggf. zwischen erzielter Lösungsqualität und Aufwand abgewogen werden.

Das 3-opt-Verfahren

Dieses Verfahren ist im Vergleich zum 2-opt-Verfahren zwar wesentlich rechenintensiver, es liefert aber in der Regel genauere Ergebnisse. Dabei werden in jedem Schritt drei Kanten aus der Tour entfernt und es wird versucht, sie derart durch neue Kanten zu ersetzen, dass die daraus entstehende Tour verbessert wird. Dafür müssen sieben Möglichkeiten untersucht werden, deren Anzahl sich jedoch reduzieren lässt, indem davor der 2-opt-Algorithmus ausgeführt wird.⁷⁰

In Abb. 2.8 wird eine beispielhafte Vertauschungsiteration veranschaulicht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.8: Beispielhafte Ausführung eines 3-opt-Verfahrens (Quelle: Wenger 2010, S. 77)

Hierbei erfolgt eine Ersetzung der Kanten (vi , vi+1), (vj , vj+1) sowie (vk , vk+1) durch (vi ,vj+1), (vk,vi+1) sowie (vj ,vk+1). Somit entsteht aus der ersten ermittelten Route

Abbildung in dieser Leseprobe nicht enthalten

die Nachbarroute⁷¹

Abbildung in dieser Leseprobe nicht enthalten

2.3.3 Metaheuristiken

Die bisher behandelten Heuristiken können als deterministische Verfahren eingeord- net werden, die zur Konstruktion oder Verbesserung von Lösungen dienen.

[...]

---

¹ Vgl. Linke 2013, S. 16f.

² Vgl. Prokop und Stoller 2012, S. 12.

³ Vgl. ebd., S. 10.

⁴ Vgl. ebd., S. 49.

⁵ Vgl. Richter 2007, S. 32f. Ohrt 2008, S. 9.

⁶ Vgl. Vahrenkamp 2003, S. 233.

⁷ Vgl. Richter 2007, S. 32f.

⁸ Vgl. Richter 2007, S. 19.

⁹ Vgl. Domschke und Scholl 2010, S. 95.

¹⁰ Vgl. Vahrenkamp 2003, S. 235.

¹¹ Vgl. Domschke und Scholl 2010, S. 167.

¹² Vgl. J.-O. Vogt 2002, S. 86.

¹³ Vgl. Rieck 2008, S. 11.

¹⁴ Es existieren unterschiedliche Formulierungen von Standardproblemen mit leichten Variationen.

¹⁵ Vgl. Rieck 2008, S. 11.

¹⁶ Vgl. ebd., S. 11.

¹⁷ Vgl. M. Vogt 1998, S. 29.

¹⁸ Vgl. Krause 2007, S. 150.

¹⁹ Vgl. J.-O. Vogt 2002, S. 90f.

²⁰ Vgl. Erdmann 1999, S. 171.

²¹ Vgl. M. Vogt 1998, S. 30.

²² Vgl. M. Vogt 1998, S. 30.

²³ Vgl. ebd., S. 30.

²⁴ Vgl. ebd., S. 30.

²⁵ Vgl. ebd., S. 30.

²⁶ Vgl. M. Vogt 1998, S. 30.

²⁷ Vgl. Wenger 2010, S. 67.

²⁸ Unter der Annahme, dass P = NP.

²⁹ Vgl. Ohrt 2008, S. 49.

³⁰ Vgl. Gietz 2008, S. 147.

³¹ Vgl. Wenger 2010, S. 68.

³² Vgl. ebd., S. 69.

³³ Vgl. Ohrt 2008, S. 63.

³⁴ Vgl. M. Vogt 1998, S. 70.

³⁵ Vgl. Rieck 2008, S. 53.

³⁶ Vgl. Baudach u. a. 2013, S. 350.

³⁷ Vgl. ebd., S. 350.

³⁸ Vgl. Baudach u. a. 2013, S. 354.

³⁹ Vgl. Siepermann und Eley 2011, S. 95.

⁴⁰ Vgl. Baudach u. a. 2013, S. 356.

⁴¹ Vgl. ebd., S. 356.

⁴² Vgl. ebd., S. 357.

⁴³ Vgl. Vahrenkamp und Mattfeld 2007, S. 49.

⁴⁴ Der Rechenaufwand von Heuristiken ist polynomial beschränkt.

⁴⁵ Vgl. Vahrenkamp und Mattfeld 2007, S. 49.

⁴⁶ Vgl. Vahrenkamp und Mattfeld 2007, S. 49.

⁴⁷ Vgl. M. Vogt 1998, S. 59.

⁴⁸ Vgl. Wenger 2010, S. 70.

⁴⁹ Vgl. ebd., S. 70.

⁵⁰ Vgl. Tesch u. a. 2013, S. 423.

⁵¹ Vgl. M. Vogt 1998, S. 60.

⁵² Vgl. Gietz 2008, S. 149.

⁵³ Dieser ist definiert über tan ϕi = yi /xi .

⁵⁴ Vgl. M. Vogt 1998, S. 60.

⁵⁵ Vgl. ebd., S. 60.

⁵⁶ Vgl. ebd., S. 60f.

⁵⁷ Vgl. ebd., S. 61.

⁵⁸ Vgl. M. Vogt 1998, S. 61.

⁵⁹ Vgl. M. Vogt 1998, S. 61.

⁶⁰ Vgl. ebd., S. 61.

⁶¹ Vgl. ebd., S. 61f.

⁶² Vgl. M. Vogt 1998, S. 62f.

⁶³ Vgl. ebd., S. 63.

⁶⁴ Vgl. Rieck 2008, S. 83.

⁶⁵ Vgl. Gietz 2008, S. 149.

⁶⁶ Vgl. M. Vogt 1998, S. 67.

⁶⁷ Vgl. ebd., S. 68.

⁶⁸ Vgl. Gietz 2008, S. 149.

⁶⁹ Vgl. ebd., S. 149.

⁷⁰ Vgl. Gietz 2008, S. 149.

⁷¹ Vgl. Wenger 2010, S. 77.