Dynamische Tourenplanung mit Zeitfenstern I

Vorwort

Die vorliegende Arbeit ist so konzipiert, dass praktische Aspekte von Tourenplanungsproblemen in den Vordergrund gestellt werden. Anhand eines realitätsnahen Beispiels werden ausgewählte Verfahren vorgestellt und auch angewendet. Das theoretische Hintergrundwissen wird natürlich auch entsprechend behandelt und vorgestellt. Ohne eine fundierte theoretische Basis ist die systematische Lösung von komplexen Problemstellungen, zu denen Tourenplanungprobleme zweifelsohne gehören, nahezu unmöglich. Bei der Vorstellung der einzelnen Verfahren wird der theoretische Aspekt jedoch zugunsten einer umfangreicheren Darstellung praktischer Anwendungsmöglichkeiten so weit wie möglich reduziert. Daher war es auch nie mein Ziel, so viele Verfahren wie möglich in dieser Arbeit vorzustellen. Es wurden solche Verfahren ausgewählt, anhand derer besonders wichtige Aspekte hinsichtlich einer Umsetzung auf in der Realität vorkommende Probleme aufgezeigt werden konnten. Hauptsächlich ging es mir bei dieser Arbeit darum, zu verdeutlichen, dass es bei konkret vorliegenden Problemen nicht darum gehen kann, ein einzelnes Verfahren auszuwählen und anzuwenden. Vielmehr geht es darum, durch geeignete Modifikationen bestehender Verfahren eine zum konkreten Problem passende Optimierungsroutine zu entwickeln. Gerade bei sehr realitätsnahen Problemstellungen, zu denen auch die dynamische Tourenplanung mit Zeitfenstern zählt, können einzelne Standardverfahren nur den Ausgangspunkt der Problembewältigung darstellen.

Vor dem Abschluss dieser einleitenden Worte möchte ich die Gelegenheit nutzen, mich für die entgegengebrachte Unterstützung zu bedanken. Zunächst bedanke ich mich bei Herrn Dr. Kulmann, der mir durch zahlreiche e-Mails immer wieder interessante Denkanstöße gegeben hat und mich auch in kritischen Situationen immer unterstützt hat. Des Weiteren bedanke ich mich bei meiner langjährigen Freundin und ehemaligen Schulkameradin Frau Mansfeld für ihre wertvollen Anregungen und Kritiken. Ein besonderer Dank gilt meiner Lebensgefährtin Frau Krybus, die mich während der Fertigstellung dieser Arbeit nach allen Kräften und in jeglicher Hinsicht unterstützt hat.

Lars Laboch

  Dynamische Tourenplanung mit Zeitfenstern  II

Inhaltsverzeichnis

  Vorwort  I

  Abbildungsverzeichnis  IV

Tabellenverzeichnis   V

  Algorithmenverzeichnis  VI

  Abkürzungsverzeichnis.  VII

  Symbolverzeichnis  VIII

1.  Grundlagen zur Tourenplanung  1

1.1  Die Tourenplanung im betriebswirtschaftlichen Kontext.  2

1.2  Tourenplanung als Disziplin des Operations Research  3

1.3  Gang der Problemanalyse und der Problemlösung.  4

   5

2.  Zur Vielfältigkeit von Tourenplanungsproblemen.  

2.1  Kriterienkatalog zur Problemidentifizierung.  5

2.1.1  Die Ausgestaltung des Netzwerks  5

2.1.2  Die Beschaffenheit des Fuhrparks  6

2.1.3  Die Zeit als wichtiger Einflussfaktor  7

2.1.4  Verschiedene Zielsetzungen  7

2.2  Grundmodelle der Tourenplanung.  9

2.2.1  Das Handlungsreisendenproblem  9

2.2.2  Das Standardproblem der Tourenplanung  10

2.2.3  Kombinations- und Erweiterungsmöglichkeiten der Modelle.  11

2.3  Berücksichtigung dynamischer Aspekte.  14

2.4  Zusammenfassung und Problempräzisierung  18

3.  Lösungsmöglichkeiten und Szenariokonstruktion  20

3.1  Konzepte zur Lösung des DTRP  20

3.1.1  Heuristische Verfahren für Tourenplanungsprobleme  22

3.1.2  Spezielle Lösungsansätze für dynamische Problemstellungen.  23

3.1.3  Tourenoptimierung mit Hilfe von Metaheuristiken.  23

3  2 Konstruktion eines DTRP - Szenarios  24

  Dynamische Tourenplanung mit Zeitfenstern  III

4.  Konstruktions- und Verbesserungsverfahren.  28

4.1  Konstruktionsverfahren  29

4.1.1  Das Savingsverfahren  29

4.1.2  Anwendungsmöglichkeiten von Einfügeheuristiken  34

4.1.3  Anwendung einer „nächster Nachbar“ Heuristik.  36

4.1.4  Anwendungsmöglichkeiten zweistufiger Verfahren  37

4.2  Verbesserungsverfahren  38

4.2.1  Intraroutenverbesserung.  39

4.2.2  Interroutenverbesserung.  41

4.2.2.1  Das 2-opt Kantentauschverfahren  41

4.2.2.2  Verbesserung anhand multipler Kriterien.  43

4.2.3  Verfahrensvergleich und Ergebnisdetails  46

4.3  Anmerkungen zur Optimalität  48

5.  Einbeziehung veränderlicher Informationen.  50

5.1  Klassifizierung von Änderungsmöglichkeiten  50

5.2  Update eines bestehenden Tourenplans.  53

5.3  Integration statischer Algorithmen in die Updateroutine  55

5.4  Betrachtung von Änderungen im Beispielproblem  57

6.  Vorstellung weiterer Lösungsmöglichkeiten  62

7.  Eine kritische Rekapitulation mit Ausblick  67

Anhang. 69   

  Literaturverzeichnis  75

  Dynamische Tourenplanung mit Zeitfenstern  

  Abbildungsverzeichnis  

  Abbildung 1: Skizze eines m-TSPTW mit zwei Fahrzeugen.  

  Abbildung 2: Illustration einer lokalen Veränderung in einer dynamischen Umwelt.  

  Abbildung 3: Beispielgraph G, erstellt auf der Grundlage eines real existierenden  

  Straßennetzes.  

  Abbildung 4: Kantentausch mit 2-opt  

  Abbildung 5: Veranschaulichung des bislang kostengünstigsten Tourenplans  

Im  Anhang enthaltene Abbildungen  

  Abbildung 6: Geographische Grundlage für das verwendete Beispiel  

  Abbildung 7: Erstellung des Beispielgraphen anhand geographischer Gegebenheiten  

  Dynamische Tourenplanung mit Zeitfenstern  V

  Tabellenverzeichnis  

Tabelle 1:  Kriterienkatalog zur Problemcharakterisierung.  8

Tabelle 2:  Übersicht aller relevanten Informationen aus Abbildung 1.  14

Tabelle 3:  Übersicht aller Daten des Tourenproblems.  28

Tabelle 4:  Savingswerte für das Beispielproblem.  30

Tabelle 5:  Tourenpläne für verschiedene Werte von F  32

Tabelle 6:  Detaillierte Übersicht eines durch den Savings-Algorithmus mit F  1

  erstellten Tourenplans.  33

Tabelle 7:  Tourenpläne verschiedener Konstruktionsverfahren  38

Tabelle 8:  Beziehungsmatrix M B und Änderungsmöglichkeiten der Ausgangstour  39

Tabelle 9:  Tourenpläne nach Anwendung von 2-opt und 2-opt  42

Tabelle 10:  Der beste für das Beispielproblem ermittelte Tourenplan  48

Tabelle 11:  Verschiedene Lösungen zur Integration eines Kunden  58

Tabelle 12:  Mögliche Tourenpläne nach Bekanntwerden einer Servicezeit-  

  verlängerung  60

Tabelle 13:  Skizzierung des kostengünstigsten Tourenplans nach drei Änderungen.  61

Im  Anhang enthaltene Tabellen  

Tabelle 14:  Distanzmatrix D für den Graphen G aus Abbildung 3, Seite 27  71

Tabelle 15:  Wegematrix P für den Graphen G aus Abbildung 3, Seite 27  72

Tabelle 16:  Zeitmatrix Z M für den Graphen G aus Abbildung 3, Seite 27  73

Tabelle 17:  Kostenmatrix C für einzelne Teilstrecken des Graphen G aus Abbildung  

  3, Seite 27  74

  Dynamische Tourenplanung mit Zeitfenstern  VI

  Algorithmenverzeichnis  

  Algorithmus 1: Der Tripel Algorithmus  25

  Algorithmus 2: Ein modifizierter Savings-Algorithmus  31

  Algorithmus 3: Eine mögliche Einfügeheuristik  35

  Algorithmus 4: Tourenkonstruktion durch eine NN - Heuristik.  37

  Algorithmus 5: Das 2-opt Verfahren  40

  Algorithmus 6: Die 2-opt Interroutenverbesserung.  43

  Algorithmus 7: Ein universeller Verbesserungsalgorithmus  45

  Algorithmus 8: Updateprozedur bei zusätzlichen Aufträgen  56

  Dynamische Tourenplanung mit Zeitfenstern  VII

  Abkürzungsverzeichnis  

  BARTOC : Booking Algorithm for Routing and Timing of Customers.  

  Cm : Zentimeter.  

  DRIVE : Dynamic Routing of Independent Vehicles.  

  DTRP : Dynamic Travelling Repairman Problem in dieser Arbeit in der  

  Form zu verstehen, dass mehrere Mitarbeiter eingesetzt werden  

  und auch Zeitfensterrestriktionen berücksichtigt werden.  

  Km : Kilometer.  

  Km/h : Kilometer pro Stunde.  

  MACS-VRPTW : Multiple Ant Colony System for Vehicle Routing Problems  

  with Time Windows.  

  Min. : Minute.  

  m-TSPTW. : Handlungsreisendenproblem mit Zeitfensterrestriktionen und  

  mehreren Fahrzeugen bzw. Handlungsreisenden.  

  NN : Nächster Nachbar.  

  Std. : Stunde.  

  TSP : Travelling Salesman Problem Handlungsreisendenproblem.  

  TSPTW : Handlungsreisendenproblem mit Zeitfensterrestriktionen.  

  u.d.N. : Unter den Nebenbedingungen.  

  Unpr. : Kostenanteil unproduktiver Tätigkeiten.  

  VRP :  

  Vehicle Routing Problem.  

  VRPTW : Vehicle Routing Problem with Time Windows  

  Dynamische Tourenplanung mit Zeitfenstern  VIII

  Symbolverzeichnis  

  (f i , l i ) : Zeitfenster für Knoten bzw. Kunde i Angabe als Uhrzeit.  

  (x i , y i ) : Koordinatenwerte x und y des Knoten i.  

  0, i, , 0 : Kantenfolge mit Knoten 0, dem Depot, als Start- und Endpunkt. Wird  

  insbesondere zur Darstellung des Tourenverlaufs verwendet.  

  i,j : Kante mit den Endknoten i und j.  

  : Symbolisiert eine Teilmenge von n.  

n   

a  : Gewichtungsfaktor zur Strafkostenberechnung bei Wartezeiten vor dem  

  Endpunkt, welcher dem Depot entspricht, der Route.  

  ab i : Abfahrtszeit bei Kunden i Angabe als Uhrzeit.  

  an i : Ankunftszeit bei Kunden i Angabe als Uhrzeit.  

b  i : Servicebeginn bei Kunden i, Angabe als Uhrzeit.  

C  : Bezeichnet die Kostenmatrix.  

c  d : Durch das Fahrzeug über die Gesamtdistanz einer Tour verursachte Kosten.  

c  F : Fahrzeugkosten pro Kilometer hier 0,76  

c  ij : Kosten eines Weges zwischen Knoten i und Knoten j Angabe in Euro.  

c  L : Kosten einer Lösung bzw. zulässigen Tourenplans Angabe in Euro.  

c  M : Kosten des Mitarbeiter pro Stunde hier  24

c  t : Zeitabhängige Gesamtkosten des Mitarbeitereinsatzes Angabe in Euro.  

c  T : Kosten einer Tour Angabe in Euro.  

c  ü : Durch Verspätungen entstandene Kosten Angabe in Euro.  

c  üi : Kosten einer zulässigen Verspätung beim Kunden i Angabe in Euro.  

c  w : Durch unproduktive Tätigkeiten, insbesondere der Wartezeit, entstandene  

  Kosten Angabe in Euro.  

  00  

c  w0 : Strafkosten für ein Tourende vor 16 Uhr Angabe in Euro.  

c  wi : Kosten der Wartezeit bei Kunden i, Angabe in Euro.  

D  : Bezeichnet die Distanzmatrix.  

d  : Euklidischer Abstand. e  

  ij  

d  i0 : Entfernung von Kunden i zum Depot bzw. Knoten 0 Angabe in Kilometer.  

d  ij : Distanz zwischen Kunde i und Kunde j. Vorausgesetzt wird die Wahl eines  

  kürzesten Weges Angabe in Kilometer.  

d  r : Gesamtdistanz einer Route Angabe in Kilometer.  

  Insbesondere wird in Tabellen der Industriestandard verwendet, also 8,45 statt 8 27 Uhr  

  Dynamische Tourenplanung mit Zeitfenstern  IX

E  : Kantenmenge eines Graphen (engl. edge)  

e  : Bezeichnet eine einzelne Kante in G.  

f  e : Frühestmögliche Ankunftszeit beim Depot wenn keine Strafkosten anfallen  

  sollen, Angabe als Uhrzeit.  

f  i : Frühestmöglicher Servicebeginn bei Kunden i Angabe als Uhrzeit.  

G  : Symbol für einen Graphen.  

  G’ : Teilgraph bzw. Untergraph von G, mit G’ V’, E’  

G  V, E : Graph mit Knotenmenge V und Kantenmenge E.  

h  i : Bedarf bzw. nachgefragte Menge bei Kunden i, nur im Rahmen des VRP  

  relevant.  

  i, j. : Einzelne Kunden bzw. Knoten im Graphen.  

  job T : Tätigkeit desjenigen Mitarbeiters der die Tour T fährt zum Zeitpunkt z.  

k  : Index für ein einzelnes Fahrzeug, mit k 1, ,m.  

L  : Lösung des Tourenproblems bzw. Tourenplan.  

l  i : Spätestmöglicher Servicebeginn beim Kunden i, Angabe als Uhrzeit.  

m.  : Anzahl der Fahrzeuge in dieser Arbeit gilt m 3.  

M  B : Beziehungsmatrix zur Vorabprüfung hinsichtlich der Zulässigkeit einer Route.  

n  : Anzahl der Knoten in einem Graphen i 1, ,n ist zu interpretieren als  

  Knoten bzw. Kunde 1, , bis Knoten bzw. Kunde n.  

  N(L) : Menge der zur Lösung L benachbarten Lösungen. Die konkrete Definition von  

  „benachbart“ ist im Text angegeben.  

  NF i : Nachfolger von Knoten i auf dem kürzesten Weg zu Knoten j.  

NP.  : Abkürzung für „nicht polynomial“  

O  : Landausches Symbol, bezieht sich auf Komplexitätsangaben von Algorithmen.  

P.  : Bezeichnet die Wegematrix.  

Q  k : Kapazität des Fahrzeugs k.  

r.  : Variable für die Anzahl von getauschten Kanten beim r-opt Verfahren.  

  R(i) i : Menge der von Knoten i aus erreichbaren und von i verschiedenen Knoten.  

s  i : Benötigte Servicezeit bei Kunden i Angabe in Minuten.  

  SP T : Neuer geographischer Startpunkt der Tour T bei einer Änderung des bisherigen  

  Tourenplans.  

s  ü : Faktor zur Ermittlung der Strafkosten bei Verspätungen. Dies betrifft nur  

  Verspätungen bei Kunden, der Satz ist 0,35 pro Minute.  

  SZ T : Nächstmögliche Startzeit der Tour T bei einer Änderung des Tourenplans.  

  Insbesondere wird in Tabellen der Industriestandard statt regulärer Uhrzeiten verwendet  

  Dynamische Tourenplanung mit Zeitfenstern  X

t  ij : Für den Weg zwischen Knoten i und j benötigte Zeit Angabe in Minuten.  

T  : Abkürzung für Tour in der Regel mit einem Index für die Tournummer,  

  welche sich aus der Fahrzeugnummer ergibt, versehen. Die Darstellung ist  

  dann T k , mit k 1, ,m.  

t  r : Insgesamt für eine Route bzw. Tour benötigte Zeit Angabe in Minuten.  

u  : Bezeichnet einen „ungerouteten“ Kunden der in eine Tour eingefügt wird.  

ü  0max : Maximal zulässige Toleranz für Verspätungen beim Endpunkt Angabe in  

  Minuten.  

ü  i : Verspätung beim Kunden Angabe zumeist im Industriestandard, sonst genau  

in  Stunden und Minuten aufgeteilt.  

ü  max : Maximal zulässige Toleranz für Verspätungen bei den Kunden insgesamt  

  Angabe in Minuten.  

   i

ü  : Für den Kunden i maximal verfügbarer Toleranzwert bis ü max erreicht ist.  

  max  

  00  

Üz.  : Überstundenzuschlag bei Ankunft am Depot nach 17 Uhr.  

V  : Knotenmenge eines Graphen (engl. vertex)  

w  i : Wartezeit bei Kunden i Angabe zumeist im Industriestandard, sonst genau in  

  Stunden und Minuten aufgeteilt.  

4.  : Symbol für einen Iterationsschritt. Steht 4 im Index einer Variablen, so ist der  

  Wert der Variablen im 4-ten Iterationsschritt gemeint.  

z  : Aktuelle Zeit beim Eintreffen neuer Informationen.  

Z  : Zielfunktionswert.  

Z  k : Maximal zulässige Unterwegszeit für das Fahrzeug k.  

Z  M : Zeitmatrix.  

  Mathematische Symbole  

  : : Definiert als.  

  : Ist gleich.  

  : Ist nicht gleich.  

  : Entspricht etwa.  

  : Kleiner als.  

  : Kleiner gleich.  

  : Größer als.  

  : Unendlich.  

  : Summenzeichen  

  Dynamische Tourenplanung mit Zeitfenstern  XI

  : Quadratwurzel aus.  

χ  : Ist Element.  

ϖ  : Ist nicht Element.  

  : Leere Menge.  

  : Mengenklammer.  

4  : Vereinigt mit.  

3  : Geschnitten mit.  

  : Ist echte Teilmenge von.  

  : Ist Teilmenge von.  

  : „Malzeichen“  

  Zusätzliche Bemerkungen  

Im  Verlauf dieser Arbeit sind noch einige weitere Symbole und Kürzel verwendet worden.  

  Die Bedeutung der entsprechenden Symbole geht direkt aus dem Text hervor, so dass eine  

  Darstellung im Symbolverzeichnis nicht zweckmäßig wäre. Es handelt sich im Wesentlichen  

  um Kürzel die dazu verwendet werden, spezifische Punkte oder Variablen innerhalb  

  bestimmter Lösungskonzepte genau zu identifizieren. Des Weiteren sind noch spezielle  

  Parameter, die nur für einzelne Verfahren benötigt werden, nicht in das vorstehende  

  Verzeichnis aufgenommen worden  

Dynamische Tourenplanung mit Zeitfenstern 1

Kapitel 1

Grundlagen zur Tourenplanung

Bei Tourenplanungsproblemen geht es im Allgemeinen darum, Fahrzeugtouren hinsichtlich einer im Vorfeld zu benennenden Zielsetzung optimal einzuplanen. Die Fahrzeuge können dabei einer bereits existierenden Fahrzeugflotte angehören und somit als feste Größe betrachtet werden, oder die Planung der Fahrzeugflotte kann Bestandteil des Optimierungsprozesses sein. Die Aufgabe der Fahrzeuge und deren Fahrer besteht darin, an geographisch unterschiedlichen Punkten einen, wie auch ¹ immer gearteten, Service zu leisten.

Ein häufig verwendetes Zielkriterium ist die Minimierung der für den ² Tourenplan insgesamt benötigten Fahrtzeit. Darüber hinaus können aber je

nach konkreter Problemausprägung auch andere Zielsetzungen, wie zum Beispiel die Minimierung der Gesamtkosten des Tourenplans, die Minimierung nicht besuchter Kunden in einer Planperiode, oder eine ³ möglichst gleichmäßige Auslastung der Touren relevant sein. Als Restriktionen werden häufig die Fahrzeugkapazität und die Routenlänge ⁴ bzw. -zeit betrachtet. Eine weitere wichtige Restriktion stellen Zeitfenster dar. Zeitfenster besagen, dass es nur bestimmte Zeiten oder Zeitintervalle ⁵ gibt, innerhalb derer der Service stattfinden kann. Die bisher genannten Kriterien können sowohl Bestandteil einer statischen als auch einer dynamischen Problemstellung sein. Ein statisches Tourenplanungsproblem liegt dann vor, wenn alle problemrelevanten Daten bekannt sind und sich diese im Zeitablauf auch nicht mehr ändern. Bei einem dynamischen Tourenplanungsproblem können sich aber wichtige Daten im Zeitablauf ändern, so dass ein bereits optimaler Tourenplan gegebenenfalls modifiziert werden muss, damit die Erfüllung der ⁶ Zielsetzung unter Einhaltung aller Restriktionen gewährleistet bleibt.

¹ Siehe DOMSCHKE (1982, S. 131).

² Vgl. NEUMANN/MORLOCK (2002, S. 468).

³ Vgl. CHRISTOFIDES (1985, S. 435).

⁴ Siehe DOMSCHKE (1982, S. 132).

⁵ Siehe SOLOMON (1987, S. 254).

⁶ Vgl. SAVELSBERGH/SOL (1998, S. 475).

Dynamische Tourenplanung mit Zeitfenstern 2

Die Anwendungsgebiete der Tourenplanung sind sehr vielfältig. In der Praxis werden Touren von Spediteuren und Paketdiensten, von Taxi Unternehmen, von Kurier- und Rettungsdiensten sowie von öffentlichen ⁷ Verkehrsbetrieben geplant. Die Liste ist damit keinesfalls vollständig und soll nur einen ersten Eindruck über die Relevanz der Tourenplanung für praktische Problemstellungen liefern.

Der Fokus dieser Arbeit ist auf die Tourenplanung eines Reparaturdienstes gerichtet. Ein solches Dienstleistungsunternehmen wird von den Kunden beauftragt defekte Geräte oder Anlagen zu reparieren, wobei es sich bei solchen Unternehmen um Installationsfirmen für sanitäre Anlagen oder auch

um Reparaturdienste für elektronische Haushaltsgroßgeräte handeln kann.

Um eine solche Reparatur durchführen zu können, muss ein Mitarbeiter der

Firma den Kunden aufsuchen und das Gerät vor Ort instand setzen. Da der Kunde oftmals nicht den ganzen Tag über anwesend ist, sind Zeitfenster hier von besonderer Bedeutung. Zudem sind dynamische Aspekte zu

berücksichtigen, d.h. es sind nicht unbedingt alle problemrelevanten Daten

zu Beginn einer Planungsperiode bekannt. Es können neue Aufträge eingehen deren Erfüllung unter Beibehaltung des bestehenden Tourenplans nicht möglich ist, aber durch eine Planumstellung möglich wäre. In solchen Fällen ist eine Modifizierung des bestehenden Tourenplans unerlässlich. Bevor die Problemstellungen im Folgenden detaillierter beschrieben und behandelt wird, soll zunächst eine Einordnung der Tourenplanung in den betriebswirtschaftlichen Kontext und in das Forschungsgebiet des Operations Research erfolgen. Im Anschluss daran wird der weitere Verlauf der Untersuchung skizziert.

1.1 Die Tourenplanung im betriebswirtschaftlichen Kontext Die Tourenplanung lässt sich in das Aufgabengebiet der betriebs- wirtschaftlichen Logistik einordnen. In diesem Kontext besteht die Kernaufgabe darin, ein nachgefragtes Gut oder Produkt zum richtigen Zeitpunkt in der richtigen Menge am vereinbarten Übergabeort zu ⁸ minimalen Kosten bereitzustellen. Der Güterfluss lässt sich in diesem

Zusammenhang idealtypisch in die Phasen der Beschaffung, Produktion,

⁷ Vgl. GENDREAU/POTVIN (1998, S. 2).

⁸ Siehe hierzu LACKNER (2004, S. 6ff.).

Dynamische Tourenplanung mit Zeitfenstern 3

Absatz und Entsorgung einteilen. Die Tourenplanung ist dabei als ein Teilproblem der Distributionslogistik zu sehen. Hinsichtlich des Güterflusses ist die Distributionslogistik ihrerseits dem Absatz von Gütern oder Produkten zugeordnet. Das Aufgabenfeld der Distributionslogistik umfasst dabei die strategische Planung, wie zum Beispiel die Standortwahl, taktische Aufgabenstellungen, worunter beispielsweise die Festlegung des Lieferbereiches und der Fuhrparkgröße fallen, und eben auch operative ⁹ Entscheidungen wie die konkrete Planung der Touren. Zu beachten ist

hierbei, dass die einzelnen Teilaufgaben nicht isoliert voneinander betrachtet werden können, da zum Beispiel die Festlegung eines Liefergebietes die Größe des Fuhrparks, und somit die Tourenanzahl und Tourenlänge, beeinflusst. Umgekehrt können aber die hieraus resultierenden Touren bei zu hohen Kosten Einfluss auf strategische Entscheidungen, wie beispielsweise die Standortwahl, nehmen.

Auch wenn in der betriebswirtschaftlichen Logistik primär von Gütern ausgegangen wird, so ist ein enger Zusammenhang mit der hier behandelten Problemstellung gegeben. Ein Reparaturdienst bietet zwar kein Gut im eigentlichen Sinne an, aber der zu erbringende Service ist quasi sein Produkt und dieses muss ebenfalls nach den besagten Kriterien abgesetzt werden.

1.2 Tourenplanung als Disziplin des Operations Research

Im Hinblick auf das Forschungsfeld des Operations Research lässt sich die ¹⁰ Tourenplanung eindeutig der Graphentheorie zuordnen. Ein Graph bildet

real vorhandene Netzwerke, wie zum Beispiel Straßennetze, in einfacher und anschaulicher Weise ab und ist so in der Lage, einen ersten Überblick über komplexe Zusammenhänge zu liefern.

Grundsätzlich besteht ein Graph aus einer nichtleeren Menge von Knoten V, einer Menge von Kanten E mit V ∩ E = und einer Inzidenzabbildung, die ¹¹ jedem Element e χ E genau zwei Elemente i,j χ V zuordnet. Im weiteren

Verlauf wird für einen solchen Graphen die übliche Notation G = [V, E] verwendet. Des Weiteren lassen sich Tourenplanungsprobleme dem Bereich der kombinatorischen Optimierung zuordnen. Ein kombinatorisches Optimierungsproblem liegt dann vor, wenn die Menge der möglichen

⁹ Vgl. LACKNER (2004, S. 8).

¹⁰ Siehe NEUMANN/MORLOCK (2002, S. 176ff.).

¹¹ Ebenda (2002, S. 177).

Dynamische Tourenplanung mit Zeitfenstern 4

¹² Alternativen begrenzt ist bzw. der zulässige Lösungsbereich endlich ist. Es

geht mit anderen Worten darum, durch verschiedene Anordnungen der zu betrachtenden Objekte eine Menge zulässiger Lösungen zu generieren und aus dieser Menge dann diejenige Lösung zu ermitteln, die gemäß den Zielkriterien als optimal angesehen werden kann. Eine weitere wichtige Unterteilung von Tourenplanungsproblemen ist die ¹³ Einteilung in kantenorientierte und knotenorientierte Probleme. Da ein

Graph aus Kanten und Knoten besteht, müssen bei kantenorientierten Problemen demnach alle oder zumindest ein Teil der Kanten durchlaufen werden. Bei knotenorientierten Problemen stehen hingegen die einzelnen Knoten im Vordergrund. Ein praktisches Beispiel für ein kantenorientiertes Problem ist unter anderem das Briefträgerproblem, bei dem alle Straßen eines Zustellbezirkes mit der Zielsetzung, die unproduktiven Strecken zu ¹⁴ minimieren, durchlaufen werden müssen.

Die Kunden eines Reparaturdienstes sind jedoch als Knoten in einem Straßennetzwerk zu interpretieren; es werden somit keine kompletten Straßen bedient und dementsprechend handelt es sich bei der hier zugrunde liegenden Problemstellung um ein knotenorientiertes Optimierungsproblem.

1.3 Gang der Problemanalyse und der Problemlösung Im weiteren Verlauf werden in Kapitel 2 Grundprobleme der

Tourenplanung vorgestellt und Möglichkeiten der Klassifizierung eines konkreten Problems aufgezeigt. Kapitel 3 gibt einen Überblick über prinzipielle Möglichkeiten zur Problemlösung. Anschließend werden in Kapitel 4 Konstruktions- und Verbesserungsverfahren vorgestellt. Die Anwendung dieser Verfahren beschränkt sich hierbei zunächst auf eine statische Problemausprägung. In Kapitel 5 werden Übertragungsmöglichkeiten der vorgestellten Methoden in ein dynamisches Umfeld erörtert. Zur Anwendung weiterer Lösungsmethoden und deren Eignung zur Problembewältigung liefert Kapitel 6 einige Anhaltspunkte. Im Anschluss hieran wird in Kapitel 7 abschließend ein Resümee der Arbeit und unter Berücksichtigung praktischer Aspekte noch ein kurzer Ausblick angegeben.

¹² Vgl. NEUMANN/MORLOCK (2002, S. 380).

¹³ Vgl. DOMSCHKE (1982, S. 133).

¹⁴ Ebenda (1982, S. 108).

Dynamische Tourenplanung mit Zeitfenstern 5

Kapitel 2

Zur Vielfältigkeit von Tourenplanungsproblemen

In der Realität existieren sehr viele unterschiedliche Bereiche und Aufgaben bei deren Bewältigung die Tourenplanung eine bedeutende Stellung einnimmt. Da all diesen Bereichen und Aufgabenstellungen unterschiedliche Problemausprägungen zugrunde liegen, stellen sich Tourenplanungsprobleme als sehr facettenreich dar. Die Planung einer Busroute oder -linie bringt andere Anforderungen mit sich als beispielsweise die Planung des Einsatzes von Rettungsfahrzeugen oder die Routen- und Einsatzplanung eines Fahrradkuriers. Entsprechend der mannigfaltigen konkreten Problemausprägungen ist es nicht verwunderlich, dass es in der wissenschaftlichen Theorie viele unterschiedliche Modelle und Lösungsansätze für Tourenplanungsprobleme gibt. Vor diesem Hintergrund ist es zweckmäßig, zunächst Ansatzpunkte und Möglichkeiten zur Klassifizierung eines konkret vorliegenden Problems anzugeben, bevor entsprechende Lösungsverfahren behandelt werden. In den Abschnitten 2.1 bis 2.3 werden solche Klassifizierungsansätze vorgestellt. Darauf aufbauend wird in Abschnitt 2.4 das dieser Arbeit zugrunde liegende Problem näher spezifiziert.

2.1 Kriterienkatalog zur Problemidentifizierung

In diesem Abschnitt wird ein Kriterienkatalog als Hilfestellung zur genauen Identifizierung des vorliegenden Problemtyps vorgestellt. Der Katalog erhebt nicht den Anspruch der Vollständigkeit sondern ist vielmehr auf das in dieser Arbeit fokussierte Problem eines Reparaturservices zugeschnitten.

2.1.1 Die Ausgestaltung des Netzwerks

Das dem Problem zugrunde liegende Netzwerk bzw. der Graph kann ¹⁵ unterschiedlicher Natur sein. Sind die Knoten und deren Positionen in

Form von Koordinaten, also (x i , y i ) und (x j , y j ), angegeben, so handelt es sich um ein Koordinatennetz. Als Kantenlänge bzw. Distanz zwischen den Knoten gilt dann der euklidische Abstand. Dies entspricht formal dem

( ) ( ) ^{2 2} = − + − ^e d : x x y y Ausdruck .

ij i j i j

¹⁵ Vgl. LACKNER (2004, S. 12).

Dynamische Tourenplanung mit Zeitfenstern 6

Wird hingegen von einem Straßennetz ausgegangen, so entfallen diese luftlinienartigen Verbindungen. Vor einer Optimierung in einem solchen Netzwerk muss zunächst eine Matrix mit kürzesten Wegen zwischen den Knoten erstellt werden. Nur so ist es möglich, die zurückgelegte Entfernung entsprechend zu bewerten. Das Straßennetz kann dabei symmetrisch, das ¹⁶ bedeutet ohne Einbahnstraßen, asymmetrisch oder gemischt sein. Zudem

kann der Ort der Nachfrage als Knoten oder als Kante vorliegen. Auch ein ¹⁷ Mix ist in diesem Zusammenhang möglich. Des Weiteren ist die Anzahl

der Depots, welche der Position an der die Fahrt eines Fahrzeuges beginnt und eventuell auch endet entsprechen, zu berücksichtigen. Im Hinblick auf dynamische Aspekte, auf welche in Abschnitt 2.3 näher eingegangen wird, ist es zudem von Bedeutung, festzustellen, ob es sich bei der Problemstellung und dem zugehörigen Netzwerk um ein eher lokales Gebiet oder um ein eher globales Gebiet handelt. Bei kleineren Gebieten haben die Zeitrestriktionen eine höhere Priorität und eine kleine Veränderung kann zu einer kompletten Revidierung des bisherigen Plans führen. Bei globalen ¹⁸ Gebieten existieren jedoch oftmals ausreichende Zeitpuffer.

2.1.2 Die Beschaffenheit des Fuhrparks

Hinsichtlich des Fuhrparks ist es zunächst einmal interessant zu wissen, ob es sich um mehrere Fahrzeuge oder nur um ein einziges Fahrzeug handelt. Ist nur ein Fahrzeug gegeben, so ist das Problem leichter zu lösen, da eine ¹⁹ Zuordnung von Fahrzeug zu Kunde entfällt. Sind mehrere Fahrzeuge

vorhanden, so ist zu klären, ob es sich bei diesen um homogene oder heterogene Vehikel handelt. Dies ist besonders dann von Interesse, wenn ²⁰ Kapazitätsrestriktionen berücksichtigt werden müssen. Sollte ein Fahrzeug

auf einer Auslieferungstour eingesetzt sein und die Fahrzeugkapazität nicht für alle Kunden der Tour ausreichen, so stellt sich die Frage, ob ein anderes Fahrzeug eingesetzt werden kann oder ob ein oder mehrere Aufträge dieser Tour teilbar sind, die Kunden also von mehreren Fahrzeugen beliefert ²¹ werden können. Zudem kann zwischen geschlossenen und offenen Touren unterschieden werden. Geschlossene Touren liegen vor, wenn das Fahrzeug

¹⁶ Siehe BODIN/GOLDEN (1981, S. 98).

¹⁷ Ebenda (1981, S. 98).

¹⁸ Vgl. GENDREAU/POTVIN (1998, S. 2ff.).

¹⁹ Vgl. LACKNER (2004, S. 12).

²⁰ Siehe BODIN/GOLDEN (1981, S. 98f.).

²¹ Siehe LACKNER (2004, S. 13).