Aiming at the internalization of negative externalities caused by ship operation in the actual iron ore shipping process, the negative externalities such as environmental impacts, port congestion and traffic accidents caused by ship transportation at sea were considered comprehensively and evaluated quantitatively. By analyzing the sea transportation activities of iron ore, combining the negative externality problem with ship routing, and aiming at minimizing the negative externality cost and maximizing the operating profit, a dual-objective optimization model of iron ore ship routing was established, which was solved and verified by the improved genetic algorithm. Taking the three iron ore routes from Brazil to China via the Cape of Good Hope as an example, the model was solved and verified, and the sensitivity analysis of ship type and fuel price was carried out. The results show that the negative externality cost is not negligible in the operating income of shipping enterprises, and the reasonable ship type capacity ratio will significantly reduce the negative externality cost in the transportation process. With the increase of fuel price, it will lead to a significant increase of negative externality cost. Optimization suggestions can be put forward for shipping-related enterprises, and provide reference for the government's macro-control of capacity and shipping enterprises to formulate transportation plans.