Projects
Master's thesis · University of Vienna · 2025

Catching trash that drifts away.

How should a collection boat decide which drifting plastic to go after next?
ÖGOR Master Prize · grew into a Springer paper (OR 2025)

A night sea seen from above: current lines, warm glowing plastic hotspots and two collection boats with their lights on. Title: Catching trash that drifts away. Master's thesis by Paulina Heine, University of Vienna, 2025, awarded the ÖGOR Master Prize.

North Pacific
Out in the Pacific, the currents turn in a huge circle.
Schematic of the North Pacific Gyre, not measured data
Floating plastic gets caught in it.
It comes from land, carried out by rivers, and from the sea itself: lost fishing nets.
Meijer et al. 2021 · Lebreton et al. 2018 · both cited in the thesis
Great Pacific Garbage Patch
And it gathers in one area between Hawaii and California.
Location schematic · Lebreton et al. 2018
1.6 million km²
At least 79,000 tonnes of plastic. A collection boat would need about 19 days non-stop just to cross it once.
Lebreton et al. 2018 · 19 days at 1.5 knots collection speed: estimate in the thesis, p. 10 (speed from den Hertog et al. 2024)
Up close it is no island of trash: scattered pieces, and here and there a denser cluster.
The thesis models these clusters as hotspots.
Close-up schematic

A dotted map of the North Pacific at night. The currents turn clockwise in one large gyre. Plastic from the coasts of Asia and North America and fishing nets lost at sea drift into it and gather between Hawaii and California in the Great Pacific Garbage Patch: 1.6 million square kilometres, at least 79,000 tonnes of plastic; a collection boat would need about 19 days non-stop to cross it. Up close it is no island of trash but scattered pieces with denser clusters, the hotspots.

The mission
Two boats start in the middle.
Around them, 50 hotspots. Some are worth far more than others.
The value comes from the area, density and weight of the plastic, scaled from 1 to 10,000.
After 100 hours the mission ends.
Orienteering problem
There is no time for all of them. So you have to choose.
Which hotspots, and in which order, to end up with the most value?
Default scenario of the thesis: 50 hotspots within 10 km, 2 boats, 100 h (Table 4.1) · routes and count here are schematic

Schematic of the default scenario: two collection boats start in the middle of a circle with a radius of 10 kilometres. Around them lie 50 plastic hotspots with values from 1 to 10,000. A clock runs for 100 hours. In this sketch the boats collect a dozen hotspots, then the time is up and most are left behind. So you have to choose: the orienteering problem.

Moving targets
Except that nothing out here stays where it is.
The current carries every hotspot along.
Light, flat plastic drifts faster than heavy plastic.
In the thesis each hotspot drifts at 1 to 20 % of the current's speed, depending on its density, area and weight · current drawn as a schematic
A boat sets off towards where the hotspot is right now.
An hour later it has moved on.
So every hour, the boat sets a new course for it.
In the thesis's example the boat needs six hours even for a hotspot that starts close by (Fig. 3.5)
Time-dependent
The boat drifts too. Nobody knows in advance how long a trip will take.
The straight line is not the way the boat sails.
Online decisions
A plan fixed before the start would soon be out of date.
So the boats decide as they go.
Time-Dependent Orienteering Problem with Moving Targets (TDOP-MT)

Schematic: the current sets in and all 50 hotspots drift away, light ones faster than heavy ones. Then close up on one boat and one hotspot: the boat heads for where the hotspot is now; an hour later it has moved on and the boat turns; after six hours it reaches it, on a bent path instead of the straight line. Because the boat drifts too, nobody knows the travel time in advance. A plan fixed before the start would soon be out of date, so the boats decide as they go.

The rule
A free boat gives every hotspot a score.
It goes for the one with the highest score.
Two things count: how close it is, and how much it is worth.
Both go on a scale from 0 to 1: the farthest hotspot gets 0 for closeness, the most valuable gets 1 for value.
One number, α, sets the mix.
α weighs closeness, 1 − α weighs value. With α = 0.5, hotspot 4 wins with 0.58.
Worked example from the thesis, Table 3.2
α = 1: always the nearest one.
Short trips, but often little value.
α = 0: always the most valuable one, however far.
Long trips, and the target keeps drifting while you sail.
Both sound sensible. Which α is best?

Worked example from the thesis: one boat and four hotspots. Hotspot 1 is worth 8,000 and 10 kilometres away, hotspot 2 is worth 3,000 and 3 kilometres away, hotspot 3 is worth 10,000 and 14 kilometres away, hotspot 4 is worth 8,000 and 9 kilometres away. Closeness and value go on a scale from 0 to 1 and are mixed with α: α weighs closeness, 1 minus α weighs value. With α = 0.5 hotspot 4 wins with 0.58. With α = 1 the nearest wins, hotspot 2; with α = 0 the most valuable, hotspot 3. Which α is best?

Test 0 · default scenario
The thesis tried every α from 0 to 1.
In steps of 0.05, counting the value collected after 100 hours.
One simulation: a dip around 0.3, a peak around 0.6.
Thesis, Fig. 4.2 (values read off the figure)
Every simulation looks different.
Each has its own hotspots, so its own curve.
45 simulations from Table 8.2 of the thesis
On average both extremes lose. A mix at α ≈ 0.65 does best.
Mean of all simulations, Fig. 4.3 and Table 8.2

Chart from Test 0: the collected value over α from 0 to 1. A single simulation (Figure 4.2) reaches about 28,300 at α = 0, falls to about 19,000 between 0.1 and 0.4 and rises to about 45,000 at 0.6 and 0.65; from 0.9 to 1 it is at about 24,000. The 45 simulations of Table 8.2 spread widely. Their mean: 23,348 at α = 0, 30,086 at α = 0.65 and 16,261 at α = 1. Both extremes lose, a mix wins.

Changing your mind
Once a boat has a target, should it stick to it?
OG sticks to it. OGR looks again every hour.
Online Greedy, and Online Greedy with Retargeting.
OGR only switches when the new target is clearly better.
A threshold keeps it from switching back and forth all the time.
In the thesis: a second weight β for targets along the way, and a threshold r
So it picks up two small ones on the way.
After five time steps: OG 20, OGR 30.
The thesis's own example, Fig. 3.11 and Table 3.3: big hotspots are worth 20, small ones 5

Two panels side by side, the same water: OG on the left, OGR on the right. Both head for the big hotspot at the top left first. OG sticks to that target and collects it in step three: a value of 20. OGR checks again every hour, switches to a small hotspot that drifted close, collects it in step two (5), then a second small one in step three (5) and the big one in step four (20): 30 in total. A second weight β rates detours on the way, and a threshold r makes sure it only switches when the new target is clearly better.

Data
The currents in the thesis are real.
Hourly data from June 2024 around the garbage patch: where the water flows, and how fast.
Copernicus Marine Service, product GLOBAL_ANALYSISFORECAST_PHY_001_024 · simulated in Python with OpenDrift · drawn here as a schematic
10 scenarios
Ten test worlds, from “Short Time” to “Vast & Dense”.
More or less time, hotspots, space or boats.
Thesis, Table 4.1
In all ten, a mix beats both extremes.
On average it collects 37.8 % more than the better of the two extremes.
Test 1 with OG, 20 runs per scenario · best α picked afterwards in each run · Table 4.2

The current data of the thesis is real: hourly surface currents from the Copernicus Marine Service, June 2024, around the garbage patch, drawn here as a schematic. The tests ran in ten scenarios: Default (100 hours, 50 hotspots, 10 km, 2 boats), Short Time (50 hours), Long Time (500 hours), Few Hotspots (20), Many Hotspots (300), Narrow Radius (2 km), Wide Radius (30 km), Few Vessels (1 boat), Many Vessels (5 boats) and Vast and Dense (300 hotspots, 30 km, 1 boat). In all ten the best α (picked afterwards for each run) collects more than α = 0 and α = 1, on average 37.8 percent more than the better extreme; most in Vast and Dense with 104.7 percent, least in Long Time with 2.1 percent.

Exact baseline
An optimisation program plans the route in advance, as if the water stood still.
B1: the static orienteering problem, solved with Gurobi (600 s time limit) · routes here are schematic
Sailed in moving water, that plan loses a quarter of its value.
B2 against B1, mean over all scenarios, Table 4.3
The online rules beat that plan: OG in 8 of 10 scenarios, OGR in 9.
On average OG collects 15.6 % more, OGR 21.4 %.
Test 2, three runs per scenario · weights picked afterwards in each run by grid search · Table 4.3 and Fig. 4.14
And changing your mind paid off in every scenario.
OGR collected 5.1 % more than OG on average.
Table 4.3, column ΔOG

Results from Test 2. The optimisation program Gurobi plans the route in advance for still water (B1). Sailing that plan in moving water (B2) lowers the collected value by 25.1 percent on average, from 35,595 to 26,660. The online rules (weights picked afterwards for each run) do better than that plan: OG in 8 of 10 scenarios, by 15.6 percent on average, OGR in 9 of 10, by 21.4 percent on average. OGR collects more than OG in every scenario, 5.1 percent on average, most in scenario 8 with a single boat (11.8 percent).

ÖGOR Master Prize
The thesis won the ÖGOR Master Prize and grew into a paper.
“Reactive Planning for Marine Debris Collection in Dynamic Ocean Environments” · Springer Proceedings, OR 2025 International Conference · ÖGOR: Austrian Society of Operations Research
The topic does not end there.
In my PhD: ghost nets instead of hotspots, cost in euros per kilogram instead of collected value. The same ocean, moving targets again.

The master's thesis was awarded the ÖGOR Master Prize and grew into a paper: Reactive Planning for Marine Debris Collection in Dynamic Ocean Environments, Springer Proceedings of the OR 2025 International Conference. The topic continues in the PhD: a ghost net with a GPS buoy drifts into view; instead of hotspots, ghost nets are recovered, and instead of the collected value it is the cost in euros per kilogram.

Master's thesis · University of Vienna · 2025

A Heuristic Approach for the Time-Dependent Orienteering Problem with Moving Targets in a Maritime Environment

Paulina Heine · ÖGOR Master Prize

Grew into · paper, accepted
Reactive Planning for Marine Debris Collection in Dynamic Ocean Environments
Springer Proceedings · OR 2025 International Conference
Read the thesis ↗ PhD: ghost nets → Bachelor's thesis → CV ← All projects