Intelligent environmental monitoring is an exciting and impactful use case of autonomous vehicles. In this work, we explore measuring water quality parameters via a battery-powered Autonomous Surface Vehicle to obtain an accurate spatial model of the quality of a water resource while minimizing the distance traveled (alternatively, time, or battery consumption). We develop an objective function for this class of problems and propose an evolutionary multi-objective optimization algorithm that selects the measurement locations while using a quick novel construction heuristic for determining the path. Our method leverages new crossover and mutation operators that seem to be of independent interest. We demonstrate the efficacy of the proposed approach in obtaining results for two different waterbodies: Lake Ypacarai in Paraguay, and Mar Menor in Spain.