I. INHALTSVERZEICHNIS

Seite

1. Inhalt

2. Grundlegende Definitionen und Routing Probleme 2

2.1 Grundbegriffe der kombinatorischen Optimierung 2

2.2 Vehicle Routing Probleme 6

3. Online Probleme 22

3.1 Offline-/ Online-Probleme 22 3.2 Online-Algorithmen 22

4. Patiententransporte an der Uni-Klinik Homburg 30

4.1 Daten über die Uni-Kliniken 30

4.2 Patiententransporte im Krankenhaus 34

5. Implementierung und Lösung des Problems 53

5.1 Implementierung in OPL-Studio 53

5.2 Ergebnisse 62

6. Algorithmen 66

6.1 Überblick und Vorbemerkungen 66

6.2 Online-Routing-Strategien 67

6.3 Online-Load-Balancing-Strategien 80

6.4  Anwendung zweier Online-Strategien auf das Problem  86

7.  Ergebnisse  89

4

ABKÜRZUNGSVERZEICHNIS

Abb. -Abbildung allg. -allgemein Aufl. -Auflage bzw. -beziehungsweise ca. -circa CVRP - CapacitatedVehicle Routing Problem d.h. -das heißt DM -Deutsche Mark f. -folgende ff. -fort folgende Hrsg. -Herausgeber i.a. -im Allgemeinen inkl. -inklusive Kap. -Kapitel Km -Kilometer No. - Number o.g. -oben genannt Pos. -Position S. -Seite sog. -so genannte Tab. -Tabelle u.a. -unter anderem u.d.NB. -unter den Nebenbedingungen usw. -und so weiter VRP - VehicleRouting Problem VRPB - VehicleRouting Problem with Backhauls VRPPD - VehicleRouting Problem with Pickup and Delivery VRPPDTW - VehicleRouting Problem with Pickup and Delivery and Time Windows VRPTW - VehicleRouting Problem with Time Windows Vol. - Volume Vgl. -vergleiche z.B. -zum Beispiel

5

GRAFIKEN UND TABELLEN

Grafik 1: Vehicle Routing Problem.

Seite: 8

Grafik 2: Die Grundprobleme der Klasse von VRP.

Seite: 9

Quelle: Toth, Paolo; Vigo, Daniele: An Overview of Vehicle Routing Problems, in: Toth, Paolo (Hrsg.): The Vehicle Routing Problem, SIAM (Philadelphia), 2002, S. 1-23.

Grafik 3: Campus der Universitätskliniken in Homburg/ Saar.

Seite: 31

Quelle: http://www.uniklinik-saarland.de/daten/lageplan.html.

Grafik 4: Routenführung der optimalen Lösung einer Dateninstanz.

Seite: 63

Tabelle 1: stationärer Behandlungsbereich der Unikliniken.

Seite: 32

Quelle: http://www.uniklinik-saarland.de/daten/eckdaten.html.

Tabelle 2: Personal der Unikliniken.

Seite: 33

Quelle: http://www.uniklinik-saarland.de/daten/eckdaten.html.

6

1 Inhalt

Die Diplomarbeit handelt von Online Routing Problemen im Krankenhaus am Beispiel der Universitätskliniken in Homburg/Saar. Bei Routing-Problemen im Krankenhaus ist an den Materialfluss, sowie den Transport von Patienten über das Straßennetz innerhalb des Krankenhauscampus zu denken. Dabei steht der Online-Charakter des Problems im Vordergrund. „Online“ bedeutet in diesem Zusammenhang, dass nicht alle Transportaufträge zum Zeitpunkt der Planung bekannt sind, sondern im Laufe des betreffenden Tages eingehen. Zur Zeit werden Transportaufträge manuell an die zur Verfügung stehenden Transportmittel vergeben.

Im Zuge der unbefriedigenden allgemeinen wirtschaftlichen Entwicklung in den letzten Jahren werden in allen Bereichen der Krankenhausorganisation nach Einsparpotentialen gesucht. Durch den Wechsel von einer manuellen zu einer computergestützten Auftragszuordnung können Einsparungen bezüglich der Anzahl an eingesetzten Mitarbeitern und Fahrzeugen, sowie Fahrzeit und Fahrdistanz erzielt werden.

Kapitel 2 beschäftigt sich mit den Grundbegriffen, die zur Bearbeitung des Problems benötigt werden, sowie einer Einführung in den Bereich der Vehicle Routing Probleme. Danach werden verschiedene Möglichkeiten zur mathematischen Modellierung von Vehicle Routing Problemen aufgezeigt und einige Ausprägungen des Problems diskutiert. In Kapitel 3 folgen allgemeine Definitionen zum Gebiet Online-Probleme, sowie eine Einführung in den Umgang mit Online-Algorithmen. Es wird ein Überblick über verschiedene Arten von Online-Algorithmen gegeben und eine Bewertungsmöglichkeit für Algorithmen erklärt und an einem einfachen Beispiel erläutert.

Kapitel 4 beinhaltet allgemeine Informationen über die Universitätskliniken in Homburg und den Ist- und Soll-Zustand der Patiententransporte. Im Anschluss werden ein allgemeines Modell für Patiententransportprobleme und die Anforderungen des Homburger Krankenhauses an ein spezielles Transportmodell beschrieben. Auf Basis dieser Anforderungen folgt die Aufstellung eines mathematischen Modells für die Universitätskliniken, sowie in Kapitel 5 die Implementierung des Problems in eine Optimierungssoftware zur Verifizierung und optimalen Lösung des Problems. Da die Größe des Problems, dessen Online-Charakter und Schwierigkeit eine zeitnahe Optimierung in der Praxis unmöglich machen, werden in Kapitel 6 Online-Algorithmen vorgestellt, die alternative Möglichkeiten zur Bestimmung von Fahrtrouten und zur Transportauftragsverteilung enthalten. Danach werden einige dieser Online-Strategien anhand

1

von Aufträgen untersucht, die zeitlich nach der Optimierung liegen. Diese Aufträge werden mittels der Online-Strategie in die zuvor in Kapitel 5 berechneten (optimalen) Transportrouten der Fahrzeuge integriert.

2 Grundlegende Definitionen und Routing Probleme

2.1 Grundbegriffe der kombinatorischen Optimierung

2.1.1 Vorgehensweise der Optimierung

Seit etwa 70 Jahren existiert der Begriff „Operations Research“, unter dem Methoden und Verfahren der mathematischen Entscheidungsvorbereitung subsummiert sind. Hauptmerkmal dieser entscheidungsvorbereitenden Maßnahmen ist ein Optimalitätsstreben, das sich im wirtschaftlichen Bereich beispielsweise in der Maximierung von Erträgen oder der Minimierung von Kosten äußern kann. Die Vorgehensweise ist hierbei immer identisch:

1. Mittels eines mathematischen Modells wird ein reales Problem abstrahiert.

2. Das Modell wird analytisch exakt, näherungsweise, heuristisch oder auf Basis einer

Simulation gelöst.

3. Es wird eine Entscheidungsempfehlung gegeben.

2.1.2 Optimierungs- / Entscheidungsprobleme

Unter einem Problem versteht man eine generelle Fragestellung. In der kombinatorischen Optimierung benötigt man des weiteren den Begriff einer Probleminstanz, die die Menge aller Eingabedaten darstellt, welche zur Lösung eines Problems benötigt werden. Also kann ein Problem als eine Menge von Probleminstanzen beschrieben werden. ¹ Zur Definition eines Optimierungsproblems versteht man unter dem Begriff Alphabet ∑ eine endliche Menge von Symbolen. ∑* bezeichnet die Menge aller endlichen Zeichenketten über ∑.

Definition 1.1 (Optimierungsproblem) 2

¹ Vgl. Nickel, Stefan: Skript zur Vorlesung Operations Research II, Universität des Saarlandes, 2003, S. 53.

² Krumke, Sven O.; Rambau Jörg: Online Optimierung, Technische Universität Berlin, Januar 2002, S. 7.

2

Ein Optimierungsproblem (über einem Alphabet ∑ ) ist ein Quadrupel (Ì, X, F, M) mit folgenden Bedeutungen:

- Ì ⊆ ∑* ist die Menge von Eingabe - Instanzen (Inputs);

- X ( I ) ⊆ ∑* ist die Menge zulässiger Lösungen (Outputs) für die Instanz I ∈ Ì;

- F : Ì × ∑* → IR ≥0 ist die Zielfunktion, d.h. F ( I , x ) bezeichnet die Kosten / Erträge der Lösung x bei Eingabe von I. Der Wert F ( I , x ) ist nur dann definiert, wenn x ∈ X ( I );

- M ∈ { min , max } gibt an, ob es sich bei dem Problem um ein Minimierungs- oder Maximierungsproblem handelt.

Ein Beispiel für ein Optimierungsproblem ist das Vehicle Routing Problem, das im späteren Verlauf ausführlich behandelt wird. Ziel des Optimierungsproblems ist die Suche einer optimalen Lösung x* ∈ X ( I ), die F bezüglich M optimiert. Im Gegensatz zum Optimierungsproblem, dessen Lösung aus einem konkreten (optimalen) Wert (ZFW*) besteht, trifft ein Entscheidungsproblem lediglich eine Ja / Nein -Entscheidung (answer), beispielsweise bezüglich der Frage ∃ x 0 ∈ X mit f (x) ≤ k und k ∈ IN

Beispiel: Ein Knapsack - Problem

Die zugehörigen Entscheidungen sind: x 1 = 0 , x 2 = 1 , x 3 = 1 und ZFW* = 10.

Da ein Optimierungsproblem P und das zugehörige Entscheidungsproblem E ( P ) hinsichtlich ihrer Komplexität als gleichwertig einzuordnen sind, kann eine Komplexitätsuntersuchung auf Entscheidungsprobleme beschränkt und auf Optimierungsprobleme übertragen werden. 3

2.1.3 Komplexität eines Problems

Um die Komplexität eines Problems „messen“ zu können, werden sie in verschiedene Komplexitätsklassen eingeordnet. Dies geschieht anhand einer Untersuchung des

³ Vgl. Nickel, Stefan: Skript zur Vorlesung Operations Research II, Universität des Saarlandes, 2003, S. 59ff.

3

Laufzeitverhaltens bzw. der Komplexität des theoretisch besten Lösungsalgorithmus für das zu betrachtende Problem.

Definition 1.2 (Algorithmus) 4

Ein Algorithmus ist ein Lösungswerkzeug für Optimierungs-/ Entscheidungsprobleme und ist gekennzeichnet durch:

- eine endliche Anzahl von Schritten

- eine präzise Definition der Schritte

- eine vor der Ausführung festgelegte Eingabeanzahl ≥ 0

- eine Ausgabenanzahl ≥ 1

- genügend elementare Operationen zur Ausführung in endlicher Zeit.

Die Komplexität eines Algorithmus kann auf Basis des best-, average- oder worst-case- Verhaltensermittelt werden. Das bedeutet, dass man bei der Bewertung des Algorithmus A, der beispielsweise die Suche nach einer Postleitzahl p in einer Liste L gewährleistet im worstcase-Fall annimmt, dass die gesuchte Zahl ganz am Ende der Liste steht, respektive an Stelle 1 im best-case-Fall. Im Allgemeinen geht man vom worst-case-Fall aus und deshalb:

Definition 1.3 (Zeitkomplexität) 5

Die Zeitkomplexität T A (n) eines Algorithmus A zur Lösung eines Problems ist die maximale Anzahl elementarer Rechenschritte, die der Algorithmus zur Bearbeitung einer beliebigen Probleminstanz der Größe ≤ n benötigt.

Definition 1.4 (Komplexität des Algorithmus) 6

Sei g(n) : IN → IR +

Ein Algorithmus A hat die Komplexität O(g(n)), wenn zwei Konstanten c ≥ 0 und n ⁰ existieren, so dass für alle n ≥ n ⁰ T A (n) ≤ c · g(n) erfüllt ist.

Hinsichtlich der Komplexität unterscheidet man zwei Arten von Algorithmen :

⁴ Vgl. Joereßen, A.; Sebastian H.-J. : Problemlösung mit Modellen und Algorithmen, Teubner Studienbücher Wirtschaftswissenschaften (Stuttgart, Leipzig), 1998, S. 3ff.

⁵ Vgl. Nickel, Stefan: Skript zur Vorlesung Operations Research II, Universität des Saarlandes, 2003, S. 55.

⁶ Vgl. Nickel, Stefan: Skript zur Vorlesung Operations Research II, Universität des Saarlandes, 2003, S. 55.

4

1. den polynomialen Algorithmus, wenn T A (n) = O(g(n)) und g(n) ein Polynom ist und 2. den exponentiellen Algorithmus, wenn T A (n) = O(g(n)) und g(n) kein Polynom ist.

Ein Algorithmus mit der Komplexität O(n ³ ) ist also ein polynomialer Algorithmus und eine Komplexität O(c ⁿ ) bedeutet, dass ein exponentieller Algorithmus vorliegt. Wie leicht zu erkennen ist, hat die Art des Algorithmus Auswirkungen auf das Laufzeitverhalten des Computers, der das Problem löst. Während bei polynomialen Algorithmen die Laufzeit proportional zur Problemgröße n ansteigt und die Probleme auch für sehr große n noch zu lösen sind, steigt das Laufzeitverhalten bei exponentiellen Algorithmen mit steigendem n in einem Maße, dass auch für relativ kleine n bald eine so große Menge von elementaren Rechenschritten notwendig ist, so dass das Problem nicht mehr gelöst werden kann. Auf Basis dieser Unterscheidung lässt sich feststellen, wie leicht oder wie schwer ein Problem ist. Dafür werden die Klassen IP, IN.IP und IN.IP -complete eingeführt.

Definition 1.5 (IP)

Die Klasse der Entscheidungsprobleme, die durch einen polynomialen Algorithmus gelöst werden können, heißt IP und die Entscheidungsprobleme aus IP werden leichte Probleme genannt.

Definition 1.6 (IN.IP) 7

IN.IP ist die Menge aller nicht-deterministisch polynomial lösbarer Entscheidungsprobleme. Ein Entscheidungsproblem heißt nicht-deterministisch polynomial lösbar, wenn ein (geratener) Ja-Input in polynomialer Zeit als ein solcher nachgewiesen werden kann.

IP ist hierbei eine Teilmenge von IN.IP. Da für viele Entscheidungsprobleme kein polynomialer Algorithmus bekannt ist und die Annahme getroffen wird, dass auch kein solcher Algorithmus existiert, bleibt bis zu deren Widerlegung unklar, ob IP = IN.IP oder IP ⊂ IN.IP.

Definition 1.7 (Polynomiale Reduktion) 8

⁷ Vgl. Nickel, Stefan: Skript zur Vorlesung Operations Research II, Universität des Saarlandes, 2003, S. 61.

⁸ Winter, Thomas: Online and Real-Time Dispatching Problems, Dissertation FB Mathematik und Informatik, Technische Universität Braunschweig, 1999, S. 29.

5

Ein Entscheidungsproblem P ist polynomial reduzierbar auf ein Entscheidungsproblem P´, wenn es einen polynomialen Algorithmus gibt, der jede Instanz von P in eine Instanz von P´ mit der gleichen Antwort transformiert.

Mittels polynomialer Reduktion lassen sich die Probleme aus IN.IP klassifizieren. Polynomiale Reduktionen sind reflexiv und transitiv.

Definition 1.8 (IN.IP - complete) 9

Ein Problem P liegt in der Klasse IN.IP - complete, wenn das Problem P zu IN.IP gehört und jedes Problem aus IN.IP auf P reduziert werden kann.

Ein Optimierungsproblem heißt IN.IP - schwer, wenn das zugehörige Entscheidungsproblem E(P) der Klasse IN.IP - complete zugehörig ist.

2.2 Vehicle Routing Probleme

2.2.1 Die Klasse der Vehicle Routing Probleme

Seit einigen Jahrzehnten ist das Gebiet der Distributionsplanung in den Mittelpunkt der mathematischen Unternehmensforschung gerückt. Dabei liegt der Fokus auf dem Design effektiver Distributionsstrategien, um ein höheres Maß an Kundenzufriedenheit und Transportkosteneinsparungen zu erreichen. Typische Anwendungsfälle sind hierbei die Fahrzeugtourenplanung (:=Vehicle Routing) für Schulbusse oder Lastkrafttransporte zur Versorgung der Bevölkerung mit Nahrungsmitteln und anderen Gütern. Es hat sich gezeigt, dass durch den Einsatz von Optimierungsmethoden ein großes Einsparungspotential entstanden ist. 10

VRP sind IN.IP - schwer. Deshalb ist es unwahrscheinlich, dass ein polynomialer Algorithmus zur optimalen Lösung eines dieser Probleme existiert oder entwickelt werden kann. 11

⁹ Vgl. Nickel, Stefan: Skript zur Vorlesung Operations Research II, Universität des Saarlandes, 2003, S. 64.

¹⁰ Vgl. Bertsimas, Dimitris; Simchi-Levi, David: A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty, Operations Research, Vol. 44, No. 2, INFORMS (Linthicum), March 1996, S. 286-304.

¹¹ Federgruen, Awi; Simchi-Levi, David: Analysis of Vehicle Routing and Inventory-Routing Problems, in: Ball, M.O. et al. (Hrsg.): Handbooks in Operations Research and Management Science, Vol. 8, North-Holland (Amsterdam), 1995, S. 297-371.

6

Typische Ziele von Vehicle Routing Problemen (VRP) sind:

- die Minimierung der benötigten Fahrzeuge zur Erfüllung aller Aufträge.

- die Minimierung der Transportkosten, als Summe der variablen Kosten (zurückgelegte Entfernung oder benötigte Zeit) und der Fixkosten (Fahrer, Transportmittel u.a.).

- die Minimierung von Verzögerungen, Verspätungen oder Auftragsausfällen um die Kundenzufriedenheit zu maximieren.

Also kann das VRP als das Problem der Auswahl optimaler Belieferungs- oder Beladungsrouten in einem Straßennetzwerk von einem oder mehreren Depots zu einer Anzahl von geographisch getrennten Abnehmern oder Auftraggebern (Kunden) beschrieben werden. 12

Im Allgemeinen wird das Straßennetzwerk, das zum Transport der einzelnen Güter herangezogen wird, durch einen Graphen abgebildet. Der Graph besteht aus Kanten (arcs), deren Anfangspunkt und Endpunkt (vertices) Straßenverzweigungen oder Start- bzw. Zielorte (Depot, Kunde) angeben. Die Kanten sind ungerichtet (undirected), wenn die Strecke in beide Richtungen befahren werden kann und sind gerichtet (directed), wenn die Fahrt nur in eine Richtung möglich ist. Jeder Kante sind Kosten zugeordnet, die sich normalerweise aus der Länge der Strecke und der Fahrtzeit des jeweils betrachteten Fahrzeugs ergeben. Folgende Grafik zeigt beispielhaft ein Vehicle Routing Problem, bei dem 8 Kunden von einem zentralen Depot beliefert werden und eine mögliche Routeführung (mit Zwischenstopp am Depot unter Vernachlässigung von zugeordneten Kosten).

¹² Laporte, Gilbert: The Vehicle Routing Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, Vol. 59 , North Holland (Amsterdam), 1992, S. 345-358.

7

Grafik 1: Vehicle Routing Problem.

Die Routenführung in Grafik 1 ist willkürlich gewählt. Ziel von VRP ist hingegen die Konstruktion von kostenminimalen Routen, die folgende Anforderungen erfüllen müssen: 13

- jeder Kunde wird genau einmal von einem Fahrzeug besucht.

- alle Routen beginnen und enden an einem Depot.

- bestimmte Nebenbedingungen müssen erfüllt sein.

Beispiele für solche Nebenbedingungen sind:

1. Kapazitätsbeschränkungen.

2. Das Fahrzeug kann nur eine bestimmte Anzahl an Kunden beliefern, bevor es zurück zum Depot muss (Obergrenzen für Anfahrtspunkte).

3. Zeit- und Entfernungsobergrenzen für Routen.

4. Zeitfenster.

5. Reihenfolgebeziehungen zwischen Kunden.

Aufgrund der Unterschiedlichkeit der möglichen Nebenbedingungen für VRP gibt es verschiedene Ausprägungen von VRP, die in der folgenden Grafik aufgeführt sind:

¹³ Laporte, Gilbert: The Vehicle Routing Problem: An overview of exact and approximate algorithms, European Journal of Operational Research , Vol. 59 , North Holland (Amsterdam), 1992, S. 345-358.

8

Grafik 2: Die Grundprobleme der Klasse von VRP 14

Legende: CVRP:= Capacitated VRP; DCVRP:= Distance-Constrained VRP; VRPB:= VRP with Backhauls; VRPTW:= VRP with Time Windows; VRPPD:= VRP with Pick up and Delivery; VRPBTW:= VRP with Backhauls and Time Windows; VRPPDTW:= VRP with Pick up and Delivery and Time Windows.

Im folgenden wollen wir uns die einzelnen Ausprägungen der VRP genauer ansehen.

2.2.2 Ausprägungen von VRP

2.2.2.1 Das CVRP 2.2.2.1.1 Definition und Notation

Wie in Grafik 1.2 zu erkennen ist, ist das Capacitated Vehicle Routing Problem das allgemeinste Problem der VRP.

Definition 1.9 (CVRP) 15 16

¹⁴ Toth, Paolo; Vigo, Daniele: An Overview of Vehicle Routing Problems, in: Toth, Paolo (Hrsg.): The Vehicle Routing Problem, SIAM (Philadelphia), 2002, S. 1-23.

¹⁵ Laporte, Gilbert; Louveaux, Francios V., Van Hamme, Luc : An Integer L-Shaped Algorithm For the Capacitated Vehicle Routing Problem with Stochastic Demands, Operations Research, Vol. 50, No. 3, INFORMS (Linthicum), May 2002, S. 415-423.

¹⁶ Toth, Paolo; Vigo, Daniele: An Overview of Vehicle Routing Problems, in: Toth, Paolo (Hrsg.): The Vehicle Routing Problem, SIAM (Philadelphia), 2002, S. 1-23.

9

Das deterministische Capacitated VRP ist definiert als:

Sei G= (V,A) ein Graph mit A als Menge an Kanten und V = {0,....,n} als Menge an Punkten. Die Punkte 1,...,n gehörend zu den Kunden, der Punkt 0 ist das Depot. Zu jeder Kante a ∈ A gehört die Endpunkte α (a) und β (a). Mit jeder Kante (i,j) i ≠ j sind nicht negative Entfernungen c ij verbunden, die als Transportkosten oder Transportzeit interpretiert werden können. Zusätzlich gibt es K verfügbare Fahrzeuge im Depot mit identischer Kapazität C. Wenn G ein gerichteter Graph ist, heißt das CVRP asymmetrisch und wenn der Graph ungerichtet ist gilt c ij = c ji für alle a ∈ A und das CVRP ist symmetrisch. Für Punkt i sei ∆ ⁺ (i) die Nachfolgermenge (forward star) von i , definiert als alle Punkte j, so dass die Kante (i,j) ∈ A (alle Punkte, die von i aus direkt erreicht werden können). Für Punkt i sei ∆ ^- (i) die Vorgängermenge (backward star) von i, definiert als alle Punkte j, so dass die Kante (j,i) ∈ A (alle Punkte von denen i direkt erreicht werden kann).

Jeder Punkt (Kunde) i (i = 1,...,n) ist verbunden mit einer nichtnegativen Nachfrage (demand) d i , und das Depot hat die fiktive Nachfrage d 0 = 0.

Im Folgenden wird die Menge der Kanten im Graph als A bezeichnet, wenn sie durch ihre Endpunkte (i,j) , i,j∈V gekennzeichnet sind (gerichtet) und als E, wenn der Kante nur eine eigene Kantenbezeichnung e zugeordnet ist (ungerichtet).

Sei S eine Menge an Punkten S ⊆ V, dann ist δ(S) die Menge an Kanten e ∈ E, bei denen nur ein Endpunkt in S liegt und E(S), die Menge an Kanten e ∈ E, bei denen beide Endpunkte in S liegen.

Sei S eine Menge an Punkten S ⊆ V \ {0}, dann ist r(S) die Minimalanzahl an Fahrzeugen, die benötigt wird, um alle Punkte (Kunden) aus S zu bedienen. Die Kostenmatrix genügt der sog. Triangle inequality (Dreiecksungleichung), wenn gilt: c ik + c kj ≥ c ij für alle i,j,k ∈ V.

Das bedeutet, dass die Summe der Kosten von Punkt i nach k und von Punkt k nach j nicht kleiner sind, als die Kosten von Punkt i nach Punkt j: der direkte Weg ist „billiger“ oder genau so „billig“ wie jeder andere Weg. In manchen Anwendungsfällen wird diese Ungleichheit zur Lösung des Problems durch einen Algorithmus verlangt.

2.2.2.1.2 Modellierungsmöglichkeiten 17

¹⁷ Toth, Paolo; Vigo, Daniele: An Overview of Vehicle Routing Problems, in: Toth, Paolo (Hrsg.): The Vehicle Routing Problem, SIAM (Philadelphia), 2002, S. 1-23.

10

Drei Modellierungsmöglichkeiten zur Formulierung von VRP sind als besonders wichtig anzusehen: 1. Die Vehicle Flow Formulierung 2. Die Commodity Flow Formulierung 3. Die Set-Partioning Formulierung

Die Unterschiede zwischen den Modellierungsmöglichkeiten lassen sich sehr gut anhand dreier Modelle von Paolo Toth und Daniele Vigo zeigen:

Zu 1: Die Vehicle Flow Formulierung benutzt Variablen, die den einzelnen Kanten zugeordnet sind. Diese zählen, wie oft eine Kante (bzw. die Strecke) vom jeweils betrachteten Fahrzeug passiert wird. Man unterscheidet zwischen einer allgemeineren Version mit 2 Indizes und einer ausführlicheren Version mit 3 Indizes.

Modell 1: Asymmetrisches CVRP nach Vehicle Flow Formulierung mit 3 Indizes. 18

Variablen: x ijk = Anzahl der Passierungen von Kante (i,j)∈ A durch Fahrzeug k mit k = 1,..,K

(ACVRP1) min ∑

(1)

u.d.NB.

¹⁸ Toth, Paolo; Vigo, Daniele: An Overview of Vehicle Routing Problems, in: Toth, Paolo (Hrsg.): The Vehicle Routing Problem, SIAM (Philadelphia), 2002, S. 1-23.

11

∑

(5)

(6)

y ik ∈ {0,1} ∀ i ∈ V , k = 1,…,K (7) x ijk ∈ {0,1} ∀ i,j ∈ V , k = 1,…,K (8)

Erläuterungen zu Modell:

(1) ist die Zielfunktion. Es werden alle Kosten, die zu den jeweiligen Kanten (i,j) gehören, mit der Häufigkeit der jeweiligen Passierung durch jedes Fahrzeug k multipliziert und die Gesamtkosten minimiert.

(2) gewährleistet, dass jeder Kunde genau einmal von genau einem Fahrzeug besucht wird.

(3) gewährleistet, dass genau K Fahrzeuge das Depot „bedienen“, d.h., dass genau K Fahrzeuge das Depot verlassen.

(4) gewährleistet, dass das Fahrzeug, dass den Kunden j in Kante (i,j) bedient, den Kunden j auch wieder verlässt.

(5) gewährleistet, dass jedes Fahrzeug seine Kapazität C nicht überschreitet. (6) gewährleistet, dass die Verknüpftheit der Route jedes Fahrzeuges gegeben ist. Diese Verknüpftheitsgarantie wird erreicht, indem für alle Teilmengen S von V\{0}, die einen Kunden enthalten verlangt wird, dass eine benutzte Kante der Route die Teilmenge verlässt.

(7) gewährleistet, dass alle y ik binäre Variablen sind. (8) gewährleistet, dass alle x ijk binäre Variablen sind.

Offensichtlich ist diese Formulierung sehr allgemein. In einigen Fällen muss das Modell modifiziert werden, z.B. wenn einige Kanten fehlen (d.h. der Graph ist nicht vollständig). Dann modelliert man anhand der Nachfolger- und Vorgängermengen.

Zu 2: Zur Modellierung in Commodity Flow Formulierung wird der Graph G erweitert zu G´ = (V´,A´). Die Erweiterung besteht aus der Einführung eines zusätzlichen Punktes n + 1, der eine Kopie des Depots darstellt. Jeder Kante (i,j) ∈ A´ sind zwei nichtnegative Fließvariablen

12

y ij und y ji zugeordnet. y ij gibt die Gesamtladung eines Fahrzeugs an, wenn es von Punkt i zu Punkt j fährt und y ji gibt die freie Kapazität des Fahrzeuges an, wenn es von Punkt i nach Punkt j fährt. Die Routen sind in diesem Fall Pfade vom Depot 0 zu „neuen“ Punkt n + 1, also besteht jede Route aus einem gerichteten Pfad von 0 bis n + 1 mit den jeweiligen (Rest-) Ladungen, und einem gerichteten Pfad von n + 1 zu 0 mit den jeweilig freien Kapazitäten. Dabei wird im ersten Pfad an jedem Punkt i die Ladung abgegeben, die der Nachfrage d i , des Kunden i entspricht und in Punkt 0, dem Depot, entspricht die Beladung der Summe aller Nachfragen der zu beliefernden Kunden. Im zweiten Fall wird bei jedem Kunden i die Ladung entsprechend seiner Nachfrage aufgenommen.

d ( V´ \ {0, n + 1}) bezeichnet die Nachfragen an allen Punkten außer an den Depots, K ist die Anzahl der Fahrzeuge, C ist die Kapazität der Fahrzeuge.

Modell 2: Asymmetrisches CVRP nach Commodity Flow Formulierung mit 2 Indizes. 19

Variablen: x ij = ⎩

A´

(ACVRP2) min ∑

(1) c ij x ^ij ∈ ´ A j i ^{) , (} u.d.NB.

∑

¹⁹ Toth, Paolo; Vigo, Daniele: An Overview of Vehicle Routing Problems, in: Toth, Paolo (Hrsg.): The Vehicle Routing Problem, SIAM (Philadelphia), 2002, S. 1-23.

13

∑

(5)

∀ (i,j) ∈ A´ (6) y ij + y ji = C x ij

∑

∀ i ∈ V´ \ {0, n + 1} (7) (x ij + x ji ) = 2 ∈ ´ V j

∀ (i,j) ∈ A´ (8) y ij ≥ 0 x ij ∈ {0,1} ∀ (i,j) ∈ A´ (9)

Erläuterungen zu Modell:

(1) ist die Zielfunktion. Wenn Kante (i,j) in der Lösung ist (x ij = 1) sind die korrespondierenden Kosten lösungsrelevant. Die Summe der Kosten wird minimiert. (2) gewährleistet, dass die Differenz zwischen der Summe der Fließvariablen, die zu Kanten gehören, welche in einen i Punkt eingehen, und der Summe der Fließvariablen, die zu Kanten gehören, welche einen Punkt i verlassen gerade gleich der doppelten Nachfrage d i des Punktes i ist.

(3) gewährleistet, dass die Fahrzeuge genau mit den Mengen das Depot verlassen, die sie benötigen, um alle Nachfragen zu decken (Vorwärtsfall). (4) gewährleistet, dass die Fahrzeuge mit allen aufgeladenen Aufträgen im Depot ankommen (Rückwärtsfall).

(5) gewährleistet, dass die Gesamtkapazität nicht überschritten wird. (6) gewährleistet, dass, falls die Kante (i,j) in der Lösung enthalten ist, die Summe aus Beladung und freier Kapazität bei Durchlaufen dieser Kante die Gesamtkapazität ergibt.

(7) gewährleistet, dass, falls die Kante (i,j) in der Lösung enthalten ist, sie sowohl auf dem Hinweg, als auch auf dem Rückweg durchlaufen wird. (8) ist Nichtnegativitätsbedingung für die Fließvariablen. (9) gewährleistet, dass alle x ij binäre Variablen sind.

Zu 3: Die Set-Partioning Formulierung ordnet jeder möglichen Route (circuit) H j ∈ IH aus G

(= Graph, siehe Vehicle Flow Formulierung) korrespondierende Kosten c j für die Route zu, mit IH = {H 1 ,...,H q }. Außerdem existieren binäre Koeffizienten a ij , die angeben, ob ein Knoten i durch eine Route j abgedeckt wird.

14