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 such as cargo transit time limits. The classic liner shipping network design problem is already a hard problem, and 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 114 ports and, if applied to the classic liner shipping network design problem, finds new best solutions to all instances, 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 their implications.