In global liner shipping networks a large share of transported cargo is transshipped at least once between container vessels, and the total transportation time of these containers depends on how well the corresponding services are synchronized. We propose a problem formulation that integrates service scheduling into the liner shipping network design problem. Furthermore, the model incorporates many industry-relevant modeling aspects; it allows for leg-based sailing speed optimization, it is not limited to simple or butterfly-type services and it accounts for service level requirements like cargo transit time limits. The classic liner shipping network design problem is already a hard problem and in order to solve the extended version we propose a column generation matheuristic that uses advanced linear programming techniques. The proposed method solves LINER-LIB instances of up to 45 ports and finds new best solutions to all of them, outperforming existing methods reported in the literature. Additionally, we analyze the relevance of scheduling for liner shipping network design. The results indicate that neglecting scheduling and approximating transshipments instead may result in the design of liner shipping networks that underestimate cargo transit times and its~implications.