Compact route–time graph construction within 3D dynamic programming for ETA-constrained ship weather routing

Ship weather routing under a target estimated time of arrival (ETA) is commonly solved with three-dimensional dynamic programming (3DDP), but uniformly expanding route and arrival-time states rapidly increases computation. This study presents a two-pass procedure that builds a compact second graph within established 3DDP. A moderate-resolution first pass retains feasible terminal routes, whose fuel-oil-consumption (FOC) gaps define a stage-wise guide for the second graph. Both passes use the same recursion and feasibility rules, and the selected first-pass route is retained. Across eight long-voyage cases, the proposal returned 3.816 t lower mean evaluated FOC than expanded fourfold 3DDP while using approximately 58% fewer FOC evaluations and 57% less computation time. Lower FOC occurred in all eight primary cases and 38 of 40 departure-date cases. An eightfold comparison narrowed the mean FOC gap to 2.927 t. Controls with identical allocated state counts gave paired mean differences below 0.05% of mean voyage FOC, with no systematic advantage for either component rule; tests using successive forecast cycles changed one of four route rankings. These results position the method as a compact and competitive construction under the tested deterministic conditions.