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
- Grundlegende Definitionen und Routing Probleme
- Grundbegriffe der kombinatorischen Optimierung
- Vorgehensweise der Optimierung
- Optimierungs- / Entscheidungsprobleme
- Komplexität eines Problems
- Vehicle Routing Probleme
- Die Klasse der Vehicle Routing Probleme
- Ausprägungen von VRP
- Das CVRP
- Definition und Notation
- Modellierungsmöglichkeiten
- Das VRP mit Zeitfenstern
- Das VRP mit Pickup und Delivery
- Online Probleme
- Offline-/Online-Probleme
- Online-Algorithmen
- Grundbegriffe
- Kompetitive Analyse
- Beispiel: Das Skifahrerproblem
- Patiententransporte an der Uni-Klinik Homburg
- Daten über die Uni-Kliniken
- Geschichte
- Der Campus
- Eckdaten und deren Entwicklung in den letzten Jahren
- Patiententransporte im Krankenhaus
- Das Modell von Nickel / Tenfelde
- Patiententransporte in Homburg
- Grundsätze – Ist-Zustand - Soll-Zustand
- Daten – Voraussetzungen - Besonderheiten
- Das Transportmodell für die Uni-Kliniken Homburg
- Bemerkungen und mögliche Erweiterungen des Modells
- Implementierung und Lösung des Problems
- Implementierung in OPL-Studio
- Vorgehensweise
- Mengen
- Strukturen
- Größen und Variablen
- Zielfunktion und Routing-Bedingungen
- Zeitbedingungen
- Kapazitätsbedingungen
- Inputdaten
- Ergebnisse
- Optimale Lösung für eine Dateninstanz
- Vergleich des Laufzeitverhaltens für verschiedene Instanzen
- Algorithmen
- Überblick und Vorbemerkungen
- Online-Routing-Strategien
- REPLAN
- IGNORE, SMARTSTART, IG GREEDY
- FIFO, LIFO
- FIRSTFIT, FF MAXAGE, FF DYNAGE, BESTFIT
- REBUS
- HARMONIC
- Die Clarke & Wright Heuristik
- Online-Load-Balancing-Strategien
- Passive Strategien
- Aktive Strategien
- Gemischte Strategien
- Das Auftragsauktionsprinzip SIMULATED TRADING von MARS
- Anwendung zweier Online-Strategien auf das Problem
- Ergebnisse
Zielsetzung und Themenschwerpunkte
Die Diplomarbeit befasst sich mit der Modellierung und Lösung von Online Vehicle Routing Problemen im Kontext von Patiententransporten in einem Krankenhaus. Ziel ist es, effiziente Algorithmen zu entwickeln, die die zeitliche und räumliche Planung der Transporte optimieren und gleichzeitig den Bedürfnissen der Patienten gerecht werden.
- Kombinatorische Optimierung und Vehicle Routing Probleme
- Online-Algorithmen und ihre Anwendung auf Routing-Probleme
- Modellierung und Simulation von Patiententransporten in einem Krankenhaus
- Entwicklung und Evaluierung von effizienten Online-Routing-Strategien
- Analyse der Auswirkungen verschiedener Strategien auf die Effizienz und Effektivität des Patiententransports
Zusammenfassung der Kapitel
- Das erste Kapitel definiert grundlegende Begriffe der kombinatorischen Optimierung und führt in die Klasse der Vehicle Routing Probleme ein. Es werden verschiedene Ausprägungen des Vehicle Routing Problems, wie das Capacitated Vehicle Routing Problem (CVRP) und das Vehicle Routing Problem mit Zeitfenstern (VRPTW), vorgestellt.
- Das zweite Kapitel behandelt Online-Probleme und die Eigenschaften von Online-Algorithmen. Es werden verschiedene Online-Strategien und ihre kompetitive Analyse vorgestellt.
- Das dritte Kapitel stellt die Patiententransporte an der Uni-Klinik Homburg vor und beschreibt die Daten, Voraussetzungen und Besonderheiten des Systems. Es wird ein Transportmodell für die Uni-Kliniken Homburg vorgestellt und mögliche Erweiterungen diskutiert.
- Das vierte Kapitel beschreibt die Implementierung des Problems in OPL-Studio und präsentiert die Ergebnisse der Optimierung für verschiedene Dateninstanzen. Es wird das Laufzeitverhalten verschiedener Algorithmen verglichen.
- Das fünfte Kapitel analysiert verschiedene Online-Routing- und Load-Balancing-Strategien und präsentiert die Ergebnisse der Anwendung auf das Patiententransportproblem.
Schlüsselwörter
Vehicle Routing Problem, Online-Algorithmen, Patiententransport, Krankenhauslogistik, Optimierung, Simulation, Effizienz, Effektivität, kompetitive Analyse, Strategien, Implementierung, OPL-Studio.
- Arbeit zitieren
- Andreas Treitz (Autor:in), 2003, Online Vehicle Routing Probleme im Krankenhaus, München, GRIN Verlag, https://www.grin.com/document/34300
