Retailers which deliver products directly to their customer locations often rely on Logistics Service Intermediaries (LSI) for order management, warehousing, transportation and distribution services. Usually, the LSI acts as a shipper and subcontracts the transportation to carriers for longhaul and last-mile delivery services. All agents interact and are connected through cross-docking facilities. As the demand from customers may vary significantly over time, the shipper's requirements for transportation evolve accordingly at the tactical level. This creates opportunities for the LSI to take advantage of medium-term contracts with the carriers at prices lower than those offered by the spot market. In this article, we propose a MILP formulation for the multi-period planning problem with minimum purchase commitment contracts faced by the LSI. The study focuses on designing dynamically, at a tactical level, a suitable network of cross-docking facilities and related transportation capacities (belonging to different carriers) to reduce the LSI operational costs in the long term. We propose several exact and heuristic decomposition methods for the the model, respectively, based on combinatorial Benders cuts and on relax-and-repair approaches. The performance of these algorithms is experimentally compared to that of commercial solvers (brand-and-cut and classical Benders). The numerical results show that our methods bring benefits for the solution of large size instances.