This paper proposes an agent-based metaheuristic to solve large-scale multi-period supply chain network design problems. The generic design model formulated covers the entire supply chain, from vendor selection, to production–distribution sites configuration, transportation options and marketing policy choices. The model is based on the mapping of a conceptual supply chain activity graph on potential network locations. To solve this complex design problem, we propose Collaborative Agent Team (CAT), an efficient hybrid metaheuristic based on the concept of asynchronous agent teams (A-Teams). Computational results are presented and discussed for large-scale supply chain networks, and the results obtained with CAT are compared to those obtained with the latest version of CPLEX.