DLVG-TDA*: A dual layer vectorized graph framework and time-dependent A* algorithm for ship route optimization

The complex marine environments are challenging for ship route planning, due to inaccurate obstacle modeling, time-varying wind and ocean current. This study proposes a Time-Dependent A* (TDA*) algorithm based on a Dual-Layer Vectorized Graph (DLVG) for ship route planning. The DLVG is constructed by integrating Automatic Identification System (AIS) data with Electronic Navigational Charts (ENCs) to form a safety constrained navigable graph. A cost function considering fuel consumption, voyage time, and distance is formulated by coupling the interpolated wind and current fields with the ship resistance models, thereby achieving environment constrained multi-objective optimization. Furthermore, the TDA* algorithm is designed with a time-slice caching mechanism, in order to enhance computational efficiency and enable effective global search in dynamic environments.Simulation results demonstrate that, compared with the DLVG-ACO, RRT* and A*, the proposed DLVG–TDA* could reduce computational burden, meanwhile, ensure route feasibility and improve economic effectiveness.