According to the operation feature of tramp shipping which involves numerous cargos, ships, ports and lanes, a tramp ship scheduling and speed optimization model was proposed to deal with the ship scheduling problem with variable speed, after analysis of the effect of ship speed on fuel cost and time table. In light of the structure of the model, the two phase algorithm based on set partition model was designed. The availability and reasonability of the model and algorithm was tested and proved by some cases. The results show that the operating income increases by 10%~25%, when speed is taken as a decision variable. The model established could comprehensively optimize ship scheduling, cargo selection, contractual cargo transportation organization, and ship speed, which can provide decision-making support for tramp schedule practice.