This paper proposes efficient heuristics to solve large-scale production–distribution network design models. The problem studied is an extension of the twoechelon multicommodity CFLPSS (capacitated facility location problem with single sourcing) considering direct shipments frommanufacturing facilities, alternative facility configurations, and concave inventory holding costs. After reviewing the relevant literature, a detailed description of the production–distribution network design problem studied is provided, and the problem is formulated as a mixed-integer program. The heuristic solution approach proposed is then presented. It is a variable neighborhood search (VNS) method integrating a tabu procedure. Experiments are designed to calibrate the heuristics developed, and to compare their performance with the CPLEX solver, for problems with different realistic characteristics. Computational results are presented and discussed.