Mine Countermeasures (MCM) present a challenging motion-planning problem when taking into account ocean currents, complex bathymetry, and vehicle dynamics. In an effort to improve autonomous underwater vehicle (AUV) motion planning for MCM, this work presents a Physical Traveling Salesmen Problem (PTSP) approach as a way to quickly and robustly generate motions for the reacquisition and identification portion of a MCM mission while considering the temporally and spatially complex marine environment as well as the nonlinear dynamics of the AUV. By leveraging TSP solvers as well as sampling-based motion planning, this work shows that it is possible to efficiently compute low-cost, dynamically-feasible, and collision-free trajectories.