With the advancement of intelligent vehicles and unmanned systems, there is a growing interest in underwater surveys using autonomous marine vehicles (AMVs). This study presents an automated planning strategy for a long-term survey mission using a fleet of AMVs consisting of autonomous surface vehicles and autonomous underwater vehicles. Due to the complex nature of the mission, the actions of the vehicle must be of high-level abstraction, which means that the actions indicate not only motion of the vehicle but also symbols and semantics, such as those corresponding to deploy, charge, and survey. For automated planning, the planning domain definition language (PDDL) was employed to construct a mission planner for realizing a powerful and flexible planning system. Despite being able to handle abstract actions, such high-level planners have difficulty in efficiently optimizing numerical objectives such as obtaining the shortest route given multiple destinations. To alleviate this issue, a widely known technique in operations research was additionally employed, which limited the solution space so that the high-level planner could devise efficient plans. For a comprehensive evaluation of the proposed method, various PDDL-based planners with different parameter settings were implemented, and their performances were compared through simulation. The simulation result shows that the proposed method outperformed the baseline solutions by yielding plans that completed the missions more quickly, thereby demonstrating the efficacy of the proposed methodology.