The paper is devoted to the problem of motion optimization of a ship on a given long trajectory with respect to weather forecast and additional constraints. This problem has practical meaning for long distances, where saving of fuel consumption and reducing travel time is of significant importance. A finite-dimensional formulation of the optimization problem is considered taking into account the mathematical model of ship motion, weather forecast, constraints and given cost functionals. The computational algorithms for calculation of travel time and fuel consumption are proposed. The main result is presented by the algorithm for optimizing the velocity distribution on a given trajectory. This algorithm is based on the representation of the route of motion on a fixed trajectory in two-dimensional space. The obtained results are demonstrated by illustrative examples.