A large neighborhood search metaheuristic for the personal planning problem

Menschen mit komplexen Tagesablaufen, wie beispielsweise mobile Selbststandige, mussen sich ihre Zeit sinnvoll einteilen, um alle beruflichen und privaten Termine sowie Freizeitaktivitaten wahrnehmen zu konnen. Ein automatischer Tagesplaner, der die effiziente Planung von Terminen und Aktivitaten mit dazugehoriger Routenplanung ubernimmt, kann diese Zielgruppe unterstutzen. Die vorliegende Arbeit, verfasst im Rahmen einer Zusammenarbeitmit dem Austrian Institute of Technology (AIT), prasentiert und lost das Personal Planning Problem (PPP) - ein mathematisches Modell welches sowohl die zeitlichen als auch die ortlichen Aspekte einer realistischen Terminplanung berucksichtigt. Das PPP erweitert das bekannte Orienteering Problem with Time Windows (OPTW). Im Unterschied zum OPTW, ermoglicht die PPP Formulierung, dass eine Aufgabe an mehreren Standorten und zu verschiedenen Zeitfenstern geplant werden kann. Weiters werden Reihenfolgebedingungen und zeitliche Mindest- und/oder Maximalabstande zwischen den Aufgaben berucksichtigt. Um die Balance zwischen mehr Aktivitaten und mehr Freizeit zu berucksichtigen, wird eine bikriterielle Formulierung des Problems gelost. Das vorgestellte Losungsverfahren basiert auf Large Neighborhood Search. Der Losungsraum wird erkundet indem verschiedene Teile eines Plans iterativ zerstort und anschliesend wieder rekonstruiert werden. Der Algorithmus setzt verschiedene Zerstorungs- und Reparaturoperatoren ein um die Suche zu diversifizieren bzw. zu verstarken. Bekannte Verfahren aus der Literatur wurden an die problemspezifischen Nebenbedingungen des PPP angepasst. Die prasentierte Metaheuristik wurde implementiert und auf problemspezifischen Vergleichsinstanzen getestet. Der Algorithmus erweist sich als effektiv und zuverlassig fur alle untersuchten Problemgrosen. Fur die kleinen Testinstanzen, fur welche die exakte Pareto-Menge bekannt ist, findet die Metaheuristik nahezu immer die exakten Losungen und fur grosere Instanzen ist die Qualitat der Ergebnisse konsistent. Der Algorithmus erzeugt stets reprasentative Fronten von Pareto-effizienten Losungen - dadurch konnen diverse Terminplane ohne einen Neustart des Verfahrens verglichen, und die unterschiedlichen Praferenzen von verschiedenen Entscheidungstragern berucksichtigt werden.