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.
Inhaltsverzeichnis
2. Grundlegende Definitionen und Routing Probleme
2.1 Grundbegriffe der kombinatorischen Optimierung
2.1.1 Vorgehensweise der Optimierung
2.1.2 Optimierungs- / Entscheidungsprobleme
2.1.3 Komplexität eines Problems
2.2 Vehicle Routing Probleme
2.2.1 Die Klasse der Vehicle Routing Probleme
2.2.2 Ausprägungen von VRP
2.2.2.1 Das CVRP
2.2.2.1.1 Definition und Notation
2.2.2.1.2 Modellierungsmöglichkeiten
2.2.2.2 Das VRP mit Zeitfenstern
2.2.2.3 Das VRP mit Pickup und Delivery
3. Online Probleme
3.1 Offline-/ Online-Probleme
3.2 Online-Algorithmen
3.2.1 Grundbegriffe
3.2.2 Kompetitive Analyse
3.2.3 Beispiel: Das Skifahrerproblem
4. Patiententransporte an der Uni-Klinik Homburg
4.1 Daten über die Uni-Kliniken
4.1.1 Geschichte
4.1.2 Der Campus
4.1.3 Eckdaten und deren Entwicklung in den letzten Jahren
4.2 Patiententransporte im Krankenhaus
4.2.1 Das Modell von Nickel / Tenfelde
4.2.2 Patiententransporte in Homburg
4.2.2.1 Grundsätze – Ist-Zustand – Soll-Zustand
4.2.2.2 Daten – Voraussetzungen - Besonderheiten
4.2.3 Das Transportmodell für die Uni-Kliniken Homburg
4.2.4 Bemerkungen und mögliche Erweiterungen des Modells
5. Implementierung und Lösung des Problems
5.1 Implementierung in OPL-Studio
5.1.1 Vorgehensweise
5.1.2 Mengen
5.1.3 Strukturen
5.1.4 Größen und Variablen
5.1.5 Zielfunktion und Routing-Bedingungen
5.1.6 Zeitbedingungen
5.1.7 Kapazitätsbedingungen
5.1.8 Inputdaten
5.2 Ergebnisse
5.2.1 Optimale Lösung für eine Dateninstanz
5.2.2 Vergleich des Laufzeitverhaltens für verschiedene Instanzen
6. Algorithmen
6.1 Überblick und Vorbemerkungen
6.2 Online-Routing-Strategien
6.2.1 REPLAN
6.2.2 IGNORE, SMARTSTART, IG GREEDY
6.2.3 FIFO, LIFO
6.2.4 FIRSTFIT, FF MAXAGE, FF DYNAGE, BESTFIT
6.2.5 REBUS
6.2.6 HARMONIC
6.2.7 Die Clarke & Wright Heuristik
6.3 Online-Load-Balancing-Strategien
6.3.1 Passive Strategien
6.3.2 Aktive Strategien
6.3.3 Gemischte Strategien
6.3.4 Das Auftragsauktionsprinzip SIMULATED TRADING von MARS
6.4 Anwendung zweier Online-Strategien auf das Problem
7. Ergebnisse
Zielsetzung & Themen
Die Diplomarbeit widmet sich der Optimierung von Transportabläufen in Krankenhäusern, speziell am Beispiel der Universitätskliniken Homburg/Saar. Das primäre Ziel ist die Entwicklung eines Modells und der Einsatz effizienter Online-Algorithmen, um die manuelle Auftragszuordnung durch ein computergestütztes System zu ersetzen und so Fahrzeiten, Distanzen sowie den Ressourceneinsatz zu minimieren.
- Mathematische Modellierung von Vehicle Routing Problemen (VRP)
- Online-Optimierung bei unvollständiger Information (Patiententransport)
- Implementierung von Transportmodellen in OPL-Studio
- Vergleich und Anwendung heuristischer Online-Routing-Strategien
- Analyse der Leistungsfähigkeit und Laufzeit von Optimierungsalgorithmen
Auszug aus dem Buch
2.2.2.2 Das VRP mit Zeitfenstern (VRP with Time Windows)
Die erste Variation von VRP, die hier betrachtet werden soll sind VRP mit Zeitfenstern. Diese Variation wird gewählt, wenn Kunden in einer vorgegebenen Zeitspanne bedient werden sollen. Von den Fahrzeugen wird verlangt, dass sie innerhalb der jeweils definierten Zeitfenster bei dem korrespondierenden Kunden ankommen und der Service für den Kunden bis zum Ende des Zeitfensters begonnen wird. Man unterscheidet in diesem Fall zwischen harten (hard) und weichen (soft) Zeitfenstern. Im Falle von harten Zeitfenstern muss das Fahrzeug, wenn es zu früh bei einem Kunden ankommt, so lange warten, bis das Zeitfenster des Kunden beginnt und Verspätungen sind nicht erlaubt. Bei weichen Zeitfenstern sind diese Bedingungen nicht bindend, werden aber durch die Addition von zusätzlichen Kosten in der Zielfunktion berücksichtigt.
Auch dem Depot ist ein Zeitfenster zugeordnet, welchen den gesamten Planungshorizont beschreibt. Zusätzlich zu den aus dem CVRP bekannten Kosten, entstehen beim VRPTW noch Kosten für Wartezeiten.
Zur Modellierung des VRPTW müssen einige neue Variablen eingeführt werden, die das VRP (ausgehend von der bisherigen Notation) ergänzen. Das Depot ist wie in (ACVRP2) mit den Punkten 0 und n + 1 beschrieben. Die Zeitfenster beziehen sich auf Punkte. [ai,bi] geben den frühesten und spätesten Anfangszeitpunkt des Service an Punkt i an. [E,L] seien frühest mögliche Abfahrt am Depot 0 und spätest mögliche Ankunft am Depot n + 1.
Zusammenfassung der Kapitel
Grundlegende Definitionen und Routing Probleme: Einführung in die kombinatorische Optimierung und die theoretischen Grundlagen der Vehicle Routing Probleme.
Online Probleme: Definition und Erläuterung der Herausforderungen bei Online-Optimierungsproblemen sowie Einführung in kompetitive Analyse.
Patiententransporte an der Uni-Klinik Homburg: Analyse der Ist-Situation des Patiententransports am Campus Homburg und mathematische Modellierung des PTP.
Implementierung und Lösung des Problems: Technische Umsetzung des Modells in OPL-Studio und Präsentation der Ergebnisse für verschiedene Instanzen.
Algorithmen: Vorstellung verschiedener heuristischer Routing- und Load-Balancing-Strategien für die Online-Auftragszuordnung.
Ergebnisse: Zusammenfassende Bewertung der Modellierung und Diskussion der Anwendbarkeit auf die reale Situation in der Klinik.
Schlüsselwörter
Vehicle Routing Problem, Online-Optimierung, Patiententransport, OPL-Studio, kombinatorische Optimierung, Zeitfenster, Tourenplanung, Heuristik, Transportkosten, Ressourcenoptimierung, Dial-a-Ride, kompetitive Analyse, Logistik, Krankenhausorganisation, mathematisches Modell.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit?
Die Diplomarbeit untersucht Optimierungsmöglichkeiten für Patiententransportprozesse in Krankenhäusern durch den Einsatz von mathematischen Modellen und Online-Algorithmen.
Welche zentralen Themen werden behandelt?
Der Fokus liegt auf der Fahrzeugtourenplanung, dem Umgang mit zeitlich variabel eingehenden Aufträgen (Online-Probleme) und der Implementierung in eine Optimierungssoftware.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist die Reduktion von Fahrzeiten, Personaleinsatz und Fahrzeuganzahl durch eine computergestützte, effiziente Auftragszuordnung an den Universitätskliniken Homburg.
Welche wissenschaftliche Methode kommt zum Einsatz?
Es wird die Theorie der kombinatorischen Optimierung verwendet, um das Problem als VRP zu modellieren und mit Methoden wie Branch-and-Bound sowie verschiedenen heuristischen Online-Strategien zu lösen.
Was wird im Hauptteil behandelt?
Neben den theoretischen Grundlagen werden das PTP für Homburg modelliert, in OPL-Studio implementiert und zahlreiche Online-Routing-Algorithmen auf ihre Eignung geprüft.
Welche Keywords charakterisieren die Arbeit?
Die Arbeit lässt sich vor allem über Begriffe wie Vehicle Routing Problem, Online-Optimierung, Patiententransport und Tourenplanung definieren.
Warum ist das Problem für Homburg so speziell?
Der Campus in Homburg ist in Pavillonbauweise errichtet, was die effiziente Ver- und Entsorgung erschwert und einen speziellen Fuhrpark mit verschiedenen Fahrzeugtypen und Anforderungen erfordert.
Wie beeinflusst der "Online-Charakter" die Planung?
Da nicht alle Aufträge zu Planungsbeginn feststehen, ist eine statische Planung unzureichend; es bedarf flexibler Algorithmen, die in der Lage sind, neu eintreffende Anfragen dynamisch in laufende Pläne zu integrieren.
- Quote paper
- Andreas Treitz (Author), 2003, Online Vehicle Routing Probleme im Krankenhaus, Munich, GRIN Verlag, https://www.grin.com/document/34300
