Optimizing the Path Towards Plastic-Free Oceans

• 成果类型: Article
• 署名作者: den Hertog, Dick; Pauphilet, Jean; Pham, Yannick; Sainte-Rose, Bruno; Song, Baizhi
• 署名单位: University of Amsterdam; University of London; London Business School
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0515
• 发表日期: 2025
• 关键词: traveling salesman problem; longest path; shortest-route; ship; algorithm; optimization; pollution; debris

摘要

Increasing ocean plastic pollution is irreversibly harming ecosystems and human economic activities. We partner with a nonprofit organization and use optimization to help clean up oceans from plastic faster. Specifically, we optimize the route of their plastic collection system in the ocean to maximize the quantity of plastic collected over time. We formulate the problem as a longest path problem in a well-structured graph. However, because collection directly impacts future plastic density, the corresponding edge lengths are nonlinear polynomials. After analyzing the structural properties of the edge lengths, we propose a search-and-bound method, which leverages a relaxation of the problem solvable via dynamic programming and clustering, to efficiently find high-quality solutions (within 6% optimal in practice) and develop a tailored branch-and-bound strategy to solve it to provable optimality. On one year of ocean data, our optimization-based routing approach increases the quantity of plastic collected by more than 60% compared with the current routing strategy, hence speeding up the progress toward plastic-free oceans.