“A Heuristic Approach for the Time-Dependent Orienteering Problem with Moving Targets in a Maritime Environment”. My master's thesis sends collection boats into the Great Pacific Garbage Patch: drifting plastic hotspots, real current data and online heuristics deciding at every time step.
Two collection boats start at the centre of the map, plastic hotspots drift around, and the clock is ticking: after 100 hours the mission ends. Unlike the TSP, you don't have to visit everything. It's an orienteering problem: pick the subset that maximizes the collected value (bigger = more valuable). The catch: hotspots and boats both drift with the current. Travel times are never certain, and the plan from a minute ago is already stale.
The thesis title spells the difficulty out: Time-Dependent Orienteering Problem with Moving Targets. Orienteering means there are more targets than the clock allows — the route is always also a selection. Time-dependent means what a leg costs depends on when you sail it, because the current pushes with you or against you. And moving targets means a hotspot is not a coordinate but a function of time — you don't sail to where it is, you sail to where it will be. Each of the three properties alone makes the problem hard. Together they ensure that a plan computed in advance is already stale while the boat is still sailing it. Which is exactly why the heuristic decides online: at every time step, with the knowledge of now.
Every free boat scores all hotspots with a single formula: α weighs proximity, 1−α weighs value. α = 1 only chases the nearest, α = 0 only the most valuable. Why both extremes lose: α = 1 fills the 100 hours with cheap nearby pickups, α = 0 chases valuable hotspots that keep drifting during the long approach. The mixture pays distance only where the value justifies it. Test 0 of the thesis shows a non-linear curve: a dip around α ≈ 0.3–0.4 and a peak at α ≈ 0.6. Balanced beats extreme. Set your α and race both extremes. All three boats fish in the same waters.
The online greedy (OG) has a weakness: once assigned, it stubbornly sticks to its target, even if it drifts away or something better pops up next door. The OGR therefore checks at every time step with a second rule (factor β) whether switching pays off, but only if the new score beats the old one by the threshold r, so the boat doesn't jitter back and forth. Same scene, same currents, same α (value-leaning here, as in the thesis's own example). Watch who collects more. Every ↻ is a target switch.
The simulation didn't use toy waves but hourly surface currents from the Copernicus Marine Service (June 2024) around the Great Pacific Garbage Patch, implemented in Python with OpenDrift. Tested across 10 scenarios, from “Short Time” to “Vast & Dense”, and compared against exact Gurobi baselines — on instances small enough for the exact solver, the comparison shows how far the online heuristic sits from the optimum. The findings: balanced weighting beats both extremes, and retargeting significantly improves adaptability.
The topic doesn't end here. In the PhD, value collection becomes recovery: ghost nets instead of hotspots, euros per kilogram instead of a score — the same ocean, the same moving targets, a harder objective.