Online Vehicle Routing Probleme im Krankenhaus

Inhaltsverzeichnis

1. Inhalt

2. Grundlegende Definitionen und Routing Probleme
2.1 Grundbegriffe der kombinatorischen Optimierung 2
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 84
6.4 Anwendung zweier Online-Strategien auf das Problem

7. Ergebnisse

ABKÜRZUNGSVERZEICHNIS

Abbildung in dieser Leseprobe nicht enthalten

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.

LITERATURVERZEICHNIS

Albers, Susanne; Westbrook, Jeffrey: Self-Organizing Data Structures, in: Fiat, A. (Hrsg.): Online Algorithms: The State of the Art, Springer (Berlin, Heidelberg), 1998, S. 13-51.

Ben-David, S et.al.: On the Power of Randomization in On-Line Algorithms, Algorithmica, Vol. 11, Springer (New York), 1994, S. 2-14.

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.

Blom, Michiel; Krumke, Sven O.; Paepe, Willem de; Stougie, Leen: The Online-TSP against Fair Adversaries: in Bongiovanni, G. et al. (Hrsg.): CIAC 2000, LNCS 1767, Springer (Berlin, Heidelberg), 2000, S. 137-149.

Chrobak, Marek; Sgall, Jiri: A Simple Analysis of the Harmonic Algorithm for Two Servers, Information Processing Letters, Vol. 75, Elsevier (Amsterdam), 2000, S. 75-77.

Cordeau, Jean-Francois et al.: VRP with Time Windows, in: Toth, Paolo (Hrsg.): The Vehicle Routing Problem, SIAM (Philadelphia), 2002, S. 157-193.

Cordeau, J.; Laporte, G.: A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transportation Research B, Vol. 37, Pergamon Elsevier Science (Oxford), 2003, S. 579-594.

Cortes, A.; Ripoll, A.; Senar, M.A.; Luque E.: Performance Comparison of Dynamic Load-Balancing-Strategies for Distributed Computing, Proceedings of the 32nd Hawaii International Conference on System Sciences – 1999, S. 8041ff.

Desrosiers, Jacques, et al.: Time Constrained Routing and Scheduling, in: Ball, M.O. et al. (Hrsg.): Handbooks in Operations Research and Management Science, Vol. 8, North-Holland (Amsterdam), 1995, S. 35-139.

Derigs, U.; Metz A.: A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints, Operations Research Spektrum, Vol. 14, Springer (Berlin, Heidelberg), 1992, S. 91-106.

Dror, Moshe; Trudeau, Pierre: Stochastic Vehicle Routing with Modified Savings Algorithm, European Journal of Operational Research, Vol. 23, North-Holland (Amsterdam), 1986, S. 228-235.

Dumas, Y., Desrosiers, J., Soumis F.: The Pickup and Delivery Problem with Time Windows, European Journal of Operational Research, Vol. 54, North-Holland (Amsterdam), 1991, S. 7-22.

Dumas, Y.; Desrosiers, J.; Soumis, F.: Large Scale Multi-vehicle Dial-a-ride Problems, GERAD, G-89-30, September 1989.

Ejnioui, Abdel; Ranganathan, Nagarajan: Multiterminal Net Routing for Partial Crossbar-Based Multe-FPGA Systems, Proceedings of the 1999 ACM/SIGDA 7th International Symposium on Field Programmable Gate Arrays, Monterey, February 1999, S. 176-185.

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.

Feuerstein, Esteban; Stougie, Leen: On-Line single-server dial-a-ride problems, Theoretical Computer Science, Vol. 268, Springer (Berlin, Heidelberg), 2001, S. 91-105.

Fischer, Klaus; Müller, Jörg P.; Pischel: Cooperative Transportation Scheduling: An Application Domain for DAI, Applied Artificial Intelligence, Taylor & Francis (London), Vol. 10, 1996, S. 1-33.

Fischer, Klaus; Müller, Jörg P.; Pischel, Markus; Schier, Darius: A Model for Cooperative Transportation Scheduling, Proceedings of the 1st International Conference on Multiagent Systems, AAAI Press / MIT Press (Menlo Park, Ca.), 1995, S. 109-115.

Grötschel, Martin; Krumke, Sven O.; Hauptmeier, Dietrich; Rambau, Jörg: Simulation Studies for the Online Dial-a-Ride Problem; ZIB Preprint SC 99-09, Berlin, March 1999.

Grötschel, Martin; Krumke, Sven O.; Rambau, Jörg: Online Optimization of Complex Transportation Systems, ZIB-Report 01-17, Berlin, July 2001.

ILOG Optimization Suite – White paper – Delivering a Competitive Advantage, http://www.ilog.com, May 2001.

Ioachim, I.; Desrosiers, J. et al.: A Request Clustering Algorithm for Door-to-Door Handicapped Transportation, Transportation Science, Vol. 29, No. 1, INFORMS (Linthicum), February 1995, S. 63-78.

Irani, Sandy: Competitive Analysis of Paging, in: Fiat, A. (Hrsg.): Online Algorithms: The State of the Art, Springer (Berlin, Heidelberg), 1998, S. 52-73.

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

Jungfleisch, Stefan: Präsentation zum Thema Patiententransporte der Unikliniken Homburg.

Krumke, Sven O.: Online Optimization – Competitive Analysis and Beyond, ZIB Report 02-25, Berlin, 2002.

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

Kuchen, Herbert; Wagener, Andreas: Comparison of Dynamic Load Balancing Strategies, Journal of Parallel and Distributed Processing, Academic Press, 1991, S. 303-314.

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. 335-358.

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.

Madsen, Oli B.G.; Ravn, Hans F.; Rygaard, Moberg: A Heuristic Algorithm for a Dial-a-Ride Problem with Time Windows, Multiple Capacities, and Multiple Objectives, Annals of Operations Research, Vol. 60, Baltzer (Bussum), 1995, S. 193-208.

Nickel, Stefan: Skript zu Vorlesung Operations Research II, Universität des Saarlandes, http://www.wiwi.uni-sb.de/lst/ufo/main.html, 2003.

Nickel, Stefan et al.: Präsentation zum Thema: Planungsunterstützung durch Simulation und moderne Planungsalgorithmen – Patiententransport.

Nickel, Stefan; Tenfelde, Dagmar: Planning and Organisation in the Hospital, Universität des Saarlandes.

Pereira, F.; Tavares, J.; Penousal, M.; Costa, E.: GVR: A New Genetic Representation for the Vehicle Routing Problem, in: O´Neill, M. et al. (Hrsg.): AICS 2002, LNAI 2464, Springer (Berlin, Heidelberg), 2002, S. 95-102.

Potvin, Jean-Yves; Rousseau, Marc: A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows, European Journal of Operational Research, Vol. 66, North-Holland (Amsterdam), 1993, S. 331-340.

Qualitätsbericht der Universitätskliniken Homburg 2001, Kapitel VII. Innerbetrieblicher Transport, http://www.uniklinik-saarland.de/.

Reimann, Marc; Doerner, Karl; Hartl, Richard F.: Analyzing a Unified Ant System for the VRP and Some of its Variants, Lecture Notes in Computer Science, Vol. 2611, Springer (Heidelberg), January 2003, S. 300-310.

Sleator, D.; Tarjan R.: Amortized efficiency of list update and paging rules, Communication of the ACM, Vol. 28,(New York), 1985, S. 202-208.

Teodorovic, D.; Radivojevic, G.: A fuzzy logic approach to dynamic Dial-a-Ride problem, Fuzzy Sets and Systems, Vol. 116, North-Holland (Amsterdam), 2000, S.23-33.

Toth, P.; Vigo, D.: Heuristic Algorithms for the Handicapped Persons Transportation Problem, Transportation Science, Vol. 31, No. 1, INFORMS (Linthicum), February 1997, S. 60-71.

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

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

VERZEICHNIS DER GESPRÄCHSPARTNER

Herr Georg Roget, Sanka-Zentrale Universitätskliniken Homburg.

Dr. ing. A. Crauser, Forschung und Entwicklung von Algorithmen bei der Firma Algorithmic Solutions GmbH.

ERKLÄRUNG

Hiermit versichere ich, Andreas Treitz, daß ich diese Arbeit selbständig angefertigt habe. Des weiteren habe ich keine anderen, als die angegeben Hilfsmittel benutzt, und alle wörtlichen und sinngemäßen Entlehnungen deutlich als solche gekennzeichnet.

Saarbrücken, den 22.10.2003 ______________________________________

Andreas Treitz

[...]