Due to the intensification of economic globalization and the impact of global warming, the development of methods to reduce shipping costs and reduce carbon emissions has become crucial. In this study, a multi-objective optimization algorithm was designed to plan the optimal ship route for safe cross-ocean navigation under complex sea conditions. Based on the traditional non-dominated sorting genetic algorithm, considering ship stability and complex marine environment interference, a non-dominated sorting genetic algorithm model considering energy consumption was designed with the energy consumption and navigation time of the ship as the optimization objectives. The experimental results show that although the proposed method is 101.23 nautical miles more than the large ring route, and the voyage is increased by 10.1 h, the fuel consumption is reduced by 92.24 tons, saving 6.94%. Compared with the traditional genetic algorithm, the voyage distance and time are reduced by 216.93 nautical miles and 7.5 h, and the fuel consumption is reduced by 58.82 tons, which is almost 4.54%. Through experimental verification, the proposed model can obtain punctual routes, avoid areas with bad sea conditions, reduce fuel consumption, and is of great significance for improving the safety and economy of ship routes.