Optimizing the path towards plastic-free oceans

Département Information Systems et Operations Management

Intervenant: Jean Pauphilet (LBS)

Salle Bernard Ramanantsoa

Abstract

Over 8 million tons of plastic are poured in the seas every year, damaging entire ecosystems from the coastlines up to the open waters. Because of marine currents, a large fraction of this plastic then accumulates in specific areas of the oceans, such as the Great Pacific Garbage Patch (GPGP) in the Pacific ocean. We partner with a non-profit organization and use optimization to help them clean up oceans from plastic faster. Specifically, we optimize the route of their plastic collection system in the GPGP to maximize the quantity of plastic collected over time. We need to account for numerous operational constraints, complex plastic dynamics, as well as the direct impact of our collection on future plastic density. Eventually, we model the problem as a longest path problem in a well-structured graph, yet with non-convex and non-decomposable edge lengths. We propose a search-and-bound method, which leverages a relaxation of the problem solvable via dynamic programming, to efficiently find high-quality solutions with certificates of near optimality (around 5% in practice). On one-year ocean data, our optimization-based routing approach increases the quantity of plastic collected by over 50% compared with their current routing strategy. It also provides a tool to evaluate the impact of system characteristics on the overall efficiency and improve the design of future systems.