Detailansicht
A heuristic approach for the time-dependent orienteering problem with moving targets in a maritime environment
Paulina Heine
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Business Analytics
Betreuer*in
Jan Fabian Ehmke
DOI
10.25365/thesis.79893
URN
urn:nbn:at:at-ubw:1-17225.22228.850680-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Masterarbeit untersucht das zeitabhängige Orienteering-Problem mit beweglichen Zielen (TDOP-MT) im maritimen Kontext der Plastiksammlung im offenen Ozean. Angesichts der wachsenden Umweltbelastung durch Meeresmüll entwickelt die Arbeit heuristische Algorithmen zur effizienten Routenplanung von Sammelbooten, die treibende Plastik-Hotspots unter dem Einfluss von Meeresströmungen einsammeln. Das Problem wird als Orienteering-Problem modelliert, bei dem Sammelschiffe innerhalb eines begrenzten Zeithorizonts eine Teilmenge von Hotspots auswählen und ansteuern müssen, um den Gesamtwert der gesammelten Verschmutzung zu maximieren. Die zentrale Herausforderung liegt in der Bewegung sowohl der Ziele als auch der Schiffe durch Ozeanströmungen, was zu einer zeitabhängigen Problemstruktur führt, bei der Reisezeiten nicht vorhersagbar sind. Der Kern der Arbeit liegt in der Entwicklung und systematischen Evaluation von Online-Routing-Heuristiken, um zu untersuchen, wie die Gewichtung zwischen Nähe und Wert bei der Zielauswahl die Performance beeinflusst. Zwei Algorithmen werden entwickelt: ein grundlegender Greedy-Algorithmus (OG) und eine erweiterte Variante mit Retargeting-Mechanismus (OGR). Die zentrale Forschungsfrage ist, ob eine ausgewogene Gewichtungsstrategie beiden Extremfällen (reine Wert- oder Distanzfokussierung) überlegen ist und ob sich verallgemeinerbare Muster identifizieren lassen. Die Algorithmen-Parameter werden durch Offline-Kalibrierung mittels Grid-Search optimiert, um die optimalen Parameterwerte und deren Einfluss auf das Sammelergebnis zu untersuchen. Die Online-Ausführung erfolgt in einer zeitschrittbasierten Simulation unter Verwendung realer Strömungsdaten des Copernicus Marine Service. Die Ergebnisse zeigen, dass ausgewogene Gewichtungsstrategien konsistent bessere Performance erzielen als Extremfälle und dass der Retargeting-Mechanismus die Anpassungsfähigkeit an dynamische Umgebungen signifikant verbessert. Die Arbeit liefert wichtige Erkenntnisse für die Gestaltung adaptiver Routenplanungssysteme in dynamischen maritimen Umgebungen und legt eine methodische Grundlage für zukünftige Forschung zur vollständig autonomen Parameteranpassung.
Abstract
(Englisch)
This master’s thesis examines the Time-Dependent Orienteering Problem with moving targets (TDOP-MT) in the maritime context of plastic collection in the open ocean. In view of the growing environmental impact of marine litter, the thesis develops heuristic algorithms for efficient route planning for collection boats that collect drifting plastic hotspots under the influence of ocean currents. The problem is modelled as an Orienteering Problem in which collection vessels must select and navigate to a subset of hotspots within a limited time horizon to maximize the total value of the pollution collected. The central challenge lies in the movement of both the targets and the ships through Ocean currents, resulting in a time-dependent problem structure where travel times are unpredictable. The core of the work lies in the development and systematic evaluation of online routing heuristics to investigate how the weighting between proximity and value in target selection influences performance. Two algorithms are developed: a basic greedy algorithm (OG) and an Extended variant with a retargeting mechanism (OGR). The central research question is whether a balanced weighting strategy is superior to both extreme cases (pure value or distance focus) and whether generalizable patterns can be identified. The algorithm parameters are optimized through offline calibration using grid search to investigate the optimal parameter values and their influence on the collection result. Online execution takes place in a time step based simulation using real current data from the Copernicus Marine Service. The results show that balanced weighting strategies consistently achieve better Performance than extreme cases and that the retargeting mechanism significantly improves adaptability to dynamic environments. The work provides important insights for the design of adaptive route planning systems in dynamic maritime environments and lays a methodological foundation for future research on fully autonomous parameter adaptation.
Schlagwörter
Schlagwörter
(Deutsch)
Orienteering-Problem Zeitabhängige Optimierung Online-Heuristik Greedy- Algorithmus Müllsammlung Plastikverschmutzung Operations Research
Autor*innen
Paulina Heine
Haupttitel (Englisch)
A heuristic approach for the time-dependent orienteering problem with moving targets in a maritime environment
Publikationsjahr
2025
Umfangsangabe
100 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Jan Fabian Ehmke
Klassifikation
85 Betriebswirtschaft > 85.00 Betriebswirtschaft. Allgemeines
AC Nummer
AC17733915
Utheses ID
78543
Studienkennzahl
UA | 066 | 977 | |