Algorithmen für Außendienstmitarbeiter Schedulingprobleme

Dieses Forschungsprojekt ist motiviert von der Problemsituation, die sich Anbietern mobiler Pflegedienste oder technischer (Reparatur-) Services stellt. In beiden Fällen besteht der Kern des Problems aus der Zuordnung von Service- oder Pflegeaufträgen zu einer bestimmten Anzahl von MitarbeiterInnen. Jeder Mitarbeiter/jede Mitarbeiterin ist charakterisiert durch verschiedene Qualifikationen auf unterschiedlichen Niveaus, Verfügbarkeitsperioden, km-basierte Kosten (abhängig von dem ihm/ihr zugeordneten Fahrzeug) und unterschiedlich hohe Lohnkosten. Jeder Service- oder Pflegeauftrag besitzt ein Zeitfenster, muss innerhalb einer bestimmten Zeitperiode, die von einem Tag bis zu mehreren Wochen dauern kann, erledigt werden und stellt an den Mitarbeiter/die Mitarbeiterin bestimmte Qualifikationsanforderungen. In manchen Fällen benötigt eine Aufgabe zwei AußendienstmitarbeiterInnen, um erledigt zu werden. Schließlich müssen auch arbeitszeitabhängige Nebenbedingungen, wie maximale Dienstlängen und minimale Pausenzeiten zwischen zwei Diensten, in der Planung berücksichtigt werden. Das generelle Ziel ist es Touren- und Dienstpläne von möglichst geringen Kosten zu generieren, wobei wegzeitabhängige, arbeitszeitabhängige und klienten- so wie mitarbeiterzufriedenheitsabhängige Kostenterme berücksichtigt werden. Klientenzufriedenheit beruht, zum Beispiel, auf Konsistenz. Dies bedeutet, dass die Anzahl an unterschiedlichen AußendienstmitarbeiterInnen, die denselben Klienten/dieselbe Klientin betreuen, so niedrig wie möglich sein sollte. Bisher wurden Problemstellungen dieser Art überwiegend mit heuristischen Verfahren gelöst, die in der Regel Lösungen von guter Qualität innerhalb akzeptabler Laufzeit erstellen. Exakte Algorithmen, die das garantierte Optimum berechnen, dafür aber häufig exponentielle Laufzeiten aufweisen, wurden für diese Art der Probleme noch kaum erforscht. Im ersten Teil dieses Projekt werden daher exakte Verfahren zur Lösung der deterministischen Problemstellung entwickelt. Branch-and-Cut und Branch-and-Cut-and-Price Algorithmen sind vielversprechende Kandidaten. Probleminstanzen realistischer Größe werden mit exakten Verfahren vermutlich nicht gelöst werden können. Daher planen wir auch heuristische Lösungsmethoden basierend auf dem Large Neighborhood Search Paradigm zu entwerfen. Auch die Entwicklung hybrider Methoden, an der Kreuzung von heuristischen und exakten Ansätzen, ist geplant. In der Realität sind gerade Weg- und Servicezeiten nur sehr selten deterministisch. Über die sinnvolle Integration von Unsicherheit in Bezug auf Weg- und Servicezeiten in Verbindung mit Zeitfenstern gibt es bisher nur wenige Arbeiten. Im zweiten Teil dieses Projekts planen wir daher Formulierungen der stochastischen Programmierung und solche der robusten Optimierung, die auf unterschiedlichen Unsicherheitsannahmen beruhen, zu entwickeln, zu analysieren und zu vergleichen, um ihre Vorteile und Grenzen in Theorie und Praxis zu bestimmen. Diese Ansätze werden als Basis für die Entwicklung von entsprechenden heuristischen Verfahren dienen. In diesem Projekt soll somit eine breite theoretische Basis für die Modellierung und Lösung des generischen Außendienstmitarbeiter Schedulingproblems im Bereich mobiler Pflege und technischer (Reparatur-) Services geschaffen werden.

In diesem Forschungsprojekt wurden Optimierungsalgorithmen für das Außendienstmitarbeiter Routing und Scheduling im Bereich mobiler Pflege und technischer (Wartungs-) Services entwickelt.Der Kern dieser Probleme besteht in der Verteilung einer Menge von Service- oder Pflegeaufträgen an eine Anzahl von MitarbeiterInnen. JedeR MitarbeiterIn ist durch bestimmte Skills unterschiedlicher Levels, Verfügbarkeitszeiten, distanzbasierte Kosten (abhängig vom gefahrenen Fahrzeug) und Lohnkosten charakterisiert. Jeder Auftrag kann mit einem Zeitfenster versehen sein, muss in einem bestimmten Zeitraum (zwischen einem Tag und mehreren Wochen) erfüllt werden und verlangt eineN MitarbeiterIn mit den notwendigen Skills. In manchen Fällen werden zwei oder mehr MitarbeiterInnen benötigt, um einen Auftrag zu erfüllen. Dies erfordert die Synchronisierung zweier oder mehrere Mitarbeitertouren. Auch arbeitszeitabhängige Anforderungen wie maximale Schichtlängen können in der Planung berücksichtigt werden. Ziel ist es möglichst günstige Tourenpläne zu erstellen in Bezug auf die zurückgelegte Strecke, Arbeitszeit und Kundenzufriedenheit oder Servicequalität. Kundenzufriedenheit wird oft in Verbindung mit Konsistenz gesehen: Betreuung durch möglichst wenige unterschiedliche MitarbeiterInnen und wiederholte Besuche zu möglichst ähnlichen Zeiten. Andere komplizierende Aspekte betreffen die Planung von fußläufigen Subtouren in Fußgängerzonen (das Fahrzeug muss an einem Parkplatz zurückgelassen und ein oder mehrere Klienten müssen zu Fuß besucht werden) und beträchtliche Unsicherheit in Bezug auf die Länge der Servicezeiten. In diesem Projekt wurden neue Konzepte zur Behandlung dieser Aspekte im Kontext von exakten und heuristischen Optimierungsverfahren entwickelt. Exakte Verfahren berechnen den bewiesenermaßen optimalen Plan während heuristische Ansätze Suchstrategien anwenden, die gute, aber möglicherweise nicht optimale Pläne in kurzer Rechenzeit generieren. Daher werden exakte Verfahren dazu genützt, um optimale Tourenpläne für kleinere Instanzen zu berechnen und so die Performance von heuristischen Verfahren zu validieren. Im vorliegenden Projekt wurden exakte Verfahren, die auf sogenannten Branch-and-Cut und Branch-and-Price Ansätzen beruhen und sowohl die Tourensynchronisierung- als auch die Subtourplanungsanforderungen erfüllen können, und effiziente heuristische Komponenten für sogenannte Large Neighborhood Search Algorithmen entwickelt, die auch in viele andere heuristische Suchstrategien zur Außendienstmitarbeiterplanung integriert werden können. Darüberhinaus wurden wertvolle Erkenntnisse in Bezug auf das Kompromissverhältnis von serviceorientierten und kostenorientierten Zielsetzungen erlangt: Erhebliche Verbesserungen in der Servicequalität sind oft zu verhältnismäßig geringen Kosten möglich. Die im vorliegenden Projekt entwickelten algorithmischen Komponenten können und werden als Basis für Entscheidungsunterstützungssoftwaretools für die Außendienstmitarbeiterplanung herangezogen.