[Zurück]

G. Hiermann:
"Metaheuristics for a multimodal home-health care scheduling problem";
Betreuer/in(nen): G. Raidl, J. Puchinger; Institut für Computergraphik und Algorithmen, 2012; Abschlussprüfung: 05/2012.

Das multimodal home healthcare scheduling (MHS) Problem beschäftigt sich mit der Zuweisung von HeimhelferInnen zu PatientInnen unter Berücksichtigung von Präferenzen sowie gesetzlicher und vertraglicher Bestimmungen als auch mit der Erstellung von Touren anhand der zuvor festgelegten Zuteilung. Im Zuge des Projekts CareLog des Austrian Institute of Technology (AIT) wurde bereits ein Framework zur automatisierten Lösung eines solchen Problems anhand der Fallstudie der Organisation Sozial Global entwickelt. Untersucht wurde das Lösen von Ein-Tages-Problemen anhand einer vom AIT entwickelten Zielfunktion.
In dieser Arbeit werden die weiteren entwickelten Lösungsmethoden, die in das bestehende Framework implementieren wurden, beschrieben und mit dem vorhandenen Lösungsansatz verglichen. Da das MHS mit den gut untersuchten vehicle routing problem with time windows und dem nurse rostering problem verwandt ist, wurden drei Lösungsansätze aus diesem Bereich ausgewählt und an das MHS angepasst.
Die erste Metaheuristik ist eine simulated annealing hyper heuristic, welche mittels einer Menge an so genannten low-level heuristics eine gute Lösung sucht. Bereits dieser Ansatz zeigte vergleichbar gute Ergebnisse mit dem existierenden Ansatz. Der zweite Lösungsansatz ist ein Populations-basierter, ein so genannter memetic algorithm. Dieser erzielte die besten Ergebnisse bereits nach kurzer Zeit. Der dritte Ansatz ist ebenfalls ein Populations-basierter, ein so genannter scatter search, der deterministischere Techniken anwendet als der zuvor genannte memetic algorithm. Die Resultate zeigen jedoch, dass dieser Ansatz sehr hohe Laufzeiten benötigt, um vergleichbar gute Ergebnisse zu erziehlen.
In einer Vielzahl an Tests wurden Entscheidungen bezüglich Parameter und Methoden auf ihre Auswirkung auf die Leistung der Ansätze überprüft sowie der bereits existierende Ansatz mit den in dieser Arbeit Beschriebenen anhand von Instanzen aus der Praxis verglichen. Die Ergebnisse zeigen, dass vor allem der memetic algorithm sehr gute Ergebnisse erziehlt. Auch im Bezug auf die praktische Verwertbarkeit liefert der memetic algorithm die besten Lösungen.

The multimodal home healthcare scheduling (MHS) problem tackled in this thesis is modelled based on the operational process of a Viennese home healthcare provider. The problem is to find an assignment of jobs to nurses as well as the order in which these jobs are performed by each nurse under consideration of contractual and legal constraints and preferences as well as travel time based on the selected mode of transport.
The existing approach by the Austrian Institute of Technology is part of the project Carelog, an automatic solving architecture to create reasonably good schedules based on constraint programming and variable neighbourhood search. The focus of this thesis was to implement several different metaheuristic approaches into the existing framework to solve one day real world instances and compare the results with the existing approach.
Three metaheuristics have been selected and implemented based on experiences with them on related problems, the vehicle routing problem with time windows and the nurse rostering problem. First a simulated annealing hyper heuristic, a general optimization approach using a set of so-called low-level heuristics, was implemented. This approach yielded similarly good results compared to the existing approach in most of the tested instances. The second heuristic is a so-called memetic algorithm. This population-based approach known for its good performance when tackling related problems achieved the best results in all test instances within a relatively short amount of time and provided an in-depth view into the structure of good solutions. The third approach, the scatter search, is also a population-based approach using more deterministic techniques in contrast to memetic algorithm. Results show that this metaheuristic needs high runtimes to achieve a comparable solution quality of solutions and indicate that this approach is not the best choice for this kind of problem.
In various tests the impact of parameter and design decisions on the performance of the heuristics were observed and documented. Additionally a comparison with the existing approach is provided using real world instances. The results show that the memetic algorithm performs best.
Also in terms of their applicability in praxis, the MA provided the most satisfying solutions.

http://publik.tuwien.ac.at/files/PubDat_211627.pdf