When planning shipping routes, it is common to use a sequential approach where it is first assumed that each ship sails with a given service speed, and then later during the execution of the routes optimize the sailing speeds along the routes. In this paper we propose a new modeling approach for integrating speed optimization in the planning of shipping routes, as well as a rolling horizon heuristic for solving the combined problem. As a case study we consider a real deployment and routing problem in RoRo-shipping. Computational results show that the rolling horizon heuristic yields good solutions to the integrated problem within reasonable time. It is also shown that significantly better solutions are obtained when speed optimization is integrated with the planning of shipping routes.