Problem definition: To collect data on ocean plastic pollution and build more accurate predictive models, we need to manually take high-resolution pictures of the sea surface via floating or flying drones. Operating these vehicles, like many data collection problems in agriculture or environmental science, challenges the traditional optimal experimental design (OED) formulation from statistics by its scale as well as the presence of complex routing constraints. Methodology/results: We develop a discrete optimization algorithm to solve large-scale instances of OED as well as account for routing constraints. On synthetic and real-world data, our algorithm outperforms existing solutions relying on commercial branch-and-bound solvers. For our problem of ocean plastic density prediction, for example, it finds solutions with up to 10% higher objective value and solves twice as many instances to optimality. In other words, it can build ensemble models with the same accuracy as a random data collection strategy, yet with a 30-50% lower cost. Managerial implications: Our study provides an efficient algorithm for solving large-scale instances of OED problems with routing constraints. It highlights the benefit of integrating operational constraints like routing into the design of data collection strategies to reduce data collection cost.