Recently, crossdocking techniques have been successfully applied in responsive supply chain management. However, most researches focused on physical layout of a crossdock, or scheduling operations within a crossdock. In this paper, we study a multi-crossdock transshipment service problem with both soft and hard time windows. The flows from suppliers to customers via the crossdocks are constrained by fixed transportation schedules. Cargos can be delayed and consolidated in crossdocks, and both suppliers and customers have specific hard time windows. In addition to hard time windows, customers also have less-restrictive time windows, called soft time windows. The problem to minimize the total cost of the multi-crossdock distribution network, including transportation cost, inventory handling cost and penalty cost, can be proved to be NP-hard in the strong sense and hence efficient heuristics are desired. We propose two types of meta-heuristic algorithms, called Adaptive Tabu Search and Adaptive Genetic Algorithm, respectively, to solve the problem efficiently. We conduct extensive experiments and the results show that both of them outperform CPLEX solver and provide fairly good solutions within realistic timescales. We also perform sensitivity analysis and obtain a number of managerial insights.