This paper is devoted to the problem of optimal weather routing for transoceanic ship voyages. The goal of optimization is to reduce travel time and fuel consumptions. The optimal route is searched on the admissible set, which comprises routes satisfying all of the imposed static and dynamic constraints. The static constraints are represented mostly by coastal lines and shallow waters. The dynamic constraints are time-varying alarm zones restricted for ship motion due to dangerous weather conditions. The proposed route optimization algorithm uses long-term weather forecast for a sailing region and a mathematical model of ship motion. The key feature of algorithm is the three-dimensional representation of the route, which allows transforming initial finite-dimensional optimization problem to the problem of path finding on special graph.