Dynamische Tagesplanung von mobilen Pflegediensten die zeitabhängigen multimodalen Transport verwenden
Ziel des Projekts war die Entwicklung dynamischer Planungsinstrumente zur Unterstützung der täglichen Planung von häuslichen Pflegediensten (HHC). HHC-Dienste sind für die heutige Gesellschaft von entscheidender Bedeutung. Sie ermöglichen alten und gebrechlichen Menschen ein selbstbestimmtes Leben in ihrer gewohnten Umgebung und reichen von qualifizierter häuslicher Pflege bis hin zur Unterstützung bei der Haushaltsführung. Die aktuellen demografischen und gesellschaftlichen Entwicklungen führen zu einem deutlichen Anstieg der Nachfrage nach diesen Leistungen. Derzeit erfolgt die Planung in der Regel manuell und aufgrund der Komplexität sind geeignete Entscheidungsunterstützungssysteme sehr willkommen.
Wir betrachten ein reales HHC-Problem, das auf den Anforderungen des Österreichischen Roten Kreuzes (ÖRK) basiert, einem der führenden HHC-Dienstleister in Österreich. Es hat einen täglichen Planungshorizont und konzentriert sich auf urbane Regionen. In Erweiterung der bisherigen Forschung konzentrieren wir uns primär auf die dynamischen und stochastischen Aspekte des Problems. Das Ziel besteht in der Minimierung der gesamten erwarteten Reise- und Wartezeiten des Pflegepersonals. Das Problem selbst lässt sich kurz wie folgt zusammenfassen:
Eine bestimmte Anzahl heterogener Krankenschwestern mit unterschiedlichen Qualifikationsniveaus und Arbeitszeiten muss eine Menge von Klienten mindestens einmal am Tag besuchen. Dabei werden verschiedene Zuweisungsbeschränkungen (z.B. Sprachkenntnisse, abgelehnte Pflegekräfte, etc.) und harte Zeitfenster für diese Besuche berücksichtigt. Im HHC kann es mehrmals am Tag vorkommen, dass die für die Behandlung eines Klienten veranschlagte Zeit überschritten wird, da sie in der Regel von der körperlichen Verfassung des Klienten abhängt. Es kann auch vorkommen, dass neue Klienten auftauchen, die in letzter Minute Leistungen benötigen (z. B. aufgrund einer Entlassung aus dem Krankenhaus) und daher in die bestehenden Zeitpläne eingefügt werden müssen. In der Praxis benutzen die Krankenschwestern entweder das Auto oder öffentliche Verkehrsmittel, je nach geografischer Lage und Effizienz des öffentlichen Verkehrssystems. Da das Projekt auf städtische Einsatzgebiete mit gut ausgebauten öffentlichen Verkehrssystemen abzielt, wird der zeitabhängige öffentliche Verkehr als Hauptverkehrsmittel betrachtet. Abgesehen von der Tatsache, dass nicht jede Krankenschwester einen Führerschein besitzt, ist es auch effizienter, sich in Städten fortzubewegen, wenn man die Verkehrs- und Parkbedingungen berücksichtigt. Daher nutzen z.B. in Wien mehr als 90 % der ARC-Schwestern die öffentlichen Verkehrsmittel.
Die Optimierung im Bereich HHC ist ein recht junges, aber sich schnell entwickelndes Forschungsgebiet. Allerdings wird das Routing mit öffentlichen Verkehrsmitteln in der Literatur noch kaum berücksichtigt. Stochastische Programmierung wurde bisher nur auf das HHC-Zuweisungsproblem angewandt. Diese Art von Problem hat eine mittel- bis langfristige Perspektive und zielt darauf ab, die Kunden den Krankenschwestern auf der Grundlage ihrer Bedürfnisse und Fähigkeiten zuzuweisen. Während das Routing des Pflegepersonals nicht berücksichtigt wird, geht es in der Regel um Aspekte wie die Kontinuität der Pflege oder den Ausgleich der Arbeitsbelastung.
Der entwickelte Lösungsansatz musste zwei Hauptanforderungen erfüllen. Erstens sollte er sich darauf konzentrieren, robuste Zeitpläne zu berechnen, die auch mit kleineren Störungen fertig werden. Zweitens sollte er für den Fall, dass ein bestimmtes Ausmaß erreicht wird, Instrumente für eine effiziente Neuplanung bereitstellen.
Die Algorithmen wurden mit realen Daten aus dem ARC in Wien getestet. Die Lösungen werden mit jenen verglichen, die mit deterministischen Servicezeiten erzielt wurden, um die Robustheit der berechneten Fahrpläne zu bewerten.
Aus Sicht der Modellierung kann das zugrundeliegende Problem als ein zeitabhängiges Vehicle-Routing-Problem mit stochastischen Servicezeiten und zusätzlichen HHC-bezogenen Nebenbedingungen betrachtet werden. Zunächst wurde eine mathematische Problemformulierung formuliert, implementiert und mit der Solver-Software Xpress 7.8 gelöst. Das entwickelte gemischt-ganzzahlige lineare Programm ist in der Lage, Instanzen mit bis zu 3 Pflegern und 15 Jobs innerhalb von 24h Rechenzeit optimal zu lösen.
Der entwickelte Lösungsansatz baut auf unseren bisherigen zeitabhängigen und multimodalen Routing-Algorithmen auf und zielt darauf ab, robuste Fahrpläne zu berechnen, die bis zu einem gewissen Grad mit Störungen umgehen können. Derzeit wird angenommen, dass die Servicezeiten für die Behandlung eines Kunden einer bekannten Wahrscheinlichkeitsverteilung folgen und voneinander unabhängig sind. Aufgrund der Modellierung der Ungewissheit können jedoch verschiedene Ereignisse (z. B. verlängerte Reisezeiten oder neue Aufträge) mit unterschiedlichen Verteilungen behandelt werden.
Für die Modellierung der Zeitabhängigkeit wurde ein zeitdiskreter Ansatz gewählt. Zur effizienten Berechnung zeitabhängiger Reisezeitmatrizen aus den Fahrplänen der ÖPNV-Anbieter wurde ein dynamischer Programmieransatz implementiert. Er berücksichtigt sowohl das Zu-Fuß-Gehen zu nahegelegenen Haltestellen als auch das Warten auf spätere Verbindungen und erfüllt die FIFO-Eigenschaft (first in - first out), die eine natürliche Annahme für zeitabhängiges Routing ist. Um Instanzen von realer Größe in angemessener Zeit zu lösen, wurde ein zeitabhängiger Tabu-Search (TS) basierter Algorithmus entwickelt und in der Programmiersprache C++ implementiert. Unzulässige Lösungen werden vorübergehend zugelassen und eine dynamisch angepasste gewichtete Bewertungsfunktion wird verwendet, um den Suchprozess zu steuern. Um die Suche zu beschleunigen, ändert der entwickelte TS dynamisch die Größe seiner Nachbarschaft. Für die Umplanung wurde eine flexible, ereignisdiskrete Metaheuristik entwickelt. Sie generiert iterativ vielversprechende Lösungen auf der Grundlage des Auftretens von Ereignissen im Zeitverlauf. Mehrere vielversprechende Lösungen werden durch den Einsatz von Zufallsverfahren erzeugt.
Um die stochastischen Servicezeiten zu berücksichtigen und effiziente robuste Fahrpläne zu berechnen, wird eine Strafformulierung zusammen mit einer Zufallsbeschränkung verwendet. Damit wird die Zielfunktion um die erwarteten Kosten für Rückgriffsaktionen erweitert. Rückgriffsmaßnahmen werden benötigt, wenn eine Route aufgrund der verlängerten Servicezeiten nicht mehr durchführbar ist. In einem solchen Fall wird angenommen, dass HHC-Dienstleister Floater aussenden, die einspringen und eine bestimmte Anzahl von Kunden übernehmen, um die Dienste der nachfolgenden Kunden auf der Route aufrechtzuerhalten. Darüber hinaus begrenzt die Zufallsbedingung die Wahrscheinlichkeit, dass eine Route ungültig wird, auf einen bestimmten Schwellenwert.
Der Lösungsansatz wurde mit realen Daten aus dem ARC in Wien getestet, mit bis zu 202 Aufträgen und 46 Krankenschwestern. Es hat sich gezeigt, dass die meisten Fahrpläne, die die Unsicherheit ignorieren, tatsächlich nicht durchführbar sind, wenn die geplante Dienstzeit überschritten wird. Unter der Annahme einer geometrischen Verteilung (p = 0,5) steigt die durchschnittliche Wahrscheinlichkeit der Machbarkeit der Pläne von 75,5 % auf 99,9 %. Die Mindestwerte für die Durchführbarkeit steigen jedoch von 51,6 % auf 99,2 %, was zeigt, dass fast jede Route Aufträge enthält, bei denen die Servicezeit nicht überschritten werden darf. Diese Robustheit hat natürlich ihren Preis, der sich in einer durchschnittlichen Zunahme der Fahr- und Wartezeiten um 9,7 % niederschlägt.