Abstract This paper first calibrates the bunker consumption – sailing speed relation for container ships using historical operating data from a global liner shipping company. It proceeds to investigate the optimal sailing speed of container ships on each leg of each ship route in a liner shipping network while considering transshipment and container routing. This problem is formulated as a mixed-integer nonlinear programming model. In view of the convexity, non-negativity, and univariate properties of the bunker consumption function, an efficient outer-approximation method is proposed to obtain an e-optimal solution with a predetermined optimality tolerance level e. The proposed model and algorithm is applied to a real case study for a global liner shipping company.