Autonomous Underwater Vehicles (AUVs) have been widely used in scientific or industrial operations over the past years. AUV missions require the vehicle to perform a set of actions autonomously and return to the operators. These missions are currently mostly planned offline by the human operators. Existing solutions in commercial planning software usually only provide an estimate of the mission execution time. The uncertain and dynamic underwater environment can have an effect on the mission performance. More time and energy may be required, disallowing successful mission execution. This work proposes the usage of the correlated orienteering problem (COP) that maximises the utility of a sensing mission while respecting energy and time constraints. We propose a heuristic-based on genetic algorithms (GA) for the solution of the COP. This heuristic is compared against optimal mixed-integer quadratic programming (MIQP) solutions. Results show that the quality of the heuristic solution is in the worst tested case 5.5% less than the 1% optimal solutions. The heuristic proves to be at least 3 times more time efficient than the optimal MIQP solutions in the worst case. The heuristic is finally tested on an embedded platform showing its ability to be used on real robotic platforms.