Detailansicht
A large neighborhood search metaheuristic for the personal planning problem
Piotr Matl
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.34972
URN
urn:nbn:at:at-ubw:1-30347.53962.877154-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Menschen mit komplexen Tagesabläufen, wie beispielsweise mobile Selbstständige, müssen sich ihre Zeit sinnvoll einteilen, um alle beruflichen und privaten Termine sowie Freizeitaktivitäten wahrnehmen zu können. Ein automatischer Tagesplaner, der die effiziente Planung von Terminen und Aktivitäten mit dazugehöriger Routenplanung übernimmt, kann diese Zielgruppe unterstützen. Die vorliegende Arbeit, verfasst im Rahmen einer Zusammenarbeitmit dem Austrian Institute of Technology (AIT), präsentiert und löst das Personal Planning Problem (PPP) - ein mathematisches Modell welches sowohl die zeitlichen als auch die örtlichen Aspekte einer realistischen Terminplanung berücksichtigt.
Das PPP erweitert das bekannte Orienteering Problem with Time Windows (OPTW). Im Unterschied zum OPTW, ermöglicht die PPP Formulierung, dass eine Aufgabe an mehreren Standorten und zu verschiedenen Zeitfenstern geplant werden kann. Weiters werden Reihenfolgebedingungen und zeitliche Mindest- und/oder Maximalabstände zwischen den Aufgaben berücksichtigt. Um die Balance zwischen mehr Aktivitäten und mehr Freizeit zu berücksichtigen, wird eine bikriterielle Formulierung des Problems gelöst.
Das vorgestellte Lösungsverfahren basiert auf Large Neighborhood Search. Der Lösungsraum wird erkundet indem verschiedene Teile eines Plans iterativ zerstört und anschließend wieder rekonstruiert werden. Der Algorithmus setzt verschiedene Zerstörungs- und Reparaturoperatoren ein um die Suche zu diversifizieren bzw. zu verstärken. Bekannte Verfahren aus der Literatur wurden an die problemspezifischen Nebenbedingungen des PPP angepasst.
Die präsentierte Metaheuristik wurde implementiert und auf problemspezifischen Vergleichsinstanzen getestet. Der Algorithmus erweist sich als effektiv und zuverlässig für alle untersuchten Problemgrößen. Für die kleinen Testinstanzen, für welche die exakte Pareto-Menge bekannt ist, findet die Metaheuristik nahezu immer die exakten Lösungen und für größere Instanzen ist die Qualität der Ergebnisse konsistent. Der Algorithmus erzeugt stets repräsentative Fronten von Pareto-effizienten Lösungen - dadurch können diverse Terminpläne ohne einen Neustart des Verfahrens verglichen, und die unterschiedlichen Präferenzen von verschiedenen Entscheidungsträgern berücksichtigt werden.
Abstract
(Englisch)
People with complex schedules, such as self-employed people with multiple projects and clients, have to plan their time wisely to strike a balance between their professional activities and their private leisure time. An automated schedule optimizer with built-in routing functionality can provide support by offering good suggestions for when, where, and in what order to get tasks done. Carried out in cooperation with the Austrian Institute of Technology (AIT), this thesis introduces and solves the Personal Planning Problem (PPP), a combined scheduling and routing model that captures the real-life challenge faced by people with complex and flexible schedules.
The PPP extends the Orienteering Problem with Time Windows (OPTW). In contrast to the OPTW, the PPP formulation allows tasks to be done at one of several possible locations and during one of several possible time windows. In addition, precedence relations between tasks, as well as minimum and maximum time delays between related tasks, are taken into account. In order to capture the trade-off between scheduling more tasks and enjoying more leisure time, a bi-objective model is formulated.
A metaheuristic based on Large Neighborhood Search is proposed for solving the PPP. The solution space is explored by iteratively destroying different parts of a solution, and then reconstructing it in various ways. Several destroy and repair operators are used to diversify and intensify the search. Some common procedures from the literature are adapted to handle the specific constraints of the PPP.
The proposed metaheuristic is implemented and tested on a set of benchmark instances. Computational experiments show that the algorithm is effective, reliable, and scales well with increasing instance size. Near-optimal sets of schedules are consistently found for the instances for which optimal solutions are known, and the solution quality is consistent for larger instances as well. Since the algorithm generates a representative set of non-dominated solutions, the decision maker can compare different schedules without re-running the optimization, and the various preferences of different decision makers can be taken into account.
Schlagwörter
Schlagwörter
(Englisch)
combinatorial optimization metaheuristics large neighborhood search orienteering time windows logistics
Schlagwörter
(Deutsch)
kombinatorische Optimierung Metaheuristiken Large Neighborhood Search Orienteering Zeitfenster Logistik
Autor*innen
Piotr Matl
Haupttitel (Englisch)
A large neighborhood search metaheuristic for the personal planning problem
Paralleltitel (Deutsch)
Eine Large Neighborhood Search Metaheuristik für das Personal Planning Problem
Publikationsjahr
2014
Umfangsangabe
VII, 70 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikationen
31 Mathematik > 31.80 Angewandte Mathematik ,
85 Betriebswirtschaft > 85.03 Methoden und Techniken der Betriebswirtschaft
AC Nummer
AC12136722
Utheses ID
31016
Studienkennzahl
UA | 066 | 914 | |