Handout · OR 2026 · Passau · 2 September 2026
Cost-Efficient Recovery of Drifting Ghost Nets
An orienteering problem with moving targets
Paulina Heine · Kevin Tierney · Daniel Wetzel · University of Vienna
01 · Why
Rotating currents form five gyres, and the gyres accumulate the plastic. The Great Pacific Garbage Patch: 1.6 M km², at least 79,000 t of plastic — 46 % of it ghost nets.
“So take them out” — easy to say. It hides two questions: which nets, and on which route? And before that: where will the nets be?
Lebreton et al. 2018, Sci. Rep. 8:4666
02 · The targets move
Each net carries a GPS tracker buoy, about one ping per hour. One real track over the measured surface current: 7 km after 12 h, 25 km after 30 h, 43 km after 49 h, 78 km after 72 h — riding the current.
And the sea sets the price: 58 L/h with current and wind, 197 L/h against them — 3.4× the fuel.
03 · The model
A time-expanded graph in hourly slots: each net is a line of positions through time, an arc reaches a later slot of another net and is priced in fuel euros. The complete graph is what the MIP solves.
min Cfuel(x)Wcollected(x) [EUR/kg]
What gets optimised is not distance but the price per kilogram recovered. The decisions: which boat collects which net, which arcs it sails, which pickup nodes it visits. Constraints: at most one vessel per net · hold capacity · recover at least Wmin · one arc in, at most one out · one time slot per pickup · start once, stand by at the end.
04 · Solution methods, in two dimensions
Every method sits in a matrix: knowledge about the future — forecast only, like a real operator, or perfect information, an oracle — against accuracy. Beyond “now”, positions and arc costs are forecasts from a simple leeway model.
- Oracles (they see the realised drift): Gurobi over the full horizon — the proven optimum in hindsight; rolling horizon; greedy with zero, one or two steps of lookahead.
- Realistic (forecast only, every hour: new ping → forecast the drift → decide → execute one hour): reactive greedy, lookahead-1 and -2 — and the genetic algorithm, which evolves whole plans and commits the best. A plan is a sequence of nets, waypoints and speeds, aimed at where each net will be.
- GA restricted: the same genetic search, held to the exact model’s own rules — for a like-for-like comparison.
Only the genetic algorithm, in either variant, is both realistic and accurate.
05 · Results
48 instances × 5 fleet sizes = 240 missions — 5 to 201 nets, 24 h to 240 h — on real GPS drift tracks, replanned hourly. The exact solver proved an optimum for 101 of them.
as a table
| Method | Knowledge | above optimum | solved |
|---|---|---|---|
| Genetic algorithm | forecast | +0.3 % | 240 / 240 |
| GA restricted | forecast | +4.7 % | 240 / 240 |
| Lookahead-2 | forecast | +7.4 % | 240 / 240 |
| Lookahead-1 | forecast | +7.9 % | 240 / 240 |
| Reactive greedy | forecast | +12.5 % | 240 / 240 |
| Rolling horizon | oracle | +28.6 % | 128 / 240 |
| Lookahead-2 | oracle | +44.0 % | 229 / 240 |
| Lookahead-1 | oracle | +45.0 % | 233 / 240 |
| Greedy (myopic) | oracle | +54.4 % | 240 / 240 |
Without a proven optimum, against the best oracle of the same mission (leave-one-out): GA −5.2 %, GA restricted −2.3 % — the oracles on the chart stay above the line (lookahead-1 +3.4 %, lookahead-2 +7.2 %, myopic greedy +21.5 %), and the reactive greedy sits +22.4 % above.
The value of search grows with the horizon: against the reactive greedy, same forecast and same clock, −4.8 % at 24 h to −23.2 % at 240 h; −17.8 % against lookahead-1, −15.8 % against lookahead-2.
The cost of coverage (ε-constraint sweep on 40 missions, one point per run, against the cheapest run of its own mission): a few extra points of coverage cost +7.0 % per kilogram, about +10 points +12.7 %, about +20 points +19.8 %. And 101 of 211 coverage mandates could not be met at all.
06 · Conclusion
What separates the methods is search, not information.
Every oracle that sees the drift that really happened stays 28 points behind.