Data collection in application domains like agriculture and environmental science requires the deployment of sensors in large remote areas. These use cases challenge the traditional optimal experimental design (OED) formulation from statistics by their scale as well as the presence of complex operational constraints, such as that data is collected along the trajectory of a drone. This paper proposes a tailored branch-and-bound algorithm to solve large-scale instances of OED as well as account for routing constraints. Efficient screening rules and first-order methods for solving the relaxations are key to the tractability of our algorithm, which significantly outperforms commercial solvers on both the classical OED and OED with routing constraints. For classical OED for example, it increases the size of instances solvable under a minute from n=200 to n=10,000. In the presence of routing constraints, it finds solutions with up to 10% higher objective value and solves twice as many instances to optimality.