Cross-docking is one of the effective methods applied in supply chain management in order to minimize total transportation costs while satisfying the customer demands. This paper addresses the transportation problem of cross-docking network design where products are transferred from suppliers to customers through cross-docking centers without storing them for a long time. Two-dimensional truck loading constraints are taken into account for different sized products in order to find exact capacity of each truck. This assumption allows decision makers to find idle vehicle capacities and evaluate the capacity utilizations as a cost factor. The problem is formulated using mixed integer programming and solved using simulated annealing (SA) meta-heuristic algorithm which has great potential to solve NP-Hard problems. The proposed algorithm is performed for several randomly generated examples and compared with the optimum solutions. Results show that proposed algorithm demonstrates effective and efficient solutions to reduce the total transportation costs in cross-docking network design. (C) 2014 The Authors. Published by Elsevier Ltd. Selection and peer review under responsibility of Organizing Committee of BEM 2013.