Mission planning for Autonomous Marine Vehicles (AMVs) is non-trivial because significant uncertainty is present when profiling the operating environment, especially for underwater missions. Mission complexity is compounded for each vehicle added to the mission. In practice, fleet operations are formulated as separate temporal problems by the operator and solved using a temporal planner. This paper proposes a planning method that uses energy as the base planning resource instead of time. Unlike temporal planners, energy planners account for physical loads endured by the vehicles. The extent of uncertainty in the vehicle loads is clarified by using the vehicle dynamics model and Monte Carlo simulation on the model parameters. The planning method is a multistage procedure to decompose operator specified task, obstacle, and vehicle data into an energy formulation of the Team Orienteering Problem (TOP) which is then solved using Discrete Strengthened PSO (DStPSO). The DStPSO algorithm has been modified to include a selective swarm size decay method that allows for larger initial swarm sizes to promote early exploration and preserves a percentage of the best performing particles on each iteration to save computational resources. The planner produces near-optimal routes containing feasible trajectories for individual vehicles that maximise tasks completed according to individual vehicle energy constraints. A case-study mission for long-term, large-scale, underwater inspection of a wind turbine array was converted into input data to evaluate the planner. Energy planning presents the opportunity for vehicles to actively monitor the feasibility of their individual plan against their current energy consumption, allowing for advanced reasoning and fault handling to occur in situ without operator assistance.