Inhaltsverzeichnis Seite I

Inhaltsverzeichnis   

1  Einleitung  1

1.1  Problemstellung  1

1.2  Zielstellung der Arbeit  2

1.3  Aufbau und Gliederung der Arbeit  2

2  Grundlagen und Abgrenzung  3

2.1  Tourenplanung im Allgemeinen  3

2.2  Tourenplanung mit zeitlicher Restriktion  6

2.2.1  Voraussetzungen und Realitätsbeschränkung  6

2.2.2  Mathematische Modellbildung  9

2.2.3  Komplexitätsuntersuchung des VRPTW  12

2.2.4  Typologie der Zeitfensterrestriktionen  15

2.3  Ansätze zur Lösung kombinatorischer Optimierungsprobleme  17

2.3.1  Problemspezifische Heuristiken  17

2.3.2  Metaheuristiken  19

3  Verfahren zur Lösung des VRPTW  23

3.1  Konstruktionsverfahren  23

3.2  Definition der Nachbarschaftsstrukturen  24

3.3  Bewertungsfunktion eines Tourenplans  26

3.4  Aufbau des Gesamtverfahrens  28

3.4.1  Minimierung der Fahrzeuganzahl  28

3.4.2  Minimierung der Gesamtfahrstrecke  30

4  Algorithmische Beschreibung des Verfahrens  32

4.1  Repräsentation elementarer Komponenten  32

4.1.1  Repräsentation der Kunden  32

4.1.2  Repräsentation der Tourenpläne  33

4.2  Elementare Zugriffe  34

4.3  Elementare Berechnungen  35

Armin  Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig  

Inhaltsverzeichnis Seite II

4.4  Elementare Zulässigkeitsbedingungen  39

4.5  Elementare Operationen  45

4.6  Konstruktion der Ausgangslösung  53

4.7  Algorithmische Umsetzung der Nachbarschaftsstrukturen  56

4.7.1  Operator Or-Opt  56

4.7.2  Operator 2-Opt  58

4.7.3  Operator Single-Interchange  59

4.7.4  Operator Single-Insertion  60

4.7.5  Auswahl des Operators  61

4.8  Bewertung von Tourenplänen  62

4.9  Verbesserungsverfahren  70

4.9.1  Ejection-Chain Heuristik  71

4.9.2  Rekursion der Ejection-Chain  72

4.9.3  Lokale Suche zur Minimierung der Tourenanzahl  75

4.9.4  Lexikographischer Vergleichsoperator  77

4.9.5  Akzeptanz einer verschlechterten Lösung  78

4.9.6  Metaheuristik: Threshold Accepting  79

4.9.7  Verfahren zur Minimierung der Gesamtfahrstrecke  80

5  Evaluation des Gesamtverfahrens  82

5.1  Probleminstanzen von Solomon und Homberger  82

5.2  Parametrisierung des Gesamtverfahrens  89

5.3  Darstellung der berechneten Lösungen  90

5.4  Auswertung der berechneten Lösungen  97

6  Zusammenfassung  100

Armin  Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig  

Abbildungsverzeichnis Seite III

Abbildungsverzeichnis

2.1 Beziehungen innerhalb der Klasse der Tourenplanungsprobleme . . . . . 5

2.2 VRPTW als Vektoroptimierungsproblem . . . . . . . . . . . . . . . . . . 11 2.3 Komplexität eines exponentiellen Algorithmus im worst case . . . . . . . 14 2.4 Lokale Suche im gesteuerten und ungesteuerten Fall . . . . . . . . . . . 22

3.1 Inter-Move des Or-Opt Operators . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Move des 2-Opt* Operators . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3 Inter-Move des Single-Interchange Operators . . . . . . . . . . . . . . . 26 3.4 Move des Single-Insertion Operators . . . . . . . . . . . . . . . . . . . . 26 3.5 Hierarchische Vergleichskriterien bezüglich zweier Tourenpläne . . . . . 27 3.6 Aufbau des Gesamtverfahrens . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1 Repräsentation der Kunden . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Repräsentation der Tourenpläne . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Zeitliche Darstellung einer Tour . . . . . . . . . . . . . . . . . . . . . . . 47 4.4 Exemplarischer Schritt des Savingsverfahrens . . . . . . . . . . . . . . . 53 4.5 Topologische Darstellung einer Lösung . . . . . . . . . . . . . . . . . . . 55 4.6 Kennzahlen zur Bewertung von Tourenplänen . . . . . . . . . . . . . . . 63 4.7 Darstellung der zusätzlichen Pufferzeit . . . . . . . . . . . . . . . . . . . 70 4.8 Exemplarischer Rekursionsbaum der Ejection-Chain . . . . . . . . . . . . 75

5.1 Spezifikation der Solomon Probleminstanzen . . . . . . . . . . . . . . . 83 5.2 Spezifikation der Homberger Probleminstanzen mit 200 Kunden . . . . . 84 5.3 Spezifikation der Homberger Probleminstanzen mit 400 Kunden . . . . . 85 5.4 Spezifikation der Homberger Probleminstanzen mit 600 Kunden . . . . . 86 5.5 Spezifikation der Homberger Probleminstanzen mit 800 Kunden . . . . . 87 5.6 Spezifikation der Homberger Probleminstanzen mit 1000 Kunden . . . . 88 5.7 Testumgebung und Parametrisierung wichtiger Verfahrensgrößen . . . . 89 5.8 Berechnete Lösungen der Solomon Probleminstanzen . . . . . . . . . . . 91 5.9 Berechnete Lösungen der Homberger Probleminstanzen mit 200 Kunden 92 5.10 Berechnete Lösungen der Homberger Probleminstanzen mit 400 Kunden 93

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

Abbildungsverzeichnis Seite IV

5.11 Berechnete Lösungen der Homberger Probleminstanzen mit 600 Kunden 94 5.12 Berechnete Lösungen der Homberger Probleminstanzen mit 800 Kunden 95 5.13 Berechnete Lösungen der Homberger Probleminstanzen mit 1000 Kunden 96 5.14 Darstellung einer berechneten Lösung des Problems RC104 . . . . . . . 98

Algorithmenverzeichnis Seite V

Algorithmenverzeichnis

4.1 Ermittlung des Vorgängers . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Ermittlung des Nachfolgers . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3 Ermittlung einer Tour . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.4 Ermittlung der kleinsten Tour . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5 Berechnung Anzahl Touren . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.6 Kundenanzahl der kleinsten Tour . . . . . . . . . . . . . . . . . . . . . . 37 4.7 Distanz einer ausgezeichneten Tour . . . . . . . . . . . . . . . . . . . . . 38 4.8 Berechnung der Gesamtdistanz . . . . . . . . . . . . . . . . . . . . . . . 38 4.9 Zulässigkeitsprüfung: Einfügen eines Kunden . . . . . . . . . . . . . . . 39 4.10 Zulässigkeitsprüfung: Verdrängen eines Kunden . . . . . . . . . . . . . . 41 4.11 Zulässigkeitsprüfung: Einfügen einer Kundenkette . . . . . . . . . . . . . 42 4.12 Zulässigkeitsprüfung: Einfügen einer Kante . . . . . . . . . . . . . . . . 43 4.13 Zulässigkeitsprüfung: Kreuzen zweier Kanten . . . . . . . . . . . . . . . 44 4.14 Operation: Einfügen eines Kunden . . . . . . . . . . . . . . . . . . . . . 45 4.15 Operation: Aktualisierung der frühesten Abfahrtszeit . . . . . . . . . . . 46 4.16 Operation: Aktualisierung der spätest zulässigen Ankunftszeit . . . . . . 48 4.17 Operation: Aktualisierung der Tour . . . . . . . . . . . . . . . . . . . . . 48 4.18 Operation: Löschen eines Kunden . . . . . . . . . . . . . . . . . . . . . . 49 4.19 Operation: Verdrängen eines Kunden . . . . . . . . . . . . . . . . . . . . 50 4.20 Operation: Zerschneiden einer Tour . . . . . . . . . . . . . . . . . . . . . 51 4.21 Operation: Einfügen einer Kante . . . . . . . . . . . . . . . . . . . . . . 51 4.22 Operation: Kreuzen zweier Kanten . . . . . . . . . . . . . . . . . . . . . 52 4.23 Pseudo-Code: Savingsverfahren . . . . . . . . . . . . . . . . . . . . . . . 54 4.24 Pseudo-Code: Operator Or-Opt . . . . . . . . . . . . . . . . . . . . . . . 57 4.25 Pseudo-Code: Operator 2-Opt* . . . . . . . . . . . . . . . . . . . . . . . 58 4.26 Pseudo-Code: Operator Single-Interchange . . . . . . . . . . . . . . . . . 59 4.27 Pseudo-Code: Operator Single-Insertion . . . . . . . . . . . . . . . . . . 61 4.28 Zufällige Auswahl des Operators . . . . . . . . . . . . . . . . . . . . . . 62 4.29 Ermittlung der Verspätung . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.30 Bewertungsfunktion: Ermittlung der erforderlichen Gesamtverspätung . 66

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

Algorithmenverzeichnis Seite VI

4.31 Bewertungsfunktion: Ermittlung der erforderlichen Überladung . . . . . 67 4.32 Berechnung der Verschiebezeit . . . . . . . . . . . . . . . . . . . . . . . 68 4.33 Berechnung der zusätzlichen Pufferzeit . . . . . . . . . . . . . . . . . . . 69 4.34 Hauptfunktion der Ejection-Chain . . . . . . . . . . . . . . . . . . . . . . 71 4.35 Rekursion der Ejection-Chain . . . . . . . . . . . . . . . . . . . . . . . . 72 4.36 Erste Verfahrensstufe: Lokale Suche . . . . . . . . . . . . . . . . . . . . . 76 4.37 Lexikographischer Vergleich zweier Tourenpläne . . . . . . . . . . . . . 77 4.38 Akzeptanzfunktion für verschlechternde Lösungen . . . . . . . . . . . . 78 4.39 Zweite Verfahrensstufe: Threshold Accepting Metaheuristik . . . . . . . 79 4.40 Verfahren zur Minimierung der Gesamtfahrstrecke . . . . . . . . . . . . 81

1. Einleitung Seite 1

1 Einleitung

1.1 Problemstellung

In den letzten Jahrzehnten rückte ein Bereich der kombinatorischen Optimierungsprobleme immer mehr in den Brennpunkt der Forschung: die Klasse der Tourenplanungsprobleme. Immer mehr Güter müssen in immer kürzerer Zeit von einem Ort zum anderen transportiert werden. Bei der Tourenplanung werden daher Fragestellungen diskutiert, wie eine Zusammenstellung von Auslieferungs- und Sammelaufträgen aussehen muss, um einen möglichst effizienten Ablauf zu gewährleisten. Die Schwierigkeit dieser Organisation liegt darin, die dem Problem zu Grunde liegenden Restriktionen einzuhalten. In der Praxis treten häufig Einschränkungen in Form einer begrenzten Ladekapazität der zur Verfügung stehenden Fahrzeuge oder zeitlicher Vorgaben der Kunden auf. Diese zeitlichen Vorgaben beinhalten den frühest beziehungsweise den spätest möglichen Belieferungszeitpunkt des Kunden. Beispielsweise kann ein Kunde aus der Just-in-Time Fertigung keine Lieferung vor diesem Zeitfenster annehmen, da ihm dafür schlicht Lagerkapazitäten fehlen. Eine Belieferung nach Ende des Zeitfensters ist ebenfalls nicht erlaubt, da es in diesem Szenario unter Umständen zu einem Stillstand der Produktion in Folge fehlender Ressourcen kommen kann.

Wie Lenstra u. Kan (1981) zeigten, gehört das Tourenplanungsproblem mit Zeitfensterrestriktionen, das in der angelsächsischen Literatur unter dem Namen „Vehicle Routing Problem with Time Windows“ (VRPTW) zu finden ist, zu den N P-harten Optimierungsproblemen. In der Klasse der N P-harten Probleme fasst man all diejenigen Optimierungsprobleme zusammen, deren optimale Lösung nach gegenwärtigem Wissen praktisch nicht in polynomialem Zeitaufwand gefunden werden kann. Charakteristisch für solche Probleme ist vielmehr, dass die Zeitkomplexität für das Finden der optimalen Lösung exponentiell mit der Problemgröße wächst. Auf Grund dessen werden solche Probleme meist mit heuristischen Verfahren untersucht. Sie zeichnen sich dadurch aus, in akzeptablem Zeitaufwand gute Lösungen zu erzielen. Im Unterschied zu exakten Lösungsmethoden, wie beispielsweise dem Branch and Bound Algorithmus oder den Dekompositionsverfahren ist das Finden der optimalen Lösung jedoch nicht garantiert.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

1. Einleitung Seite 2

In der Literatur wird dem Tourenplanungsproblem mit Zeitfensterrestriktionen meist eine hierarchische Zielstellung zu Grunde gelegt, einem primären sowie einem sekundären Ziel. Vorrangig ist hierbei die Minimierung der benötigten Fahrzeuge, nachrangig die Minimierung der zurückgelegten Gesamtfahrstrecke. Seit Mitte der Siebziger Jahre werden zur Lösung des VRPTW die dafür entwickelten Metaheuristiken eingesetzt. Sie basieren auf der Grundidee, physikalische oder biologische Prozesse nachzuahmen. Typische Vertreter solcher Verfahren sind Genetische und Evolutionäre Algorithmen, Simulated Annealing und Tabu-Search.

1.2 Zielstellung der Arbeit

Eine Zielsetzung dieser Arbeit ist es, einen geeigneten Algorithmus zur Lösung des Tourenplanungsproblems mit Zeitfensterrestriktionen vorzustellen und diesen zu evaluieren. Um die Güte der Lösung abschätzen zu können, werden die Benchmark Probleme von Solomon (1987) bzw. Homberger (2000) herangezogen und mit den bisher besten in der Literatur veröffentlichten Lösungen verglichen. Ein zweites Ziel wird sein, ein weiteres, von der Literatur bisher unbeachtetes Kriterium zur Bewertung einer gefundenen Lösung umzusetzen: eine möglichst gleichmäßige Verteilung der Kunden auf die jeweiligen Touren. Damit soll erreicht werden, dass jeder Fahrer einer Tour zeitlich annähernd gleich lange unterwegs ist wie seine Kollegen auf den anderen Touren. Dabei wird dieses Kriterium nicht als Ziel sondern als Wunsch formuliert.

1.3 Aufbau und Gliederung der Arbeit

Nach der Einleitung wird im zweiten Kapitel das Standardproblem der Tourenplanung mit Zeitfensterrestriktionen vorgestellt, eine Realitätsabgrenzung vorgenommen und das dazugehörige mathematische Modell aufgestellt. Nach der Betrachtung grundlegender Heuristiken zur Lösung kombinatorischer Optimierungsprobleme folgt im dritten Kapitel die Konzeption des Verfahrens zur Untersuchung und Optimierung des VRPTW. Dieses Verfahren wird im Anschluss in Kapitel vier in Form einer algorithmischen Beschreibung dargestellt. Die Auswertung des Verfahrens mit den von Solomon (1987) und Homberger (2000) bereitgestellten Probleminstanzen bildet den Abschluss dieser Arbeit.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 3

2 Grundlagen und Abgrenzung

2.1 Tourenplanung im Allgemeinen

In der Tourenplanung sieht die Ausgangssituation wie folgt aus:

Anhand einer gegebenen Anzahl an Fahrzeugen, die sich an verschiedenen Depots befinden können, müssen eine bestimmte Anzahl an Kunden so bedient werden, dass gegebene Restriktionen eingehalten und eine vorher definierte Zielfunktion optimiert wird.

Diese allgemeine Aussage trifft auf fast alle Probleme innerhalb der Klasse der Tourenplanungsprobleme zu. Darin enthalten sind unter anderem das Traveling Salesman Problem (TSP), das klassische Tourenplanungsproblem sowie das Pickup and Delivery Problem (PDP). Der Begriff „Depot“ kennzeichnet hierbei den Ort, an dem die Auslieferungsbzw. Sammelaufträge beginnen und enden. Eine Übersicht der verschiedenen Problemzusammenhänge liefert Abb. 2.1. Um eine Abgrenzung der einzelnen Probleme zu erreichen, werden in der heutigen Literatur vier Kriterienklassen unterschieden (vgl. Domschke (1997)): „Adressen“, „Fahrzeuge“, „Problemcharakteristika“ und „Ziele“.

Die Kriteriumklasse Adressen lässt sich klassifizieren nach:

• Anzahl der gegebenen Depots,

• Anzahl der zu beliefernden Kunden,

• Art der Aufträge:

- nur Belieferung oder nur Abholung oder gemischt,

- kein, ein oder mehrere Zeitfenster vorhanden,

• Restriktionen an der Adressenauswahl:

- alle Adressen müssen besucht werden,

- nur eine Teilmenge der Adressen muss besucht werden,

- wie oft dürfen Adressen besucht werden.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 4

Die Kriteriumklasse Fahrzeuge lässt sich unterscheiden nach:

• der Anzahl der zur Verfügung stehenden Transportmittel,

• der ihr zur Verfügung stehenden Kapazität,

• der Transportmöglichkeit. Darunter fallen beispielsweise Spezialtransporte oder der gleichzeitige Transport mehrerer unterschiedlicher Güter.

• der momentanen Verfügbarkeit (Reparaturen, Instandsetzung, Wartung),

• der Beschränktheit der Einsatzdauer (Einhaltung von Ruhepausen bzw. der maximalen Lenkdauer der einzelnen Fahrer).

Das Kriterium Problemcharakteristika umfasst weitere Merkmale des zu Grunde liegenden Problems. Diese gliedern sich in:

• den vorliegenden Netzwerktyp,

• den Strategietyp,

• die Adressen-Adressen Beschränkungen,

• die Adressen-Fahrzeug Beschränkungen.

Der Netzwerktyp gibt hierbei an, ob ein gerichtetes oder ungerichtetes Netzwerk vorliegt. Der Strategietyp gibt beispielsweise an, ob ein Fahrzeug nur eine oder mehrere Touren bedienen darf. Unter einer Tour wird dabei die geordnete Menge an Kunden ver-standen, die an einem Depot beginnend nacheinander auf einer Fahrt bedient werden. Beschränkungen innerhalb der Klasse Adressen können gegebenenfalls die Anordnung der Kunden auf dieser Tour bestimmen. Der letzte Unterpunkt beschreibt die Konfliktfähigkeit zwischen den Adressen und Fahrzeugen. Ist für ein Fahrzeug zum Beispiel nur eine Beladung des Gutes a vorgesehen, der Kunde jedoch das Gut b benötigt, muss die Belieferung durch ein anderes Fahrzeug erfolgen.

Die Ziele können abhängig von der reinen Fahrtzeit, der zurückgelegten Gesamtfahrstrecke oder beispielsweise der Anzahl der benötigten Touren sein. Diese Ziele sind je nach Problem skalare oder vektorwertige Funktionen die unter Einhaltung gegebener Restriktionen optimiert werden sollen.

Nachfolgende Grafik, die aus (Desaulniers u. a., 1998, S. 64) entnommen wurde, veranschaulicht die Zusammenhänge der verschiedenen Modelle innerhalb der Klasse der Tourenplanungsprobleme. Ausgangspunkt und somit Grundgerüst aller weiteren betrachteten Probleme ist das Shortest Path Problem, kurz SPA. Dieses Modell befasst sich

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 5

mit der Suche kürzester Wege innerhalb eines Netzwerkes zwischen beliebigen Knoten. Als erste Erweiterung entsteht durch Hinzunahme von Kundenzeitfenstern aus dem SPA das Shortest Path Problem mit Zeitfenstern (SPTW) bzw. das Elementary Shortest Path Problem mit Zeitfenstern (ESPTW).

Der einzige Unterschied zwischen dem SPTW und dem ESPTW liegt darin, dass beim ES-PTW jeder Kunde nur einmal auf der Tour besucht werden darf. Nimmt man nun noch Kapazitätsbeschränkungen der eingesetzten Fahrzeuge auf, entsteht aus einem SPTW bzw. ESPTW das SPTWQ bzw. das ESPTWQ. Die zusätzliche Betrachtung von Ressourcenbeschränkungen führt zu einem Shortest Path Problem mit Ressourcenbeschränkung (SPR) bzw. dem Elementary Shortest Path Problem mit Ressourcenbeschränkung (ES-PR). Legt man nun verschiedene Ausprägungen des Shortest Path Problems zu Grunde, lassen sich mehrere Rundfahrtprobleme erzeugen, wie zum Beispiel das Traveling Salesman Problem mit Zeitfenstern (TSPTW) oder das Traveling Salesman Problem mit Ressourcenbeschränkung (TSPR). Diese Probleme sind mitunter dadurch gekennzeichnet, dass sie jeweils nur eine Tour besitzen, auf der alle Kunden bedient werden müssen. Lässt man jedoch mehrere Touren zu, lassen sich weitere Modelle konstruieren, wie der dritten Zeile der Abbildung zu entnehmen ist.

Gegenstand dieser Arbeit wird das Standardproblem der Tourenplanung mit Zeitfenstern (VRPTW) sein. Dabei wird das Vorhandensein eines Depots sowie die Nachfrage nach einem homogenen Gut vorausgesetzt. Ferner wird ein reines Auslieferungsproblem unterstellt, bei dem alle Kunden vom Depot aus mit Gütern zu beliefern sind.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 6

2.2 Tourenplanung mit zeitlicher Restriktion

2.2.1 Voraussetzungen und Realitätsbeschränkung

Es wird davon ausgegangen, dass dem Standardproblem der Tourenplanung mit Zeitfensterrestriktionen folgende Problemgrößen zu Grunde gelegt und bekannt sind:

Es seien i = 1, ..., n Kunden, deren Standorte in Form der Koordinaten [x i , y i ] gegeben sind. Das mit 0 gekennzeichnete Depot besitzt hierbei den Standort [x 0 , y 0 ]. Für jeden der i Kunden sei zu Planungsbeginn die von ihm nachgefragte und somit von Unternehmer zu liefernde Menge q i bekannt. Ferner besteht Kenntnis über die Servicedauer s i eines jeden Kunden, die bei der Belieferung anfällt. Diese Belieferung muss innerhalb des vorgegebenen Zeitfensters [a i , b i ] erfolgen. Diese Zeitfenster geben den frühest möglichen Belieferungszeitpunkt a i , sowie den spätest zulässigen Belieferungszeitpunkt b i am Kunden i an. Für die Ausführung der Lieferungen stehen mehrere gleichartige Fahrzeuge zur Verfügung, deren maximale Ladekapazität mit Q bezeichnet wird. Das Zeitfenster [a 0 , b 0 ] wird als Depotöffnungszeit bezeichnet und legt den frühest möglichen Abfahrtszeitpunkt der Fahrzeuge vom sowie die spätest zulässige Ankunft dieser am Depot fest.

Für die spätere Modellbildung werden folgende vereinfachende Annahmen über die Realität getroffen (vgl. Röscher (1993) und Trochelmann (1980)):

• Alle Betrachtungen beziehen sich auf ein Ein-Perioden-Modell. Die Betrachtung über mehrere Perioden ist nicht vorgesehen, da beispielsweise in der Realität selten Informationen über eine Periode hinaus bekannt sind. Die Länge einer Periode entspricht in der Regel einem Tag.

• Der Bedarf jedes Kunden wird auf genau einer Tour gedeckt. Eine Aufteilung des Bedarfs eines Kunden auf mehrere unterschiedliche Touren ist nicht möglich. Dies kann durch technische oder organisatorische Gründe bedingt sein.

• Für die Auftragserledigung steht am Depot stets eine ausreichend große Menge an Fahrzeugen V , mit v ∈ V zur Verfügung. Diese Annahme begründet sich in der Überlegung, dass es dem Unternehmer jederzeit möglich ist, Kundenaufträge, die die Kapazitäten des Unternehmens überschreiten würden, abzulehnen. Es ist außerdem nicht ungewöhnlich, in kapazitätsüberschreitenden Situationen zusätzlich Fahrzeuge anzumieten. Dabei sei auf die Homogenität der gesamten Fahrzeugflotte hingewiesen, so dass sich das Ladevolumen bzw. die Geschwindigkeit der einzelnen Fahrzeuge praktisch nicht unterscheidet.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 7

• Alle eingesetzten Fahrzeuge verlassen das Depot zum frühest möglichen Zeitpunkt a 0 . In der Praxis bedeutet dies einen üblichen, einheitlichen Arbeitsbeginn aller Fahrer. Zudem wird so das Depot frühzeitig frei um beispielsweise die Auslieferungen für den Folgetag vorzubereiten.

• Jedes Fahrzeug übernimmt genau eine Tour. Sie beginnt mit dem Verlassen des Depots und endet nach der Belieferung aller sich auf dieser Tour befindlichen Kunden wieder am Depot. Die Übernahme mehrerer Touren durch das identische Fahrzeug ist in der Realität nur in den seltensten Fällen sinnvoll. Sie eignet sich nicht, falls wie üblich, die zurückzulegenden Distanzen zwischen Depot und Kunden relativ groß sind und somit das Einhalten der Depotöffnungszeit die größte Herausforderung der Tourenplanung ist.

• Durch Kenntnis der Standorte von Kunden und Depot in Form von Koordinaten sind auch die Distanzen d i, j zwischen je zwei verschiedenen Kunden bzw. zwischen Kunde und Depot bekannt. Diese werden als euklidisch angenommen. Dabei erfüllen alle Distanzen die Dreiecksungleichung. Damit wird sichergestellt, dass die direkte Verbindung zwischen Kunde i zu Kunde j bzw. zum Depot nicht länger als ein Umweg über andere Kunden ist.

• Die Geschwindigkeit der Fahrzeuge wird als identisch angenommen und ist pro-portional zu den Distanzen d i, j . Gewöhnlich entspricht dabei eine Zeiteinheit einer Distanzeinheit. Die benötigte Fahrzeit zwischen zwei Kunden wird mit t i, j angegeben.

Für die Optimierung des Tourenplanungsproblems wird üblicherweise eine hierarchische Zielsetzung unterstellt. Dabei liegt das Hauptaugenmerk auf der Minimierung der benötigten Touren, also den benötigten Fahrzeugen um alle Kunden zulässig zu bedienen. Die Minimierung der dabei zurückgelegten Wegstrecke über alle Touren wird dabei als sekundäres Ziel formuliert. Eine zulässige Lösung ist gegenüber einer anderen umso höher zu bewerten, je niedriger die Anzahl der benötigten Touren ist. Haben zwei Lösungen die identische Anzahl an Touren, ist diejenige Lösung höher zu bewerten, die eine geringere zurückgelegte Gesamtdistanz aufweist. Im Extremfall kann dies bedeuten, dass eine zulässige Lösung, die im Vergleich zu einer anderen lediglich ein Fahrzeug weniger einsetzt, aber gleichzeitig eine wesentlich höhere Gesamtdistanz besitzt, bevorzugt wird. Eine zulässige Lösung wird dann als Tourenplan bezeichnet. Dieser sammelt unter anderem Informationen über die Anzahl der benötigten Touren, die Reihenfolge der Kunden innerhalb einer Tour und lässt eine Aussage über die zurückgelegte Gesamtfahrstrecke zu.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 8

Ein Tourenplan wird nur dann als zulässig betrachtet, falls folgende Restriktionen stets streng eingehalten werden:

• Der kumulierte Bedarf der Kunden innerhalb jeder Tour übersteigt nicht die Gesamtkapazität Q des eingesetzten Fahrzeugs. Dieser kumulierte Bedarf wird im Späteren auch als „Bedarf der Tour“ bzw. „Tourbedarf“ bezeichnet.

• Jede Tour beginnt und endet am Depot und besitzt wenigstens einen Kunden.

• Es gibt keine zwei verschiedene Touren in denen ein und derselbe Kunde vorkommt. Das heißt, ein Kunde kann nicht von zwei Fahrzeugen beliefert werden. Des Weiteren muss sichergestellt sein, dass jeder Kunde genau einer Tour zuge-ordnet wird.

• Jeder Kunde wird auf seiner ihm zugeordneten Tour genau einmal besucht. Das beinhaltet das Ankommen am und Verlassen des Kunden durch das eingesetzte Fahrzeug. Dies schließt unter anderem Kurzzyklen innerhalb einer Tour aus.

• Die Belieferung jedes Kunden muss innerhalb des ihm zugeordneten Zeitfensters erfolgen. Eine Belieferung davor bzw. danach ist unzulässig. Dabei ist ein verfrühtes Eintreffen am Kunden zulässig, da in diesem Fall von einer kostenneutralen Wartezeit bis zum frühest möglichen Beginn a i des Entladevorgangs am Kunden i ausgegangen wird. Spätestens zum Zeitpunkt b i muss der Entladevorgang am Kunden i beginnen.

• Jedes Fahrzeug verlässt den Kunden erst nach Abschluss des Entladevorgangs. Dafür sind die vorgegebenen Servicedauern s zu beachten. Ein Fahrzeug kann also den Kunden frühestens nach Beginn des Entladevorgangs plus der für den Kunden vorgesehenen Servicedauer verlassen.

• Jedes Fahrzeug verlässt das Depot pünktlich zur frühest möglichen Zeit a 0 und kehrt spätestens zum Zeitpunkt b 0 zum Depot zurück.

Es wird ferner dem betrachteten Tourenplanungsproblem unterstellt, eine oben genannte Bedingungen erfüllende, zulässige Lösung zu besitzen. Dies impliziert, dass der Bedarf eines beliebigen Kunden i nicht größer ist als die Gesamtkapazität Q eines Fahrzeugs. Zudem hält die Feststellung der Existenz wenigstens einer zulässigen Lösung fest, alle Kunden innerhalb der angegebenen Zeitfenster zu erreichen, und zwar so, dass die Rückkehr eines Fahrers von seiner Tour zum Depot nicht nach dessen maximaler Öffnungszeit b 0 erfolgt.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 9

2.2.2 Mathematische Modellbildung

Zur Formulierung eines mathematischen Modells des Tourenplanungsproblems mit Zeitfensterrestriktionen bietet sich die Übertragung auf einen bewerteten, ungerichteten Graphen G = (W, E) an. Ein Graph ist ein Mengensystem von zwei Mengen: einer nicht leeren Knotenmenge W , sowie einer Kantenmenge E ⊂ W × W , wobei jedem e ∈ E eindeutig zwei Knoten w ∈ W zugeordnet sind. In der Knotenmenge W ist die Menge der Kunden H = {1, ..., n} sowie das Depot = {0} enthalten. Jedem Kunden wird so eine beliebige aber feste Nummer zugeordnet und kann durch diese eindeutig identifiziert werden. Die Kantenmenge E ordnet jeweils zwei verschiedenen Knoten i ∈ W , j ∈ W , mit i = j eine Distanz d i, j > 0 sowie eine Fahrtzeit t i, j > 0 zu. Für i = j sind die Distanzen d i, j sowie die Fahrtzeiten t i, j nicht relevant und werden daher auf 0 gesetzt.

Eine zulässige Lösung wird als Tourenplan TP bezeichnet und lässt sich mittels der binären Entscheidungsvariable x v i, j beschreiben. Sie gibt an, ob die Kante (i, j) ∈ E von

Fahrzeug v ∈ V befahren wird, also eine Fahrt des Fahrzeugs v von i, mit i ∈ W , nach j, mit j ∈ W , erfolgt oder nicht. Findet eine solche Fahrt statt, gilt x v i, j = 1, andernfalls ist x v i, j = 0. Falls die binäre Entscheidungsvariable den Wert 1 annimmt, bezeichnet man den Knoten i als Vorgänger des Knotens j und j als Nachfolger des Knotens i.

Durch die Einführung der weiteren Variable S v i kann für alle v ∈ V und i ∈ H der Service-

beginn am Kunden i angegeben werden, so fern der Kunde i von Fahrzeug v beliefert wird. Durch die Voraussetzung, dass jedes Fahrzeug das Depot zum frühest möglichen Zeitpunkt verlässt, gilt für alle v ∈ V , S ^v 0 = a 0 . Falls die binäre Entscheidungsvariable x v i, j den Wert 1 annimmt, berechnet sich der Servicebeginn am Kunden j durch die Gleichung: S v j = max{S v i + s i + t i, j , a j }. Dies begründet sich aus der oben genannten Annahme, bei Eintreffen vor dem frühest möglichen Servicebeginn a j am Kunden j dort bis zur Öffnung des Zeitfensters zu warten.

^m Die Folge T v = {w i } ist genau dann eine zulässige Tour von Fahrzeug v ∈ V mit den i=1

Tourelementen w i ∈ W falls folgende Bedingungen erfüllt werden:

1. Die Tour beginnt am Depot: w 1 = 0.

2. Die Tour endet am Depot: w m = 0.

3. Die Tour besteht aus wenigstens einem Kunden: m ≥ 3.

4. Die Tour wird nicht durch das Depot unterbrochen: w i = 0 für alle i ∈ {2, ..., m − 1}.

5. Innerhalb der Tour kommt jeder Tourkunde genau einmal vor: w i = w j für alle i ∈ {2, ..., m − 1}, j ∈ {2, ..., m − 1} mit i = j.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 10

6. Zwischen je zwei aufeinanderfolgenden Tourelementen besteht eine direkte Verbindung:

• (w i , w i+1 ) ∈ E,

• x ^v = 1,

^w i ^,w i+1

• S ^v = max{S ^{v w} i + s ^w i + t ^w i ^,w i+1 , a ^w i+1 },

^w i+1

für alle i ∈ {1, ..., m − 1}.

7. Der Servicebeginn S v

a ^w i ≤ S ^{v w} i ≤ b ^w i , für alle i ∈ {1, ..., m}.

8. Die kumulierte Liefermenge der Tour überschreitet nicht die Gesamtkapazität Q

des Fahrzeugs:

Die Vereinigung aller zulässigen Touren bildet eine zulässige Lösung, den Tourenplan T v , wenn gilt: TP = v∈V

1. Jeder Kunde wird bedient: Für alle i ∈ H existiert genau ein v ∈ V und genau ein j ∈ W , so dass x v i, j = 1 ist.

2. Die Touren T v \ {0} mit v ∈ V sind paarweise disjunkt zueinander.

Durch Hinzunahme der beiden Ziele, „Minimierung der Fahrzeuganzahl“ und „Minimierung der zurückgelegten Gesamtdistanz“ wird die mathematische Formulierung des Tourenplanungsproblems mit Zeitfensterrestriktionen komplettiert:

(Z) lexmin z(TP) =

(a)

(b)

Die lexikographisch aufgebaute Zielfunktion z(TP) besteht aus den beiden skalaren Funktionen f (TP) und g(TP). Die Funktion f (TP), die unter (a) angegeben ist, beschreibt die Anzahl der benötigten Touren. In Gleichung (b) ist die Funktion g(TP) illustriert, die die zurückgelegte Gesamtfahrstrecke berechnet. Entsprechend den Prämissen einer hierarchischen Optimierung hat die Minimierung der Funktion f (TP) höchste Priorität. Zweitrangiges Ziel ist die Minimierung von g(TP). Diese hierarchische Zielstellung wird in (Z) durch das Präfix „lex“ für die lexikographische Minimierung berücksichtigt.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 11

In der heutigen Literatur findet sich auch häufig nachfolgende Modellierung des Tourenplanungsproblems, das dort als lineares Vektoroptimierungsproblem gestellt wird (vgl. Solomon u. Desrosiers (1988) und Homberger (2000)):

Die in Gleichung (2.1) bis (2.3) definierte lexikographische Zielfunktion soll unter den Nebenbedingungen (2.4) bis (2.11) minimiert werden. Durch die Formulierung in Gleichung (2.4) wird sichergestellt, dass jeder Kunde von genau einem Fahrzeug genau einmal besucht wird. Ein Überschreiten der Fahrzeugkapazität auf einer Tour wird durch

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 12

die Bedingung (2.5) verhindert. Die beiden nachfolgenden Restriktionen (2.6) und (2.7) garantieren, dass jedes Fahrzeug das Depot höchstens einmal in Richtung eines Kunden verlässt bzw. das Depot höchstens einmal von einem Kunden aus erreicht. Präziser könnte man fordern, dass die beiden Summen nur die Werte 0 und 1 annehmen dürfen. In Gleichung (2.8) wird beschrieben, dass jedes Fahrzeug, dass einen Kunden erreicht diesen auch wieder verlässt. Dabei muss das Fahrzeug den Kunden zulässig innerhalb des vorgegebenen Zeitfensters zum frühest möglichen Zeitpunkt nach dessen Ankunft bedienen, was in (2.9) und (2.10) festgehalten ist. Als letzte Bedingung wird in (2.11) von der binären Entscheidungsvariable x v i, j gefordert, nur die beiden Werte 0 und 1 anzunehmen.

2.2.3 Komplexitätsuntersuchung des VRPTW

Wie schon in der Einleitung erwähnt, zeigten Lenstra u. Kan (1981), dass das Tourenplanungsproblem mit Zeitfensterrestriktionen zu den N P-harten Problemen gehört. Dieser Abschnitt widmet sich der Untersuchung des VRPTW bezüglich seiner Komplexität und der Frage, warum dieses Problem so schwer zu lösen ist.

Die Komplexitätstheorie, ein Teilbereich der theoretischen Informatik, beschäftigt sich mit der Untersuchung und Eingrenzung vorliegender Probleme bezüglich ihrer „Schwierigkeit“. Dabei unterscheidet sie zwischen verschiedenen sequentiellen Komplexitätsklassen. Zwei der wichtigsten Klassen sollen kurz anhand von Entscheidungsproblemen, also Problemen, die mit „ja“ oder „nein“ beantwortet werden können, vorgestellt werden (vgl. Reischuk (1990)):

1. Komplexitätsklasse P: Diese Klasse umfasst alle Entscheidungsprobleme, die mit einem deterministischen Algorithmus in höchstens polynomialer Zeit gelöst werden können. Unter einem deterministischen Algorithmus versteht man ein Verfahren, in dem der Programmablauf unter konstanten Bedingungen bestimmt ist und somit in jedem Zustand reproduzierbare Ergebnisse erzielt werden. Die Komple-

xitätsklasse P besitzt eine Komplexitätsschranke von POL(T ) :=

ist T : N → N eine Funktion.

2. Komplexitätsklasse N P: In der Komplexitätsklasse N P befinden sich alle Entscheidungsprobleme, die in höchstens polynomialer Zeit durch einen nichtdeterministischen Algorithmus gelöst werden können. Der Nichtdeterminismus des Verfahrens beschreibt die Möglichkeit für einen Übergang von einer Stufe zur anderen innerhalb einer Berechnung mehr als nur eine Entscheidung zur Verfügung zu haben. Die Wahl des Übergangs ist hierbei im Gegensatz zum deterministischen Modell nicht vorhersagbar und quasi zufällig. Dabei gilt P ⊆ N P. Dies impliziert,

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 13

dass jedes Problem aus P in höchstens polynomialer Zeit durch einen nichtdeterministischen Algorithmus gelöst werden kann. Ein Problem P ∈ N P, P / ∈ P gilt

bis heute jedoch als nicht effizient lösbar, da die Frage nach N P = P offen ist.

(a) Die Menge N P-hart: In der Menge der N P-harten Probleme befinden sich

(b) Die Menge N PC: Die Menge N PC bezeichnet die N P-vollständigen Pro-

Dieser komplizierte Sachverhalt soll im nächsten Beispiel anhand des Traveling Salesman Problems näher erörtert werden.

Beispiel: Gegeben sei ein ungerichteter, vollständiger, bewerteter und schlichter Graph G = (W , E, c). Die Knotenmenge W = {1, ..., n} repräsentiert dabei n Orte. Die Kantenmenge E ⊂ W × W enthält die Verbindungen zwischen je zwei Knoten i ∈ W und j ∈ W , mit i = j und ordnet ihnen eine Bewertung c i, j ∈ N zu. Für i = j gilt: c i, j = ∞. Gesucht ist nun die kürzeste Rundreise, auf der alle Orte genau einmal besucht werden. Eine solche Rundreise beliebiger Länge wird als Hamiltonscher Kreis bezeichnet. Um dieses Problem als Entscheidungsproblem aufzufassen, könnte man folgende Fragestellung formulieren: Gibt es eine Rundreise, die kürzer ist als eine vorgegebene Rundreise mit bekannter Länge? In (Reischuk, 1990, S. 243-245) wird bewiesen, dass das Hamiltonsche Kreisproblem ein N P-vollständiges Problem darstellt. Da es ein Spezialfall des TSP ist, indem die Bewertung jeder Kante e ∈ E gleich eins entspricht und eine obere Schranke bezüglich der Länge von n = |W | (Besuche alle Orte auf der Rundreise) besitzt, ist das

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 14

TSP als Verallgemeinerung nicht leichter zu lösen und ebenfalls N P-vollständig. Dabei spielt es keine Rolle, ob bei der Formulierung des TSP von einem vollständigen oder unvollständigen Graphen G ausgegangen wird.

Mit diesem Wissen kann nun die Komplexitätseingrenzung des Tourenplanungsproblems mit Zeitfensterrestriktionen getroffen werden. Da das Traveling Salesman Problem selbst schon N P-vollständig ist und das VRPTW wiederum eine Verallgemeinerung des TSP darstellt, ist folglich das VRPTW als N P-vollständig einzustufen. Exakte Lösungsverfahren besitzen also mindestens eine exponentielle Zeitkomplexität, deren Einsatz nur für Probleme geringer Größe zu verantworten ist. Nachfolgende Tabelle soll ein Gefühl für den Zusammenhang zwischen Problemgröße, Komplexität und dem damit verbundenen Rechenaufwand vermitteln. Dabei wird von der kleinsten exponentiellen Zeitkomplexität O(2 ⁿ ) ausgegangen. Zudem wird unterstellt, dass der derzeit leistungsstärkste Rechner, BlueGene/L von IBM zur Verfügung steht, der in der Lage ist, 280,6 Billionen Rechenoperationen pro Sekunde auszuführen. Dies entspricht einer Leistung von ungefähr 35000 modernen Personal Computern.

Wie Abb. 2.3 verdeutlicht, ist es selbst unter den günstigsten Bedingungen nicht sinnvoll große Probleme mit exakten Algorithmen zu lösen. Im Sinne des VRPTW scheint die Verwendung eines exakten Verfahrens für eine Größe von n = 60 Kunden gerade noch vertretbar. Kommen zusätzlich 10 Kunden hinzu ist an eine Tagesplanung durch Einsatz exakter Algorithmen nicht mehr zu denken. Die bereits erwähnten Benchmark Probleme von Solomon (1987) besitzen eine Problemgröße von n = 100 Kunden, die in der Praxis eher als „klein“ angesehen wird. Für ein exaktes Lösungsverfahren ist diese Problemgröße jedoch nicht in akzeptabler Zeit realisierbar. Die Verwendung von guten heuristischen Verfahren ist daher ab einer kritischen Problemgröße unumgänglich.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 15

Sie garantieren zwar nicht die optimale Lösung, sind aber heute soweit entwickelt, in akzeptabler Zeit eine hinreichend gute Annäherung an das Optimum zu erreichen.

2.2.4 Typologie der Zeitfensterrestriktionen

Die N P-härte des VRPTW liegt nicht zuletzt im Vorhandensein von Zeitfensterrestriktionen begründet. In Solomon u. Desrosiers (1988) wird gezeigt, dass das Tourenplanungsproblem mit Zeitfensterrestriktionen wesentlich schwieriger zu lösen ist als das Standardproblem der Tourenplanung. In der Praxis jedoch kann selten auf diese Restriktionen verzichtet werden. Die Gründe hierfür können vielschichtig sein. In der Branche der Paketzusteller muss beispielsweise die Auslieferung der Ware innerhalb der Öffnungszeiten eines Betriebes erfolgen, da die Ware von einem Mitarbeiter entgegen genommen werden muss. Ein Kioskbesitzer wiederum ist auf eine Belieferung vor Öffnung seines Geschäftes angewiesen, damit die aktuelle Tageszeitung auch dem ersten Kunden rechtzeitig angeboten werden kann. Kunden aus der Just-In-Time Fertigung hingegen sind auf eine fast punktgenaue Lieferung ihrer Ware angewiesen, da für eine zu frühe Lieferung keine Lagerkapazitäten bereitstehen und eine zu späte Lieferung Störungen im Produktionsfluss verursachen.

In der Tourenplanung können verschiedene Ausprägungen der Zeitfenster auftreten. Die Zeitfensterbreite b i − a i kann sehr klein bzw. auch sehr groß sein. Dabei haben manche Kunden unter Umständen keine zeitlichen Präferenzen bezüglich ihrer Belieferung. Andere hingegen geben nur einen frühest möglichen bzw. einen spätest möglichen Belieferungszeitpunkt an. Für solch einseitig formulierte Restriktionen bezüglich des Zeitfensters von Kunde i gilt somit: [a i , ∞) bzw. (−∞, b i ]. Um eine Quantifizierung der vorliegenden Zeitfenster aller Kunden zu erreichen werden zwei Merkmale herangezogen. Zum einen der prozentuale Anteil γ der Kunden mit Zeitfenstervorgaben und zum anderen die sogenannte Zeitfensterdichte δ (vgl. Homberger (2000)). Die Zeitfensterdichte wird hierbei als Index zur Bestimmung der vorliegenden Hauptaufgaben des VRPTW aufgefasst:

(a) Planung der einzelnen Touren. Dies beinhaltet im Wesentlichen die Reihenfolgebestimmung der einzelnen Kunden innerhalb einer Tour. Dies wird im angelsächsischen als „routing“ bezeichnet.

(b) Planung der einzelnen Fahrzeugumläufe für die spätere Durchführung der Touren. Im englischen Sprachgebrauch als „scheduling“ bezeichnet.

(c) Gemischte Bearbeitung der unter (a) und (b) genannten Aufgaben.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung Seite 16

Je nachdem welche Ausprägung die Zeitfenster des vorliegenden Problems besitzen, kann es unterschiedlich schwer zu lösen sein. Bei vielen sehr engen Zeitfenstern ist beispielsweise die Reihenfolge der Abarbeitung der Kunden weitaus weniger frei bestimmbar als bei einem Problem mit relativ großzügigen Zeitfenstern der Kunden. Hier ist quasi die Reihenfolge der Kunden durch ihre Zeitfensterrestriktionen determiniert. Die folgende Definition der Zeitfensterdichte δ gibt das Verhältnis zwischen der durchschnittlichen Zeitfensterbreite aller Kunden und der maximalen Zeitfensterbreite wieder (vgl. (Homberger, 2000, S. 25) und (Bergmann, 1998, S. 35)):

Liegt die Zeitfensterdichte δ unterhalb zehn Prozent, wird in der Literatur von einem Scheduling Problem ausgegangen, da die Zeitfenster relativ eng vorgegeben sind. Ist δ größer als fünfzig Prozent, so sind die Kundenzeitfenster relativ weit bemessen und man spricht von einem Routing Problem. Sollte δ größer zehn und kleiner fünfzig Prozent sein, sind sowohl schmale wie breite Zeitfenster vorhanden und es liegt ein gemischtes Problem von Routing und Scheduling zu Grunde.

Die vorgestellte Berechnungsvorschrift in (2.12) berücksichtigt jedoch keine Spezialfälle. So kann es durchaus vorkommen, das sehr wenige Kunden sehr große Zeitfenster besitzen und die restlichen Kunden sehr kleine Zeitfenster aufweisen. Versucht man nun die Zeitfensterdichte durch Berechnung des arithmetischen Mittels im Bezug auf die maximale Zeitfensterbreite zu ermitteln, kommt es zwangsläufig zu falschen Interpretationen. Eine bessere Darstellung wird nachfolgend erläutert:

In Gleichung (2.13) wird für jeden Kunden i ∈ H ein eigener Index ermittelt. Dabei gibt δ ^neu den prozentualen Anteil des Kundenzeitfensters [a i , b i ] im Bezug auf die Depotöff-

i

nungszeit wieder. Dies begründet sich aus der Annahme, dass für jeden Kunden i ∈ H gelten muss: a i ≤ S i ≤ b i mit a 0 < S i < b 0 . Dies bedeutet, dass der Servicebeginn S ⁱ am Kunden i nicht nur durch sein eigenes Zeitfenster sondern auch durch die Depotöff-

ⁿ nungszeit [a 0 , b 0 ] begrenzt ist. Mit dem ermittelten Vektor δ ^neu = (δ neu i=1 kann nun für i )

alle möglichen Ausprägungen an Kundenzeitfenster eine genaue Aussage bezüglich des Problemcharakters getroffen werden:

(a) Scheduling: Es existieren mehr als neunzig Prozent an Kunden, deren Zeitfenster einen kleineren Anteil als zehn Prozent der Depotöffnungszeit besitzen.

Armin Bayer Hochschule für Technik, Wirtschaft und Kultur Leipzig