We introduce a decision support tool for liner shipping companies to optimally determine
the sailing speed and needed fleet for a global network. As a novelty we incorporate cargo
routing decisions with tight transit time restrictions on each container such that we get a
realistic picture of the utilization of the network. Furthermore, we show that it is possible to
extend the model to include optimal time scheduling decisions such that the time associated
with transshipments is also reflected accurately. To solve the speed optimization problem
we propose an exact algorithm based on Benders decomposition and column generation that
exploits the separability of the problem. Computational results show that the method is
applicable to liner shipping networks of realistic size and that it is important to incorporate
cargo routing decisions when optimizing speed.