Vessel routing optimization for floating macro-marine debris collection in the ocean considering dynamic velocity and direction

Floating macro-marine debris becomes a global environmental problem when emitted into the ocean. It damages the marine ecosystem, threatens human health, and also causes incalculable economic losses.Due to the impacts of ocean currents and winds, marine debris has been transported to different locations over time and time window cannot be ignored to navigate the locations of marine debris. To effectively mitigate the risk, we propose the vessel routing optimization with a time window to collect and remove marine debris. Ocean currents and winds also affect the velocity and direction of the collecting vessel. We first employ GNOME software to determine the debris trajectory and set a time window for each debris location. A mixed-integer nonlinear programming model considering vessel velocity is proposed to minimize the total debris collection cost. We propose two customized solution approaches: Branch-and-Cut (B&C) algorithm and two-stage Adaptive Large Neighborhood Search (ALNS) based heuristic algorithm to solve the proposed mathematical model in a reasonable timeframe. A computational study in waters off Boston is used to validate the proposed model and the solution algorithms. The result indicates that the average optimality gap for GUROBI and B&C algorithm is 17.53% and 10.52%, respectively, while this gap is only 3.44% for the ALNS algorithm. Moreover, the average computing time of the ALNS algorithm is roughly 24 and 17 times faster than that of the GUROBI and the B&C algorithm, respectively. The experimental results show that distance from debris location to the harbor is positively related to the collection cost and negatively related to the average usage of vessels’ capacity, and the dispersion of debris is also positively related to the fuel consumption of vessels.