The rapid increase in global solid waste generation has intensified marine pollution, as waste flows from land to oceans through rivers and canals. Studies estimate that millions of metric tons of plastic enter the ocean annually, dispersing widely due to ocean currents, tides, and winds. This accumulation on coastlines and the ocean surface poses significant environmental, economic, and health risks. Global initiatives have been introduced to improve waste management and reduce marine litter, but waste collection remains a logistical challenge, particularly in developing countries with limited resources. Optimization models, particularly the Capacitated Vehicle Routing Problem (CVRP), have been widely applied to enhance collection efficiency. Recent research extends these models to marine debris collection, integrating environmental data and predictive models to optimize vessel routing while minimizing costs and emissions. This study advances prior works by proposing a Competition-Based Large Neighborhood Search (CLNS) algorithm for large-scale Marine Debris Collection Problems (MDCP) and a modified version of a state-of-the-art hybrid algorithm from the literature. The effectiveness of our method is validated through comparative evaluations on multiple test cases.