This paper presents an on-line dynamic path re-planning system for an autonomous underwater vehicle (AUV) to enable it to operate efficiently in a spatiotemporal, cluttered, and uncertain environment. The proposed strategy combines path re-planning with an evolutionary algorithm to adapt and regenerate the trajectory during the course of the mission using continuously updated current profiles from on-board sensors, such as a Horizontal Acoustic Doppler Velocity Logger. A quantum-behaved particle swarm optimization (QPSO) algorithm is used with a cost function which is based on the total time required to travel along the path segments accounting for the effect of space-time variable currents. The proposed path planner is designed to generate an optimal trajectory for an AUV navigating through a spatiotemporal ocean environment in the presence of irregularly shaped terrains as well as obstacles whose position coordinates are uncertain. Simulation results show that using the same on-board computation resources, the proposed path re-planning methodology with reuse of information gained from the previous planning history is able to obtain a more optimized trajectory than one relying on reactive path planning. Subsets of representative Monte Carlo simulations were run to analyse the performance of these dynamic planning systems. The results demonstrate the inherent robustness and superiority of the proposed planner based on path re-planning scheme when compared with the reactive path planning scheme.